8장 URL 단축기 설계

tinyurl같은 URL 단축 서비스를 설계하는 문제

총 4단계로 설계해볼 수 있다.

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

시스템 설계 면접 문제는 의도적으로 어떤 정해진 결말을 갖지 않도록 만들어진다. 따라서 면접장에서 시스템을 성공적으로 설계해 내려면 질문을 통해 모호함을 줄이고 요구사항을 알아내야 한다.

💡 설계 범위

• ❓ URL 단축기가 어떻게 동작하는지 물어보기
  💡 https://www.systeminterview.com/q=chatsystem 입력으로 주어졌다고 했을 때 이 서비스는 https://tinyurl.com/y7ke-ocwjdh 와 같은 단축 URL을 결과로 제공해야 한다. 이 URL에 접속하면 원래 URL로 갈 수 있어야 한다.
• ❓ 트래픽 규모가 어느 정도인지 물어보기
  💡 매일 1억개의 단축 URL을 만들어 낼 수 있어야 한다.
• ❓ 단축 URL의 길이는 어느 정도인지 물어보기
  💡 짧으면 짧을수록 좋다.
• ❓ 단축 URL에 포함될 문자에 제한이 있는지 물어보기
  💡 단축 URL에는 숫자와 영문자만 사용할 수 있다.
• ❓ 단축된 URL을 시스템에서 지우거나 갱신할 수 있는지 물어보기
  💡 시스템을 단순화하기 위해 삭제나 갱신은 할 수 없다.

URL 단축기의 기본적인 기능은…

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

위 요구사항의 개략적 추정

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

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

API 엔드포인트, URL 리다이렉션, URL 단축 플로우에 대해 살펴본다.

API 엔드포인트

REST API 형태로 설계하여 서버와 클라이언트가 통신하도록 설계한다.

1. URL 단축용 엔드포인트
   • 새 단축 URL을 생성하는 API
   • POST /api/v1/data/shorten
     • body: {longUrl: longURLstring}
   • 응답 : 단축 URL
2. URL 리다이렉션용 엔드포인트
   • 단축 URL에 대해서 HTTP 요청이 오면 원래 URL로 보내주기 위한 API
   • GET /api/v1/shortUrl
   • 응답 : HTTP 리다이렉션 목적지가 될 원래 URL

URL 리다이렉션

301 vs 302 ?

• 301 Permanently Moved
  • 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다.
  • 브라우저는 이 응답을 캐시한다
  • 서버 부하를 줄이는 것이 중요할 때 사용
• 302 Found
  • 해당 URL 요청이 일시적으로 Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답.
  • 언제나 단축 URL 서버에 먼저 보내진 후에 원래 URL로 리다이렉션 되어야 함.
  • 트래픽 분석이 중요할 때 사용

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

<단축 URL, 원래 URL> 형태로 저장

URL 리다이렉션 플로우

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

URL 단축

결국 중요한 것은 원래의 긴 URL을 해시 값으로 대응시킬 해시 함수를 찾는 것!

해당 함수는 아래와 같은 요구사항을 만족해야 함.

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

3단계) 상세 설계

데이터 모델

개략적 설계에서는 모든 것을 해시 테이블에 두었다

→ 메모리는 유한하고 비싸기 때문에 실제 시스템에 쓰기는 곤란하다.

💡 SOLUTION ⇒ <단축 URL, 원래 URL>의 순서쌍을 관계형 데이터베이스에 저장하는 것

해시 함수

원래 URL을 단축 URL로 변환하는 함수.

해시 함수가 계산하는 단축 URL 값을 hashValue라고 지칭

hashValue는 [0-9, a-z, A-Z]의 문자들로 구성. ⇒ 총 62개

62^n ≥ 3650억인 n의 최솟값을 찾아야 한다!
→ 이 시스템은 3650억 개의 URL을 생성해야 하고 ************단축 URL의 길이는 최대한 짧은것이 좋으므로 n의 최솟값을 구해보자

