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

8장 URL 단축기(Shorten) 설계
김주혁's avatar
Mar 30, 2024
가상면접 사례로 배우는 대규모 시스템 설계 기초(8) - URL 단축기(Shorten) 설계

 
8장은 생소한 표현힌 URL 단축기 설계다.
 
정확히 URL 단축기란 무엇을 의미하는 걸까?
 
URL 단축기는 웹 주소를 더 짧은 형태로 변환하는 도구나 서비스를 의미한다. 일반적으로 긴 URL을 짧게 만들어주는 것을 의미한다. 사용하는 장점은 다음과 같다.
 
  • URL 압축 : 긴 URL을 짧게 요약하여 저장하고 관리할 수 있다.
  • 링크 추적 : 일부 URL 단축 서비스는 사용자가 단축한 링크의 클릭 통계를 추적할 수 있는 기능을 제공한다.
  • 맞춤 링크 : 일부 URL 단축은 링크에 대한 추가 정보를 제공하거나 사용자 정의 링크를 생성할 수 있는 기능을 제공한다.
 
대표적으로 URL 단축기는 SEO에 영향을 끼친다. 현대 사회에서 SEO는 검색 엔진 최적화로서 웹사이트에 검색 엔진 상위에 노출될 수 있도록 하는 기법으로서 B2C 서비스를 운영하는 회사 뿐만 아니라 대부분의 회사에서 중요하게 생각하는 영역이다.
 
구글에서 순위를 결정할 때 URL 단축기로서 단축된 링크의 형태와 리디렉션되어 전달되는 사이트의 응답 값이 301로서 균일하게 제공되는 것을 평가하기 때문에 만약 사이트가 404 오류가 계속해서 발생한다면 순위에서 밀려날 것이고 웹사이트로 연결되는 링크가 멈추지 않고 계속해서 안내할 수 있는 것은 의미가 있을 것이다.
 
사용자를 특정 페이지로 안내하고, 연결율와 클릭률을 높이고 검색 엔진 순위를 높일 수 있다는 측면에서 URL 단축기 설계는 분명 의미가 있을 것이다.
 

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

URL 단축기는 어떻게 동작합니까?에 대한 질문이 있다면, 이렇게 답할 수 있다.
 
https://www.systeminterview.com/q=chatsystem&c=loggedin&v=3&l=long을 https://tinyurl.com/y7ke-ocwj와 같은 단축 URL을 결과로 제공해줘야 합니다. 이 URL에 접속하면 원래 URL로도 갈 수 있어야 합니다.
 
책의 흐름대로 다음과 같은 요구사항이 발생했다.
 
  • URL 단축: 주어진 긴 URL을 훨씬 짧게 줄인다.
  • URL 리디렉션: 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내해야 한다.
  • 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구된다.
 
해당 값에 대한 개략적 추정으론
 
  • 쓰기 연산: 매일 1억 개의 단축 URL 생성
  • 초당 쓰기: 1억(100million) / 24 / 3600 = 1160
  • 읽기 연산: 읽기 연산과 쓰기 연산의 비율은 10:1로서, 초당 11600개의 읽기 요청이 발생한다.
  • 10년간 단축 서비스를 운영한다고 치면, 3650억개의 레코드를 보관할 수 있어야 한다.
  • 축약 전 평균 URL의 길이는 100이라고 한다.
  • 10년 동안 필요한 저장 용량은 3650억 * 100바이트 ⇒ 36.5TB이다.

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

API 엔드포인트

클라이언트는 서버와 API를 통해 통신한다. 이 엔드포인트를 REST API로 설계할 것이다. URL 단축기는 기본적으로 두 개의 엔드포인트가 필요하다.
 
  1. URL 단축용 : 새 단축 URL을 생성하고자 하는 클라이언트는 이 엔드포인트에 단축할 URL을 인자로 실어 POST 요청을 보내야 한다.
    1.  
      POST /api/v1/data/shorten
      • parameter : { longUrl: longURLstring }
      • return : 단축 URL
 
  1. URL 리디렉션용 엔드포인트 : 단축 URL에 대해서 HTTP 요청이 오면 원래 URL로 보내주기 위한 용도의 엔드포인트 GET /api/v1/shorten
      • return: HTTP 리디렉션 목적지 원래 URL
 

URL 리디렉션

 
notion image
 
단축 URL을 받은 서버는 그 URL을 원래 URL로 바꾸어 301 응답의 Location 헤더에 넣어 반환한다.
 
좀 더 상세하게 설명하면,
notion image
 
