가상 면접 사례로 배우는 대규모 시스템 설계 기초 (feat. 8장 URL 단축기 설계)

들어가기 앞서

이번 포스팅에서는 URL 단축기 설계에 대해 알아볼 예정입니다.

 

블로그에 글을 쓸때 불편할 때가 있습니다.

https://www.agoda.com/ko-kr/onsen-ryokan-yuen-sapporo-h15472820/hotel/sapporo-jp.html?finalPriceView=1&isShowMobileAppPrice=false&cid=1922868&numberOfBedrooms=&familyMode=false&adults=1&children=0&rooms=1&maxRooms=0&checkIn=2025-03-19&isCalendarCallout=false&childAges=&numberOfGuest=0&missingChildAges=false&travellerType=-1&showReviewSubmissionEntry=false&currencyCode=KRW&isFreeOccSearch=false&tag=a6968e79-dc67-497a-bb6c-29c5df28373e&los=1&searchrequestid=2c6f644f-e911-43a8-bac1-7f2637d8301a&ds=WDW0oLEXUe3lDgXw%EF%BB%BF

온센료칸 유엔 삿포로 (ONSEN RYOKAN YUEN SAPPORO) 실제 이용후기 및 할인 특가

네.. 링크가 너무 길어서 가독성이 떨어질 때가 입니다.

 

위에 링크를 이용하여 bit.ly에서 직접 단축 url을 만들어 보면 아래와 같습니다. 훨씬 깔끔하죠? 

https://bit.ly/40iYHAe

온센료칸 유엔 삿포로 (ONSEN RYOKAN YUEN SAPPORO) 실제 이용후기 및 할인 특가

 

실제로 두 링크 모두 클릭해 보면 동일한 아고다 숙소 페이지로 이동하는 것을 볼 수 있습니다. 물론 밑에 단축 URL은 제가 bit.ly를 통해 변환하여 http://bit.ly/~ 로 시작하지만, 아고다에서 실제 단축 URL을 개발한다면 아마 https://www.agoda.com/40iTHAe 가 될 것 같습니다.

---

URL 단축기 설계

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

단축 URL의 요구사항은 다음과 같다.

1. URL 단축: 주어진 긴 URL을 최대한 가장 짧게 줄여야 한다.
2. URL 리다이렉션 : 축약된 URL로 HTTP요청이 오면 원래 URL로 안내해야 한다.
3. 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨. (매일 1억개 URL 생성 가능)

 

개략적 추정

• 하루 쓰기 연산 : 매일 1억 개의 단축 URL 생성
• 초당 쓰기 연산 : 1억 / 24 / 3600 = 1,160개
• 하루 읽기 연산 : 하루 10억개 요청 (읽기 요청 수는 쓰기의 10배로 추정)
• 초당 읽기 연산 : 1,160개 * 10 = 11,600개
• 10년간 서비스 운영시 생성 URL 수 : 3650억개
• 10년간 서비스 운영에 필요한 저장 용량 : 3650억개 * 100 바이트 = 36.5TB (하나에 100 바이트라 추정)

---

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

API 엔드포인트

URL 단축기 서버를 개발하기 위해 기본적으로 단축 URL 생성 API와 조회 API가 필요하다.

POST /api/v1/data/shorten

{
    "longUrl" : "http://shortenUrl/~"
}

GET /api/v1/shortURL

 

 

URL 리다이렉션

단축 URL을 브라우저에 입력하게 되면 서버는 단축URL의 원래 URL로 바꾸어서 301응답 또는 302응답의 Location헤더에 넣어 반환한다. 301과 302는 둘 다 리다이렉션 응답이지만 차이가 있다.

• 301 Permanaently Moved : 301응답은 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답이다. 영구적으로 이전되었으므로, 브라우저는 이 응답을 캐시한다. 따라서 추후 같은 단축 URL에 요청을 보낼 필요가 있을때 브라우저는 캐시된 원래 URL로 요청을 보내게 된다.
• 302 Found : 302응답은 URL로의 요청이 일시적으로 Location 헤더가 지정하는 URL에 의해 처리되어야 한다는 응답이다. 따라서 클라이언트의 요청은 언제나 단축 URL 서버에 먼저 보내진 후에 원래 URL로 리다이렉션 되어야 한다.

 

