URL 단축기 설계 (대시설기)

1단계 문제 이해 및 설계 범위 확정

기본적인 기능

1. URL 단축: 주어진 긴 URL을 훨씬 짧게 줄인다.
2. URL 리디렉션: 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내
3. 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨

개략적 추정

• 쓰기 연산: 매일 1억 개의 단축 URL 생성
• 초당 쓰기 연산: 1억/24/3600 = 1160
• 읽기 연산: 읽기 연산과 쓰기 연산 비율은 10:1이라고 하자. 초당 읽기 연산은 초다아 11,600회 발생한다.
• URL 단축 서비스를 10년간 운영한다고 가정하면 1억 * 365 * 10 = 3650억개의 레코드를 보관해야 한다.
• 축약 전 URL의 평균 길이는 100이라고 하자.
• 따라서 10년 동안 필요한 저장 용량은 3650억 * 100바이트 = 36.5TB이다.

2단계 개략적 설계안 제시 및 동의 구하기

API 엔드포인트

URL 단축기는 기본적으로 두 개의 엔트포인트를 필요로 한다.

1. URL 단축용 엔드포인트: 새 단축 URL을 생성하고자 하는 클라이언트는 이 엔드포인트에 단축할 URL을 인자로 실어서 POST 요청을 보내야 한다.
2. URL 리디렉션용 엔드포인트: 단축 URL에 대해서 HTTP 요청이 오면 원래 URL로 보내주기 위한 용도의 엔드포인트

URL 리디렉션

 

• 301 Permanently Moved: 이 응답은 영구적으로 이전되었으므로, 브라우저는 이 응답을 캐시한다. 따라서 추후 같은 단축 URL에 요청을 보낼 필요가 있을 때 브라우저는 캐시된 원래 URL로 요청을 보내게 된다.
• 302 Found: 일시적. 따라서 클라이언트의 요청은 언제나 단축 URL서버에 먼저 보내진 후에 원래 URL로 리디렉션 되어야 한다.

서버의 부하를 줄이는 것이 중요하다면 301, 트래픽 분석이 중요하다면 302가 좋다.

URL 단축

해시 함수는 다음 요구사항을 만족해야 한다.

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

3단계 상세 설계

데이터 모델

모든 것을 해시 테이블에 두는 방법은 초기 전략으로는 괜찮지만 실제 시스템에 쓰지는 곤란한데, 메모리는 유한한 데다 비싸기 때문이다. 더 나은 방법은 <단축 URL, 원래 URL>의 순서쌍을 관계형 데이터베이스에 저장하는 것이다.

해시 함수

해시 함수는 원래 URL을 단축 URL로 변환하는데 쓰인다.

해시 값 길이

hashValue는 [0-9a-zA-Z]의 문자들로 구성된다. 따라서 사용할 수 있는 문자의 개수는 62개. hashValue의 길이를 정하기 위해서는 62^2 ≥ 3650억 인 n의 최소값을 찾아야 한다. n=7이면 3.5조 개의 URL을 만들 수 있다.

해시 함수 구현에 쓰일 기술 2가지

1. 해시 후 충돌 해소
2. base-62 변환

해시 후 충돌 해소

손쉬운 방법은 CRC32, MD5, SHA-1 같이 잘 알려진 해시 함수를 이용하는 것이다. 하지만 CRC32가 계산한 가장 짧은 해시값조차도 7보다는 길다.

해결법

계산된 해시 값에서 처음 7개 글자만 이용하는 것. → 충돌할 확률이 높아진다.

충돌이 실제로 발생했을 때, 충돌이 해소될 때까지 사전에 정한 문자열을 해시값에 덧붙인다.

base-62 변환

진법 변환(base conversion)은 URL 단축기를 구현할 때 흔히 사용되는 접근법 중 하나다.

62진법을 쓰는 이유는 hashValue에 사용할 수 있는 문자 개수가 62개이기 때문이다.

비교

해시 후 충돌 해소 전략 base-62 변환

단축 URL의 길이가 고정됨	단축 URL의 길이가 가변적
유일성이 보장되는 ID 생성기가 필요치 않음	유일성 보장 ID 생성기가 필요
충돌이 가능해서 해소 전략이 필요	ID의 유일성이 보장된 후에야 적용 가능한 전략이라 충돌은 아예 불가능
ID로부터 단축 URL을 계산하는 방식이 아니라서 다음에 쓸 수 있는 URL을 알아내는 것이 불가능	ID가 1씩 증가하는 값이라고 가정하면 다음에 쓸 수 있는 단축 URL이 무엇인지 쉽게 알아낼 수 있어서 보안상 문제가 될 소지가 있음

URL 단축기 상세 설계

1. 입력으로 긴 URL을 받는다.
2. 데이터베이스에 해당 URL이 있는지 검사한다.
3. 있다면 단축URL을 가져와서 클라이언트에게 반환한다.
4. 없다면 유일한 ID를 생성한다.
5. 62진법 변환을 적용, ID를 단축 URL로 만든다.
6. ID, 단축 URL, 원래 URL로 새 데이터베이스 레코드를 만든 후 단축 URL을 클라이언트에게 전달한다.

URL 리디렉션 상세 설계

1. 사용자가 단축 URL을 클릭한다.
2. 로드밸런서가 해당 클릭으로 발생한 요청을 웹 서버에 전달한다.
3. 단축 URL이 이미 캐시에 있는 경우에는 원래 URL을 바로 꺼내서 클라이언트에게 전달한다.
4. 캐시에 없다면 데이터베이스에서 꺼내서 사용자에게 반환한다.

4단계 마무리 (더 고민해 볼 주제)

• 처리율 제한 장치
• 웹 서버의 규모 확장
• 데이터베이스의 규모 확장
• 데이터 분석 솔루션
• 가용성, 데이터 일관성, 안정성