Profile
2026년 1월 3일

[가상 면접 사례로 배우는 대규모 시스템 설계 기초] 8. URL 단축기 설계

1. 문제 이해 및 설계 범위 확정1.1. 시스템 요구사항1.2. 개략적 추정2. 개략적 설계안 제시 및 동의 구하기2.1. API 엔드포인트2.2. URL 리디렉션2.3. URL 단축3. 상세 설계3.1. 데이터 모델3.2. 해시 함수3.3. URL 단축기 상세 설계3.4. URL 리디렉션 상세 설계
 

1. 문제 이해 및 설계 범위 확정

1.1. 시스템 요구사항

  1. URL 단축: 주어진 긴 URL을 훨씬 짧게 줄인다.
      • 단, 단축 URL에는 숫자(0부터 9까지)와 영문자(a부터 z, A부터 Z까지)만 사용 가능하다.
  1. URL 리디렉션(redirection): 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내
  1. 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨
 

1.2. 개략적 추정

  • 쓰기 연산: 매일 1억 개의 단축 URL 생성
  • 초당 쓰기 연산: 1억 / 24 / 3600 = 1160
  • 읽기 연산:
    • 읽기 연산과 쓰기 연산 비율은 10:1 이라고 가정
    • 읽기 연산은 초당 11,600회 발생 (1,160 * 10 = 11,600)
  • 저장 공간:
    • 서비스를 10년간 운영할 경우 1억 * 365 * 10 = 3650억 개의 레코드 필요
    • 축약 전 URL의 평균 길이는 100이라고 가정
    • 따라서 10년 동안 필요한 저장 용량은 3,650억 * 100바이트 = 36.5TB
 

2. 개략적 설계안 제시 및 동의 구하기

  • API 엔드포인트(endpoint), URL 리디렉션, 그리고 URL 단축 방법에 관한 개략적인 설계안 제시
 

2.1. API 엔드포인트

  1. URL 단축용 엔드포인트:
      2. 목적: 새 단축 URL을 생성
      POST /api/v1/data/shorten
      • 인자: {longUrl: longURLstring}
      • 반환: 단축 URL
  1. URL 리디렉션용 엔드포인트:
      2. 목적: 단축 URL에 대해서 HTTP 요청이 오면 원래 URL로 보내주기 위함
      GET /api/v1/shortUrl
      • 반환: HTTP 리디렉션 목적지가 될 원래 URL
 

2.2. URL 리디렉션

  • 단축 URL을 받은 서버는 그 URL을 원래 URL로 바꾸어서 301 응답 혹은 302 응답 Location 헤더에 넣어 반환한다.
  • URL 리디렉션을 구현하는 가장 직관적인 방법은 해시 테이블을 사용하는 것이다.
    • <단축 URL, 원래 URL> 쌍 저장
 
  • 301 Permanently Moved:
    • 이 응답은 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답이다.
    • 영구적으로 이전되었으므로, 브라우저는 이 응답을 캐시(cache)한다.
    • 따라서 추후 같은 단축 URL에 요청을 보낼 필요가 있을 때 브라우저는 캐시된 원래 URL로 요청을 보내게 된다.
    • 장점: 캐시를 사용하기 때문에 서버 부하를 줄일 수 있다.
    • 단점: 트래픽 분석에 상대적으로 약하다.
  • 302 Found:
    • 이 응답은 주어진 URL로의 요청이 ‘일시적으로’ Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답이다.
    • 따라서 클라이언트의 요청은 언제나 단축 URL 서버에 먼저 보내진 후에 원래 URL로 리디렉션 되어야 한다.
    • 장점: 트래픽 분석이 가능하다.
    • 단점: 서버 부하가 늘어난다.
 

2.3. URL 단축

  • URL 단축기 서비스에서 중요한 것은 긴 URL을 이 해시 값으로 대응시킬 해시 함수 fx를 찾는 일이다.
  • 이 해시 함수는 다음 요구사항을 만족해야 한다.
      1. 입력으로 주어지는 긴 URL이 다른 값이면 해시 값도 달라야 한다.
      1. 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야 한다.
 

3. 상세 설계

  • 데이터 모델, 해시 함수, URL 단축 및 리디렉션에 대한 구체적인 설계안 제시
 

3.1. 데이터 모델

  • 앞서 개략적 설계를 진행할 때는 모든 것을 해시 테이블에 두었었다.
  • 이 접근법은 초기 전략으로는 괜찮지만 실제 시스템에 쓰기에는 곤란하다.
    • 왜냐하면 메모리는 유한한 데다 비싸기 때문이다.
  • 더 나은 방법은 <단축 URL, 원래 URL>의 순서쌍을 관계형 데이터베이스에 저장하는 것이다.
    • id, shortURL, longURL 세 개 컬럼으로 저장
 

3.2. 해시 함수

  • 해시 함수(hash function)는 원래 URL을 단축 URL로 변환하는 데 쓰인다.
  • 편의상 해시 함수가 계산하는 단축 URL 값을 hashValue라고 지칭한다.
 
  • 해시 값 길이
    • hashValue는 [0-9, a-z, A-Z]의 문자들로 구성된다.
    • 따라서 사용할 수 있는 문자의 개수는 10 + 26 + 26 = 62개다.
    • hashValue의 길이를 정하기 위해서는 인 의 최솟값을 찾아야 한다.
      • = 약 560억
      • = 약 3.5조
    • n = 7 이면 3.5조 개의 URL을 만들 수 있으므로 hashValue의 길이는 7로 설정한다.
 
  • 해시 함수 구현에 쓰일 기술로는 두 가지 방법을 살펴본다.
  • 하나는 ‘해시 후 충돌 해소’ 방법이고, 다른 하나는 ‘base-62 변환’ 법이다.
 