서버 부하를 줄이는 것이 중요하다면 301응답을 사용하는 것이 좋다. 반대로 302는 트래픽 분석이 중요할때나 클릭 발생률, 발생 위치를 추적하는데 유리하다.

 

URL 단축

URL단축기의 핵심은 원래의 긴 URL을 대응시킬 단축 URL로, 해시 함수를 찾는 것이다. 해시 함수는 항상 다음을 만족해야 한다.

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

---

3단계 : 상세 설계

데이터 모델

2단계 개략적 설계에서 해시 테이블을 이용하여 설계를 하였다. 하지만 실제 서비스에서 해시 테이블을 사용하는 것은 좋은 전략은 아니다. 해시를 사용하기 위해서는 메모리 자원을 사용해야 하는데, 메모리는 비싸기 때문이다. 따라서 데이터베이스에 저장하는 것이 좋다.

해시 함수

해시 함수는 원래 URL을 단축 URL로 변환하는 데 쓰인다. (해시를 통해 생성된 단축URL을 편의상 hashValue라고 지칭하겠습니다.) 해시함수를 구현하는 방법에는 "해시 후 충돌 해소"와 "base-62"가 있다.

 

해시값 길이

hashValue는 0-9,a-z,A-Z의 문자들로 구성된다. 따라서 사용할 수 있는 문자의 개수는 10+26+26=62개가 된다. 1단계에서 개략적으로 계산했던 추정치에 따르면 10년동안 3650억개의 URL을 만들어 낼 수 있어야 한다. 따라서 해당 조건을 만족하기 위해서는 62^7로 hashValue의 길이가 최소 7이어야 한다. 

 

해시 후 충돌 해소

긴 URL을 줄이려면 원래 URL을 7글자 문자열로 줄이는 해시 함수가 필요하다. 우선 가장 잘 알려진 해시 함수를 이용해 보자. 아래 표는 제가 제공했던 아고다 링크를 해시함수를 통해 변환한 결과 값입니다.

https://www.agoda.com/ko-kr/onsen-ryokan-yuen-sapporo-h15472820/hotel/sapporo-jp.html?finalPriceView=1&isShowMobileAppPrice=false&cid=1922868&numberOfBedrooms=&familyMode=false&adults=1&children=0&rooms=1&maxRooms=0&checkIn=2025-03-19&isCalendarCallout=false&childAges=&numberOfGuest=0&missingChildAges=false&travellerType=-1&showReviewSubmissionEntry=false&currencyCode=KRW&isFreeOccSearch=false&tag=a6968e79-dc67-497a-bb6c-29c5df28373e&los=1&searchrequestid=2c6f644f-e911-43a8-bac1-7f2637d8301a&ds=WDW0oLEXUe3lDgXw%EF%BB%BF

해시 함수	해시 결과 (16진수)
CRC32	A59FD13C
MD5	3665ac8f11125b6894610a1d8b6fd44e
SHA-1	f2b6f3a33d4b258864e608c9e5859a3a428e2756

 

표를 살펴보면 가장 짧은 CRC32로 해싱한 값 역시 7보다는 긴 값을 반환합니다. 하지만 이번 요구사항은 가장 짧은 7글자만 사용하는 것입니다. 그러면 이 문제를 해결하는 방법은 처음 7개 글자만 이용하는 것입니다. 하지만 이렇게 하면 해시 결과가 서로 충돌할 확률이 있습니다. 만약 해시가 충돌한다면 기존 해시 결과 값을 한 문자씩 덧붙이는 것입니다. 하지만 한번 이상 충돌이 발생할 수 있기에 오버헤드가 큰 편입니다. 데이터베이스 대신 블룸 필터를 사용하면 성능을 개선할 수 있습니다. 블룸 필터는 어떤 집합에 특정 우너소가 있는지 검사할 수 있도록 하는, 확률론에 기초한 공간 효율이 좋은 기술입니다. 

 

