ch08 URL 단축기 설계
URL 단축키 설계
1단계 문제 이해 및 설계 범위 확정
시스템의 기본적 기능
- URL 단축 : 주어진 긴 URL을 훨씬 짧게 줄인다.
- URL 리디렉션(redirection) : 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내
- 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨
개략적 추정
- 쓰기 연산 : 매일 1억 개의 단축 URL 생성
- 초당 쓰기 연산 : 1억 (100million) / 24 / 3600 = 1160
- 읽기 연산 : 읽기 연산과 쓰기 연산 비율은 10:1 이라고 하자. 그 경우 연산은 초당 11,600회 발생한다 (1160 x 10 = 11,600)
- URL 단축 서비스를 10년간 운영한다고 가정하면 1억 (100million ) x 365 x 10 = 3650 억 (365billion) 개의 레코드를 보관해야 한다.
- 축약 전 URL 의 평균 길이는 100이라고 하자.
- 따라서 10년 동안 필요한 저장 용량은 3650억 (365billion) X 100 바이트 = 36.5TB이다.
2단계 개략적 설계안 제시 및 동의 구하기
API 엔드포인트
엔드포인트를 REST 스타일로 설계
- URL 단축용 엔드 포인트 :
POST /api/v1/data/shorten
- 인자 :
{longUrl : longURLstring} - 반환 : 단축 URL
- URL 리디렉션용 엔드포인트 : 단축 URL 요청이 들어오면 원래 URL로 보내주기 위한 용도
GET /api/v1/shortUrl
- 반환 : HTTP 리디렉션 목적지가 될 원래 URL
URL 리디렉션
단축 URL을 받은 서버는 원래 URL로 바꾸어서 301 응답의 Location 헤더에 넣어 반환
301응답과 302응답의 차이
301 Permanently Moved :
해당 URL에 대한 HTTP 요청의 처리 액임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다
영구적으로 이전되었으므로, 브라우저는 응답을 캐싱한다. 같은 단축 URL 요청이 있으면 캐시된 URL로 요청을 보내게 된다
사용하기 좋은 상황 : 서버 부하를 줄이는 것이 중요하다면 사용하는 것이 좋음, 첫 번째 요청만 단축 URL로 요청되기 때문
302 Found :
주어진 URL로의 요청이 '일시적으로' Location 헤더가 지정하는 URL로 처리되어야 한다
클라이언트 요청이 무조건 단축 URL 요청으로 보내지고 원래 URL로 리디렉션 되어야 한다.
사용하기 좋은 상황 : 트래픽 분석이 중요할 때 쓰는게 좋다. 클릭 발생률, 발생 위치를 추적하는 데 유리
해시 테이블로 구현:
<단축 URL, 원래 URL>
- 원래 URL = hashTable.get(단축 URL)
- 301 또는 302 응답 Location 헤더에 원래 URL을 넣은 후 전송
URL 단축
위 해시함수는 아래와 같은 요구사항을 만족해야 한다
요구사항
- URL이 다른 값이면 해시 값도 달라야함
- 계산된 해시 값이 URL로 복원될 수 있어야 한다
3단계 상세 설계
데이터 모델
단점
초기전략에는 괜찮으나, 메모리는 유한하기에 실제로 사용하기 곤란함
따라서, <단축 URL, 원래 URL> 의 순서쌍을 데이터베이스에 저장하는 방법이 있음
해시 함수
원래 URL을 단축 URL로 변환하는데 쓰임
해시 값 길이
단축 URL 값을 hashValue라고 할때,
[0-9, a-z, A-Z] 의 문자들로 구성
총 62개의 문자를 사용가능
62^n >= 3650억 내에서 hashValue 길이를 정해볼 수 있을 것이다.
해시 함수 구현에 쓰이는 기술
해시 후 충돌 해소
긴 URL을 줄이기 위해서는 원래 URL을 7글자 문자열로 줄이는 해시함수가 필요함
CRC32가 계산한 가장 짧은 해시값이 7보다는 길다. 어떻게 하면 줄일 수 있을까?
방법1
계산된 해시 값에서 처음 7개 글자만 이용
단점
해시 결과가 서로 충돌할 확률이 높아짐. 충돌이 발생하면, 사전에 정한 문자열을 해시값에 덧붙이기
단축 URL 생성에 데이터베이스 질의를 하므로 오버헤드가 큼
데이터베이스 대신 블룸 필터 사용으로 성능을 높일 수 있음
블룸 필터는 어떤 집합에 특정 원소가 있는지 검사할 수 있도록 하는, 확률론에 기초한 공간 효율이 좋은 기술
base-62 변환
진법 변환(base conversion) 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하여야 하는 경우 유용
62진법을 사용하는 이유 hashValue에 사용할 수 있는 문자 개수가 62개이기 때문
- 0-9 , A-Z(10-61)
- 11157(10진수) = 2 x 62^2 + 55 x 62 ^1 + 59 x 62 ^ 0 =
[2, 55, 59]=>[2, T, X]=> 2TX(62진수)이다.
| 해시 후 충돌 해소 전략 | base-62 변환 |
|---|---|
| 단축 URL의 길이가 고정됨 | 단축 URL의 길이가 가변적, ID 값이 커지면 같이 길어짐 |
| 유일성이 보장되는 ID 생성기가 필요하지 않음 | 유일성 보장 ID 생성기가 필요 |
| 충돌이 가능해서 해소 전략이 필요 | ID의 유일성이 보장된 후에야 적용 가능한 전략이라 충돌은 아예 불가능 |
| ID로부터 단축 URL을 계산하는 방식이 아니라서 다음에 쓸 수 있는 URL을 알아내는 것이 불가능 | ID가 1씩 증가하는 값이라고 가정하면 다음에 쓸 수 있는 단축 URL이 무엇인지 쉽게 알아낼 수 있어서 보안상 문제가 될 소지가 있음 |
URL 단축기 상세 설계
- 입력으로 긴 URL을 받는다.
- 데이터베이스에 해당 URL이 있는지 검사한다.
- 데이터베이스에 있다면 해당 URL에 대한 단축 URL을 만든 적이 있는 것이다. 해당 URL을 가져와서 클라이언트에게 반환
- 데이터베이스에 없는 경우, 새로운 ID를 생성한다. 데이터베이스의 기본키로 사용한다.
- 62진법 변환을 적용, ID를 단축 URL로 사용
- ID, 단축 URL, 원래 URL로 새 데이터베이스 레코드 생성, 단축 URL을 클라이언트에게 전달
예제
URL 리디렉션 상세 설계
쓰기보다 읽기를 더 자주 하는 시스템이어서, 캐시에 저장하여 성능을 높임
- 사용자가 단축 URL을 클릭
- 로드밸런서가 해당 클릭으로 발생한 요청을 웹 서버에 전달
- 단축 URL이 이미 캐시에 있는 경우에는 원래 URL을 바로 꺼내서 클라이언트에게 전달
- 캐시에 해당 단축 URL이 없는 경우에는 데이터베이스에서 꺼냄, 데이터베이스에 없다면 아마 사용자가 잘못된 URL을 입력한 경우 일 것
- 데이터베이스에서 꺼낸 URL을 캐시에 넣은 후 사용자에게 반환
4단계 마무리
설계 후 시간이 남아 할 수 있는 것들
- 처리율 제한 장치(rate limiter)
- 웹 서버의 규모 확장
- 데이터베이스의 규모 확장
- 데이터 분석 솔루션(analytics)
- 가용성, 데이터 일관성, 안정성
다음 챕터