8장. URL 단축기 설계

• 이번 장에서는 재미있으면서도 고전적인 시스템 설계 문제 가운데 하나인,
  tinyURL 같은 URL 단축기를 설계하는 문제를 풀어보도록 하겠다.

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

지원자 👩🏻‍💼 : URL 단축키가 어떻게 동작해야 하는지 예제를 보여주실 수 있을까요?

면접관 👨🏻‍💻: https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long
이 입력으로 주어졌다고 해 봅시다. 이 서비스는 https://tinyurl.com/y7ke-ocwj 같은 단축 URL을 결과로 제공해야 합니다. 이 URL에 접속하면 원래 URL로 갈 수도 있어야 합니다.

지원자 👩🏻‍💼 : 트래픽 규모는 어느 정도일까요?

면접관 👨🏻‍💻: 매일 1억개의 단축 URL을 만들어 낼 수 있어야 합니다.

지원자 👩🏻‍💼 : 단축 URL의 길이는 어느 정도여야 하나요?

면접관 👨🏻‍💻: 짧으면 짧을수록 좋습니다.

지원자 👩🏻‍💼 : 단축 URL 에 포함될 문자에 제한이 있나요?

면접관 👨🏻‍💻: 단축 URL에는 숫자(0-9)와 영문자(a-z,A-Z) 만 사용할 수 있습니다.

지원자 👩🏻‍💼 : 단축된 URL을 시스템에서 지우거나 갱신할 수 있습니까?

면접관 👨🏻‍💻: 시스템을 단순화하기 위해 삭제나 갱신은 할 수 없다고 가정합시다

시스템 기본적 기능 정리

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

개략적 추정

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

⭐️ 계산이 끝나면 결과를 면접관과 점검하여 합의한 후 진행하도록 하자.

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

• 이번 절에서 API 엔드포인트(endpoint), URL 리디렉션, 그리고 URL 단축 플로우에 대해 살펴보겠다.

API 엔드포인트

• 클라이언트는 서버가 제공하는 API 엔드포인트를 통해 서버와 통신한다.
• 우리는 이 엔드포인트를 REST 스타일로 설계할 것이다.
• URL 단축기는 기본적으로 2개의 엔드포인트를 필요로 한다.

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

URL 리디렉션

• 브라우저에 단축URL을 입력했을 때

  • Request
    • Request URL: https://tinyurl.com/qtj4opu
    • Status Code: 301
  • Response
    • location: https://www.amazon.com/dp/B017VDASDFSF?pLink=63eaef76-979c-43&ref=aabldf13dfasdlf_d2_3_sif

• 단축 URL을 받은 서버는 그 URL을 원래 URL로 바꾸어서 301 응답의 Location 헤더에 넣어 반환한다.
• 여기서 유의할 것은 301, 302 응답의 차이다. 둘 다 리디렉션 응답이긴 하지만, 차이가 있다.
  • 301 Permanently Moved : 이 응답은 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답이다. 영구적으로 이전되었으므로, 브라우저는 이 응답을 캐시한다. 따라서 이후 같은 단축 URL에 요청을 보냈을 때 브라우저는 캐시된 원래 URL로 요청을 보내게 된다.
  • 302 Found : 이 응답은 주어진 URL로의 요청이 '일시적으로' Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답이다. 따라서 클라이언트의 요청은 언제나 단축 URL 서버에 먼저 보내진 후 원래 URL로 리디렉션 되어야 한다.
• 이 두 방법은 각기 다른 장단점을 갖고 있다.
  • 서버 부하를 줄이는 것이 중요하다면 → 301
  • 하지만, 트래픽 분석이 중요하다면→ 302를 쓰는 쪽이 클릭 발생률이나 발생 위치를 추적하는 데 좀 더 유리할 것이다.
• URL 리디렉션을 구현하는 가장 직관적인 방법은 "해시 테이블"을 사용하는 것이다.✅
• 해시 테이블에 <단축URL, 원래 URL> 의 쌍을 저장한다고 가정한다면,
  URL 리디렉션은 다음과 같이 구현될 수 있을 것이다.
  • 원래 URL = hashTable.get(단축 URL)
  • 301 또는 302 응답 Location 헤더에 원래 URL을 넣은 후 전송

URL 단축

• 단축 URL이 www.tinyurl.com/{hashValue} 같은 형태라고 해보자.
• 결국 중요한 것은 긴 URL을 이 해시 값으로 대응시킬 해시 함수 fx를 찾는 일이 될 것이다.
• 이 해시 함수는 다음 요구사항을 만족해야 한다.
  • 입력으로 주어진 긴 URL이 다른 값이면 해시 값도 달라야 한다.
  • 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야 한다.

3단계: 상세 설계

• 지금까지 URL을 단축하는 방법, 리디렉션 처리에 관계된 개략적 설계안을 살펴보았다.
• 이번 절에서는 데이터 모델, 해시 함수, URL 단축 및 리디렉션에 관한 보다 구체적인 설계안을 만들어 보겠다.

데이터 모델

• 개략적 설계를 진행할 땐 모든 것을 해시 테이블에 두었다.
  이 접근법은 초기 전략으로는 괜찮으나, 실제 시스템에 쓰기엔 곤란한데, 메모리는 유한한 데다 비싸기 때문이다.
• 더 나은 방법은 <단축URL, 원래URL> 순서쌍을 관계형 데이터베이스에 저장하는 것이다.
• 테이블의 간단한 설계를 한다면 아래와 같다. (더 많은 컬럼을 가질 수 있지만 중요한 컬럼만 추렸다)