(개인적인 생각입니다. 요구사항이 가장 짧은 길이를 사용하는 것이지만 굳이 이렇게 해야 될까요..? 해시 충돌이 발생하면 데이터베이스를 조회해야 합니다. 또한 최악의 경우에는 n번 충돌이 발생해 여러번 데이터베이스를 조회해야 하는 경우도 있습니다. 물론 뒤에 볼룸 필터라는 대안을 제시하기는 하지만 저는 이러한 방법이 크게 좋은 설계라고 생각하지는 않습니다. 예전에는 데이터의 저장소가 값비싼 자원이였지만 최근에는 저장장치가 저렴한 자원이라고 생각합니다. 굳이 저렴한 자원을 아끼기 위해 성능을 포기하고 이러한 복잡한 구조를 설계해야 한다는 것에 크게 공감가지는 않습니다.)

 

base-62 변환

진법 변환은 URL단축기를 구현할 때 흔히 사용되는 접근법 중 하나 입니다. 이 기법은 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하여야 하는 경우에 유용합니다. 62진법을 사용 하는 이유는 hashValue에 사용 할 수 있는 문자 개수가 62개 이기 때문입니다. 

 

10진수 11157을 62진수로 변환해 보겠습니다. 따라서 11157을 62진법으로 표현하면 XT2가 된다.

 

 

 

해시 후 충돌 해소 vs base-62 변환

해시 후 충돌 해소 전략	base-62 변환
단축 URL 길이가 고정됨	길이가 가변적임. ID값이 커지면 길이가 길어짐
유일성이 보장되는 ID 생성기가 필요하지 않음	유일성 보장 ID 생성기가 필요함
충돌이 가능해서 해소 전략이 필요함	ID의 유일성이 보장되면 충돌은 불가능
ID로 부터 단축 URL을 계산하는 방식이 아니라서 다음에 사용할 URL을 알아내는 것이 불가능	ID가 1씩 증가하는 수라고 가정하면 다음에 쓸 단축 URL이 무엇인지 쉽게 유추 가능

 

 

URL 단축기 상세 설계

URL 단축기는 시스템의 핵심 컴포넌트이다. 해당 예제에서는 62진법 변환 기법을 사용해 설계할 것이다.

1. 입력으로 긴 URL을 받는다.
2. 데이터베이스에 해당 URL이 있는지 검사한다.
   1.  데이터베이스에 있다면 해당 URL에 대한 단축 URL을 클라이언트에게 반환한다.
   2.  데이터베이스에 없다면 해당 URL에 대한 유일 ID를 생성한다. (ID 데이터베이스의 기본 키로 사용한다.)
3. 62진법 변환을 적용해 ID를 URL로 만든다.
4. 생성된 단축 URL을 원래 URL과 함께 저장한다.

 

해당 URL 단축기에서 유의해야 할 점이 있다. 분산환경에서는 ID를 생성할때 유일성이 보장되도록 해야한다. 만약 유일 ID 생성에 대해 알고 싶다면 7장 내용을 참고해 주시면 감사하겠습니다.

가상 면접 사례로 배우는 대규모 시스템 설계 기초 (feat. 7장 부산 시스템을 위한 유일 ID 생성기 설계)

 

URL 리다이렉션 상세 설계

단축 URL은 생성보다 조회가 더 많은 시스템이라 캐시에 저장하여 성능을 높이면 좋다.

 

---

4단계 : 마무리

조금더 설계를 고도화 해보겠습니다.

 

• 처리율 제한 장치 : 지금까지 살펴본 시스템은 엄청난 양의 생성 요청이 밀려들 경우 무력화 될 수 있다는 단점을 가지고 있다. 처리율 제한 장치를 두면 IP주소를 비롯한 필터링 규칙을 이용한 필터링 규칙들을 이용해 요청을 걸러낼 수 있다.
  가상 면접 사례로 배우는 대규모 시스템 설계 기초 (feat. 4장 처리율 제한 장치의 설계)
• 웹 서버 / 데이터베이스 서버의 규모 확장 : 웹 계층은 무상태 계층이므로 자유롭게 증성 및 삭제가 가능하고, 데이터베이스는 샤딩을 통해 규모 확장이 가능하다.
  가상 면접 사례로 배우는 대규모 시스템 설계 기초 (feat. 1장 사용자 규모에 따른 규모 확장성)
• 데이터 분석 솔류션 : 성공적인 비즈니스를 위해 URL 단축기에 데이터 분석 솔루션을 통합해 두면 통계로 활용하기 용이하다.