3.2.1. 해시 후 충돌 해소
  • 긴 URL로 줄이려면, 원래 URL을 7글자 문자열로 줄이는 해시 함수가 필요하다.
  • 가장 간단한 방법은 CRC32, MD5, SHA-1과 같이 잘 알려진 해시 함수를 이용하는 것이다.
  • 아래는 이들 함수를 사용하여 https://dongho-blog.kro.kr 을 축약한 결과다.
      • 해시 함수
      해시 결과 (16진수)
      CRC32
      19a421f1
      MD5
      5ca569a000b5518c1fd83cfbcff672ef
      SHA-1
      3993aa14b79b449a950fbeea855c1b44f288ab5d
  • 문제는 CRC32가 계산한 가장 짧은 해시값조차도 7보다는 길다. 어떻게 하면 줄일 수 있을까?
  • 이 문제를 해결할 첫 번째 방법은 계산된 해시 값에서 처음 7개 글자만 이용하는 것이다.
  • 하지만 이렇게 하면 해시 결과가 서로 충돌할 확률이 높아진다.
  • 충돌이 실제로 발생했을 때는, 충돌이 해소될 떄까지 사전에 정한 문자열을 해시값에 덧붙인다.
 
notion image
  • 이 절차는 위 그림과 같다.
  • 이 방법을 쓰면 충돌은 해소할 수 있지만 단축 URL을 생성할 때 한 번 이상 데이터베이스 질의를 해야 하므로 오버헤드가 크다.
  • 데이터베이스 대신 블룸 필터를 사용하면 성능을 높일 수 있다.
 
블룸 필터는 어떤 집합에 특정 원소가 있는지 검사할 수 있도록 하는, 확률론에 기초한 공간 효율이 좋은 기술이다.
 
3.2.2. base-62 변환
  • 진법 변환(base conversion)은 URL 단축기를 구현할 때 흔히 사용되는 접근법 중 하나다.
  • 62진법을 쓰는 이유는 hashValue에 사용할 수 있는 문자(character) 개수가 62개이기 때문이다.
  • 그럼 이제 10진수 11157을 62진수로 변환해보자.
    • 62진법은 수를 표현하기 위해 총 62개의 문자를 사용하는 진법이다.
    • 따라서 0은 0으로, 9는 9로, 10은 a로, 11은 b로, …, 35는 z로, 36은 A로, …, 61은 Z로 대응시켜 표현하도록 할 것이다.
  • 따라서 단축 URL은 https://tinyurl.com/2TX 가 된다.
 
3.2.3. 두 접근법 비교
해시 후 충돌 해소 전략
base-62 변환
단축 URL의 길이가 고정됨
단축 URL의 길이가 가변적. ID 값이 커지면 같이 길어짐
유일성이 보장되는 ID 생성기가 필요치 않음
유일성 보장 ID 생성기가 필요
충돌이 가능해서 해소 전략이 필요
ID의 유일성이 보장된 후에야 적용 가능한 전략이라 충돌은 아예 불가능
ID로부터 단축 URL을 계산하는 방식이 아니라 다음에 쓸 수 있는 URL을 알아내는 것이 불가능
ID가 1씩 증가하는 값이라고 가정하면 다음에 쓸 수 있는 단축 URL이 무엇인지 쉽게 알아낼 수 있어서 보안상 문제가 될 소지가 있음
 

3.3. URL 단축기 상세 설계

  • 이제 62진법 변환 기법을 사용해 URL 단축 처리 흐름을 살펴보자.
      1. 입력으로 긴 URL을 받는다.
      1. 데이터베이스에 해당 URL이 있는지 검사한다.
      1. 데이터베이스에 있는 경우: 데이터베이스에서 해당 단축 URL을 가져와서 클라이언트에게 반환한다.
      1. 데이터베이스에 없는 경우: 유일한 ID를 생성한다. 이 ID는 데이터베이스의 기본 키로 사용된다.
      1. 62진법 변환을 적용해 ID를 단축 URL로 만든다.
      1. ID, 단축 URL, 원래 URL로 새 데이터베이스 레코드를 만든 후 단축 URL을 클라이언트에 전달한다.
 
  • 주의할 점은 ID는 전역적 유일성(globally unique)이 보장되어야 한다.
    • 고도로 분산된 환경에서 이런 생성기를 만드는 것은 무척 어려운 일이다.
    • 7장에서 분산 ID 생성기를 구현하는 몇 가지 방법을 살펴봤으니 기억이 잘 나지 않는다면 복습하자.
 

3.4. URL 리디렉션 상세 설계

  • URl 단축기 서비스는 쓰기보다 읽기를 더 자주 하는 시스템이다.
  • 따라서 <단축 URL, 원래 URL>의 쌍을 캐시에 저장하면 성능을 높일 수 있다.
  • 로드밸런스의 동작 흐름은 다음과 같다.
      1. 사용자가 단축 URL을 클릭한다.
      1. 로드밸런서가 해당 클릭으로 발생한 요청을 웹 서버에 전달한다.
      1. 캐시에 해당 단축 URL이 있는 경우: 원래 URL을 바로 꺼내서 클라이언트에게 전달한다.
      1. 캐시에 해당 단축 URL이 없는 경우: 데이터베이스에서 꺼낸 URL을 캐시에 넣은 후 클라이언트에게 전달한다.