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

문제 이해 및 설계 범위 확정

이번 챕터에서는 긴 URL을 짧은 URL로 바꿔주는 URL 단축기를 설계한다. 전체적인 요구사항은 아래와 같다.

매일 1억개의 단축 URL을 생성할 수 있어야 한다.
단축 URL은 짧으면 짧을수록 좋다.
생성된 단축 URL은 삭제하거나 갱신할 수 없다.
높은 가용성(HA, High Availability)과 규모 확장성(Scalability), 장애 감내(FT, Fault Tolerance)가 요구된다.

장애 감내 혹은 내결함성이란 시스템을 구성하는 하나 이상의 구성요소에 장애가 발생해도 시스템이 중단없이 계속 작동할 수 있는 성질을 의미한다.

HA와 FT는 비슷해보이지만, 약간의 차이가 존재한다. HA는 서비스 중단이 허용되는 최소의 시간이 존재한다. 예를 들어 가용성이 99.99999999999999%인 시스템은 연간 5분의 다운타임을 허용한다. 하지만, FT는 서비스 중단이 전혀 없이 동작해야한다. 비유하자면 스페어 타이어가 있는 자동차는 HA이다. 타이어는 펑크가 날 수 있지만, 빠른 시간내에 타이어를 교체할 수 있다. 반면 엔진이 2개인 쌍발 비행기는 FT이다. 엔진 하나가 고장나도 다른 엔진으로 계속 비행할 수 있다. (참고)

HTTP 리디렉션

단축 URL 서비스는 단축된 URL로 접근하면, 응답 헤더 Location 에 실제 URL을 넣어두고 상태 코드로 301 또는 302를 반환하는 방식으로 동작한다. 브라우저는 Location 헤더에 적힌 URL로 클라이언트를 리디렉션 시킬 것이다. 그런데, 301과 302 중 어떤것을 사용하는게 적합할까?

301 Permanently Moved는 영구적으로 URL이 변경됨을 의미한다. 따라서 한번 301을 만난 브라우저는 Location 값을 캐싱해두고, 단축 URL로 접근하면 단축 URL 서버에 요청하지 않고 곧바로 캐싱된 원본 URL로 이동한다. 이 방식은 단축 URL 서버에 부하를 줄이고 싶을 때 사용할 수 있다.

반면, 302 Found는 일시적으로 URL이 변경됐음을 의미한다. 따라서 브라우저는 별도의 캐싱 없이 항상 단축 URL 서버에 실제 요청을 보낸다음 Location 헤더를 읽어 원본 URL로 이동한다. 이 경우 서버에 부하가 있겠지만, 트래픽 분석 등이 필요할 때 사용한다.

데이터 모델링

간단하게 생각하면, 우리는 원본 URL과 단축 URL의 쌍을 저장하여 서비스를 구현할 수 있다. 적합한 자료구조로 해시 테이블이 떠오르지만, 우리는 이 많은 데이터를 해시 테이블에 저장할 수 없으므로 (메모리 용량과 휘발성의 한계) 데이터베이스에 저장해야한다. 데이터베이스로는 관계형 데이터베이스를 선택한다.

가장 간단한 방법은 shortURL 컬럼과 longURL 컬럼 두개를 한 row에 저장하는 방법이다. 모델링은 이렇게 하도록 한다.

URL 단축을 위한 해싱

해시 함수

해시 함수는 원래 URL을 단축 URL로 변환하는데 사용된다.

해시 값 길이

앞서 개략적인 추정을 생략했는데, 요구사항 중 매일 1억개의 단축 URL을 생성할 수 있어야한다고 했다. 1년을 365일이라고 했을 때 1년에 365억개의 URL이 생성된다. 서비스 운영 기간을 10년이라고 가정하면, 3650억개의 URL이 생성된다. 즉, 시스템은 유일한 URL을 3,650억개 이상 생성할 수 있어야한다. 그러면서도 ‘단축 URL은 짧으면 짧을수록 좋다.’ 요구사항을 만족하기 위해 최대한 짧아야한다.

