단축 URL 이 필요한 이유

URL 공유를 하고 싶은 메시지의 길이에 제약이 있을 경우 단축된 URL을 제공한다.

요구 사항

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

개략적 설계안

API 엔드포인트

1. 새 단축 URL을 생성 API
   • POST /api/v1/data/shorten
     * params: {longURL: longURLstring}
     • response: {shortUrl: shortUrl}
2. shortenUrl 리다이렉션
   • GET /api/v1/shortUrl
     * response : longUrl

URL 리다이렉션

단축 URL을 받은 서버는 그 URL을 원래 URL로 바꿔서 301 응답의 location 헤더에 넣어 반환

301 응답 vs 302 응답

• 301 Permanetly Moved : HTTP 요청 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전 되었다는 의미. 브라우저는 이 응답을 캐시한다. 따라서 추후 같은 단축 URL에 요청을 보내게 되면 브라우저는 캐시된 원래 URL로 요청을 보낸다. 서버 부하를 줄이는 것이 중요할때 사용한다.
• 302 Found : URL 요청이 일시적으로 Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 의미. 클라이언트의 요청은 언제나 단축 URL 서버에 먼저 보내진 후에 원래 URL로 리다이렉션 된다. 트래픽 분석이 중요할때는 이 방식을 사용한다.

URL 리다이렉션을 구현하는 가장 직관적인 방법은 해시 테이블을 사용하는 것이다.

해시 테이블에 <단축 URL, 원래 URL>의 쌍을 저장한다고 가정한다면, URL 리다이렉션은 다음과 같이 구현될 수 있을 것이다.

• 원래 URL = hashTable.get(단축 URL)
• 301 또는 302 응답 Location 헤더에 원래 URL을 넣은 후 전송

URL 단축

결국 중요한 것은 긴 URL을 해시 값으로 대응시킬 해시 함수 fx를 찾는 일이다.

이 해시 함수의 요구사항은 아래와 같다.

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

상세 설계

데이터 모델

모든 단축 URL을 해시 테이블로 메모리에 저장하기에는 너무 비효율적이다. 더 나은 방법은 <단축 URL, 긴 URL>의 순서쌍을 데이터베이스에 저장하는 것이다. 아래 그림은 간단한 설계 사례이다.

해시함수

해시 값 길이

hashValue는 [0-9, a-z, A-Z]의 문자들로 구성된다. 따라서 사용할 수 있는 문자의 개수는 10 + 26 + 26 = 62개다.
hashValue의 길이를 정하기 위해서는 3650억인 n의 최솟값을 찾아야 한다.
이전 요구사항에서 계산했던 추정치에 따르면 이 시스템은 3650억 개의 URL을 만들어 낼 수 있어야 한다.
n = 7 이면 3.5조 개의 URL을 만들 수 있다. 그러면 3650억개를 만들 수 있는 요구사항을 만족시키기 충분한 값이다.
따라서 hashValue의 길이는 7로 하면 된다.

해시 후 충돌 해소

손쉬운 방법은 CRC32, MD5, SHA-1같이 잘 알려진 해시 함수를 이용해 원래 URL을 7글자 문자열로 줄인다.
아래는 해시 함수를 사용하여 https://en.wikipedia.org/wiki/Systems_design 을 축약한 결과다.

모든 해시 결과가 7보다 길다. 이를 위해 해시 값에서 처음 7개 글자만 이용한다. 하지만 이러면 해시 결과가 충돌할 가능성이 높아진다. 그러면 사전에 정한 문자열을 해시값에 붙인다.

이 방법을 사용하면 DB에 있는지 확인하는 쿼리가 한번 더 들어가게 된다. 이때는 쿼리를 하지 않고 블룸 필터를 사용해 성능을 높일 수 있다.

base-62 변환

62진법을 사용해서 hashValue를 생성한다. 62진법을 쓰는 이유는 hashValue에 사용할 수 있는 문자 개수가 62개이기 때문이다.
11157을 62진수로 변환해보자.

62진법은 수를 표현하기 위해 62개의 문자를 사용하는 진법이다. 따라서 0은 0으로 9는 9로, 10은 a로 61은 Z로 대응시켜 표현하도록 할 것이다. 따라서 62진법에서 ‘a’는 10을 나타내고 ‘Z’는 61을 나타낸다.
11157 = 2 x 622 + 55 X 621 + 59 x 620 = [2, 55, 59] => [2, T, X] => 2TX 이다.
따라서 단축 URL은 https://tinyurl.com/2TX가 된다.

두 접근법 비교

URL 단축기 상세 설계

62진법 변환 기법을 사용한 설계이다.

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

예제

• 입력된 URL이 'https://en.wikipedia.org/wiki/Systems_design' 이라고 하자.
• 이 URL에 대해 ID 생성기가 반환한 ID는 2009215674938이다.
• 이 ID를 62진수로 변환하면 zn9edcu를 얻는다.
• 아래 표와 같은 새로운 데이터베이스 레코드를 만든다.
  

URL 리디렉션 상세 설계

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

마무리

URL 단축기 설계시 추가로 고려할만한 사항

• 처리율 제한 장치(rate limiter)
  - 지금까지 살펴본 시스템은 엄청난 양의 URL 단축 요청이 있을 경우 무력화될 수 있다는 잠재적 보안 결함을 갖고 있다. 처리율 제한 장치를 두면, IP 주소를 비롯한 필터링 규칙들을 이용해 요청을 걸러낼 수 있을 것이다.

• 웹 서버의 규모 확장
  - 본 설계에 포함된 웹 계층은 무상태 계층이므로, 웹 서버를 자유롭게 증설하거나 삭제할 수 있다.

• 데이터베이스의 규모 확장
  - 데이터베이스를 다중화하거나 샤딩(sharding)하여 규모 확장성을 달성할 수 있다.

• 데이터 분석 솔루션(analytics)
  - 성공적인 비즈니스를 위해서는 데이터가 중요하다. URL 단축기에 데이터 분석 솔루션을 통합해 두면 어떤 링크를 얼마나 많은 사용자가 클릭했는지, 언제 주로 클릭했는지 등 중요한 정보를 알아낼 수 있을 것이다.

• 가용성, 데이터 일관성, 안정성
  - 대규모 시스템이 성공적으로 운영되기 위해서는 반드시 갖추어야 할 속성들이다.
  

---

본 포스트는 알렉스 쉬 저자의 가상 면접 사례로 배우는 대규모 시스템 설계 기초를 기반으로 스터디하며 정리한 내용들입니다.

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