가상 면접 사례로 배우는 대규모 시스템 설계 기초 chapter 8. URL 단축기 설계를 읽으면서 작성한 글 입니다.
문제 이해 및 설계 범위 확정
면접관 : https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long 이 주어졌을 때 이 서비스를 단축 URL 로 제공해야하고, 이 URL에 접속하면 원래 URL로 갈 수 도 있어야합니다. 풀어말하자면 주어진 긴 URL을 훨씬 짧게 줄이고 축약 URL로 요청이오면 원래 URL로 안내가 되어야합니다. 덧붙여 높은 가용성과 규모 확장성, 장애 감내가 요구 됩니다.
면접관이 다음과 같은 상황을 설계하려면 어떻게 해야하는지 묻는다고 하자.
그럼 고려해야하는게 무엇이 있을까? 여러 사항이 있겠지만, 크게 다음과 같은 사항들에 고려해볼 수 있을 것이다.
- 트래픽 규모
- 단축 URL 길이
- 단축 URL 에 포함될 문자 제한 여부
- 단축 URL 삭제 및 갱신 가능 여부
고려사항과 더불어 개략적으로 상황을 추정해보자.
- 매일 1억 개의 단축 URL이 생성, 초당 1160번 (1억/24/3600) 쓰기 연산이 일어난다고 가정하자.
- URL 단축 서비스를 10년간 운영, 3650억개의 (1억 x 365일 x 10년) 레코드를 보관해야한다.
개략적 설계안 제시 및 동의 구하기
API endPoint, URL 단축 flow에 대해 살펴보자.
API endPoint
URL 단축기는 기본적으로 2가지 endPoint를 필요로한다. endPoint는 RESTful API로 설계한다.
- URL 단축용 endPoint
- 사용자는 새로운 단축 URL을 생성하고자 단축할 URL을 인자로 POST 요청을 보낸다.
- POST /api/v1/data/shorten
- 단축 URL을 반환한다.
- URL 리디렉션 endPoint
- 단축 URL에 대해 HTTP 요청이 오면 원래 URL로 보내주기 위한 용도이다.
- GET /api/v1/shortUrl
- HTTP 리디렉션 목적지가 될 원래 URL을 반환한다.
URL 단축
그렇다면 어떻게 URL을 단축할 수 있을까. ?는 어떤 과정일까?
URL 단축에서 핵심은 해시 값으로 대응시킬 해시 함수 fx를 찾는 일이다.
이 해시 함수는 다음 요구 사항을 만족해야 한다.
- 입력으로 주어진 긴 URL이 다른 값이면 해시 값이 달라야 한다.
- 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야 한다.
상세 설계
데이터 모델
<단축 URL, 원래 URL>의 순서쌍을 관계형 데이터베이스에 저장한다. 간단하게만 표현해보자면 id, shortURL, longURL의 세개의 칼럼을 갖는다.
해시 함수
원래 URL을 단축 URL로 변환하는데 쓰이는 함수로, 해시 함수가 계산하는 단축 URL값을 편의상 hashValue라고 하자.
해시 값 길이
URL 단축 서비스를 10년간 운영, 3650억개의 (1억 x 365일 x 10년) 레코드를 보관해야한다. 3650억개 레코드에 대응되는 hashValue의 길이를 어떻게 정할 수 있을까?
- hashValue는 [0-9,a-z,A-Z] 의 문자들로 구성되고, 총 사용 문자는 62개이다.
- 62^n 을 계산했을 때, 3650억 이상되는 n을 찾아야한다.
계산했을 경우 n = 7 이 나오게 된다. (62^7 = 3,521,614,606,208 = 약 3.5조)
따라서 hashValue의 길이는 7로 설정할 수 있다.
해시 함수 구현에 쓰일 기술 2가지
해시 후 충돌 해소
원래 URL을 7글자 문자열로 줄이는 해시 함수가 필요하다. CRC32, MD5, SHA-1 같이 잘 알려진 해시 함수를 사용할 수 있다. 이 함수들을 이용하여 아래 URL을 축약하면 다음과 같은 결과가 나온다.
https://en.wikipedia.org/wiki/Systems_desing
CRC32 : 5cb54054
MD5 : 5a62509a84df9ee03fe1230b9df8b84e
SHA-1 : 0eeae7916c06853901dccbefbfcaf4de57ed85b그런데 자세히보면 가장 짧은 길이인 CRC32의 결과값도 7 보다 길다. 이를 어떻게하면 좋을까?
계산된 해시 값에서 처음 7개를 사용하는 방법이 있다. 하지만 이렇게 할 경우 해시 충돌 확률이 높아지기 때문에 실제로 충돌이 발생하면 충돌이 해소될 때까지 사전에 정한 문자열을 해시값에 덧붙이면 된다.
그러나 이 방법은 단축 URL을 생성할 때 한 번 이상 데이터베이스에 쿼리를 날려야하므로 오버헤드가 크다. (데이터베이스 대신 블룸 필터를 사용하면 성능을 높일 수 있다고하니 이 부분은 개인적으로 찾아보자!)
base-62변환
진법 변환은 URL 단축기를 구현할 때 흔히 사용되는 접근법 중 하나로, 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하는 경우에 유용하다. 62진법을 쓰는 이유는 hashValue에 사용할 수 있는 문자 개수가 62개이기 대문이다.
해시 후 충돌 해소 VS base-62변환
| 해시 후 충돌 해소 | base-62변환 |
|---|---|
| 단축 URL 길이 가변적 | ID값이 커지면 같이 길어짐 |
| 유일성이 보장되는 ID 생성기 필요 없음 | 유일성이 보장되는 ID 생성기 필요 |
| 충돌이 가능해서 해소 전략 필요 | ID 유일성이 보장된 후 적용 가능 전략이기 때문에 충돌 불가능 |
| ID로부터 단축 URL을 계산하는 방식이 아닌 다음에 쓸 수 있는 URL을 알아내는 것이 불가능 | ID가 1씩 증가하는 값이라고 가정하면 다음에 쓸 수 있는 단축 URL이 무엇인지 쉽게 알아낼 수 있어서 보안상 문제가 될 수 있음 |
URL 단축기 상세 설계
- 입력으로 긴 URL을 받는다.
- 데이터베이스에 해당 URL이 있는지 검사한다.
- 데이터베이스에 있다면 해당 URL에 대한 단축 URL을 만든 적이 있는 것이므로 데이터베이스에서 해당 단축 URL을 가져와서 클라이언트에게 반환한다.
- 데이터베이스에 없는 경우, 유일ID를 생성하고, 이 ID를 데이터베이스 기본키로 사용한다.
- 62진법 변환 적용, ID를 단축 URL로 만든다.
- ID, 단축 URL, 원래 URL로 새 데이터베이스 레코드를 만든 후 단축 URL을 클라이언트에 전달한다.
