8장: URL 단축기 설계

*<가상 면접 사례로 배우는 대규모 시스템 설계 기초> 을 참고하여 작성한 게시물입니다.

URL 단축기 설계

문제 이해 및 설계 범위 확정

• URL 단축: 주어진 긴 URL을 훨씬 짧게 줄인다.
• URL 리디렉션: 축약된 URL로 HTTP 요청이 오면 원래 URL로 안내
• 높은 가용성과 규모 확장성, 그리고 장애 감내가 요구됨
• 개략적 추정
  • 쓰기 연산: 매일 1억 개의 단축 URL 생성
  • 초당 쓰기 연산: 1억/24/3600=1160
  • 읽기 연산: 읽기 연산과 쓰기 연산 비율은 10:1이라고 하자. 그 경우 읽기 연산은 초당 11,600회 발생한다.
  • URL 단축 서비스를 10년간 운영한다고 가정하면 1억x365x10 = 3650억 개의 레코드를 보관해야 한다.
  • 축약 전 URL의 평균 길이는 100이라고 하자.
  • 따라서 10년동안 필요한 저장 용량은 3650억x100바이트 = 36.5TB이다.

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

• API 엔드 포인트

  • 1.URL 단축용 엔드포인트: 새 단축 URL을 생성하고자 하는 클라이언트는 이 엔드포인트에 단축할 URL을 인자로 실어서 POST 요청을 보내야 한다. 이는 다음과 같은 형태를 띤다. POST /api/v1/data/shorten 인자:{longUrl:longUrlString} 반환:단축 URL
  • 2.URL 리디렉션용 엔드포인트: 단축 URL에 대해서 HTTP 요청이 오면 원래 URL로 보내주기 위한 용도의 엔드포인트. 다음과 같은 형태를 띤다. GET /api/v1/shortUrl 반환:HTTP 리디렉션 목적지가 될 원래 URL

• URL 리디렉션

  • 단축 URL을 받은 서버는 그 URL을 원래 URL로 바꾸어서 301 응답의 Location 헤더에 넣어서 반환한다. 즉, 클라이언트가 단축 URL을 방문하면, 해당 서버가 반환한 값에 따라 원래 URL에 방문하게 되는 것이다. 이때 301, 302 응답에 차이가 있다.
    • 301 Permanently Moved: 해당 URL에 대한 HTTP 요청의 처리 책임이 영구적으로 Location 헤더에 반환된 URL로 이전되었다는 응답이다. 영구적으로 이전되었으므로 브라우저는 이 응답을 캐시(cache)한다. 따라서 추후 같은 단축 URL에 요청을 보낼 필ㅇ가 있을대 브라우저는 캐시된 원래 URL로 요청을 보내게 된다.
    • 302 Found: 주어진 URL로의 요청이 '일시적으로' Location 헤더가 지정하는 URL에 의해 처리되는 것으로, 클라이언트의 요청은 언제나 단축 URL 서버에 머넞 보내진 후에 원래 URL로 리디렉션 되어야 한다.
  • 이 두 방법은 각기 다른 장단점을 갖고 있다. 서버 부하를 줄이는 것이 중요하다면 301, 트래픽 분석이 중요하면 302가 유리할 것이다.
  • 이를 구현하는 가장 직관적인 방법은 해시테이블 사용이다. <단축 URL, 원래 URL>의 쌍으로 저장하면 다음과 같이 구현할 수 있다.
    • 원래 URL = hashTable.get(단축 URL)
    • 301 또는 302 응답 Location 헤더에 원래 URL 넣은 후 전송

• URL 단축

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

상세 설계

• 데이터 모델

  • 해시 테이블은 초기 전략으론 괘낞으나 실제에는 곤란한데, 메모리는 유한한데다 비싸기 떄문. 더 나은 방법은 해당 순서쌍을 RDB에 저장하는 것이다. id, longURL, shortURL 세 개의 컬럼을 가지면 됨.