n의 최솟값은 7이 되므로 hashValue의 길이는 7이 되어야 한다.

해시 함수 구현에 쓰일 기술로는 해시 후 충돌 해소 방법과 base-62 방법이 있다.

✅ 해시 후 충돌 해소)

긴 URL을 줄이려면, 원래 URL을 7글자 문자열로 줄이는 해시 함수가 필요하다. 손쉬운 방법은 CRC32, MD5, SHA-1 같이 잘 알려진 해시 함수를 이용하는 것이다.

해시 함수	해시 결과 (16진수)
CRC32	5cb54054
MD5	5a62509a84df9ee03fe1230b9df8b84e
SHA-1	0eeae7916c06853901d9ccbefbfcaf4de56ed85b

❓ CRC32가 계산한 가장 짧은 해시값도 7보다는 길다.

💡 해시 값에서 처음 7개 글자만 사용한다

→ 해시 결과가 서로 충돌할 확률이 있음

실제로 충돌이 발생했을 때, 충돌이 해소될 때 까지 사전에 정한 문자열을 해시값에 덧붙인다

→ 한 번 이상 데이터베이스 질의를 해야 하므로 오버헤드가 크다.

(데이터베이스 대신 블룸 필터를 사용하면 성능을 높일 수 있다고 한다.)

✅ base-62 변환)

진법 변환은 URL 단축기를 구현할 때 흔히 사용되는 접근법

hashValue에 사용할 수 있는 문자가 62개이므로 62진법을 사용

• 62진법은 수를 표현하기 위해 총 62개의 문자를 사용하는 진법이다. 따라서 0은 0으로, 9는 9로, 10은 a로, 61은 Z로 대응시켜 표현하도록 할 것이다.
• 11157(10진수) = 2 x 62^2 + 55 x 62 ^1 + 59 x 62 ^ 0 = [2, 55, 59] => [2, T, X] => 2TX(62진수)이다.
• 따라서 단축 URL은 https://tinyurl.com/2TX가 된다.

두 접근법 비교

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

URL 단축기 상세 설계

처리 흐름 순서도

• 입력된 URL이 https://en.wikipedia.org/wiki/Systems_design이라고 하면
• 이 URL에 대해 ID 생성기가 반환한 ID는 2009215674938이다.
• 이 ID를 62진수로 변환하면 zn9edcu를 얻는다.

D	shortURL	longURL
2009215674938	zn9edcu	https://en.wikipedia.org/wiki/Systems_design

URL 리다이렉션 상세 설계

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

로드밸런서의 동작 흐름)

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

4단계) 마무리

설계를 마친 후 시간이 좀 남는다면 아래와 같은 것들을 추가로 생각해볼 수 있다.

• 처리율 제한 장치(rate limiter)
  • 지금까지 살펴본 시스템은 엄청난 양의 URL 단축 요청이 밀려들 경우 무력화될 수 있다는 잠재적 보안 결함을 갖고 있다. 처리율 제한 장치를 두면, IP 주소를 비롯한 필터링 규칙들을 이용해 요청을 걸러낼 수 있다.
• 웹 서버 규모 확장
  • 웹 계층은 무상태 계층이므로 웹 서버를 자유로이 증설하거나 삭제할 수 있다.
• 데이터베이스 규모 확장
  • 데이터베이스를 다중화하거나 샤딩하여 규모 확장성을 달성할 수 있다.
• 데이터 분석 솔루션
  • 성공적인 비즈니스를 위해서는 데이터가 중요하다. URL 단축기에 데이터 분석 솔루션을 통합해 두면 어떤 링크를 얼마나 많은 사용자가 클릭했는지, 언제 주로 클릭했는지 등 중요한 정보를 알아 낼 수 있을 것이다.
• 가용성, 데이터 일관성, 안정성
  • 대규모 시스템이 성공적으로 운영되기 위해서는 반드시 갖추어야 할 속성이다.