URL 단축기 설계

Gunjoo Ahn·2022년 10월 25일

system-design

문제 이해 및 설계 범위 확정

https://www.something-long.com/thisis/long/url/sameple
➜ https://short.com/L13fsnl6

https://short.com/L13fsnl6 로 접속하면 원래 URL로 간다.

트래픽 규모는 매일 1억개의 단축 URL을 만들 수 있어야 한다.

단축 URL의 길이는 짧으면 짧을 수록 좋다.

URL에 포함될 문자 제한은 숫자와 영문자만 사용할 수 있다.

시스템 단순화를 위하여 불가능하다고 가정한다.

개략적 추정

쓰기 연산 : 매일 1억개 단축 url 생성
초당 쓰기 연산 : 1억 / 24 / 3600 = 1160
읽기 연산 : 초당 11,600회 ( 읽기 연산 : 쓰기 연산 = 10 : 1)
URL 단축 서비스를 10년간 운영한다 가정하면 1억 x 365 x 10 = 3650억개 레코드 저장 필요
축약 전 URL 평균 길이가 100이라고 가정
10년 동안 필요한 저장 공간은 3650억 x 100바이트 = 36.5TB

개략적 설계안

API 엔드포인트

URL 단축용 엔드포인트 - 새 단축 URL을 생성하고자하는 클라이언트는 이 엔드포인트에 다축할 URL을 인자로 실어서 POST 요청을 보내야 한다.
POST /api/v1/data/shorten
- 인자: { longUrl: longURLString }
- 반환: 단축 URL
URL 리다이렉션용 엔드포인트 - 단축 URL에 대해서 HTTP 요청이 오면 원래 URL로 보내주기 위한 용도의 엔드포인트.
GET /api/v1/shortUrl
- 반환: HTTP 리다이렉션 목적지가 될 원래 URL

단축 URL을 받은 서버는 그 URL을 원래 URL로 바꾸어서 301 응답의 Location 헤더에 넣어 반환한다.

301 코드를 사용하여 영구적으로 Location 헤더에 반환된 URL로 이전되었다 응답하면, 브라우저는 이 응답을 캐시하여 사용한다.
하지만 트래픽 분석이 중요할 때는 302 코드를 사용하여 일시적으로 Location 헤더가 지정하는 URL로 리다이렉션한다고 반환하는 것이 클릭 발생률이나 발생 위치를 추적하는데 유리할 것이다.

URL 단축

URL 단축을 위한 해시 함수를 찾을 것이다.

입력으로 주어지는 긴 URL이 다른 값이면 해시 값도 달라야 한다.
계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야 한다.

상세 설계

해시 함수가 계산하는 단축 URL 값을 hashValue라 하겠다. HashValue는 숫자, 알파벳인 총 62개의 문자로 이루어져 있다.

해시 후 충돌 해소

64^n >= 3650억(10년간 운영했을 때 예상 레코드 수)을 만족하는 n은 7이므로 hashValue의 길이는 7로 한다.
원래 URL을 7글자 문자열로 줄이는 손쉬운 방법은 CRC32, MD5, SHA-1 등 과 같은 잘 알려진 해시 함수를 이용하여 해싱을 한 이후에 앞 7자리를 사용하는 것이다. 하지만 이렇게 하면 해시 결과가 서로 충돌할 확률이 높다. 충돌이 실제로 발생했을 때는, 충돌이 해소될 때까지 사전에 정한 문자열을 long URL 뒤에 덧붙여 다시 해싱하는 것이다.

이 방법은 단축 URL을 생성할 때마다 DB 질의가 발생하므로 오버헤드가 크다. DB대신 블룸 필터를 사용하면 성능을 높일 수 있다.

Base-62 변환

진법 변환(base conversion)은 URL 단축기를 구현할 때 흔히 사용하는 접근법중 하나이다. 62진법인 이유는 hashValue에 사용할 수 있는 문자의 개수가 62개이기 때문이다.

새로 등록한 long URL에 유일한 아이디를 부여하고, 해당 아이디를 진법 변환하여 단축 URL로 사용하는 것이다.

두 접근법 비교

해시 후 충돌 해소 전략	base-62 변환
단축 URL 길이 고정	단축 URL 길이 가변적, ID 값이 커지면 같이 커짐
유일성 보장 ID 생성기 필요 X	유일성 보장 ID 생성기 필요
충돌이 가능해서 해소 전략 필요	충돌 X
다른 사용 가능한 URL 추측 불가	ID 생성 기반이기에 알아낼 수 있어 보안에 문제가 있을 수 있음