개요
8장은 bitly와 같은 단축 URL을 생성하는 서비스를 설계하는 장이다.
단축 URL 생성기를 만들 때 중요한 지점인 해시 함수를 어떻게 사용할까?와 리다이렉트 시점에서 어떤 HttpStatus를 리턴할까?를 중심으로 다룬다.
요구사항 명확하게 하기
이 장은 면접자와 면접관 사이에 대화로 요구사항을 명확하게 하는 과정을 상세하게 다룬다.
면접자가 질문을 통해 명확하게 한 요구사항은 다음과 같다.
- URL 단축기의 동작 예시
- 서비스의 트래픽 규모
- 단축 URL의 길이
- 단축 URL에 포함될 문자의 제한
- 단축 URL에 대한 기능
이를 통해 다음과 같이 결론을 내렸다.
- 쓰기 연산 : 매일 1억개의 단축 URL 생성
- 초당 쓰기 연산 : 1억/24/3600 = 1160개
- 읽기 연산 : 읽기 연산와 쓰기 연산의 비율은 10대 1로 잡아 읽기 연산은 초당 11,600회
- 이 서비스를 10년간 운영한다고 하면 10억 * 10 * 365 => 3650억개의 레코드 저장
- 축약전 URL의 평균 길이는 100
- 10년간 저장할 저장 용량은 3650억 * 100바이트 = 36.50TB
설계
이제 개요에서 다뤘던 2가지 포인트인 해시 함수 설계와 리다이렉트 HttpStatus에 대해서 다뤄야 한다.
Redirect Status
먼저 Redirect Status 부터 알아보자.
redirect status는 HttpStatus에서 3xx번대에 위치한다. 책에서는 그 중에서 301 Moved Permanently와 302 Found 중에서 선택해야 한다고 알려준다.
책에서 말하기를 이 둘의 주된 차이점은 301의 경우 브라우저가 이동할 URL을 캐싱하여 다음 요청에서는 단축 URL 생성기에 접속하지 않고 즉시 이동을 한다고 한다.
그와 달리 302의 경우는 캐싱되지 않아서 단축 URL 생성기 서버로 접속하기 때문에, 트래픽 분석이나 사용양등에 대해서 파악할 수 있다는 장점이 존재하기 때문에 상황에 맞게 고려하면 될 것이다.
아래 사진을 보면 301의 경우 2차 시도에서는 캐싱되어 301 status가 나오지 않는 것을 볼 수 있지만 302의 경우 2차례 모두 302가 찍히는 것을 확인할 수 있다.
마찬가지로 서버에서도 301의 경우 로그가 하나밖에 남지 않지만, 302의 경우 매번 로그가 남는 것을 확인할 수 있다.
해시 함수 설계
이 다음은 해시 함수를 설계하는 방법이다.
먼저 사전 요구사항에서 단축 URL이 가질 수 있는 문자는 a-z, A-Z, 0-9까지 62개이고, 이 62개를 진법화하여 3650억개를 계산할 경우 총 7글자로 표현이 가능하다는 결론이 나온다.
책에서 소개하는 해시 함수를 설계하는 방법은 2가지로 해시 후 충돌 해소 방법과 base-62 변환 방법이 있다.
해시 후 충돌 해소
해시 후 충돌 해소 방법은 이미 만들어진 해시 알고리즘인 SHA-1, MD5와 같은 알고리즘을 사용한 후 7글자만을 사용하는 방법이다. 하지만 이럴 경우 해시 충돌이 발생할 수 있기 때문에, 원문에 사전에 정의한 단어를 추가해서 다시 해시값을 만들어내는 방법을 이용한다.
예를 들면 다음과 같이 동작한다.
www.google.com을 해싱하고자 한다.
- 알고리즘 A로
www.google.com을 해싱한다.aaaaaaaaaaaaaaaaa라는 결과가 나와서 앞에 7글자인aaaaaaa만을 선택한다. - DB에
aaaaaaa가 있는지 질의한다.
2-1. 없다면 저장 후 사용한다. - 만약 있다면
www.google.com에 사전에 정한 문자열을 추가한다.a라고 가정하자.
다시 1로 돌아가서www.google.coma를 해싱한다. (반복)
이 경우 매번 DB에 질의하는 2번 과정이 필요하기 때문에, 성능상 손해가 발생할 수 있다고 한다.
이를 해결하기 위해 블룸 필터를 이용해 DB 질의과정을 줄인다고 한다.
base-62 변환
base-62 변환은 일반적으로 사용하는 방법이라고 한다. 62개의 수를 사용하기 때문에 62진법으로 변환이 가능한데, DB에 저장을 하면서 생길 PK를 62진법으로 변환한 후 이를 shortURL로 사용하는 방법이다.
책에서는 11157이라는 PK를 변환하는 과정을 보여준다.
11157 => 2 * 62^2 + 55 * 62^1 + 59 * 62^0 => [2, 55, 59] -> [2, T, X] => 2TX
이 두 접근법의 차이는 다음 표로 정리할 수 있다.
| 해시 후 충돌 해소 전략 | base-62 변환 |
|---|---|
| 단축 URL의 길이가 고정됨 | 단축 URL의 길이가 가변적이다. PK의 길이에 따라서 다르다. |
| 유일성이 보장되는 ID 생성기가 필요하지 않다. | 유일성 보장 ID 생성기가 필요하다. |
| 충돌이 가능하기 때문에, 해소 전략이 필요하다. | ID가 유일하다면 충돌이 발생하지 않는다. |
| 다음에 사용될 URL을 파악할 수 없다. | ID를 파악한다면 다음에 사용할 URL을 파악할 수 있다. |
상세 설계
이제 위에서 말한 점에서 base-62 변환과 302 Found 를 사용해서 실제 설계를 진행해보자.
이 시스템에는 2개의 기능이 존재한다.
- Long URL을 ShortURL로 등록하고 저장한다.
- ShortURL을 입력하면 Long URL로 리다이렉트 시켜준다.
ShortURL 등록 기능 설계
먼저 API에 대해서는 아래와 같이 설계하겠다.
[POST] /api/v1/data/shortedbody : {longUrl: (string)}response : 201 Created(status) | {shortenUrl : (string)}(body)
그리고 workflow는 다음과 같이 동작한다.
ShortURL 리다이렉트 설계
리다이렉트를 해주는 API에 대해서는 아래와 같이 설계한다.
[GET] /api/v1/{shortURL}response : 302 Found
그리고 다음과 같이 동작한다.
shortURL에 대해서는 DB의 unique 값을 설정해서 중복값이 저장되지 않게 하면서 조회 성능 향상을 위한 index를 생성한다.
그리고 shortUrl을 key로 가지고 있고 longUrl을 value로 가지고 있는 캐시 데이터를 캐시 저장소에 저장해 조회 성능을 올리도록 했다.
위의 과정에서는 cache 읽기 전략으로 look aside를 사용했다. 편의에 따라서 원하는 전략을 사용해도 좋다.
최종 아키텍처
최종 아키텍처는 아래와 같다.
추가적으로 처리율 계산기 등을 추가해서 서버의 부하를 줄이거나, 유저에게 제한 사용율을 주는 방법도 있을 것이다.
