서론
tinyurl 같은 URL 단축기를 설계하는 문제에 대해 알아보자

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

설계해야 할 시스템의 기본적 기능
1. URL 단축: 주어진 긴 URL을 훨씬 짧게 줄임
2. URL 리디렉션(redirection): 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내
3. 높은 가용성과 규모 확장성, 장애 감내

개략적 추정

• 쓰기 연산: 매일 1억 개의 단축 URL 생성
• 초당 쓰기 연산 = 1160
• 읽기 연산: 읽기와 쓰기 연산 비율을 10:1이라 했을 대 초당 11,600회 발생
• URL 단축 서비스를 10년간 운영한다고 가정하면 3650억 개의 레코드 보관 필요
• 축약 전 URL 평균 길이는 100이라고 가정
• 10년 동안 필요한 저장 용량은 36.5TB

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

API 엔드포인트, URL 리디렉션, URL 단축 플로에 대해 알아보자

API 엔드포인트

클라이언트는 서버가 제공하는 API 엔드포인트를 통해 서버와 통신함
REST 스타일로 설계, URL 단축기는 기본적으로 두 개의 엔드포인트를 필요로 함

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 Permanently Moved
  - 해당 URL에 대한 HTTP 요청 처리의 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답
  - 영구적으로 이전되었으므로 브라우저는 이 응답을 캐시함
  - 따라서 추후 같은 단축 URL에 요청을 보낼 필요가 있을 때 브라우저는 캐시된 원래 URL로 요청을 보내게 됨
  - 서버 부하를 줄일 때 Good <- 첫 번째 요청만 단축 URL 서버로 전송되기 때문에
  302 Found
  - 주어진 URL로의 요청이 일시적으로 Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답
  - 따라서 클라이언트의 요청은 언제나 단축 URL 서버에 먼저 보내진 후 원래 URL로 리디렉션되어야 함
  - 트래픽 분석이 중요할 때 Good <- 클릭 발생률이나 발생 위치를 추적할 때 유리함
• URL 리디렉션을 구현하는 가장 직관적인 방법은 해시 테이블을 사용하는 것
• 해시 테이블에 < 단축 URL, 원래 URL> 쌍을 저장한다고 가정하면 아래처럼 구현 가능

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

URL 단축

• 단축 URL이 www.tinyurl.com/{hashValue} 형태라고 가정
• 중요한 것은 긴 URL을 이 해시 값으로 대응시킬 함수 fx를 찾는 것
  해시 함수 요구 사항
• 입력으로 주어지는 긴 URL이 다른 값이면 해시 값도 달라야 함
• 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야 함

3단계 상세 설계

데이터 모델, 해시 함수, URL 단축 및 리디렉션에 대해 구체적으로 설계안을 만들어 보자

데이터 모델

• 실제 시스템에서는 <단축 URL, 원래 URL> 순서쌍을 관계형 데이터베이스에 저장하는 게 좋음
• 중요 칼럼만 추린 테이블: id, shortURL, longURL 세 개의 칼럼을 가짐
  

해시 함수

• 원래 URL -> 단축 URL 변환할 때 쓰임
• 편의상 해시 함수가 계산하는 단축 URL 값을 hashValue라 하자

해시 값 길이

hashValue

• [0-9, a-z, A-Z] 문자로 구성되어 사용할 수 있는 문자의 개수는 62개
• hashValue의 길이를 정하기 위해서는 3650억인 n의 최소값을 찾아야 하며, 개략적으로 계산한 추정치를 따르면 이 시스템은 3650억 개의 URL을 만들어 낼 수 있어야 함

해시 함수 구현에 쓰일 기술

• 해시 후 충돌 해소
• base-62 변환

해시 후 충돌 해소

긴 URL을 줄일 때 원래 URL을 7글자 문자열로 줄이는 해시 함수가 필요함
-> CRC32, MD5, SHA-1처럼 잘 알려진 해시 함수를 이용하는 게 쉬운 방법
=> 근데 해시 함수로 계산한 가장 짧은 해시값도 7보다 길 때 어떻게 더 줄일 수 있을까?

계산된 해시 값에서 처음 7개 문자만 이용하는 방법

• 해시 결과가 서로 충돌할 확률이 높아짐 => 실제로 발생하면 해소될 때까지 사전에 정한 문자열을 해시값에 덧붙임
  
• 충돌은 해소할 수 있지만 단축 URL을 생성할 때 한 번 이상 데이터베이스 질의를 해야 해서 오버헤드가 큼
• 데이터베이스 대신 블룸 필터를 사용하면 성능 높일 수 있음

base-62 변환

진법 변환(base conversion)

• URL 단축기를 구현할 때 흔히 사용되는 접근법 중 하나
• 수의 표현 방식이 다른 두 시스템이 같은 수를 공유해야 할 경우에 유용
• 62진법을 쓰는 이유는 hashValue에 사용할 수 있는 문자 개수가 62개이기 때문

두 접근법 비교

해시 후 충돌 해소 전략	base-62 변환
단축 URL 길이가 고정됨	단축 URL 길이가 가변적, ID 값이 커지면 같이 길어짐
유일성이 보장되는 ID 생성기 필요치 않음	유일성 보장 ID 생성기 필요
충돌 가능해서 해소 전략 필요	ID 유일성이 보장된 후에 적용 가능한 전략이라 충돌 불가
ID로부터 단축 URL을 계산하는 방식이 아니라 다음에 쓸 수 있는 URL 알아내기 불가능	ID가 1씩 증가하는 값이라고 가정하면 다음에 쓸 수 있는 단축 URL이 무엇인지 쉽게 알아낼 수 있어 보안상 문제 될 소지 있음

URL 단축기 상세 설계

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

ID 생성기

• 목적: 단축 URL을 만들 때 사용할 ID 만들기
• ID는 전역적 유일성 보장되어야 함
• 고도로 분산된 환경에서 이런 생성기 만드는 건 어려운데 7장 기법을 사용해서 만들 수 있음

URL 리디렉션 상세 설계

• 쓰기보다 읽기를 더 자주 하는 시스템이러 <단축 URL, 원래 URL> 쌍을 캐시에 저장하여 성능을 높임
  
  로드밸런서 동작 흐름

1. 사용자가 단축 URL 클릭
2. 로드밸런서가 해당 클릭으로 발생한 요청을 웹 서버에 전달
3. 단축 URL이 이미 캐시에 있는 경우 원래 URL을 바로 꺼내서 클라이언트에게 전달
4. 캐시에 해당 단축 URL이 없는 경우 DB에서 꺼냄
5. DB에서 꺼낸 URL을 캐시에 넣고 사용자에게 반환

4단계 마무리

추가 논의 사항

• 처리율 제한 장치
• 웹 서버의 규모 확장
• 데이터베이스의 규모 확장
• 데이터 분석 솔루션
• 가용성, 데이터 일관성, 안정성