8장. URL 단축기 설계

문제 이해 및 설계 범위

면접관에게 질문해서 파악한 설계 요구사항

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

 

개략적 설계안

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

API 엔드포인트

클라이언트는 서버가 제공하는 API 엔드포인트를 통해 통신하고, 엔트포인트는 REST API로 설계

 

아래 두 가지 API를 설계

1. URL단축용 엔드포인트
   • POST /api/v1/data/shorten
   • 인자: {longUrl: longURLstring}
   • 반환: 단축 URL
2. URL 리다이렉션용 엔드포인트
   • GET /api/v1/shortUrl
   • 반환: HTTP 리다이렉션 목적지가 될 URL

 

URL 리다이렉션

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

• 301 Permanently Moved
  => 서버 부하를 줄이고 싶을 때 사용
  - 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답
  - 영구적으로 이전 되었으므로, 브라우저는 응답을 캐시(cache)한다.
  - 추후 같은 단축 URL에 요청을 보낼 필요가 있을 때, 브라우저는 캐시된 원래 URL로 요청을 보내게 된다.
• 302 Found
  =>트래픽 분석이 중요할 때 사용
  - 해당 URL에 대한 HTTP 요청이 일시적으로 Location 헤더가 지정하는 URL에 의해 처리 되어야 한다.
  - 클라이언트의 요청은 단축 URL 서버에 먼저 보낸 후, 원래 URL로 리다이렉션 되어야 한다.

이미지 출처: https://donghyeon.dev/%EC%9D%B8%ED%94%84%EB%9D%BC/2022/04/06/URL-%EB%8B%A8%EC%B6%95%EA%B8%B0-%EC%84%A4%EA%B3%84/

URL 단축

긴 URL을 해시 값으로 대응시킬 해시 함수 fx를 찾아야 한다.

 

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

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

 

상세 설계

데이터 모델, 해시 함수, URL 단축 및 리다이렉션에 관해 설계

데이터 모델

• 해시 테이블에 모든 것을 두었는데, 유한하고 비싼 메모리를 사용하기 때문에 실제 시스템에서는 사용하기 곤란
• 더 나은 방법으로 <단축 URL, 원래 URL>의 순서쌍을 관계형 데이터베이스에 저장하는 것.
• url 데이터 테이블에 id(Primary Key), shortURL, logURL의 세 개 컬럼을 갖는다.

 

해시함수

해시 함수가 계산하는 단축 URL 값을 hashValue로 표현

 

해시 값 길이

• [0-9, a-z, A-Z]의 문자들로 구성된다.
• 10 + 26 + 26 = 62개
• 62^n >= 3650억 에서 n의 최소값을 찾아야 hashValue의 길이를 정할  수 있다.

해시 후 충돌 해소

• URL을 줄이려면 해시 함수가 필요
• 해시 함수는 CRC32, MD5, SHA-1 같은 해시 함수를 이용
• 시스템에서 요구하는 7자리보다 길어서 해결방법으로 계산된 해시 값에서 처음 7개만 사용한다.
  • 그러나, 해당 방법은 해시 결과가 충돌할 가능성이 있다.
  • DB에 단축 URL의 처음 7개 값이 있는지 확인.
    - 있을 경우, 정한 문자열을 해시값에 덧붙이고 충돌이 해소될 때까지 반복한다.
    - 없을 경우, DB에 저장

해시 후 충돌 해소를 적용한 URL 단축기

 

• 해당 방법을 사용하면 단축 URL을 생성할 때 한 번 이상 데이터베이스 질의를 해야한다.
• 데이터베이스 대신 블룸 필터를 사용하면 성능을 높일 수 있다,
• 블룸 필터는 어떤 집합에 특정 원소가 있는지 검사할 수 있도록 하는 확률론에 기초한 공간 효율이 좋은 기술.

 

 

base-62 변환

• 진법 변환 접근 방법
• 수의 표현 방식이 다른 시스템이 같은 수를 공유할 때 유용
• 62진법을 사용하는 이유는 hashValue에 사용할 수 있는 개수가 62개

 

10진법을 62진법으로 변환 방법

 

두 접근법의 차이점

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

 

URL 단축기 상세 설계

62진법 변환 기법을 사용해서 적용하는 순서.

base-62 방법을 적용한 URL단축기 다이어그램

 

예시)

• 입력된 URL: https://en.wikipedia.org/wiki/Systems_design (1번)
• 해당 URL에 대해 ID 생성기가 반환 ID는 2009215674938 (4번)
• 해당 ID를 62진수로 변환하면 zn9edcu (5번)

 

예시

URL 리다이렉션 상세 설계

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

 

마무리

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