8장 URL 단축기 설계

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

URL  단축기 설계

 

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

• 질문 : URL 단축기가 어떻게 동작해야 하는지 예제를 보여주실 수 있나요?
• 답변 : https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long이 입력이 주어질 경우
           이 서비스는 https://tinyurl.com/y7ke-ocwj와 같은 단축 URL을 결과로 제공해야하며, 단축 URL로 접속하여도 원래 URL로 갈 수 있어야 합니다.
• 질문 : 트래픽 규모는 어느 정도 인가요?
• 답변 : 매일 1억(100million) 개의 단축 URL을 만들어 낼 수 있어야 합니다.
• 질문 : 단축 URL의 길이는 어느 정도여야 하나요?
• 답변 : 짧을수록 좋습니다.
• 질문 : 단축 URL에 포함될 문자에 제한이 있나요?
• 답변 : 단축 URL에 숫자(0~9)와 영문자(a~z, A~Z)만 사용이 가능합니다.
• 질문 : 단축된 URL을 시스템에서 지우거나 갱신할 수 있나요?
• 답변 : 시스템을 단순화하기 위해 삭제나 갱신은 할 수 없다고 가정합니다.

 

기능 정리

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

 

개략적 추정

• 쓰기 연산 : 매일 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 엔드포인트

1. URL 단축용 엔드포인트 
   • POST /api/v1/data/shorten
   • 인자 : longUrl : String
   • 반환 : 단축 URL
2. URL 디리렉션용 엔드포인트
   • GET /api/v1/shortUrl
   • 반환 : HTTP 리디렉션 목적지가 될 원래 URL

 

URL 리디렉션

• 단축 URL을 브라우저에 요청할 경우 HTTP 상태 코드는 301
• 응답 헤더에 Location 원본 URL 포함하여 반환

클라이언트-서버간 통신 절차

 

301과 302 차이

• 301 Permanently Moved
  • 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답
  • 브라우저가 캐시하여 추후에 똑같은 단축 URL로 올 경우 원본 URL로 방문
  • 장점
    • 서버 부하를 줄여줌
• 302 Found
  • 일시적인 Location 헤더에 지정한 URL에 의해 처리한다는 응답
  • 항상 단축 URL 서버를 거쳐 원래 URL로 방문
  • 장점
    • 트래픽 분석이 중요할 경우 필요, 클릭 발생률이나 발생 위치 추적에 유리함

URL구현 방법

• URL 리디렉션을 구현하는 가장 직관적인 방법은 해시 테이블
• <단축 URL, 원래 URL> 쌍으로 저장
• 원래 URL = hashTable.get(단축 URL)
• 301 or 302 응답 Location 헤더에 원래 URL 넣고 전송

 

URL 단축

• www.tinyurl.com/{hashvalue} 형태
• 긴 URL을 해시 값으로 대응 시킬 해시 함수를 찾는게 중료

 

해시 함수 요구사항

• 입력으로 주어지는 긴 URL은 다른값이면 해시값도 달라야함
• 해시값은 원래 값으로 복원이 가능해야함.

 

3단계 상세 설계

데이터 모델

• 메모리는 유한하고 비싸므로, <단축 URL, 원래 URL>의 순서쌍을 RDB에 저장
• id, shortURL, longURL 3개 칼럼으로 구성

 

해시 값 길이

• 해시값은 [0-9, a-z, A-Z]로 구성이 되어야 함
• 사용할 수 있는 문자 개수는 10+26+26 = 62개
• 62^n >= 3650억인 n의 최솟값을 찾아야 함
• n = 7이면 대략 3.5조개의 URL 생성 가능

 

해시 후 충돌 해소

해시 함수	해시 결과(16진수)
CRC32	5cb54054
MD5	ac8b3b54df4124a34387d7e8da8f3838
SHA-1	8778e88b64149974b0806e7d12644e641f9f8ea7

• https://en.wikipedia.org/wiki/Systems_design을 해시 함수 결과
• 해시 함수 종류 및 결과
• CRC32를 사용해도 7보다 길다.
• 해결 방법
  • 맨 처음 7글자만 사용하는 방법
    • 충돌할 확률이 높음
    • 충돌을 해결할때까지 DB 질의하여 있는지 조회
    • 있을 경우
      • 사전에 정한 문자열을 해시값에 붙이기
    • 없을 경우 종료
    • 단점
      • 단축 URL을 생성할 때 마다 한번 이상 DB에 질의해야 하므로 오버헤드가 큼
      • DB 대신 블룸 필터를 사용하면 성능을 높일 수 있다.

 

 base-62 변환

• 진법 변환(base conversion)은 URL 단축기를 구현할 때 흔히 사용되는 접근법
• 62 진법인 경우는 hashvalue에 사용할 수 있는 문자 개수는 62개
• 예
  • 11157을 62진수로 변환
  • 0은 0, 9는 9, 10은 a, 61은 Z
  • 11157 = 2 * 62^2 + 55 * 62 + 59 * 62^0 = [2, 55, 59] => [2, T, X] => 2TX
  • 단축 URL은 https://tinyrul.com/2TX

 

두 접근법 비교

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

 

URL 단축기 상세 설계

 

1. 입력으로 긴 URL을 받는다.
2. DB에 해당 URL이 있는지 확인
3. DB에 있다면 찾은 URL 클라이언트에 반환
4. 없을 경우 유일한 ID를 생성, ID는 데이터베이스의 기본 키로 사용(ID 생성기는 전역적 유일성이 보장되어야함)
5. 62진법 변환을 적용, ID를 단축 URL로 만들기
6. ID, 단축 URL, 원래 URl로 DB에 저장 후 단축 URL을 클라이언트에게 반환

 

URL 라디렉션 상세 설계

• 쓰기보다 읽기를 더 자주하는 연산이므로 캐시를 사용
• 동작 흐름
  1. 사용자가 단축 URL을 클릭
  2. 로드밸랜서가 해당 클릭으로 발생한 요청을 웹 서버에 전달
  3. 단축 URL이 캐시에 있을 경우 바로 반환
  4. 캐시에 없을 경우 DB 조회 후 사용자에게 반환
  5. DB 없을 경우 사용자가 잘못 입력

 

4단계 마무리

• 처리율 제한 장치
  
  • 엄청난 양의 URL 단축 요청이 밀려들 경우 무력화될 수 있으므로 처리율 제한 장치를 두자
• 웹 서버의 규모 확장
  • 웹 계층은 무상태 계층이므로 웹 서버를 자유로이 증설 및 삭제 가능
• 데이터베이스 규모 확장
  • 데이터베이스를 다중화하거나 샤딩하여 규모 확장성을 달성할 수있음
• 데이터 분석 솔루션
  • 어떤 링크를 얼마나 많은 사용자가 클릭했는지, 언제 주로 클릭했는지 중요한 정보를 알아 낼 수 있음
• 가용성, 데이터 일관성, 안정성
  • 대규모 시스템이 성공적으로 운영되기 위해 반드시 갖춰야하는 속성