위와 같은데, 상태 코드 301과 302의 응답의 차이에 유의해야 한다. 둘 다 리디렉션 응답이지만 차이가 있는데,
 
  • 301 Permanently Moved: 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전됐다는 응답이다. 영구적으로 이전 됐기 때문에, 브라우저는 이 응답을 캐시한다. 따라서 같은 요청을 보내면 캐싱된 본래 URL로 요청을 보내게 된다.
  • 302 Found: 이 응답은 해당 URL로의 요청이 ‘일시적으로’ Location 헤더가 지정하는 URL에 의해 처리되야 한다는 응답이다. 따라서 클라이언트의 요청은 언제나 단축 URL 서버에 먼저 보내진 후에 URL로 리디렉션되야 한다.
 
서버 부하를 줄이기 위해선 301이 좋은데, 트래픽 분석이 중요할 때는 302를 쓰는 것이 클릭 발생률이나 발생 위치 추적에 좀 더 유리하기 때문에 상황에 따라 다른 전략을 사용해야 한다.
 
URL 리디렉션을 구현하는 가장 직관적인 방법은 해시 테이블이다. 해시 테이블에 <단축 URL, 원래 URL>의 쌍을 저장한다고 가정하면, 다음과 같이 구현될 수 있다.
 
  • 원래 URL ⇒ hashTable.get(단축 URL)
  • 301 또는 302 응답 Location 헤더에 원래 URL을 넣은 후 전송
 

URL 단축

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

3단계 상세 설계

데이터 모델

개략적 설계 당시 모든 것을 해시 테이블에 두었다. 이 접근법은 초기에는 괜찮지만 실제로는 곤란한게, 메모리는 유한한 데다 비싸기 때문이다(레디스). 더 나은 방법은 <단축키 URL, 원래 URL>의 순서쌍을 관계형 데이터베이스에 저장하는 것이다.
 

해시 함수

해시 함수는 원래 URL을 단축 URL로 변환하는 데 쓰인다. 일단 사용할 수 있는 hashValue는 [0-9, a-z, A-Z]로 구성되며 사용할 수 있는 문자 개수는 62개다. hashValue의 길이를 정하기 위해선 62^n ≥ 3650억인 n의 최소값을 찾아야 한다.
 
다음은 해시함수가 만들 수 있는 URL의 개수 사이의 관계를 나타낸다.
n
URL 개수
1
62^1 = 62
2
62^2 = 3,844
3
62^3 = 238,328
4
62^4 = 14,776,336
5
62^5 = 916,132,832
6
62^6 = 56,800,235,584
7
62^7 = 3,521,614,606,208
8
62^8 = 218,340,105,584,896
n이 7이면, 3.5조개의 URL을 만들 수 있다. n이 6이라면 568억개로 최소 숫자를 충족시키지 못하기 때문에 n은 7이다. 따라서 hashValue의 길이는 7이된다.
 
해시 함수에 사용될 기술은 다음과 같다.
 
  • 해시 후 충돌 해소
    •  
      긴 URL을 줄이려면 원래 URL을 7자 문자열로 줄이는 해시 함수가 필요하다. 만약 https://en.wikipedia.org/wiki/Systems_design을 해쉬한다고 다음과 같다.
       
      해시 함수
      해시 결과 (16진수)
      CRC32
      5cb54054
      MD5
      5a62509a84df9ee03fe1230b9dfb84e
      SHA-1
      0eeae7916c06853901d9ccbefbfcaf4de57ed85b
      제일 짧은 CRC32 마저 최소 값인 7을 넘기고 있다. 여기서 더 줄이기 위해 어떻게 해야 할까?
       
      첫 번째 방법은 위 글자 중 7자리인 5cb5405까지만 사용하는 것이다. 하지만, 이럴 경우 해시 충돌이 발생할 확률이 높아진다. 만약, 충돌이 실제로 발생했다면 충돌이 해소될 때 까지 사전에 정한 문자열을 해시 값에 덧붙인다.8-5
      notion image
       
      이 방법을 사용하면 충돌은 해결할 수 있지만, 데이터베이스에 계속해서 충돌이 일어나는지 탐색해야 하기 때문에 오버헤드가 크다. 데이터베이스 대신 블룸필터를 사용하면 성능을 높일 수 있다.
  • base-62 변환
    •  
      진법 변환은 URL 단축기를 구현할 때 사용되는 일반적인 방법이다. 62진법인 base-62를 쓰는 이유는 사용 가능한 문자가 62개이기 때문이다.
      1115710을 62진수로 변환해보자.
    • 62진법은 수를 표현하기 위해 62개의 문자를 사용하는 진법이다. 따라서 0은 0으로 9는 9로, 10은 a로 61은 Z로 대응시켜 표현하도록 할 것이다. 따라서 62진법에서 ‘a’는 10을 나타내고 ‘Z’는 61을 나타낸다.
    • 11157 = 2 * 62^2 + 55 * 62^1 + 59 * 62^0 = [2, 55, 59] => [2, T, X] => 2TX^62 이다.
    • 따라서 단축 URL은 https://tinyurl.com/2TX가 된다.
 
