가상 면접 사례로 배우는 대규모 시스템 설계 기초 8장 - URL 단축기 설계
가상 면접 사례로 배우는 대규모 시스템 설계 기초 책 정리 글입니다.
개요
URL 단축기는 말그대로 URL을 줄이는 모듈을 말한다.
✏️ 1단계 문제 이해 및 설계 범위 확정
여태까지 그래왔듯 질문을 통해 요구사항을 명확히 해야한다.
- 트래픽의 규모는? (예제에서는 매일 1억개의 단축url생성)
- url의 길이는? (예제에서는 최대한 줄이도록)
- url문자제한은? (예제에서는 0~9숫자, a~Z, A-Z 알파벳)
- url을 시스템에서 지우거나 갱신 가능? (예제에서는 불가능)
고로 이 시스템의 기본 기능은 다음과 같다고 한다.
- URL단축: 주어진 긴 URL을 훨씬 짧게 줄인다.
- URL 리다이렉션: 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내
- 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구
개략적 추정
- 쓰기 연산: 매일 1억개 단축URL 생성
- 초당 쓰기 연산: 1억/24/3600 = 1160
- 읽기 연산: 여기서는 읽기와 쓰기 비율이 10:1로 가정. 그러므로 1160 * 10 = 11,600
- URL 단축 서비스를 10년 운영한다하면 1억 * 365 * 10 = 3650억URL을 저장할 레코드가 필요.
- 축약 전 URL의 평균 길이는 100이라 가정.
- 따라서 10년 운영에 필요한 데이터 저장 용량은 3650억 * 100 = 36.5TB
✏️ 2단계 개략적 설계안 제시 및 동의 구하기
API 엔드포인트
API 엔드포인트로 서버와 통신할 것이기에, REST 스타일로 설계를 한다.
1
2
3
4
POST /api/v1/data/shorten //책에는 이렇게 되어있는데, Restful하게 짜려면 명사를 사용하는게 좋다 그래서 나는
POST /api/v1/short-url 로 하겠다.
인자: {longUrl: longURLString}
반환: 단축URL
URL 리디리렉션용 엔드포인트: 단축 URL에 대해서 요청이 오면 원래 URL로 보내주기 위한 용도의 엔드포인트이다.
1
2
3
GET /api/v1/shortUrl //책에는 이렇게 써져있지만 나는
GET /api/v1/short-url //로해서 POST와 동일하게 하였다.
반환: HTTP 리다이렉션 목적지가 될 원래 URL
즉,
이런식으로 요청의 흐름이 이루어질 것이다.
301 응답과 302응답의 차이점에 대해 간단히 짚고 넘어가야된다.
- 301 응답(Permanently Moved): 브라우저가 응답을 캐시해서 추후 같은 단축URL에 요청을 보낼 필요가 있고 요청이 도착하면 브라우저는 캐시된 원래URL로 보내버린다.
- 302 응답(Found): 클라이언트의 요청은 언제나 단축URL 서버에 먼저 보내진 후에 원래 URL로 리다이렉션 된다.
첫 번째 요청만 단축URL 서버로 전송되기 때문에 서버 부하를 줄이기엔 301이 낫다.
그러나 트래픽 분석이 중요할때는 302를 써서 클릭 발생률, 발생 위치 등을 추적하는 것도 좋다.
URL 단축
이런식으로 원본URL이 어떠한 해시함수에 들어가면 단축URL로 바뀐다고 생각하자. 요구사항은 다음과 같다.
- 입력으로 주어지는 긴 URL이 다른값이면 해시 값도 달라야 한다.
- 계산된 URL은 다시 원본 URL로 복원될 수 있어야 한다.
✏️ 3단계 상세 설계
데이터모델
<단축URL,원본URL>을 쌍으로 가지는 해시테이블을 만들 수도 있겠지만, 메모리는 유한하고 비싸기에 이러한 쌍을 RDB에 저장하는 편이 좋을거라 생각이 든다.
1
2
3
4
5
url
--------
PK id
shorUrl
longUrl
을 컬럼으로 가지는 테이블을 만든다.
해시 함수
원래 URL을 단축URL로 만드는 해시 함수를 만들어야 한다.
해시 값 길이
단축URL은 0~9, a-z, A-Z까지의 문자들로 구성된다. 따라서 사용할 수 있는 문자의 개수는 10 + 26 + 26 = 62개이다. 이 시스템은 10년간 운영될 3650억개의 URL을 중복없이 담아야하므로, $ 62^n >= 3650억 $을 넘는 n을 구해야한다.
이러한 n은 7이고 이는 3.5조개의 URL을 만들 수 있다. 따라서 단축URL의 길이는 7이다.
함수 구현에 쓰일 기술로는 해시 후 충돌 해소 방법과 base-62 변환법이 있다.
해시 후 충돌해소
긴 URL을 줄이려면, 원래 URL을 7글자 문자열로 줄이는 해시 함수가 필요하다. CRC32, MD5, SHA-1과 같이 잘 알려진 해시 함수를 이용하는것도 방법이다.
1
2
3
4
해시함수 | 해시 결과
CRC32 | 5cb54054
MD5 | 5a62509a84df9ee03fe1230b9df8b84e
SHA-1 | 0eeae7916c06853901d9ccbefbfcaf4de57ed85b
문제는 CRC32가 계산한 가장 짧은 해시조차도 단축URL의 길이인 7글자를 넘겨버린다.
이 문제를 해결할 첫 번째 방법은 7글자까지 그냥 잘라버리는 것이다.
이렇게 구현할 경우 해시 결과가 서로 충돌할 확률이 높아진다. 실제 충돌을 하면 충돌을 해소할 때까지 사전에 정한 문자열을 해시값에 덧붙이는 방법이 있다.
하지만 이렇게 하면 단축URL을 생성할 때 한 번 이상 데이터베이스에 질의해야하므로 오버헤드의 부담이 생긴다. 앞에서 배운 블룸 필터를 통해 공간 효율성을 증대시킬 수는 있지만 충돌을 피하기는 쉽지 않다는 것이다.
base-62 변환
진법 변환(base conversion)은 단축URL을 구성할 때 흔히 사용되는 접근법이다. 이 기법은 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하여야 하는 경우에 유용하다. 62진법을 사용하는 이유는 이 예시에서 한 글자에 들어올 수 있는 문자의 경우의 수가 62이기 때문이다.
base-62 변환 예제이다. $ 11527_{10} $을 62진수로 변환해 보는 예제다.
- 여기서 62진법은 이런식으로 구성되어 있다.
1
2
3
0 ~ 9 : 0 ~ 9
a ~ z: 10 ~ 35
A ~ Z: 36 ~ 61
따라서 62진법에서 ‘a’는 $ 10{10} $이고, ‘Z’는 $ 61{10} $ 이다.
이러한 방식으로 $ 11157{10} $의 62진법 변환은 $ 2TX{62} $가 될 것이다.
두 접근법을 비교해 보겠다.
| 해시 후 충돌 해소 전략 | base-62 변환 |
|---|---|
| 단축URL길이가 고정 | 단축URL길이가 가변, ID값이 커지면 같이 커진다. |
| 유일성이 필요한 ID 생성기가 필요 없음. | 유일성 보장 ID가 필요함. 해시 중복 방지 |
| 충돌이 가능해서 해소 전략필요 | ID가 유일하면 충돌이 불가능 |
| ID로부터 도출해내는 방식이 아니라 다음에 쓸 URL을 알아내는것이 불가능 | 다음에쓸 단축URL을 알아낼 수 있어서 보안상의 문제가 있을 수 있다. |
URL 단축기 상세 설계
62진법 변환을 기준으로 설명 되어 있다.
처리 로직은 간단하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
입력으로 긴 원본URL을 받는다
|
|
|
|
입력된 URL이 DB에 있나?
┌----------------------┐
yes | | no
| |
| |
DB에서 찾은 단축URL 변환 새로운 ID 생성
|
|
|
|
생성된 ID를 단축URL로 변환
|
|
ID, 단축 URL, 원래URL을 DB에 저장
ID생성기는 7장에서 구현하는 방법을 이야기 했다.
URL 리다이렉션 상세 설계
- 사용자가 단축 URL을 클릭한다.
- 로드 밸런서가 해당 클릭으로 발생한 요청을 웹 서버에 전달한다.
- 단축URL이 이미 캐시에 있는 경우 원래 URL을 꺼내 반환한다.
- 단축URL이 캐시에 없는 경우 데이터베이스에서 꺼낸다. 만약 데이터가 없으면 사용자가 잘못된 단축URL을 입력한 것이다.
- 데이터베이스에서 꺼낸 URL을 캐시에 넣은 후 사용자에게 반환한다.
🤔 정리
단축URL이라는 시스템디자인을 이 책을 읽어보면서 처음 해보았다.
그렇게 어렵다고 느끼지는 않았고, 구현과정을 다시 되짚어볼 필요가 있음을 느꼈다.
API 설계, 데이터 모델 설계, 해시 함수 설계, URL 단축 및 리다이렉션 절차를 설계하였다.
추가적으로 고려해볼만한건 다음과 같은게 있다.
- 처리율 제한 장치: 엄청난 양의 URL 단축 요청이 밀려 들어오면 시스템이 무력화 될 수도 있다. 처리율 제한 장치를 둬서 요청을 어느정도 걸러낼 수 있을 것이다.
- 본 설계는 무상태(stateless) 웹 계층을 가지고 있으므로 자유롭게 웹 서버를 증설하거나 삭제할 수 있다.
- 데이터베이스 규모 확장: 데이터베이스 다중화하거나 샤딩하여 규모 확장성을 달성할 수 있다.
- 데이터 분석 솔루션: 데이터를 통해 링크를 얼마나 많은 사용자가 클릭했는지, 언제 주로 클릭했는지 등 중요한 정보를 알아낼 수 있을 것이다.
- 가용성, 데이터 일관성, 안정성 적용에 대한 논의