[가상 면접 사례로 배우는 대규모 시스템 설계 기초]8. URL 단축키 설계

https://product.kyobobook.co.kr/detail/S000001033116 

가상 면접 사례로 배우는 대규모 시스템 설계 기초 | 알렉스 쉬 - 교보문고

1장 사용자 수에 따른 규모 확장성 : https://inhyeok-blog.tistory.com/40
2장 개략적인규모추정 : https://inhyeok-blog.tistory.com/41
3장 시스템 설계 면접 공략법 : https://inhyeok-blog.tistory.com/42
4장 처리율제한장치의설계 : https://inhyeok-blog.tistory.com/43
5장 안정해시설계 : https://inhyeok-blog.tistory.com/44
6장 키-값저장소설계 : https://inhyeok-blog.tistory.com/45
7장 분산시스템을위한유일 ID 생성기설계 : https://inhyeok-blog.tistory.com/46
8장 URL 단축기설계 : https://inhyeok-blog.tistory.com/47
9장 웹크롤러설계 : https://inhyeok-blog.tistory.com/48
10장알림시스템설계 : https://inhyeok-blog.tistory.com/49
11장뉴스피드시스템설계 : https://inhyeok-blog.tistory.com/50
12장채팅시스템설계 : https://inhyeok-blog.tistory.com/51
13장검색어자동완성시스템 : https://inhyeok-blog.tistory.com/52
14장유튜브설계 : https://inhyeok-blog.tistory.com/53
15장구글드라이브설계 : https://inhyeok-blog.tistory.com/54

 

이번 장에서는 URL 단축 서비스를 설계해 볼 것이다. 그 전에 URL 단축 서비스가 왜 필요한지 먼저 이야기 해보자. 사실 필자는 URL 단축 서비스를 사용해본 적이 없다. 조금 긴 URL을 전송하거나 사용한다고 해서 큰 문제가 발생하지 않기 때문이다. 하지만 아마 twitter와 같이 제한된 글자 수를 보낼 수 있는 서비스를 사용하는 사람들은 URL을 짧게해야 한다는 필요성이 있을 것이다. 최근 자주 보고 있는 유명한 서비스로 bit.ly와 tiney url과 같은 서비스가 있다.

 

요구사항

- URL 단축: 주어진 긴 URL을 훨씬 짧게 줄인다.

- URL 리디렉션(redirection): 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내

- 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨

 

개략적인 추정

- 쓰기 연산: 매일 1억 개의 단축 URL 생성

- 초당 쓰기 연상: 1억/24/3600=1160

- 읽기 연산: 읽기 연산과 쓰기연산의 비율을 10:1로 한다. 따라서 초당 읽기 연산은 11600이다.

- URL단축 서비스를 10년간 운영한다고 가정하면 1억*365*10=3650억개의 레코드를 보관해야 한다.

- 축약 전 URL의 평균 길이는 100B라고 가정하자. 따라서 10년 동안 필요한 저장 용량은 3650억 * 100Byte = 36.5TB이다.

 

데이터 모델

단축 URL 서비스를 위해서는 데이터를 어떤 형태로 저장해 둬야할까? 간단하게 DB에 id, shortURL, longURL으로 저장하면 된다. (실제 테이블은 이것보다 더 많은 칼럼을 가질 수 있지만, 간추린 것이다) 이게 logURL으로 shortURL을 만드는 방법을 알아보자.

 

해시함수

앞선 요구사항에서 3650억개의 레코드를 저장해야 했기 때문에, Hash Value의 길이는 7으로 정하자.(hashValue는 [0-9, a-z, A-Z]총 62개의 문자로 구성되며, 62^7 = 약 35조로 충분하다) 해시 함수 구현에 쓰일 기술로는 해시 후 충돌 해소 방법과 base-62변환을 살펴보자.

 

해시 후 충돌 해소

잘 알려진 해시 함수는 CRC32, MD5, SHA-1 등이 있다. 이때 7글자를 넘는 해시 결과는 뒤를 잘라서 사용하자. 이렇게 되면 충돌확률이 증가하는데, 충돌이 발생하면 기존 hashFunction에 넣어줬던 longURL의 맨 뒤에 정해진 문자열을 더해서 다시 hashFunction에 넣어주는 식으로 해결한다.

이 방법은 충돌을 해결하지만, URL을 생성할때 DB 조회를 여러번 해야 하므로 오버헤드가 크다. 이때 어떤 집합에 특정 원소가 있는지 검사할 수 있는 확률론에 기초한 공간 효율이 좋은 기술인 블룸 필터를 사용할 수 있다.

블룸필터는 개념도 간단하고 재미있기 때문에 꼭 찾아보길 추천한다.

 

base-62 변환

base-62방식은 특정 진법으로 되어있는 숫자를 62진법으로 변환하는 것이다. 이때 62진법인 이유는 앞서 확인했던 것 처럼 hashValue가 62개의 문자로 구성되어 있기 때문이다. 이제 ID값을 shortURL 생성 요청이 들어올 때마다 만들어서 생성된 ID를 62진법으로 변환한 결과를 URL으로 사용하게 된다.(ID를 생성하는 방법은 앞선 7장에서 열심히 살펴봤다)