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

• Q. URL 단축기 동작 예시
  • A. https://tinyurl.com/y7ke-ocwj
• Q. 트래픽 규모는?
  • A. 매일 1억개의 단축 URL 생성
• Q. 단축 URL의 길이는?
  • A. 짧을수록 좋음
• Q. 단축 URL에 포함될 문자제한은?
  • A. 숫자(0~9), 영문자(A~z) 사용 가능
• Q. 단축된 URL을 지우거나 갱신 가능?
  • A. 시스템 단순화를 위해 삭제나 갱신은 할 수 없다 가정

이 시스템의 기본적 기능은 아래와 같다.

• 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
  • 필요한 저장 용량은 3650억 * 100바이트 = 36.5TB

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

API 엔드포인트

클라이언트는 서버가 제공하는 API 엔드포인트를 통해 서버와 통신한다.

RESTful API로 설계한다고 가정하면, 기본적으로 두 개의 엔드포인트를 필요로 한다.

1. URL 단축용 엔드포인트
   • 새 단축 URL을 생성하고자 하는 클라이언트는 이 엔드포인트에 단축할 URL을 인자로 담아 POST 요청을 보내야한다.

   • 1	POST /api/v1/data/shorten

   • 인자: {longUrl: longURLstring}
   • 반환: 단축 URL
2. URL 리디렉션용 엔드포인트
   • 단축 URL에 대해 HTTP 요청이 오면 원래 URL로 보내주기 위한 용도의 엔드포인트

   • 1	GET /api/v1/shortUrl

   • 반환: HTTP 리디렉션 목적지가 될 원래 URL

URL 리디렉션

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

유의할 점은 301 응답과 302 응답의 차이로, 둘 다 리디렉션 응답이지만 차이가 있다.

• 301 Permanently Moved
  • URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전됨
  • 영구적인 이전이므로 브라우저는 이 응답을 캐싱한다.
  • 따라서 같은 단축 URL로 재요청시 캐시된 원래 URL로 요청을 보낸다.
  • 서버 부하를 줄이는 것이 중요할 때 사용될 수 있음
• 302 Found
  • URL로의 요청이 일시적으로 Location 헤더의 URL에 의해 처리되어야함
  • 클라이언트의 요청은 캐싱되지 않으므로, 언제나 단축 URL 서버에 먼저 보내짐
  • 트래픽 분석 같이 클릭 발생률이나 발생 위치를 파악해야할 때 사용

URL 리디렉션을 구현하는 가장 직관적인 방법은 해시 테이블을 사용하는 것으로 <단축 URL: 원래 URL> 형식으로 구현될 수 있다.

URL 단축

단축 URL이 <www.tinyurl.com/{hashValue}> 같은 형태로 만들어진다면, 긴 URL을 이 해시 값으로 대응시킬 해시 함수 fx 를 찾는 것이다.

해시 함수는 다음과 같은 요구사항을 만족해야 한다.

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

3단계: 상세 설계

데이터 모델

개략적 설계에서는 모든 것을 해시 테이블에 두었지만, 이 방식은 메모리는 유한하고 비싸기 때문에 실제 시스템에서 사용되기 어렵다.

더 나은 방식은 <단축 URL, 원래 URL>의 순서쌍을 RDB에 저장하는 것이다.

erDiagram
    URL {
        number id pk
        string shortURL
        string longURL
    }

해시 함수

해시 함수는 원래 URL을 단축 URL로 변환하는 데 쓰인다.

해시 값 길이
hashValue는 [0-9, a-z, A-Z]의 문자들로 구성된다.

• 사용할 수 있는 문자의 개수는 10 + 26 + 26 = 62개이다.
• hashValue의 길이를 정하기 위해서는 62^n >= 3650억을 만드는 n의 최소값을 찾아야한다.
  • n = 7, 약 3.5조 개

해시후 충돌 해소
긴 URL을 줄이려면, 원래 URL을 7글자 문자열로 줄이는 해시 함수가 필요하다.

가장 쉬운 방법은 CRC32, MD5, SHA-1 같이 잘 알려진 해시 함수를 이용하는 것이다.

잘 알려진 해시 함수를 사용한 결과가 계산한 가장 짧은 해시값조차도 7보다는 길이가 긴데, 이 문제를 해결하기 위한 첫 번째 방법으로 처음 7개 문자만 사용하는 방법을 고려할 수 있다.

• 해시 결과가 충돌할 확률이 높아진다.
• 충돌이 발생한 경우, 충돌이 해소될 때까지 사전에 정한 문자열을 해시값에 덧붙인다.

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

base-62 변환
진법 변환(base conversion)은 URL 단축기를 구현할 때 흔히 사용되는 접근법이다.

• 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하여야 하는 경우 유용하다.

두 접근법 비교

URL 단축기 상세 설계

URL 단축기는 시스템의 핵심 컴포넌트이므로, 그 처리흐름이 논리적으로는 단순해야 하고, 기능적으로는 언제나 동작하는 상태로 유지되어야 한다.

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

고도로 분산된 환경에서 이런 생성기를 만드는 것은 무척 어려운 일로 필요하다면 7장 내용을 응용하여 분산 환경에 사용될 유일한 ID를 만들 수 있다.

URL 리디렉션 상세 설계

쓰기보다 읽기를 더 자주하는 시스템의 특성에 맞추어, <단축 URL, 원래 URL>의 쌍을 캐싱하여 성능을 높힐 수 있다.

마무리

설계를 마친 후 시간이 좀 남는다면 다음과 같은 것을 면접관과 이야기 할 수 있을것이다.

• 처리율 제한 장치
  • 엄청난 양은 단축 요청이 들어올 경우 무력화될 수 있다는 잠재적 보안 결함을 갖고 있다.
  • 처리율 제한 장치를 통해 요청을 걸러낼 수 있다. 4장 참조
• 웹 서버의 규모 확장
  • 설계에 포함된 웹 계층은 무상태 계층이므로, 웹 서버를 자유롭게 증설, 삭제 할 수 있다.
• 데이터베이스 규모 확장
  • 데이터베이스를 다중화하거나 샤딩하여 규모 확장성을 달성할 수 있다.
• 데이터 분석 솔루션
  • URL 단축기에 데이터 분석 솔루션을 통합해 두면 어떤 링크를 얼마나 많은 사용자가 클릭했는지, 언제 주로 클릭했는지 등 중요한 정보를 알아낼 수 있다.
• 가용성, 데이터 일관성, 안정성
  • 1장 참조