1. 문제 이해 및 설계 범위 확정
•
URL 단축 : 주어진 긴 URL을 짧게 줄인다.
•
URL 리디렉션 : 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내
•
높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨
1.2. 개략적 추정
•
쓰기 연산 : 매일 1억 개의 단축 URL 생성
•
초당 쓰기 연산 : 1억 / 24 / 3600 = 1160회
•
읽기 연산 : 읽기 연산과 쓰기 연산의 비율이 10:1 이라고 가정하면, 읽기 연산은 초당 11,600회 발생
•
URL 단축기 서비스를 10년간 운영한다고 했을 때, 1억 365 10 = 3650억 개의 레코드를 보관해야 함
•
축약 전 URL의 평균 길이는 100이라고 가정
•
따라서 10년 동안 필요한 저장 용량은 3650억 * 100바이트 = 36.5TB
2. 개략적 설계안 제시 및 동의 구하기
2.1. API 엔드포인트
•
URL 단축기는 기본적으로 두 개의 엔드포인트를 필요로 한다.
◦
URL 단축용 엔드포인트
▪
새 단축 URL을 생성하는 API
▪
POST /api/v1/data/shorten
•
단축 URL을 반환
◦
URL 리다이렉션용 엔드포인트
▪
단축 URL에 대해서 HTTP 요청이 오면 원래 URL로 보내주기 위한 API
▪
GET /api/v1/shortUrl
•
원래 URL 반환
2.2. URL 리디렉션
•
HTTP 상태코드 중 301과 302은 둘 다 리디렉션이지만 아래 차이점이 있다.
◦
301 Permanently Moved
▪
해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전됨
▪
브라우저는 이 응답을 캐싱하여 같은 단축 URL호출 시 브라우저 캐시로 원래 URL로 요청전달
▪
부하 절감
◦
302 Found
▪
해당 URL 요청이 일시적으로 Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답.
▪
언제나 단축 URL 서버에 먼저 보내진 후에 원래 URL로 리다이렉션 되어야 함.
▪
트래픽 분석에 용이
2.3. URL 단축
•
긴 URL을 단축 형태로 만들기 위해서는 해시 값으로 대응시킬 해시 함수 fx를 찾아야 한다.
•
해당 해시는 다음 요구사항을 만족한다.
◦
입력으로 주어지는 긴 URL이 다른 값이면 해시 값도 달라야 한다.
◦
계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야 한다.
3. 상세 설계
3.1. 데이터 모델
•
개략적 설계 당시엔 모든 것을 해시 테이블에 두었지만, 비싸고 유한한 메모리에 두기엔 곤란하다.
•
더 나은 방법으로는 <단축 URL, 원래 URL>의 순서쌍을 관계형 DB에 저장하는 것이다.
3.2. 해시 함수
•
해시 함수는 원래 URL을 단축 URL로 변환하는 데 쓰인다.
3.2.1. 해시 값 길이
•
hashValue는 [0-9, a-z, A-Z]의 문자로 구성된다.
◦
사용 가능 문자 수는 10+26+26 = 62개다.
•
hashValue의 길이를 정하기 위해선 62^n ≥ 3650억인 n의 최솟값을 찾아야 한다!
◦
추정치에 따르면 이 시스템은 3650억 개의 URL을 만들어 낼 수 있어야 한다.
3.2.2. 해시 후 충돌 해소
•
긴 URL을 줄이려면, 원래 URL을 7글자 문자열로 줄이는 해시 함수가 필요하다.
◦
손쉬운 방법은 알려준 해시 함수를 사용하는 것
•
가장 짧은 해시 문자열을 만드는 CRC32도 8글자로 7자 보다도 크다.
•
줄이기 위한 첫 번째 방법이 해시 후 처음 7글자만 이용하는 방법이다.
◦
하지만 이럴 경우 해시 결과가 충돌할 확률이 높다.
•
충돌 발생 시 사전에 정한 문자열을 해시값에 덧붙인다.
◦
다만 이 방법은 질의에 대한 오버헤드가 크다.
◦
이 경우 DB의 블룸 필터를 사용해서 성능을 높힐 수 있다.
3.2.3. base-62 변환
•
진법 변환은 URL 단축기를 구현할 때 흔히 사용되는 접근법 중 하나다.
•
62 진법을 쓰는 이유는 hashValue에 사용할 수 있는 문자 개수가 62개이기 때문이다.
진수 변환
3.2.4. 두 접근법 비교
3.4.5. URL 단축기 상세 설계
1.
입력으로 긴 URL을 받는다.
2.
데이터베이스에 해당 URL이 있는지 검사한다.
3.
데이터베이스에 있다면 해당 URL에 대한 단축 URL을 만든 적이 있는 것이다. 따라서 데이터베이스에서 해당 단축 URL을 가져와서 클라이언트에게 반환한다.
4.
데이터베이스에 없는 경우에는 해당 URL은 새로 접수된 것이므로 유일한 ID를 생성한다. 이 ID는 데이터베이스의 기본 키로 사용된다.
5.
62진법 변환을 적용, ID를 단축 URL로 만든다.
6.
ID, 단축 URL, 원래 URL로 새 데이터베이스 레코드를 만든 후 단축 URL을 클라이언트에 전달한다.
3.4.6. URL 리디렉션 상세 설계
1.
사용자가 단축 URL을 클릭한다.
2.
로드밸런서가 해당 클릭으로 발생한 요청을 웹 서버에 전달한다.
3.
단축 URL이 이미 캐시에 있는 경우에는 원래 URL을 바로 꺼내서 클라이언트에게 전달한다.
4.
캐시에 해당 단축 URL이 없는 경우에는 데이터베이스에서 꺼낸다. 데이터베이스에 없다면 아마 사용자가 잘못된 단축 URL을 입력한 경우일 것이다.
5.
데이터베이스 꺼낸 URL을 캐시에 넣은 후 사용자에게 반환한다.
4. 마무리
•
설계를 마친 후 시간이 좀 남는다면 다음 사항을 이야기 나눠볼 수 있다.
◦
처리율 제한 장치
◦
웹 서버의 규모 확장
◦
데이터베이스의 규모 확장
◦
데이터 분석 솔루션
◦
가용성, 데이터 일관성, 안정성
