URL 단축기 설계

8장 URL 단축기 설계

URL 단축기 요구사항

• 매일 1억개의 단축 URL을 만들어낸다.
• 단축 URL의 길이는 짧으면 짧을 수록 좋다.
• 단축 URL에는 숫자(0-9), 영문자만 사용가능하다
• 만든 URL 정보를 삭제하거나 갱신할 수 없다.
• 높은 가용성과 규모 확장성, 장애 감내가 요구된다.

개략적 추정

매일 1억개라고 치면 1초당 1160개의 연산을 한다.

읽기 연산과 쓰기 연산의 비율이 10:1의 비율이라고 할 때 초당 11,600회 발생한다.

10년간 운영한다고 가정하면 1억 * 365 * 10 = 3650억개의 레코드를 보관해야하고, url 평균 길이가 100이라면 3650억 * 100 = 36.5tb를 저장해야한다.

 

HTTP Redirect code

301 permanently moved : 브라우저는 이 응답을 캐시하여 앞으로 이쪽으로 요청을 보낸다.

302 found: 일시적으로 이곳으로 redirect 처리되어야한다.

301, 302 응답은 POST로 요청을 보내도, GET으로 메서드를 바꾸어버린다. 따라서 메서드를 유지시킬 필요가 있는 경우에는 307, 308을 대신 사용한다. 실제로 Next에서는 redirect시 307, 308을 사용하고 있다.

 

URL 단축 방법

 

해시함수를 사용한다고 하면, URL 단축이란 해시값으로 대응시킬 해시 함수를 찾는 문제로 바뀐다.

입력으로 주어지는 긴 url이 다른 값이면 해시 값도 달라야하고, 해시값은 원래의 url로 복원될 수 있어야한다.

 

메모리에 대한 고민

모든 것을 해시 테이블에 두는 것은 곤란한데, 메모리는 유한하고 비싸기 때문이다. 따라서 url 순서쌍을 관계형 데이터베이스에 저장하는 것이 좋을 것이다.

 

해시 값 길이 정하기

문자 62(0-9, a-z, A-Z)개로 3650억개의 url를 만들어야하기 때문에 길이는 7로 정한다.

62 ^ 6 = 568억 이므로, 길이가 6일 때에는 568억, 길이가 7일 때에는 3조개의 url을 감당 가능하다.

 

해시 후 충돌 해소

 

crc32, md5, sha-1같이 잘 알려진 해시 함수를 이용하여 url을 단축하면 7보다 길다. 계산된 해시값에서 처음 7개 글자만 이용하면 해시 결과가 충돌할 확률이 높아진다.

충돌 발생 시에는, 문자열을 해시값에 덧붙이는 방식을 사용하면 충돌 해소가 가능하지만 url 생성 시에 한 번 이상 데이터베이스 질의를 해야하므로 오버헤드가 크다.

 

base-62 변환

유일한 id 생성 후에 62진법으로 변환, 해시 충돌은 발생하지 않지만 id가 1씩 증가하는 값이라고 가정하면 다음에 쓸 단축 url을 쉽게 알아낼 수 있다. 분산 환경에서는 분산 ID 생성기를 사용할 수 있다.

 

마무리

사용자가 단축 URL을 클릭하면, 로드밸런서가 요청을 웹 서버에 전달한다. 이미 캐시에 있는 경우 바로 전달한다. 없다면 데이터베이스에서 꺼낸다. 데이터베이스에서 꺼낸 url을 캐시에 넣은 후 사용자에게 반환한다.

 

더 고려해볼 사항

• 처리율 제한 장치 : 엄청난 요청이 밀려온다면 IP 주소를 비롯한 필터링 규칙을 이용해서 요청을 걸러낼 수 있다.
• 웹 서버의 규모 확장 : 본 웹 계층은 무상태 계층이므로 웹 서버를 자유롭게 증설/삭제 가능
• 데이터베이스의 규모 확장 : 다중화 또는 샤딩하여 규모 확장성 달성

 

* 가상 면접 사례로 배우는 대규모 시스템 설계 8장을 요약한 내용입니다.