URL을 구성하는 문자를 알파벳 소문자, 알파벳 대문자, 숫자로 제한한다면 사용할 수 있는 문자의 종류는 26 + 26 + 10 = 62개이다. 62^6 = 568억 23만 5584 이고, 62^7 = 약 3.5조이다. 즉 해시 값의 길이가 7 이상이면 생성할 수 있는 URL 개수가 3,650억개가 넘어가므로 요구사항을 만족한다.

해시 함수는 어떻게 구현할까? 첫번째는 ‘해시 충돌 후 해소 방법’ 이고, 두번째는 ‘base-62 변환법’ 이다.

해시 후 충돌 해소

https://en.wikipedia.org/wiki/Systems_design 을 유명한 해시 함수로 해싱해보자.

CRC32 : 5cb54054
MD5 : 5a62509a84df9ee03fe1230b9df8b84e
SHA-1 : 0eeae7916c06853901d9ccbefbfcaf4de57ed85b

가장 짧은 CRC32의 경우도 8글자로 7글자보다 길다. 이를 해결하기 위해 해시 값의 앞 7글자만 사용하는 방법이 있을 것이다. 하지만, 이렇게 하면 해시 충돌 확률이 올라간다. 따라서 충돌이 발생하면 해소하는 작업이 필요하다. 충돌이 해소될 때 까지 사전에 정한 문자열을 해시값에 덧붙이는 방법이다.

이 방법은 해시 충돌을 해결할 수 있지만, 해시 충돌이 발생할 때마다 데이터베이스에 쿼리 해야하므로 오버헤드가 크다. 데이터베이스 대신 블룸필터를 사용하면 성능을 더 높일 수 있다고 하는데, 나중에 공부해보자.

base-62 변환

진법 변환(base conversion)은 URL 단축기를 만들때 흔히 사용하는 방법이라고 한다. URL에 들어갈 수 있는 문자 종류가 62개라고 했다. 따라서 62진법을 사용한다. 그럼 무엇을 62진수로 변환할까? 데이터베이스에 저장되는 유일 키이다. 만약 PK가 12345678라면, 62진법으로는 pnfq 이다. 단축 URL은 https://hudiurl.com/pnfq 가 된다.

62진법에서 z 가 61을 나타낸다고 했을 때, 7글자로 나타낼 수 있는 62진법의 가장 큰 숫자는 zzzzzzz 이다. 이는 62^7이며, 아까 계산했듯 3.5조가 넘는 숫자이다. 요구사항을 만족한다.

두 접근법 비교

해시 후 충돌 해소	base-62 변환
단축 URL의 길이가 고정된다.	가변적인 단축 URL 길이를 갖는다. ID 값이 커지면, URL 길이도 길어진다.
유일성 보장 ID 생성기가 필요없다.	ID를 기반으로 URL이 결정되므로, 유일성이 보장되는 ID 생성기가 필요하다.
충돌을 해소하는 작업이 필요하다. 이로 인한 오버헤드가 발생한다.	충돌이 아예 불가능하다. 유일한 ID로 URL을 생성하기 때문이다.
다음에 생성된 단축 URL을 유추할 수 없다.	ID가 Auto Increment로 생성된다는 가정하에, 다음 URL을 예측할 수 있으므로 보안상 문제가 될 수도 있다.

마치며

옛날 한창 URL 단축 사이트가 많이 등장했을 때 ‘만들기 참 쉬워보이는데 나도 만들어볼까?’ 라는 생각을 잠깐 해본적이 있다. 물론 직접 만든적은 없지만… 사실 구현이야 누구나 한다. 하지만 ‘대용량 트래픽’, ‘적은 용량’, ‘분산 환경’, ‘고성능’, ‘고가용성’ 등의 요구 사항이 붙는 순간 아무리 단순한 것도 어려워지는 것 같다. 이것이 프로그래밍이 어려운 이유이자 재밌는 이유인 것 같다. 아무리 단순한 프로그램을 만든다고 하더라도, 극한의 상황을 상정하고 끊임없이 개선해보는 경험을 해봐야 진짜 성장하는 것 같다.

더 공부해볼 키워드

블룸필터

참고

가상 면접 사례로 배우는 대규모 시스테 설계 기초, 알렉스 쉬
https://www.imperva.com/learn/availability/fault-tolerance/