#08. URL 단축기 설계

8장. URL 단축기 설계

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

• 문제 이해
  • URL 단축기가 어떻게 동작해야하는지?
    → 단축 URL을 결과로 제공. 접속 시 원래 URL로 갈 수 있어야 함
  • 트래픽 규모는?
    → 매일 1억개의 단축 URL 생성 가능해야함
  • 단축 URL의 길이는?
    → 짧을 수록 좋음
  • 단축 URL에 포함될 문자 제한 여부?
    → 숫자, 영문자만 사용 가능
  • 단축된 URL을 시스템에서 지우거나 갱신 가능?
    → 시스템을 단순화하기 위해 삭제나 갱신은 할 수 없다고 가정
• 개략적 추정
  • 쓰기 연산: 매일 1억 개의 단축 URL 생성
    → 초당 쓰기 연산: 100milion/24/3600 = 1160
  • 읽기 연산
    • 읽기 연산, 쓰기 연산 비율이 10:1 이라고 했을 때,
    • 읽기 연산은 초당 11,600회
  • URL 단축 서비스를 10년간 운영하면
    • 1억 x 365 x 10 = 3650억개의 레코드 보관 필요
  • 축약 전 URL의 평균 길이 = 100
  • 10년 동안 필요한 저장 용량 = 3650억 x 100byte = 36.5TB

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

API 엔드포인트

• URL 단축용 엔드포인트
  • 새 단축 URL 생성
  • POST /api/v1/data/shorten
  • 인자: {longUrl: longURLstring}
  • 반환: 단축 URL
• URL 리디렉션용 엔드포인트
  • 단축 URL에 대해 HTTP 요청이 오면 원래 URL로 보내주기 위한 용도
  • GET /api/v1/shortUrl
  • 반환: HTTP 리디렉션 목적지가 될 원래 URL

URL 리디렉션

• 단축 URL 받은 서버는 원래 URL로 바꿔 301 응답의 Location 헤더에 넣어 반환
• 301 Permanently Moved
  • 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답
  • 영구적으로 이전.
  • 브라우저는 이 응답을 cache
  • 추후 같은 단축 URL에 요청을 보낼 때 브라우저는 캐시된 원래 URL로 요청을 보내게 됨
  • 서버 부하 감소
• 302 Found
  • 주어진 URL로의 요청이 일시적으로 Location 헤더가 지정하는 URL에 의해 처리되어야한다는 응답
  • 클라이언트 요청은 언제나 단축 URL 서버에 보내진 후 원래 URL로 리디렉션
  • 트래픽 분석이 중요할 때, 클릭 발생률이나 발생 위치 추적에 유리
• 리디렉션 구현 방법: 해시 테이블
  • <단축 URL, 원래 URL>

URL 단축

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

3. 3단계 상세 설계

데이터 모델

• 해시 테이블은 실제 시스템에 쓰기에는 곤란
  • 메모리 유한, 비쌈
• <단축 URL, 원래 URL> 순서쌍을 관계형DB에 저장하는 것!
  • id shortURL longURL

해시 함수

• 해시 함수
  • 원래 URL <-> 단축 URL 변환
  • 단축 URL: hashValue
• 해시 값 길이
  • [0-9, a-z, A-Z] 62개 문자 사용
  • 6*(2^n) >= 3650억
    → n의 최솟값 = 7
• 해시 후 충돌 해소
  • 7글자 문자열로 줄이는 해시 함수가 필요
    • ex. CRC32 MD5 SHA-1
  • 해시 함수값이 7글자보다 길다면? 어떻게 줄일 수 있을까?
    • 처음 7개 글자만 이용? 충돌 확률 ⬆️
  • 충돌 발생 시, 해소될 때까지 사전에 정한 문자열을 해시값에 덧붙임
    • 한 번 이상 질의 필요 → 오버헤드 ⬆️
  • DB 대신 블룸 필터 사용하면 성능 높일 수 있음
    • 블룸 필터: 어떤 집합에 특정 원소가 있는지 검사할 수 있도록 하는
    • 확률론에 기초한 공간 효율이 좋은 기술
• base-62 변환
  • 진법 변환(base conversion): 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하여야 하는 경우에 유용
  • 왜 62진법?
    • hashValue에 사용할 수 있는 문자 개수가 62개
    • 11157(10) = 262^2 + 5562^1 + 59*62^0 = [2, 55, 59] = [2, T, X] = 2TX(62)
• 두 접근법 비교
  • 해시 후 충돌 해소 전략
    • 단축 URL의 길이가 고정
    • 유일성이 보장되는 ID 생성기가 필요 X
    • 충돌이 가능해서 해소 전략 필요
    • ID로부터 단축 URL을 계산하는 방식이 아니라서 다음에 쓸 수 있는 URL을 알아내는 것이 불가능
  • base-62 변환
    • 단축 URL의 길이가 가변적 → ID값 커지면 같이 길어짐
    • 유일성 보장 ID 생성기 필요
    • ID의 유일성이 보장된 후에야 적용 가능한 전략이라 충돌 아예 불가능
    • ID가 1씩 증가하는 값이라고 가정하면 다음에 쓸 수 있는 단축 URL이 무엇인지 쉽게 알아낼 수 있어서 보안상 문제가 될 소지 있음

URL 단축기 상세 설계

• URL 단축기
  1. 입력: longURL
  2. DB에 입력된 URL이 있는지 검사
     2-1. 있다면, 단축 URL 반환
     2-2. 없다면, 3번으로
  3. 유일한 ID를 생성 → DB의 기본키로 사용
  4. 62진법 변환 적용 → ID를 단축 URL로 변환
  5. ID, 단축 URL, 원래 URL로 새 DB 레코드 만든 후 단축 URL을 클라이언트에 전달
• ID 생성기
  • 단축 URL을 만들 때 사용할 ID를 만드는 용도
  • 전역적 유일성 globally unique 보장
  • 고도로 분산된 환경에서는 이런 생성기를 만드는 것이 무척 어려움

URL 리디렉션 상세 설계

• redirection 메커니즘
  1. 사용자 → 로드밸런서 : GET https://.. 사용자가 단축 URL 클릭
  2. 로드밸런서 → 웹서버
  3. 웹서버 → 캐시 : 단축 URL이 이미 캐시에 있는 경우
  4. 웹서버 → 데이터베이스 : 캐시에 없다면, 꺼내서 캐시에 저장
  5. 로드밸런서 → 사용자 : 원래 URL 반환
• 쓰기보다 읽기를 자주하는 시스템
• <단축 URL, 원래 URL> 의 쌍을 캐시에 저장

4. 4단계 마무리

더 보면 좋은 것.

• 처리율 제한 장치 rate limiter
  • 엄청난 양의 URL 단축 요청이 밀려들 경우 무력화될 수 있음
  • IP 주소를 비롯한 필터링 규칙들을 이용해 요청을 걸러낼 수 있을 것임
• 웹 서버의 규모 확장
  • 웹 서버를 자유로이 증설 및 삭제 가능
  • 웹 계층이 stateless 계층이니까
• 데이터베이스의 규모 확장
  • 데이터베이스 다중화, sharding
• 데이터 분석 솔루션
  • 어떤 링크를 얼마나 많은 사용자가 클릭했는지, 언제 주로 클릭했는지 등
• 가용성, 데이터 일관성, 안정성