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

이번 장에서는 tiny url 같은 URL 단축기를 설계해볼 것이다.

문제 이해 및 설계 범위 확정

다음과 같이 긴 URL이 주어졌을 때, 훨씬 짧은 URL을 생성하는 단축기를 만드는 것이 목표이다.

https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long 
-> https://tinyurl.com/y7keocwj

시스템 기본 기능

1. URL 단축: 주어진 긴 URL을 훨씬 짧게 줄인다
2. URL 리디렉션: 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내
3. 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨

개략적 추정

• 쓰기 연산: 매일 1억 개의 단축 URL 생성
  • 초당 쓰기 연산: 1억/24/3600 = 1160
    
• 읽기 연산: 읽기 연산과 쓰기 연산 비율은 10:1이라고 가정
  • 초당 읽기 연산: 11600
    
• URL 단축 서비스를 10년간 운영한다고 가정하면 1억 365 10 = 3650억개의 레코드 보관
  

개략적 설계안 제시

이번 절에서는 API 엔드포인트, URL 리디렉션, URL 단축 플로에 대해 살펴보겠다.

API 엔드포인트

클라이언트는 서버가 제공하는 API 엔드포인트를 통해 서버와 통신한다. 엔드포인트는 REST 스타일로 설계할 것이다. URL 단축기는 기본적으로 두 개의 엔드포인트를 필요로 한다.

1. URL 단축용 엔드포인트

   • 새 단축 URL 생성 용도

     POST api/v1/data/shorten 
       - request parameter: {longUrl: longURLString} 
       - return: shortURL

2. URL 리디렉션용 엔드포인트

   • 단축 URL에 대해 HTTP 요청이 오면 원래 URL로 리디렉션 용도

     GET api/v1/shortUrl
       - return: longURL for HTTP redirection 

URL 리디렉션

단축 URL에 접근하면 아래와 같이 리디렉션이 일어나게 된다.

• 단축 URL을 받은 서버는 301 상태코드를 줄 것임
  
• 이때, 단축 URL을 원래 URL로 변경 후 응답 헤더의 Location에 넣어서 응답
  
• 이후 원래 URL로 리디렉션을 하게됨
  

이 통신 과정을 더 자세히 나타내면 다음과 같다.

301 응답 말고 302 응답으로 리디렉션을 할 수도 있다. 간단히 알아보자.

• 301 Permanently Moved
  • 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답
    
  • 즉, 브라우저는 이 응답을 캐싱하고, 추후 같은 단축 URL에 대해 캐시된 원래 URL로 리디렉션
    
  • 서버 부하를 줄일 수 있다는 장점
    
• 302 Found
  • 주어진 URL로의 요청이 일시적으로 Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답
    
  • 즉, 클라이언트의 요청은 항상 단축 URL 서버에 들렀다가 원래 URL로 리디렉션
    
  • 더 정확한 분석(트래픽, 클릭 발생률, 발생 위치 추적 등) 가능하다는 장점
    

가장 간단하게는 리디렉션을 구현하는 방법은, 해시 테이블에 <단축URL, 원래URL> 쌍을 저장하는 것이다. 그 과정은 다음과 같은 흐름일 것이다.

1. 단축 URL 요청
2. 원래 URL 획득 (by hashTable.get(단축URL))
3. 301(또는 302) 응답 Location 헤더에 원래 URL 넣어서 전송

URL 단축

단축 URL이 http://www.tinyurl.com/{hashValue}와 같은 형태라고 하자. 결국 중요한 것은 긴 URL을 hashValue로 대응시킬 수 있는 해시 함수를 찾는 것이다.

요구사항

• 입력으로 주어지는 긴 URL이 다른 값이면 해시 값도 달라야 한다.
  
• 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야 한다.
  

상세 설계

이번 절에서는 데이터 모델, 해시 함수, URL 단축 및 리디렉션에 관한 보다 구체적인 설계안을 만들어보자.

데이터 모델

데이터는 단순화하여 id, 단축 URL, 원래 URL 세 개의 칼럼을 갖는 DB 테이블에 저장하는 것으로 하자.

• 초기에는 해시 테이블을 메모리에 놓고 써도 되지만, 메모리는 유한하고 비싸기 때문에 비추천한다.
  
• 실제론 더 많은 칼럼을 넣을 수 있을 것이다.
  

해시 함수

해시 함수는 원래 URL을 단축 URL(hashValue)로 변환하는 데 쓰인다. 적절한 해시 함수를 설계하는 과정을 알아보자.

해시 값 길이

• hashValue는 숫자와 알파벳 대소문자로 구성됨 → 사용가능 문자 62개
• 요구사항: 3560억 개의 URL을 만들어내야함 (10년짜리 서비스)
• 따라서 3560억 이상의 경우의수를 만들어낼 수 있을 만큼 충분히 긴, 그러나 최소로 긴 적절한 길이를 찾아야 함
  
• 길이가 7이면 3.5조 정도의 문자열 조합을 만들어낼 수 있으므로, 요구사항을 충족하는 최소 길이는 7
  

