URL 단축기는 아래와 같은 상황에서 주로 사용됩니다.
- 문자 제한이 있는 Twitter와 같은 소셜 미디어 플랫폼에서 긴 URL은 공간을 너무 많이 차지하여 메시지를 완전히 전달하지 못하는 경우
- 얼마나 많은 사람들이 링크를 클릭했는지, 어디에서 왔는지, 언제 클릭했는지 알 수 있는 추적 기능을 사용할 경우
문제 이해 및 설계 범위 확정
기본적인 기능
- URL 단축
- URL 리디렉션(redirection)
- 높은 가용성과 규모 확장성, 그리고 장애 감내 요구됨.
개략적 추정
- 쓰기 연산 : 매일 1억 개의 URL 생성
- 초당 쓰기 연산 1억(100million) / 24 / 3600 = 1160
- 읽기 연산 : 읽기 연산과 쓰기 연산 비율은 10:1 이라고 하자. 그 경우 읽기 연산은 초당 11,600회 발생한다. (1160 x 10 = 11,600)
- URL 단축 서비스를 10년간 운영한다고 가정하면 1억 x 365 x 10 = 3650억 개의 레코드를 보관해야 한다.
- 축약 전 URL의 평균 길이는 100이라고 하자.
- 따라서 10년 동안 필요한 저장 용량은 3650억 x 100바이트 = 36.5TB이다.
개략적 설계안 제시 및 동의 구하기
API 엔드포인트
클라이언트는 서버가 제공하는 API 엔드포인트를 통해 서버와 통신한다.
이 엔드포인트를 REST 스타일로 설계할 것이다.
URL 단축기는 기본적으로 두 개의 엔드포인트를 필요로 한다.
-
URL 단축용 엔드포인트 : 새 단축 URL을 생성하고자 하는 클라이언트는 이 엔드포인트에 단축할 URL을 인자로 실어서 POST 요청을 보내야 한다. 이 엔드포인트는 다음과 같은 형태를 띤다.
POST /api/v1/data/shorten
인자 : {longUrl: longURLstring}
반환: 단축 URL -
URL 리디렉션용 엔드포인트 : 단축 URL에 대해서 HTTP 요청이 오면 원래 URL로 보내주기 위한 용도의 엔드포인트로, 다음과 같은 형태를 띤다.
GET /api/v1/shortUrl
반환 : HTTP 리다이렉션 목적지가 될 원래 URL
URL 리디렉션
단축 URL을 받은 서버는 그 URL을 원래 URL로 바꾸어서 301 응답의 Location 헤더에 넣어 반환한다.
301 VS 302
-
301 Permanetly Moved
이 응답은 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답이다. 영구적으로 이전되었으므로, 브라우저는 이 응답을 캐시한다.
따라서 추후 같은 단축 URL에 요청을 보낼 필요가 있을 때 브라우저는 캐시된 원래 URL로 요청을 보내게 된다. -
302 Found
이 응답은 주어진 URL로의 요청이 일시적으로 Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답이다.
따라서 클라이언트의 요청은 언제나 단축 URL 서버에 먼저 보내진 후에 원래 URL로 리다이렉션 되어야 한다.
서버 부하를 줄이는 것이 중요하다면 301 응답을 사용하는 것이 좋지만, 트래픽 분석이 중요할 때는 302 응답을 사용하는 것이 좋다.
URL 단축
단축 URL이 www.tinyurl.com/{hashValue} 같은 형태라고 해보자.
결국 중요한 것은 긴 URL을 이 해시 값으로 대응시킬 해시 함수 f(x)를 찾는 일이 될 것이다.
이 해시 함수는 다음 요구 사항을 만족해야 한다.
- 입력으로 주어진 긴 URL이 다른 값이면 해시 값도 달라야 한다.
- 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야 한다.
상세 설계
데이터 모델
<단축 URL, 원래 URL>의 순서쌍을 관계형 데이터베이스에 저장할 것이다.
테이블은 단순화된 것으로 id, shortUrl, longURL의 세 개 컬럼을 갖는다.
해시 함수
해시 함수는 원래 URL을 단축 URL로 변환하는 데 쓰인다.
편의상 해시 함수가 계산하는 단축 URL 값을 hashValue라고 하자.
해시 값의 길이
hashValue는 [0-9, a-z, A-Z]의 문자들로 구성된다.
따라서 사용할 수 있는 문자의 개수는 10 + 26 + 26 = 62개다.
hashValue의 길이를 정하기 위해서는 3650억인 n의 최솟값을 찾아야 한다.
n = 7 이면 3.5조 개의 URL을 만들 수 있다. 그러면 3650억개를 만들 수 있는 요구사항을 만족시키기 충분한 값이다.
해시 함수 구현
해시 후 충돌 해소
CRC32, MD5, SHA-1같이 잘 알려진 해시 함수를 이용한다.
ex)
https://en.wikipedia.org/wiki/Systems_design
해시 함수 해시 결과 (16진수) CRC32 5cb54054 MD5 5a62509a84df9ee03fe1230b9dfb84e SHA-1 0eeae7916c06853901d9ccbefbfcaf4de57ed85b
그런데 위의 표와 같이, CRC32가 계산한 가장 짧은 해시값조차도 7보다는 길다.
이를 해결하기 위한 첫번째 방법은 계산된 해시 값에서 7개의 글자만 이용하는 것이다.
하지만 이렇게 하면 해시 충돌 확률이 높아진다.
충돌이 발생했을 때, 충돌이 해소될 때까지 사전에 정한 문자열을 해시값에 덧붙인다.
이 방법을 쓰면 충돌은 해소할 수 있지만 단축 URL을 생성할 때 한 번 이상 데이터베이스 질의를 해야하므로 오버헤드가 크다.
base-62 변환
진법 변환은 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하여야 하는 경우에 유용하다.
62진법을 쓰는 이유는 hashValue에 사용할 수 있는 문자 개수가 62개이기 때문이다.
1115710을 62진수로 변환해보자.
62진법은 수를 표현하기 위해 62개의 문자를 사용하는 진법이다.
따라서 0은 0으로 9는 9로, 10은 a로 61은 Z로 대응시켜 표현하도록 할 것이다.
예를 들어 62진법에서 ‘a’는 10을 나타내고 ‘Z’는 61을 나타낸다.1115710 = 2 x 622 + 55 X 621 + 59 x 620 = [2, 55, 59] => [2, T, X] => 2TX62 이다.
따라서 단축 URL은https://tinyurl.com/2TX가 된다.
두 접근법 비교
| 해시 후 충돌 해소 전략 | base-62 변환 |
|---|---|
| 단축 URL의 길이가 고정됨 | 단축 URL의 길이가 가변적. ID 값이 커지면 같이 길어짐 |
| 유일성이 보장되는 ID 생성기가 필요치 않음 | 유일성 보장 ID 생성기가 필요 |
| 충돌이 가능해서 해소 전략이 필요 | ID 유일성이 보장된 보장된 후에야 적용 가능한 전략이라 충돌은 아예 불가능 |
| ID로부터 단축 URL을 계산하는 방식이 아니라서 다음에 쓸 수 있는 URL을 알아내는 것이 불가능 | ID가 1씩 증가하는 값이라고 가정하면 다음에 쓸 수 있는 단축 URL이 무엇인지 쉽게 알아낼 수 있어서 보안상 문제가 될 소지가 있음 |
URL 단축기 상세 설계
base-64 기반 URL 단축기의 처리 흐름
- 입력으로 긴 URL을 받는다.
- 데이터베이스에 해당 URL이 있는지 확인한다.
- 있다면, 해당 단축 URL을 가져와서 반환한다.
- 없다면, 유일한 ID를 생성하고 이 ID를 데이터베이스의 기본키로 사용한다.
- 62진법 변환을 적용, ID를 단축 URL로 만든다.
- ID, 단측 URL, 원래 URL로 새 데이터베이스 레코드를 만든 후 단축 URL을 반환한다.
https://en.wikipedia.org/wiki/Systems_design로 예를 들어보자.
이 URL에 대한 유일한 ID는2009215674938이다.
이 ID를 62진수로 변환하면zn9edcu이다.
ID shortURL longURL 2009215674938 zn9edcu https://en.wikipedia.org/wiki/Systems_design위와 같은 레코드가 생성된다.
URL 리디렉션 상세 설계
URL 리디렉션 흐름
- 사용자가 단축 URL을 클릭한다.
- 로드 밸런서가 해당 클릭으로 발생하는 요청을 웹 서버에 전달한다.
- 단축 URL이 이미 캐시되어 있다면 원래 URL을 바로 반환한다.
- 없다면 데이터베이스에서 꺼내서 캐시에 저장한 후 반환한다.
출처
가상 면접 사례로 배우는 대규모 시스템 설계 기초(알렉스 쉬 지음 | 이병준 옮김)