CREATE TABLE url (
    id BIGINT AUTO_INCREMENT PRIMARY KEY,
    shortURL VARCHAR(255) NOT NULL,
    longURL TEXT NOT NULL,
    created TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

해시 함수

• 해시 함수는 원래 URL을 단축 URL로 변환하는 데 쓰인다.
• 편의 상 해시 함수가 계산하는 단축 URL을 hashValue라고 지칭하겠다.

해시 값 길이

• hashValue는 0-9,a-z,A-Z 문자들로 구성된다.
• 따라서 사용할 수 있는 문자의 갯수는 62개다.
• hashValue 길이를 정확히 하기 위해서는 62^n >= 3650억인 n의 최소값을 찾아야 한다.
• 개략적으로 계산했던 추정치에 따르면 이 시스템은 3650억개의 URL을 만들어 낼 수 있어야 한다.
  • n=1 → 62
  • n=2 → 3,844
  • n=3 → 2383,328
  • ...
  • n=6 → 568억
  • n=7 → 3.5조
• 따라서 hashValue 길이는 7로 하도록 하겠다.
• 해시 함수 구현에 쓰일 기술로 두가지 기술을 살펴볼 건데,
  하나는 '해시 후 충돌 해소' 방법이고, 또 하나는 'Base-62 변환' 법이다.

해시 후 충돌 해소

• 긴 URL을 줄이려면, 원래 URL을 7글자 문자열로 줄이는 해시 함수가 필요하다.
• 손쉬운 방법은 CRC32, MD5, SHA-1 같이 잘 알려진 해시 함수를 이용하는 것이다.
• 하지만, CRC32가 계산한 가장 짧은 해시값조차도 7보다는 긴데 어떻게 하면 줄일 수 있을까?

해시값 길이 줄이기

1. 계산된 해시 값에서 처음 7개 글자만 이용한다.

• 이렇게 하면 해시 결과가 서로 충돌할 확률이 높아진다.
• 충돌이 실제로 발생했을 땐, 충돌이 해소될 때까지 사전에 정한 문자열을 해시값에 덧붙인다.
• 이 방법을 쓰면 충돌은 해소할 수 있으나, 단축 URL을 생성할 때 한번 이상 데이터베이스를 질의해야 하므로 오버헤드가 크다.
• 데이터베이스 대신 블룸 필터를 사용하면 성능을 높일 수 있다.
• 블룸 필터는 어떤 집합에 특정 원소가 있는지 검사할 수 있도록 하는, 확률론에 기초한 공간 효율이 좋은 기술이다.

2. base-62 변환 (진법 변환)

• 진법 변환은 URL 단축기를 구현할 때 흔히 사용되는 접근법 중 하나다.
• 이 기법은 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하여야 하는 경우 유용하다.
• 62진법을 쓰는 이유는 hashValue에 사용할 수 있는 문자 개수가 62개기 때문이다.
• 그러면 지금부터 base-62 변환이 어떻게 이루어지는지 살펴보자.

62진법 변환 예제 : 11157(10진수)를 62진수로 나타내기

• 62진법은 수를 표현하기 위해 총 62개 문자를 사용하는 진법이다.
• 따라서 0은 0으로, 9는 9로, 10은 a로, ... 36은 A로, 61은 Z로 대응시켜 표현하도록 할 것이다.
• 따라서 62진법에서 'a'는 1010을 나타내고, 'Z'는 6110을 나타낸다.
• 11157 (10진수) = 2x62^2 + 55x62^1 + 59x62^0 = [2, 55, 59] → 2TX (62진수) 이다.
• 따라서, 이 경우엔 https://tinyurl.com/2TX 가 된다.

두 접근법 비교

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

URL 단축키 상세 설계

• URL 단축키는 시스템의 핵심 컴포넌트이므로, 그 처리 흐름이 논리적으로는 단순해야 하고 기능적으로는 언제나 동작하는 상태로 유지되어야 한다.
• 본 예제에서는 "62진법 변환 기법"을 사용해서 설계할 것이다.

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

예시

• 입력된 URL : https://en.wikipedia.org/wiki/Systems_design
• 이 URL에 대해 ID 생성기가 반환한 ID는 20009215674938
• 이 ID를 62진수로 변환하여 zn9edcu 를 얻음
• 데이터베이스 레코드를 생성
  • ID : 20009215674938
  • shortURL : zn9edcu
  • longURL : https://en.wikipedia.org/wiki/Systems_design

유일 ID 생성기

• 이 ID 생성기의 주된 용도는, 단축 URL을 만들 때 사용할 ID를 만드는 것이고, 이 ID는 전역적 유일성이 보장되는 것이어야 한다.
• 고도로 분산된 환경에서 이런 생성기를 만드는 것은 무척 어려운 일이다.

URL 리디렉션 상세 설계

• 쓰기보다 읽기를 더 자주하는 시스템이므로, <단축URL, 원래URL> 쌍을 캐시에 저장해서 성능을 높였다.
• 로드밸런서의 동작 흐름
  1. 사용자가 단축 URL을 클릭한다.
  2. 로드밸런서가 해당 클릭으로 발생한 요청을 웹 서버에 전달한다.
  3. 단축 URL이 이미 캐시에 있는 경우엔 원래 URL을 바로 꺼내서 클라이언트에 전달한다.
  4. 캐시에 해당 단축 URL이 없는 경우, 데이터베이스에서 꺼낸다.
     데이터베이스에 없다면 아마 사용자가 잘못된 단축 URL을 입력한 경우일 것이다.
  5. 데이터베이스에서 꺼낸 URL을 캐시에 넣은 후 사용자에게 반환한다.

4단계: 마무리

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

---

25.02.12
25.03.02