• 해시 함수

  • 원래 URL을 단축 URL으로 변환하는데 쓰이는 것으로, 해시 함수가 계산하는 단축 URL값을 hashValue라고 하자. 고려해야할 것은 다음과 같다.
  • 해시 값 길이: hashValue는 [0-9,a-z,A-Z]의 문자들로 구성된다. 따라서 사용할 수 있는 문자는 62개. hashValue의 길이를 정하기 위해서는 3650억인 n의 최소값을 찾아야 한다. (3650억 개의 URL을 만들 수 있어야 하므로.) n이 7이면 3.5조개(62의 7승) 만들 수 있으므로, 요구사항 만족에 충분하다. 따라서 길이를 7으로 설정한다. 해시 함수 구현에 쓰일 기술로는 해시 후 충돌 해소, base-62 변환법이 있다.
    • 해시 후 충돌 해소: 원래 URL을 7가지 문자열으로 줄이려면, CRC32,MD5,SHA-1같이 잘 알려진 해시 함수를 이용할 수 있다. 하지만 이런 경우 길이가 길다. 이를 줄이려면 계산된 해시 값에서 처음 7개 글자만 이용 -> 충돌 확률이 높음. 따라서 실제 충돌 발생시에는 충돌 해소될때까지 사전에 정한 문자열을 해시값에 덧붙이도록 한다. 이렇게 하면 충돌 해소는 가능하지만 단축 URL 생성 시에 한 번 이상 DB 질의를 해야하므로 오버헤드가 크다. DB대신 블룸 필터(어떤 집합에 특정 원소가 있는지 검사할 수 있도록 하는 확률론에 기초한 공간 효율이 좋은 기술)를 사용하면 성능을 높일 수 있다.
    • base-62 변환: 진법 변환으로, 흔히 사용되는 접근법이다. 수의 표현 방식이 다른 두 시스템이 같은 수를 공유하여야 하는 경우에 유용하다. 62개 문자를 쓸 수 있으므로 62진법을 사용하는 것이다.
  • 위 두 방법의 경우, 1)해시 후 충돌 해소 전략:단축 URL 길이가 고정됨, 유일성이 보장되는 ID 생성기 필요치 않음, 충돌이 가능해서 해소 전략 필요, ID로부터 단축 URL을 계산하는 방식이 아니라서 다음에 쓸 수 있는 URL 알아내기가 불가능. 2)base-62 변환:단축 URL 길이가 가변적. ID 값이 커지면 같이 커짐. 유일성 보장 ID 생성기 필요. ID의 유일성이 보장된 후에야 적용 가능한 전략이라 충돌은 아예 불가능. ID가 1씩 증가하는 값이라고 가정하면 다음에 쓸 수 있는 단축 URL이 무엇인지 쉽게 알 수 있어 보안상 문제가 될 소지가 있음.

• URL 단축기 상세 설계

  • 1.입력으로 긴 URL을 받는다.
  • 2.DB에 해당 URL이 있는지 검사한다.
  • 3.DB에 있다면 해당 URL에 대한 단축 URL을 만든 적 있는 것으로, DB에서 해당 단축 URL을 가져와서 반환한다.
  • 4.DB에 없다면 새로 접수된 것으로, 유일한 ID를 생성한다. 이 ID는 DB의 기본 키로 사용한다.
  • 5.62진법 변환을 사용, ID를 단축 URL로 만든다.
  • 6.ID, 단축 URL, 원래 URL로 새 DB 레코드를 만든 후 단축 URL을 반환한다.
  • 이때 ID 생성기는 단축 URL을 만들때 사용할 ID를 만드는 것으로, 이 ID는 전역적 유일성(globally unique)이 보장되어야 한다.

• URL 리디렉션 상세 설계
  

  • 쓰기보다 읽기를 더 자주 하는 시스템이므로, <단축 URL, 원래 URL>의 쌍을 캐시에 저장하여 성능을 높였다.
  • 로드 밸런서의 동작 흐름은 다음과 같이 요약할 수 있다. 1)사용자가 단축 URL을 클릭한다. 2)로드밸런서가 해당 클릭으로 발생한 요청을 웹 서버에 전달한다. 3)단축 URL이 이미 캐시에 있는 경우 원래 URL을 바로 꺼내서 클라이언트에게 전달한다. 4)캐시에 해당 단축 URL이 없는 경우에는 DB에서 꺼낸다. DB에 없다면 사용자가 잘못된 단축 URL을 입력한 것이다. 5)DB에서 꺼낸 URL을 캐시에 넣은 후 사용자에게 반환한다.

마무리

더 고려해볼 사항은 다음과 같다.

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