해시 후 충돌 해소 전략
base-62 변환
단축 URL의 길이가 고정됨
단축 URL의 길이가 가변적. ID 값이 커지면 같이 길어짐
유일성이 보장되는 ID 생성기가 필요치 않음
유일성 보장 ID 생성기가 필요
충돌이 가능해서 해소 전략이 필요
ID 유일성이 보장된 보장된 후에야 적용 가능한 전략이라 충돌은 아예 불가능
ID로부터 단축 URL을 계산하는 방식이 아니라서 다음에 쓸 수 있는 URL을 알아내는 것이 불가능
ID가 1씩 증가하는 값이라고 가정하면 다음에 쓸 수 있는 단축 URL이 무엇인지 쉽게 알아낼 수 있어서 보안상 문제가 될 소지가 있음
 
 

URL 단축기 상세 설계

URL 단축기는 시스템의 핵심 컴포넌트이기 때문에 그 처리 흐름이 논리적으로 단순해야 하고 기능적으로는 언제나 동작하는 고가용성을 유지해야 한다. 62진법 방식을 예로 들면,
notion image
 
실제 예제로 살펴보면 이렇다.
 
  1. 입력된 URL이 'https://en.wikipedia.org/wiki/Systems_design'이라고 하자.
  1. 이 URL에 대해 ID 생성기가 반환한 ID는 2009215674938이다.
  1. 이 ID를 62진수로 변환하면 zn9edcu를 얻는다.
  1. 아래 표와 같은 새로운 데이터베이스 레코드를 만든다.
    1. notion image
 

URL 리디렉션 상세 설계

좀 더 상세한 구조로 보면,
notion image
  1. 사용자가 단축 URL을 클릭한다.
  1. 로드밸런서가 해당 클릭으로 발생한 요청을 웹 서버에 전달한다.
  1. 단축 URL이 이미 캐시에 있는 경우에는 원래 URL을 바로 꺼내서 클라이언트에게 전달한다.
  1. 캐시에 해당 단축 URL이 없는 경우에는 데이터베이스에서 꺼낸다. 데이터베이스에 없다면 아마 사용자가 잘못된 단축 URL을 입력한 경우일 것이다.
  1. 데이터베이스에서 꺼낸 URL을 캐시에 넣은 후 사용자에게 반환한다.
 
정도로 요약할 수 있다.
 

4단계 마무리

다음과 같은 내용들을 살펴볼 수 있다.
 
  • 처리율 제한 장치(rate limiter)
    • 지금까지 살펴본 시스템은 엄청난 양의 URL 단축 요청이 있을 경우 무력화될 수 있다는 잠재적 보안 결함을 갖고 있다. 처리율 제한 장치를 두면, IP 주소를 비롯한 필터링 규칙들을 이용해 요청을 걸러낼 수 있을 것이다.
  • 웹 서버의 규모 확장
    • 본 설계에 포함된 웹 계층은 무상태 계층이므로, 웹 서버를 자유롭게 증설하거나 삭제할 수 있다.
  • 데이터베이스의 규모 확장
    • 데이터베이스를 다중화하거나 샤딩(sharding)하여 규모 확장성을 달성할 수 있다.
  • 데이터 분석 솔루션(analytics)
    • 성공적인 비즈니스를 위해서는 데이터가 중요하다. URL 단축기에 데이터 분석 솔루션을 통합해 두면 어떤 링크를 얼마나 많은 사용자가 클릭했는지, 언제 주로 클릭했는지 등 중요한 정보를 알아낼 수 있을 것이다.
  • 가용성, 데이터 일관성, 안정성
    • 대규모 시스템이 성공적으로 운영되기 위해서는 반드시 갖추어야 할 속성들이다.
 
현대 사회에서 URL 단축기는 SEO와 뗄레야 뗄 수 없기 때문에, 위에서 살펴봤던 네트워크와 다분히 개발적인 측면 말고도, 키워드나 분석 기능이 내장됐다거나 하는 등의 SEO 성공을 위한 전략을 세워야 한다.
 
또한, 검색엔진이 301 또는 302 리디렉션을 다르게 처리한다는 것을 명심해야 한다. 웹사이트를 영구적으로 301 응답을 통해 Location 헤더에 반환된 URL로 이전됐다는 표식을 통해 순위를 유지시킬 수 있다. 따라서, 클릭과 페이지 이동 등 트래픽을 추적하기 위함과 웹사이트를 검색엔진 내에서 순위를 유지시키기 위해서 어떤 상황에 301과 302를 사용할지는 사용자의 고민거리가 될 것이다.
 
Share article

vlogue

RSS·Powered by Inblog