8장 - URL 단축기 설계

목표

재미있는ㄴ URL 단축기를 설계해보자

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

지원자 질문

URL 단축기가 어떻게 동작해야 하는지 예제를 보여줄 수 있을까? -> 이게 왜필요하지?
트래픽 규모는?
단축 URL의 길이는?
단축 ULR에 포함될 문자에 대한 제한?
단축된 URL을 시스템에서 지우거나 갱신할 수 있는지?

면접관 대답

https://www.naver.com -> https://tinyurl.com/
매일 1억개의 단축 URL을 만들어야함
길이는 짧으면 짧을수록 좋음
문자는 숫자, 영문자(소문자+대문자)까지만 사용
시스템은 단순화하기위해 갱신은 불가

질문을 통해 다음 기능을 도출

URL 단축 : 긴 URL을 훨씬 짧게 줄인다
URL 리디렉션 : 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내
높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨 (트래픽 규모 떄문에 그런건지 의문?)

개략적 추정

쓰기 연산 : 매일 1억개 URL 생성
초당 쓰기 연산 : 1억/24/3600 = 1160
읽기연산 : 읽기연산이 쓰기연산의 10배로 가정할떄 초당 11600회
레코드 보관
1. 10년간 운영하면 1억 _ 365 _ 10 = 3650억개 레코드
2. 축약전 URL의 길이를 100으로 가정
3. 3650억 * 100byte = 36.5TB

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

API 엔드포인트

URL단추기를 RESTful API로 설계할 경우 두 개의 엔드포인트를 필요로 한다.

ULR 단축용 엔드포인트
- 새 단축 URL 생성
- http method : post
- 인자 : (longURL: longURLstring)
- 반환 : 단축 URL
URL 리디렉션용 엔드포인트
- http method : get
- 단축 URL에 HTTP 요청이 오면 원래 URL로 반환
- 반환 : http 리디렉션 목적지가 될 원래 URL

URL 리디렉션

단축 url 사용시 url을 받은 서버는 원래 url로 바꾸어서 301또는 302 응답으로 location 헤더에 넣어 반환한다.

301(Permanently Moved)
URL에 대한 HTTP 요청의 처리 책임이 영구적으로 반환된 URL로 이전
브라우저는 응답을 캐시하여 추후에 같은 요청시 바뀐 URL로 이전
302(Found)
일시적으로 반환된 URL에 의해 처리되어야 한다는 응답
단축 url요청은 언제나 단축 url서버에 먼저 보내진 후 원래 url로 리디렉션
301 장점 : 서버 부하가 줄어듬
302 장점 : 트래픽 분석 가능

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

원래 url = hashTable.get(단축 url)
301또는 302응답에 원래 url을 넣어 전송

위의 단축 url을 어떻게 만들까?

URL 단축

해시함수를 이용한다 : 긴 url ➡️ 해시 함수 ➡️ 단축 url

해시 함수 요구사항

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

3단계 상세 설계

데이터 모델

초기 설계 : 모든 것을 메모리에 위치한 해시테이블

-> (단축 URL, 원래 URL)의 순서쌍을 관계형 데이터베이스에 저장

해시 함수

해시 값 길이

사용할 수 있는 문자의 개수 = 10(숫자) + 26(영소문자) + 26(영대문자) = 62개
처음에 계산했던 3650억 레코드를 보관하기 위해서는 62^n >= 3650억인 n의 최솟값을 찾아야한다.

n = 6, 568억 개 / n = 7, 3.5조 개로 hashvalue의 길이를 7로 설정

해시함수 구현에 쓰일 두가지 방법을 살펴보자

해시 후 충돌 해소

손쉬운 방법은 CRC32, MD5, SHA-1같이 알려진 해시 함수를 이용
하지만 해시값의 길이가 길다는 문제 발생

해결방법

해시 값에서 처음 7개 글자만 이용하는 것(원하는 길이만 사용)
이렇게하면 해시결과가 서로 충돌할 확률이 높아진다.
충돌이 해소될때까지 사전에 정한 문자열을 해시값에 덧붙임으로 해결

단점 충돌은 해소할 수 있지만 단축 url을 생성할때 한 번 이상 데이터베이스 질의로 오버헤드가 큼
➡️ 베이터베이스 대신 블룸필터를 사용

base-62 변환

이 기법은 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하여야 하는 경우에 유용하다(???)

유일성 보장 ID생성기에서 생성된 값을 진법 변환기를 사용하여 나온 값을 단축 URL로 사용

두 접근법 비교

URL 단축기 상세 설계

base-62 변환을 사용해 설계

URL 리디렉션 상세 설계

(단축 URL, 원래 URL)의 쌍을 캐시에 저장하여 성능 개선

4단계 마무리

다음과 같은 이야기를 마무리로 추가할 수 있다.

처리율 제한장치 : 엄청난 양의 URL 단축 요청으로인한 무력화 개선
웹 서버의 규모 확장 : 무상태 계층이므로 새로 증설하거나 삭제 할 수 있다.
데이터베이스의 규모확장 : 다중화, 샤딩으로 규모 확장성 달성
데이터 분석 솔류션 : 분석 솔류션을 두어 비지니스에 필요한 데이터 뽑아낼 수 있음
가용성, 데이터 일관선, 안전성에 대한 이야기