[System Design Interview] 8장 URL 단축기 설계

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

시스템의 기본적 기능

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

개략적 추정

• 쓰기 연산: 1억/24/3600 = 초당 1160
• 읽기 연산: 비율이 10:1일 때, 초당 11,600
• 10년간 운영 시: 1억 x 365 * 10 = 3650억개의 레코드
• 저장 용량: URL의 평균 길이가 100이면 3650억 x 100바이트 = 36.5TB

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

API 엔드포인트

REST 스타일로 설계

1. URl 단축용 엔드포인트: 단축할 URL을 인자로 실어서 POST 요청
2. URL 디라이렉션용 엔드포인트: 단축 URL에 대해 HTTP 요청이 오면 원래 URL을 얻기 위해 해당 엔드포인트에 요청

URL 리다이렉션

단축 URL을 받은 서버는 해당 URL을 원래 URL로 바꾼 후, 3xx 응답의 Location 헤더에 넣어 반환

• 301 Permantetly Moved: 영구적으로 URL 이동되었다는 표시, 브라우저가 캐싱함 → 서버로 다시 응답을 보낼 필요 없음 → 서버 부하 줄이기 가능
• 302 Found: 일시적으로 URL 이동, 요청은 언제나 서버로 보내짐, 트래픽 분석이 중요하면 이 방법 사용

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

URL 단축 플로우

긴 URL → 해시 함수 → 짧은 URL

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

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

3단계 상세 설계

데이터 모델

해시 테이블은 메모리에 저장되기 때문에 실제 시스템에 쓰기에는 힘듬

id, 단축 URL, 원래 URL을 관계형 데이터베이스에 저장하는 방법이 나음

해시 함수

해시 값 길이

hashValue = 단축 URL 값 이라고 할 때,

[0-9, a-z, A-Z] 문자열을 사용 가능하므로, 사용할 수 있는 문자의 개수는 10+26+26 = 62개

hashValue의 길이 = 62^n ≥ 3650억인 n의 최솟값 ⇒ n = 7 (길이는 7)

해시 함수 구현

• 해시 후 충돌 해소: 함수 함수(CRC32, MD5, SHA-1) 등을 이용해서 축약한 후, 앞의 7자리만 가져옴, 이후 충돌나는 값은 충돌이 없어질때까지 사전에 정한 문자열을 해시값에 덧붙임
• base-62 변환: 10진수 값을 62진법을 사용해서 62진수로 변환, 축약하는 방법

URL 단축기 상세 설계

 

URL 단축기는 시스템의 핵심 컴포넌트이므로, 처리 흐름이 논리적으로는 단순해야 하고, 기능적으로 언제나 동작하는 상태여야 함

여기서는 62진법 변환 기법을 사용해 설계함

처리 흐름

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

분산 환경에서 ID를 생성하는 ID 생성기에 대한 내용은 7장 확인

URL 리다이렉션 생성 설계

 

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

동작 흐름

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

4단계 마무리

추가로 이야기하면 좋을 것들

• 처리율 제한 장치(rate limiter)
• 웹 서버의 규모 확장
• 데이터베이스의 규모 확장
• 데이터 분석 솔루션(analytics): 성공적인 비즈니스를 위해서는 데이터가 중요함. URL 단축기에 데이터 분석 솔루션을 통합해 두면 어떤 링크를 얼마나 많은 사용자가 클릭했는지, 언제 주로 클릭했는지 등 중요한 정보를 알아낼 수 있음
• 가용성, 데이터 일관성, 안정성

 

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

가상 면접 사례로 배우는 대규모 시스템 설계 기초 - YES24