구현 방식: 해시 후 충돌 해소 vs base-62 변환

• 해시 충돌 해소 방식
  • 해시 함수를 통해 해시값을 만들고, 이 값의 일부를 취하여 단축 URL을 만드는 방식
    • 해시 함수를 통해 만들어진 해시값이 대부분 꽤나 길기 때문에 일부만 취함
  • 만들어진 단축 URL을 DB에 저장하여 유일한 URL임을 보장
  • 만약 만들어진 단축 URL이 이미 DB에 존재하면, 사전에 정한 문자열을 더하고 다시 해시값 계산 (이 과정 반복)
  • 충돌 해소에 능하나, 단축 URL 생성 시 한 번 이상의 DB 질의를 해야하므로 오버헤드가 큼
• base-62 변환 방식
  • 진법 변환을 이용한 방식으로, 어떤 ID에 대해 적절한 URL을 생성할 수 있음
  • 수의 표현 방식이 다른 시스템이 같은 수를 공유해야 하는 경우에 유용
  • hashValue에 사용할 수 있는 문자 개수에 따라 base가 달라질 수 있음
  • 예시) ID=11157에 대해 base-62 변환
    • 이 경우 단축 URL은 https://tinyurl.com/2TX
      

두 접근법 비교

URL 단축기 상세 설계

URL 단축기는 시스템의 핵심 컴포넌트이므로, 그 처리 흐름이 논리적으로는 단순해야 하고 기능적으로는 언제나 동작하는 상태로 유지되어야 한다. 다음 그림은 62진법 변환 기법을 이용한 처리 흐름을 순서도 형태로 정리한 그림이다.

1. 입력으로 긴 URL을 받는다.
2. 데이터베이스에 해당 URL이 있는지 검사한다.
3. 데이터베이스에 있다면 해당 URL에 대한 단축 URL을 만든 적이 있는 것이다. 따라서 데이터베이스에서 해당 단축 URL을 가져와서 클라이언트에게 반환한다.
4. 데이터베이스에 없는 경우에는 해당 URL은 새로 접수된 것이므로 유일한 ID를 생성한다. 이 ID는 데이터베이스의 기본 키로 사용된다.
5. 62진법 변환을 적용하여 ID를 단축 URL로 만든다.
6. ID, 단축 UR, 원래 URL로 새 데이터베이스 레코드를 만든 후 단축 URL을 클라이언트에게 전달한다.

예시

• 입력된 URL이 https://en.wikipedia.org/wiki/Systems_design이라고 하자.
  
• 이 URL에 대해 ID 생성기가 반환한 ID는 2009215674938이다.
  
• 이 ID를 62진수로 변환하면 zn9edcu를 얻는다.
  
• 아래 표와 같은 새로운 데이터베이스 레코드를 만든다.
  

단축 URL을 만들기 위해 필요한 ID 생성기는 전역적 유일성이 보장되어야 한다. 고도로 분산된 환경에서 이를 만드는 것은 어렵지만, 트위터 스노플레이크 접근법 등 해결할 수 있는 기술들이 존재한다. (7장 참고)

URL 리디렉션 상세 설계

1. 사용자가 단축 URL을 클릭한다.
2. 로드밸런서가 해당 클릭으로 발생한 요청을 웹 서버에 전달한다.
3. 단축 URL이 이미 캐시에 있는 경우에는 원래 URL을 바로 꺼내서 클라이언트에게 전달한다.
4. 캐시에 해당 단축 URL이 없는 경우에는 데이터베이스에서 꺼낸다. 데이터베이스에 없다면 아마 사용자가 잘못된 단축 URL을 입력한 경우일 것이다.
5. 데이터베이스에서 꺼낸 URL을 캐시에 넣은 후 사용자에게 반환한다.

마무리

이번 장에서는 URL 단축기의 API, 데이터모델, 해시 함수, 단축 및 리디렉션 절차를 설계해 보았다. 다음은 URL 단축기를 설계하면서 추가적으로 고민해 볼 수 있는 사항들이다.

• 처리율 제한 장치(rate limiter)
  • 많은 양의 URL 단축 요청이 있을 경우 시스템이 무력화될 잠재적 보안 결함 존재
    
  • 처리율 제한 장치를 두면, IP 주소를 비롯한 필터링 규칙들을 이용해 비교적 안정적 요청 처리 가능
    
• 웹 서버의 규모 확장
  • 본 설계에 포함된 웹 계층은 무상태 계층이므로, 웹 서버를 자유롭게 증설/삭제 가능
    
• DB 규모 확장
  • URL이 저장된 DB를 다중화하거나 샤딩(sharding)하여 규모 확장성을 달성 가능
    
• 데이터 분석 솔루션(analytics)
  • URL 단축기에 데이터 분석 솔루션을 통합해 두면 어떤 링크를 얼마나 많은 사용자가 클릭했는지, 언제 주로 클릭했는지 등 중요한 정보를 알아낼 수 있음
    
• 가용성, 데이터 일관성, 안정성