URL 단축기 설계

가상 면접 사례로 배우는 대규모 시스템 설계 기초 "URL 단축기 설계"을 요약한 내용입니다.

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

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

개략적 추정

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

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

API 엔드포인드

• URL 단축기는 기본적으로 두개의 엔드포인트를 필요로 한다.

1. URL 단축용 엔드포인트
   1. 새 단축 URL을 생성하고자하는 엔드포인트
   2. 단축 URL을 인자로 실어 POST 요청을 보냄
   3. POST /api/v1/data/shorten
      1. 인자: {longUrl, String}
      2. 반환: 단축 URL
2. URL 리디렉션용 엔드포인트
   1. 단축 URL에 대해서 원래 URL로 보내주기 위한 엔드포인트
   2. GET /api/v1/shortUrl
      1. 반환: HTTP 리디렉션 목적지가 될 원래 URL

URL 리디렉션

• 브라우저에 단축 URL을 입력하면 무슨 일이 생기는지 보여준다

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

301 응답과 302 응답의 차이

• 301 Permanently Moved
  • 브라우저는 이 응답을 캐시 한다.
  • 추후 같은 단축 URL에 요청을 보낼 필요가 있을때 브라우저는 캐시된 원래 URL로 요청을 보내게 된다.
  • 서버 부하를 줄일 수 있음, 트래픽 분석을 하기 어려움
• 302 Found
  • 브라우저는 단축 URL서버에 먼저 보낸후 원래 URL로 리디렉션
  • 서버 부하 받을 수 있음, 트래픽 분석을 하기 좋음

캐싱을 하는지 유무에 따라 사용하면 될듯, 단축 URL에 대한 원래 URL이 변경될 경우 301 응답을 사용하면 안됨

URL 단축

• 단축 URL을 생성하기 위해서는 긴 URL을 해시 값으로 대응시킬 해시 함수 fx를 찾는 일

• 해시 함수는 다음 요구사항을 만족 해야함
  • 입력으로 주어지는 긴 URL이 다른 값이면 해시 값도 달라야 함
  • 계산된 해시 값은 원래 입력으로 주어졌던 긴 URL로 복원될 수 있어야 함

3단계 상세 설계

데이터 모델

• <단축 URL, 원래 URL>의 순서쌍을 관계형 데이터베이스에 저장
  • 메모리는 유한하기 때문에
• id, shortURL, longURL 세개의 칼럼을 갖는다.

해시 함수

• hashValue는 [0-9, a-z, A-Z]의 문자열들로 구성됨
• 사용할 수 있는 문자의 개수는 10(0-9) + 26(a-z) + 26(A-Z) = 62개
• 대략적으로 계산했던 추정치에 따르면 3650억개의 URL을 만들 수 있어야 함
  • n=7 이면 3.5조개의 URL을 만들 수 있다
  • hashValue의 길이는 7로 설정

해시 후 충돌 해소

• 긴 URL을 줄이려면, 원래 URL을 7글자 문자열로 줄이는 해시 함수가 필요함
  • 손쉬운 방법으로는 CRC32, MD5, SHA-1 같이 잘 알려진 해시 함수를 이용하는 것

 

• CRC32가 가장 짧지만 7자리를 넘어간다.
  • 처음 7개 글자만 사용할 경우 결과가 충돌할 확률이 높아진다.
    • 예외를 처리할 방법이 있지만 데이터베이스에 질의를 해야하므로 오버해드가 크다

base-62 변환

• 진법 변환은 URL 단축기를 구현할 떄 흔이 사용되는 접근 방법 중 하나
• base-62를 사용하면 hashValue에 사용할 수 있는 문자 개수가 62개이기 때문

URL 단축기 상세 설계

• URL 단축기 시스템의 처리 흐름
  1. 입력으로 긴 URL을 받는다
  2. 데이터베이스에 해당 URL이 있는지 검사한다.
  3. 데이터베이스에 있다면 해당 URL에 대한 단축 URL을 가져와 클라이언트에 반환
  4. 데이터베이스에 없다면 유일한 ID를 생성
  5. 62진법 변환을 적용 ID를 단축 URL로 만든다.
  6. ID, 단축URL, 원래 URL로 데이터베이스에 저장 후 단축 URL을 클라이언트에 전달
• 아래의 예제를 통해 알아보기
  • 입력된 URL이 https://en.wikipdia.org/…..
  • 입력된 URL에 대한 ID 생성기가 반환한 ID는 20092155… 이다
  • 이 ID를 62진수로 변환하면 zn9ed..를 얻는다.
  • 새로운 데이터베이스 레코드로 만든다.

URL 리디렉션 상세 설계

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

4단계 마무리

• 처리율 제한 장치
  • 엄청난 양의 URL 단축 요청이 밀려들 경우 무력화 될수 있는 잠재적 보안 결함이 있음
  • IP 주소를 비롯한 필터링 규칙들을 이용해 요청을 걸러낼 수 있을 것
• 웹 서버의 규모 확장
  • 웹 계층은 무상태 계층이므로, 웹 서버를 자유로이 증설하거나 삭제할 수 있음
• 데이터베이스의 규모 확장
  • 데이터베이스를 다중화하거나 샤팅하여 규모 확장성을 달성 할 수 있음
• 데이터 분석 솔루션
  • 데이터 분석 솔루션을 통합해 두면 어떤 링크를 얼마나 많은 사용자가 클릭했는지, 언제 주로 클릭했는지 등 중요한 정보를 알아 낼 수 있을 것
• 가용성, 데이터 일관성, 안정성
  • 대규모 시스템이 성공적으로 운영되기 위해서는 반드시 갖추어야 할 속성들