대규모 시스템 설계 기초 - 8. URL 단축키 설계

bit.ly 를 생각하면 된다. 크게 2가지 기능이 존재함

1. 긴 URL을 넣으면 짧은 URL을 알려준다 (POST)
2. 단축된 URL을 넣으면 원래 URL을 알려준다 (GET) - redirect

 

기본적인 요구사항

• 기본 : 높은 가용성, 규모 확장성, 장애 감내
• 쓰기 연산 트래픽 : 매일 1억건
• 서비스 유지 기간 : 10년 정도

이를 통해 다음과 같은 조건을 추가로 유추할 수 있다.

• 초당 쓰기 연산 횟수 : 1160회 (매일 1억건이므로 86400초로 나눔)
• 읽기 연산을 쓰기 연산의 10배로 가정시 읽기 연산 초당 11600회
• TPS 13,000 ~ 14,000
• 하루 1억건씩 10년이면 총 3650건의 레코드 보관
• 1레코드 당 100byte 가정시 36.5TB 필요

 

비즈니스 조건

• URL의 길이는 가능한 짧으면 좋다.

GET, POST 몇 가지 생각할거리

GET

• Redirect는 HTTP header의 location 을 통해 어디로 가야할지 알려주는 방식이다.
• 301 Permanently Moved는 영구적으로 URL을 이전시킨다. 브라우저는 이 응답을 캐싱해서, 추후 한 번더 이 요청이 오게 되면 캐시된 URL로 요청을 보낸다
• 302 Found는 일시적으로 이동시킨다. 클라이언트의 요청은 언제나 단축 URL 서버에 먼저 보내진 후에 원래 URL로 이동되는 방식이다

POST

• 결국 우리는 해시 함수 fx를 찾는 것이 관건이다. (긴 문자열 → 짧은 문자열) 해시 함수는 두 가지의 조건을 만족해야 한다.
  • 주어진 URL이 다르면 해시 값도 달라야 한다
  • 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야 한다
    • DB에서 (id, long_url, short_url)

상세 설계

데이터 모델

• PK, shortUrl, long Url

 

해시 함수

해시 함수가 생산하는 문자열 길이를 추산해보자.

총 3600억개를 cover할 수 있어야 하므로 숫자, 알파벳 대소문자를 쓴다고 하면 7자리로 생산이 가능하다

 

해시 함수의 알고리즘은 크게 2가지가 가능하다

1. 해시 후 충돌 해소
   1. MD5, SHA-1 등의 해시 함수를 사용하고 7자리를 slice 한 다음 중복되는 URL이 있다면 salt를 더해 처음부터 반복하는 방법
   2. 단축 URL의 길이가 고정되고 유일성 보장 ID 생성기가 불필요하다. 또한 다음 단축 URL을 유추할 수 없다.
   3. 하지만 충돌 후 해소 로직이 있기 때문에 POST 시간이 조금더 소요될 수 있다.
2. BASE-62진법 변환
   1. 유일 ID 생성기를 이용해 ID를 생성한후 62진법으로 변환하는 알고리즘
   2. 단축 URL의 길이가 가변적이고, 다음 ID URL을 알아낼 수 있다. (즉 보안 이슈가 있음)
   3. POST 시간이 매우 짧게 된다.

몇 가지 더 생각해볼 것들

• 처리율 제한 장치
  • TPS peak 방지를 위해 전체 트래픽 처리율 제한을 둘 수 있다.
• 웹 서버 규모 확장, DB 규모 확장
• 데이터 분석 솔루션
  • URL 사용 통계 등에 대한 business적 관점