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

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

• 시스템 설계 면접 문제는 의도적으로 어떤 정해진 결말을 갖지 않도록 만들어 진다. 따라서 면접장에서 시스템을 성공적으로 설계해 내려면 질문을 통해 모호함을 줄이고 요구사항을 알아내야 한다.
• URL 단축기 시스템 기능
  • URL 단축 : 주어진 긴 URL을 훨씬 짧게 줄인다.
  • URL 리디렉션 : 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내
  • 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨

개략적 추정

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

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

API 엔드포인트

URL 단축키는 두 개의 엔드포인트를 필요로 한다.

1. URL 단축용 엔드포인트 : 새 단축 URL을 생성하고자 하는 클라이언트는 이 엔드포인트에 단추갈 URL을 인자로 실어서 POST 요청을 보내야 한다.
   1. URI : POST /api/v1/data/shorten
      1. 인자 : {longUrl : longURLstring}
      2. 반환 : 단축 URL
   2. URL 디리렉션용 엔드포인트 : 단축 URL에 대해서 HTTP 요청이 오면 원래 URL로 보내주기 우한 용도의 엔드포인트
      1. URI : GET /api/v1/shortUrl
         1. 반환 : HTTP 리디렉션 목적지가 될 원래 URL

URL 리디렉션

단축 URLㅇㄹ 받은 서버는 그 URL을 원래 URL로 바꾸어서 301 응답의 Location 헤더에 넣어 반환한다.

• 301과 302 응답 차이점
  • 301 permanently moved : 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답이다. 영구적으로 이전되었으므로, 브라우저는 이 응답을 캐시한다.
  • 302 found : 주어진 URL로의 요청이 "일시적으로" Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답이다. 따라서 클라이언트의 요청은 언제나 단축 URL 서버에 먼저 보내진 후에 원래 URL로 리디렉션 되어야 한다.
• 301응답과 302 응답의 사용법
  • 서버 부하를 줄이는 것이 중요하다면 301을 사용하는 것이 좋다.
  • 트래픽 분석이 중요할 때는 302를 쓰는 쪽이 클릭 발생률이나 발생 위치를 추적하는 데 좀 더 유리할 것이다.

URL 단축

단축 URL을 만들때 가장 중요한 것은 긴 URL을 해시 값으로 대응시킬 해시 함수 fx를 찾는 것이다.

이 해시 함수는 아래 요구사항을 만족해야 한다.

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

3단계 상세 설계

데이터 모델

• 개략적 설계를 진행할 때는 해시 테이블을 사용했었다.
  • 이 전략은 메모리가 유한한데가 비싸기 때문에 실제 시스템에서는 사용하기 곤란하다.
• <단축 URL, 원래 URL> 순서쌍을 관계형 데이터베이스에 저장하는 것이다.

해시 함수

해시 함수 : 원래 URL을 단축 URL로 반환하는 데 사용된다.

• 해시 값 길이 : hashValue는 [0-9,a-z,A-Z]의 문자들로 구성된다.
  • hashValue의 길이를 정하기 위해서는 3650억인 n의 최솟값을 찾아야 한다.

• n = 7이면 3.5조 개의 URL을 만들 수 있으므로 요구사항을 만족시킬 수 있다.
• 해시 함수 구현일 쓰일 기술로는 1) 해시 충돌 해소 2) base-62 변환 이 있다.
• 해시 후 충돌 해소
  • 가장 손쉬운 해시 함수인 CRC32, MD5, SHA-1을 이요한다.
  • 하지만 가장 짧은 해시값조차도 길이가 7이 넘어버린다.
  • 이를 해결하기 위해 계산된 해시 값에서 처음 7개 글자만 이요한다.
  • 하지만 이렇게 하면 해시 결과가 서로 충돌할 확률이 높아진다.
  • 충돌이 발생했을 때는, 충돌이 해소될 때까지 사전에 정한 문자열을 해시값에 덧붙인다. 아래 figure 8-5의 절차로 이루어진다.
  • 이 방법을 쓰면 단축 URL을 생성할 때 한 번 이상 데이터베이스 질의를 해야 하므로 오버헤드가 크다.
  • 데이터베이스 대신 블룸 필터를 사용하면 성능을 높일 수 있다.
    • 블룸 필터 : 어떤 집합에 특정 원소가 있는지 검사할 수 있도록 하는, 확률룐에 기초한 공간 효율이 좋은 기술.

• base-62 변환
  • 진법 변환은 URL 단축기를 구현할 때 흔히 사용되는 접근법 중 하나다.
  • 62진법을 쓰는 이유는 hashValue에 사용할 수 있는 문자 개수가 62개이기 때문이다.
  • 10진수로 11157을 62진수로 변환하는 절차

• 두 접근법 비교

URL 단축기 상세 설계

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

• ID 생성기 : 단축 URL을 만들 때 사용할 ID를 만드는 것이고, 이 ID는 전역적 유일성이 보장되는 것이어야 한다.

URL 리디렉션 상세 설계

firue 8-8은 URL 리디렉션 메커니즘의 상세한 설계이다. 쓰기보다 읽기를 더 자주 하는 시스테밍라, <단축 URL, 원래 URL> 쌍을 캐시에 저장하여 성능을 높였다.

로드밸런서의 동작 흐름은 아래와 같다.

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