08. URL 단축키 설계

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

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

개략적 추정

• 쓰기연산
  • 매일 1억개의 단축 URL 생성
• 초당 쓰기 연산
  • 1억 / 24 / 3600 = 1160
• 읽기 연산 (읽기 연산 : 쓰기 연산 = 10 : 1)
  • 1160 * 10 = 초당 11600회
• 10년간 운영시 보관 용량 (축약전 URL 평균 길이는 100으로 가정)
  • 1억 * 365 * 10 = 3650억 개의 레코드 보관 필요, 3650억 * 100바이트 = 36.5TB

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

API 엔드포인트

1. URL 단축용 엔드포인트
   • POST /api/v1/data/shorten
     • 인자: {longUrl: longURLstring}
     • 반환: 단축 URL
2. URL 디리렉션용 엔드포인트
   • GET /api/v1/shortUrl
     • 반환: HTTP 리디렉션 목적지가 될 원래 URL

URL 리디렉션

301, 302 응답의 차이

• 301 Permanently Moved
  • 해당 URL에 대한 HTTP 요청의 처리 책임이 ‘영구적’으로 Location 헤더에 반환된 URL로 이전되었다는 응답.
  • 영구적 이전이므로 브라우저는 이 응답을 캐시 한다.
  • 서버 부하를 줄일 때 사용하면 좋다.
• 302 Found
  • 해당 URL로의 요청이 ‘일시적’으로 Location 헤더가 지정하는 URL에 의해 처리되어야한다는 응답.
  • 트래픽 분석이 중요할 때 사용하면 좋다. (클릭 발생률이나 발생 위치를 추적하는데 좀 더 유리함)

URL 리디렉션을 구현하는 가장 직관적인 방법은 해시 테이블을 사용하는 것.

URL 단축

단축 URL이 www.tinyurl.com/{hashValue} 같은 형태라면 이 긴 URL을 해시 값으로 대응시킬 해시 함수 fx를 찾는 일이 될 것이다.

해시 함수의 요구 사항

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

3단계. 상세 설계

데이터 모델

해시 테이블에 두기보다는 관계형 DB에 저장하자.

해시 함수

원래 URL을 단축 URL로 변환하는데 쓰인다.

해시 값 길이

• hashValue는 [0-9, a-z, A-Z]의 문자들로 구성되어 사용할 수 있는 문자의 개수는 10 + 26 + 26 = 62개이다.
• 길이를 정하기 위해선 62^n >= 3650억 인 n의 최솟값을 찾아야 한다. (3650억개의 URL을 만들어야 하기 때문)

n = 7이면 3.5조개의 URL을 만들 수 있어 요구사항에 부합하게 되어 hashValue의 길이는 7로 정하였다.

해시 후 충돌 해소

긴 URL을 줄이려면 원 URL을 7글자 문자열로 줄이는 해시 함수가 필요하다. 쉬운 방법은 잘 알려진 해시함수를 이용하는 것이다.

• CRC32
• MD5
• SHA-1

하지만 해시값 길이가 제일 짧은 CRC32도 7보다는 길다. 해결할 방법은?

처음 7개 글자만 사용

• 해시 결과가 서로 충돌할 확률 높아짐.
• 충돌이 발생한다면, 충돌이 해소될 때 까지 사전에 정한 문자열을 해시값에 덧붙임.
• 단점: 단축 URL을 생성할 때 한번 이상 DB 질의를 거쳐야하므로 오버헤드가 크다. (DB대신 블룸필터를 사용하면 성능 업 가능)

base-64 변환

• URL 단축기를 구현할 때 흔히 사용되는 접근법이다. 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하여야 하는 경우에 유용하다.
• 62진법을 쓰는 이유는 hashValue에 사용할 수 있는 문자 개수가 62개이기 때문.

두 접근법 비교

URL 단축키 상세 설계

간단한 예제

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

URL 리디렉션 상세 설계

4단계. 마무리

추가 논의 부분은 아래와 같다.

• 처리율 제한 장치
  • IP 주소를 비롯한 필터링 규칙으로 요청을 걸러내어 요청을 핸들링 할 수 있다.
• 웹 서버의 규모 확장
  • 본 설계에 포함된 웹 계층은 무상태 계층이어서, 자유로이 증설하거나 삭제할 수 있다.
• 데이터베이스의 규모 확장
  • 데이터베이스를 다중화하거나 샤딩하여 규모 확장성을 달성할 수 있다.
• 데이터 분석 솔루션
  • 데이터는 중요하다.
• 가용성, 데이터 일관성, 안정성
  • 대규모 시스템이 운영되기 위해선 반드시 갖춰야할 속성들이다.