URL 단축기 설계

• tiny url 같은 URL 단축기 설계

문제 이해 및 설계 범위 확장

질문을 통해 모호함을 줄이고 요구사항을 알아내야 함.

기본적 기능

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

개략적 추정

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

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

API 엔드포인트

1. URL 단축용 엔드포인트: 새 단축 URL을 생성하고자 하는 클라이언트는 이 엔드포인트에 단축할 URL을 인자로 실어서 POST 요청을 보내야 함.

POST /api/v1/data/shorten
- 인자: {longUrl: longURLstring}
- 반환: 단축 URL

2. URL 리다이렉션용 엔드포인트: 단축 URL에 대해서 HTTP 요청이 오면 원래 URL로 보내주기 위한 용도의 엔드포인트.

GET /api/v1/shortUrl
- 반환: HTTP 리다이렉션 목적지가 될 원래 URL

URL 리다이렉션

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

301 응답과 302 응답의 차이

• 301 Permanently Moved: 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답. 브라우저는 이 응답을 캐시(cache)함.
• 302 Found: 주어진 URL로의 요청이 '일시적으로' Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답. 클라이언트의 요청은 언제나 단축 URL 서버에 먼저 보내진 후에 원래 URL로 리다이렉션 되어야 함.

서버 부하를 줄이는 것이 중요하다면 301 Permanently Moved, 트래픽 분석(analytics)이 중요하다면 302 Found를 쓰는 쪽이 용이.

URL 리다이렉션을 구현하는 가장 직관적인 방법은 해시 테이블을 사용하는 것.

• 원래 URL = hashTable.get(단축 URL)
• 301 또는 302 응답 Location 헤더에 원래 URL을 넣은 후 전송

URL 단축

긴 URL을 해시 값으로 대응시킬 해시 함수 fx가 필요.

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

상세 설계

데이터 모델

• 메모리는 유한하고 비싸기 때문에, 해시 테이블을 실제 시스템에 쓰기는 곤란. <단축 URL, 원래 URL>의 순서쌍을 관계형 데이터베이스에 저장하는 방법으로 변경.
  

해시 함수

해시 함수(hash function)는 원래 URL을 단축 URL로 변환하는 데 쓰임.

해시 값 길이

hashValue는 [0-9, a-z, A-Z]의 문자들로 구성. 사용할 수 있는 문자의 개수는 26 + 26 + 10 = 62개. hashValue의 길이를 정하기 위해서는 62^n >= 3650억(365billion)인 n의 최솟값을 찾아야 함.

n=7이면 3.5조 개의 URL 생성 가능. hashValue의 길이는 7로 결정.

해시 함수 구현에 쓰일수 있는 두 가지 방법
1. 해시 후 충돌 해소
2. base-62 변환

해시 후 충돌 해소

CRC32, MD5, SHA-1 같이 잘 알려진 해시 함수를 이용.
https://en.wikipedia.org/wiki/Systems_design를 축약한 결과

계산된 해시 값이 너무 김, 계산된 해시 값에서 처음 7개 글자만 이용.이럴 경우 해시 결과가 서로 충돌할 확률이 높아짐. 충돌이 실제로 발생했을 때는, 충돌이 해소될 때까지 사전에 정한 문자열을 해시값에 덧붙임.

이 방법을 쓰면 충돌은 해소할 수 있지만 단축 URL을 생성할 때 한 번 이상 데이터베이스 질의를 해야 하므로 오버헤드가 큼. 데이터베이스 대신 블룸 필터를 사용하면 성능을 높일 수 있다.

base-62 변환

이 기법은 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하여야 하는 경우에 유용. 62진법을 쓰는 이유는 hashValue에 사용할 수 있는 문자(character) 개수가 62개이 때문.

긴 URL에 대해서 유일성 보장 ID 생성기를 통해 ID를 할당하고, 이 ID를 base-62로 변환하여 단축 URL로 사용.

두 접근법 비교

URL 단축기 상세 설계

1. 입력으로 긴 URL을 받음.
2. 데이터베이스에 해당 URL이 있는지 검사.
3. 데이터베이스에 있다면 해당 URL에 대한 단축 URL을 만든 적이 있는 것. 해당 단축 URL을 클라이언트에게 반환.
4. 데이터베이스에 없는 경우, 해당 URL은 새로 접수된 것이므로 유일 ID를 생성. 이 ID는 데이터베이스의 기본 키로 사용.
5. 62진법 변환을 적용, ID를 단축 URL로 만듬.
6. ID, 단축 URL, 원래 URL로 새 데이터베이스 레코드를 만든 후 단축 URL을 클라이언트에 전달.

여기서 ID 생성기의 주된 용도는, 단축 URL을 만들 때 사용할 ID를 만드는 것이고, 이 ID는 전역적 유일성(globally unique)이 보장되어야 함.

URL 리다이렉션 상세 설계

쓰기보다 읽기를 더 자주 사용하는 시스템이기에, <단축 URL, 원래 URL>의 쌍을 캐시에 저장하여 성능을 높임.

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

마무리

좀 더 생각해볼 부분.

• 처리율 제한 장치(rate limiter): 엄청난 양의 URL 단축 요청이 밀려들 경우 무력화될 수 있다는 잠재적 보안 결함을 가지고 있음. 처리율 제한 장치를 둬서, IP 주소를 비롯한 필터링 규칙(filtering rule) 들을 이용해서 요청을 걸러낼 수 있음.
• 웹 서버의 규모 확장: 본 설계에 포함된 웹 계층은 무상태(stateless) 계층이므로, 웹 서버를 자유로히 증설하거나 삭제할 수 있음.
• 데이터베이스의 규모 확장: 데이터베이스를 다중화하거나 샤딩(sharding) 하여 규모 확장성을 달성할 수 있음.
• 데이터 분석 솔루션(analytics): URL 단축기에 데이터 분석 솔루션을 통합해 두면 어떤 링크를 얼마나 많은 사용자가 클릭했는지, 언제 주로 클릭했는지 등 중요한 정보를 알아낼 수 있음.
• 가용성, 데이터 일관성, 안정성

출처

• http://www.yes24.com/Product/Goods/102819435