URL Shortening service

03 February 2020 - 12 mins read time
Tags: System Design

Tiny와 같은 URL 단축 서비스를 설계하기. 이 서비스는 긴 URL로 redirection되는 짧은 aliaces를 제공한다.

URL Shortening이 필요한 이유.

URL Shortening은 긴 URL에 대한 짧은 aliaces를 만드는데 사용된다. 우리는 이 단축된 aliases를 “short link”라고 부른다. 사용자는 이러한 Short link를 누르면 원래의 URL로 redirection이 된다. Short link는 보여줄때, 출력할때 메시지를 보낼때 혹은 트위터를 할때 많은 공간을 절약해준다. 게다가 사용자들은 짧은 URL을 잘못 입력하는 경우가 있다.

예를들어, 우리는 아래의 페이지를 TinyURL을 통해 줄일경우 :

https://minsuking.github.io/blog/Key-Characteristics-of-Distributed-Systems

우리는 이런 결과를 얻을것이다.

http://tiny.cc/scdijz

위를 보게되면 Shortened URL의 경우 실제 URL의 크기에 1/3 정도다.

URL Shortening은 기기간의 링크를 최적화시키고, Audience와 Campaign performance를 분석하기위한 개별 링크를 추적하고, 연결되어있는 원래의 URL을 숨기기위해 사용된다.

시스템의 요구사항 및 목표

  • 면접 시작할 때 요구사항을 명확하게 해야한다. 면접관이 염두에 두고있는 시스템의 정확한 범위를 찾기위해 반드시 질문을한다.

URL Shortening system은 다음 요구 사항을 충족 시켜야 한다.

기능 요구 사항

  1. URL이 주어지면, 이 서비스는 그것을 짦고 Unique한 alias를 만들어야한다. 이것을 위에서 이야기했던 Short link라고 한다. 이 링크는 쉽게 복사하고 붙여넣을 수 있을 정도로 짧아야 한다.

  2. User들이 Short link에 접근 할때, 이 서비스는 원래의 링크로 redirect를 해줘야 한다.

  3. User는 선택적으로 자신의 url에 대한 사용자 정의 Short link를 선택 할 수 있어야한다.

  4. 링크는 표준 기본 시간대가 지나면 만료된다. User는 만료 시간을 지정 할 수 있어야 한다.

비 기능 요구 사항

  1. 시스템의 가용성이 높아야 한다. 이 시스템이 중단된다면 모든 url 서비스의 url redirection이 실패하기 때문이다.

  2. url redirection은 최소의 지연시간으로 실시간으로 이뤄져야한다.

  3. Shortened link는 추측될 수 없어야 한다.

확장 요구 사항

  1. 분석이 가능해야한다. 예를 들어 redirection 횟수

  2. 이 서비스는 REST API를 통해 접근 가능해야 한다.

시스템 API

일단 요구사항을 확정하고 나서 API를 정의하는 것은 항상 옳은 생각이다. 이는 시스템에서 예상되는 사항을 정확하게 명시해야한다.

우리는 SOAP 또는 REST API를 통해 서비스의 기능을 노출시킬 수 있다. 다음은 URL 생성 및 삭제를 위한 API 정의이다.

createURL(apiDevKey, originalUrl, customAlias=None, userName = None, expireDate=None)

Parameters:
apiDevKey(String) : 등록된 계정의 개발자 API키, 이것은 할당된 할당량에 기초하여 User를 Control 하는것에 사용될 것.
originalUrl : 원본 url
customAlias=None : url에 대한 사용자의 지정키
userName = None : 인코딩에 사용될 선택적 사용자 이름
expireDate=None : 단축된 url의 만료 날짜

Returns: (String)
성공적으로 Insert를 했다면 단축 URL을 리턴한다. 그렇지 않으면 error code를 반환한다. 

deleteURL(apiDevKey, urlKey)

여기서 urlKey는 검색할 단축 url을 나타내는 문자열이다. 삭제에 성공하면 url 제거에 대한 성공메시지가 반환된다.

우리는 어떻게 abuse를 막고 예방할 수 있을까? 악의적인 user는 현재설계되어 있는 모든 url키를 소비함으로써 이 서비스를 망하게 할 수 있다. 남용 방지를 위해 apiDevKey를 통해 사용자를 제한 할 수 있다. 각 apiDevKey는 일정기간당 특정 url생성 및 redirection 수로 제한 될 수 있다.

데이터베이스 디자인

인터뷰 초기단계에서 DB 스키마를 정의하는것은 다양한 요소들 간의 데이터 흐름을 이해하는 데 도움이 될 것이다.

저장할 데이터의 특성에 대한 몇 가지 관측

  1. 우리는 수십억 개의 기록들을 보관해야 한다.
  2. 각각의 Object는 용량이 작다.(1K 미만)
  3. 어떤 사용자가 url을 만들었는지 저장하는것을 제외한 레코드 사이에는 아무런 relationships가 없다.
  4. 이 서비스는 읽을때 무겁다.(read-heavy)

데이터 베이스 스키마:
우리는 두 개의 테이블이 필요할 것이다. 하나는 URL 매핑에 관한 정보를 저장하기 위한 테이블이고, 다른 하나는 짧은 링크를 만든 사용자의 데이터를 저장하기 위한 테이블이다.
Schema

어떤 종류의 데이터베이스를 사용해야할까? 우리는 수십억 개의 row를 저장할 것으로 예상되며, Object간의 relationshipis를 사용할 필요가 없기 때문에 DynamoDB, Cassandra 또는 Riak같은 NoSQL 저장소가 좋은 선택이다. NoSQL의 경우 확장하기가 더 편하다.

기본적인 시스템 디자인 그리고 알고리즘

우리가 여기서 해결하고자 하는 문제는 받은 url에 대한 짧고 고유한 키를 생성하는 것이다.

TinyURL을 예제를 보자면 단축 URL은 http://tiny.cc/scdijz 이다.그리고 이 URL의 마지막 6자리의 문자는 우리가 생성하고자하는 짧은 키다.

a. 실제 URL 인코딩 #
주어진 URL의 고유한 해시(예: MD5 또는 SHA256 등)를 계산할 수 있다. 그런 다음 표시를 위해 해시를 인코딩할 수 있다. 이 인코딩은 base36([a-z ,0-9]) 또는 base62([A-Z, a-z, 0-9])일 수 있으며, ‘+’와 ‘/’를 추가하면 Base64 인코딩을 사용할 수 있다. 합리적인 질문은, 짧은 키의 길이가 얼마야 되어야 하는가? 6, 8, 10자?

base64 인코딩을 사용하면 6자 길이의 키를 사용할 경우 64^6 = 687억 개의 문자열이 발생할 수 있다.
base64 인코딩을 사용하면 8자 길이의 키를 사용하면 64^8 = 281조 개의 문자열이 발생할 수 있다.

68.7B의 고유한 문자열을 사용하면 6개의 문자 키가 우리 시스템에 충분하다고 가정해 봅시다.

우리가 MD5 알고리즘을 해시함수로 사용하면 128비트 해시 값이 나올 겁니다. base64 인코딩 후에는 21자를 초과하는 문자열을 얻을 수 있다(각 base64 문자는 해시 값의 6비트를 인코딩하므로). 이제 우리는 짧은 키당 8자밖에 쓸 수 없는 공간이 있는데, 그렇다면 우리는 어떻게 우리의 키를 선택할 것인가? 열쇠는 처음 6자(또는 8자)를 가져갈 수 있다. 이 경우 키 중복이 발생할 수 있으며, 이를 해결하기 위해 인코딩 문자열에서 다른 문자를 선택하거나 문자를 교환할 수 있다.

우리의 솔루션 문제와 다른점은 무엇인가? 인코딩 방식에는 다음과 같은 문제가 있다.

  1. 여러 사용자가 동일한 URL을 입력하면 동일한 단축 URL을 얻을 수 있는데, 이는 허용되지 않는다.
  2. URL의 일부가 URL 인코딩된 경우(예: http://www.educative.io/distributed.php?id=design) 그리고 http://www.educative.io/distributed.php%3Fid%3D 설계는 URL 인코딩을 제외하고 동일하다.
    문제 해결 방법: 입력 URL마다 시퀀스 번호가 증가하여 고유하게 만든 다음 해시를 생성할 수 있다. 하지만 우리는 이 시퀀스 번호를 데이터베이스에 저장할 필요가 없다. 이 접근방식에서 발생할 수 있는 문제는 계속 증가하는 시퀀스 번호일 수 있다. 넘칠 수 있을까? 시퀀스 번호의 증가는 또한 서비스의 성능에 영향을 미칠 것이다.

또 다른 해결책은 입력 URL에 사용자 ID(Unique해야 함)를 추가하는 것이다. 그러나 사용자가 로그인하지 않은 경우 고유 키를 선택하도록 사용자에게 요청해야 할 것이다. 이후에도 이슈가 생기면 Unique 열쇠를 얻을 때까지 키를 계속 만들어 내야 한다.

shorturl

b. 키를 오프라인으로 생성 #
사전에 임의의 6개의 문자열을 생성하여 데이터베이스에 저장하는 독립형 KGS(Key Generation Service)를 가질 수 있다. (Key-DB라고 부르기) URL을 단축하고 싶을 떄마다, 우리는 이미 생성된 키 중 하나를 가지고 사용하는것이다. 이 방법은 사물을 상당히 단순히, 그리고 빠르게 만드는 것이다. 우리는 URL을 인코딩하지 않을 뿐만 아니라 중복이나 충돌에 대한 걱정할 이유가 없다. KGS는 key-db에 삽입된 모든 키가 고유한지 확인하여야한다.

concurrency가 문제를 일으키는가? 키를 사용하는 즉시, 재사용 할수 없도록 데이터베이스에 표시를 해야한다. 키를 동시에 읽는 서버가 여러대 있는 경우, 우리는 두대 이상의 서버가 데이터베이스에서 동일한 키를 읽으려고 시도하는 시나리오를 얻을 수 있다. 이럴경우 이런 concurrency 문제를 어떻게 해결할 수 있을까?

서버는 KGS를 이용하여 데이터베이스에서 키를 읽거나 표시를 할 수 있다. KGS는 아직 사용하지 않은 키(Not used yet)와 사용된 키(Used) 두개의 테이블을 사용하여 키를 저장한다. KGS는 서버 중 하나에 키를 주는 즉시, Used 테이블로 키를 옮길 수 있다. KGS는 서버가 필요로 할 때마다 신속하게 제공할 수 있다록 항상 일부키를 메모리에 보관할 수 있다.

단순성을 위해 KGS는 메모리에 일부 키를 로드하는 즉시 Used 테이블에 키를 옮길 수 있다. 이렇게 하면 각 서버가 고유한 키를 갖게 된다. 어떤 서버에 모든 로드된 키를 할당하기 전에 KGS가 죽는다면, 우리는 그 키를 낭비하게 될 것이다. 이것은 우리가 가지고 있는 엄청난 수의 키를 고려할 때 받아들일 수 있는 수준이다.

KGS도 여러 서버에 같은 키를 주지 않도록 해야 한다. 이를 위해 키를 제거하고 서버에 제공하기 전에 키를 잡고 있는 데이터 구조를 synchronize(or get a lock on)해야한다.

Key-DB 크기는? Base64 인코딩으로 68.7억개의 고유한 키를 생성 할 수 있다.하나의 alpha numeric문자를 저장하기 위해 하나의 바이트가 필요한 경우, 밑의 용량만큼 저장 가능하다.

6(키당 문자수) * 68.7억개(특수 키) = 412GB

KGS는 하나의 실패점인가? 그렇다. 이것을 해결 하기위해 우리는 KGS의 대기 복제품(standby replica)을 가질 수 있다. 주 서버가 사망할때 마 대기서버가 키를 생성하고 제공할 수 있다.

각 앱 서버가 key-DB에서 일부키를 캐시할 수 있을까? 가능하다. 캐시는 확실히 속도를 낼수있기 때문이다. 이럴 경우, 모든 키를 소비하기 전에 어플리케이션 서버가 종료된다면, 우리는 결국 그 키를 잃게 될 것이다. 68억개의 고유 6자키를 가지고 있기때문에 이것을 appcetable 할 수 있다.

키 조회를 어떻게 할 것인가? 데이터베이스에서 키를 검색하여 전체 URL을 가져올 수 있다. DB에 있는 경우 Request의 “Location”필드에 저장된 URL을 전달해 “HTTP 302 Rediect” 상태를 브라우저로 다시 전송한다. 시스템에 해당키가 없다면 “HTTP 404 Not Found”상태를 발생시키거나 사용자를 다시 홈페이지로 redirection을 시킨다.

우리는 costom aliase들에 대해 크기 제한을 가해야 하는가? 우리 서비스는 custom aliases을 지원한다. 사용자는 원하는 ‘키’를 선택할 수 있지만, 사용자 지정 alias를 제공하는 것은 의무적인 상황은 아니다. 그러나 우리가 잉ㄹ관된 URL 데이터베이스를 갖도록 하기위해 사용자 지정 alias 에 대한 크기 제한을 두는 것이 합리적이고 바람직할 때가 많다. 사용자가(위의 데이터베이스 스키마가 반영된) 고객 키당 최대 16자를 지정할 수 있다고 가정해보자.)

KeySErver

데이터 파티셔닝 및 복제

DB를 Scale out하기위해선, 수억개의 URL정보를 저장할 수 있도록 분할(partitioning) 해야한다. 우리는 우리의 데이터를 서로 다른 DB 서버로 나누고 저장할 수 있는 방법을 생각해야 한다.

범위 기반 파티셔닝 우리는 Hash key의 첫 문자를 기반으로 URL을 별도의 파티션에 저장할 수 있다. 따라서 우리는 문자 ‘A’(혹은 ‘a’)로 시작하는 모든 URL을 하나의 파티션에 저장하고, 문자’B’로 시작하는 URL을 다른 파티션 등에 저장한다. 이러한 방식을 범위 기반 파티셔닝이라고 한다. 우리는 심지어 덜 자주 발생하는 특정문자를 하나의 데이터베이스 파티션에 결합할 수 있다. 항상 예측 가능한 방식으로 URL을 저장 및 찾을 수 있도록 정적 분할 방식을 마련해야한다.

이 접근방식의 주요 문제는 불균형한 DB서버로 이어질 수도 있다는 것이다. 예를 들어, 우리는 문자 ‘E’로 시작하는 모든 URL을 DB파티션에 넣기로 결정하지만, 나중에는 ‘E’로 시작하는 URL이 너무 많다는 것을 알게된다

Hash 기반 파티셔닝 이 계획에서는, 우리가 저장하고 있는 Object의 해시를 가져온다. 그런 다음 Hash를 기반으로 사용할 파티션을 계산한다. 우리의 경우에는, 우리는 데이터 객체를 저장하는 파티션을 결정하기 위해 ‘Key’또는 short link의 해시를 이용 할 수 있다.«br>

우리의 해싱 기능은 URL을 무작위로 다른 파티션으로 배포할 것이다.(예를들어 우리의 해싱 기능은 항상 [1-256]사이의 숫자에 Key를 매핑할 수 있다.) 이 숫자는 우리의 Object를 저장하는 파티션을 나타낼 것이다.

이러한 접근방식은 여전히 Oveerloaded 파티션으로 이어질 수 있고, 일관된 해시를 사용하여 해결 할 수 있다.

Cache

우리는 자주 접속하는 url을 cache할 수 있다. 우리는 Memcached와 같은 일부 규격된 솔루션을 사용할 수 있는데, 이것은 각각의 Hash로 전체 URL을 저장할 수 있다. backend storage를 사용하기 전에 Application Server는 Cache에 원하는 URL이 있는지 신속하게 확인 할 수 있다.

Cache memory는 얼마나 가져야 할까? 우리는 일일 트래픽의 20%로 시작할 수 있고, 클라이언트의 사용 패턴에 따라 필요한 Cache server 를 적용할 수 있다. 위에서 추정한대로 우리는 일일 트래픽의 20%를 cache하기 때문에 170GB의 메모리가 필요하다. 현재 우리는 256GB의 메모리를 충분히 가질 수 있기 때문에 우리는 모든 Cache를 하나의 기계에 쉽게 넣을 수 있다. 혹은, 우리는 이 모든 hot URL을 저장하기 위해 두 개의 작은 서버를 사용할 수 있다.

어떤 cache 제거 정책이 우리의 요구에 가장 적합할까? cache가 가득 차 있고 최신 혹은 인기있는 URL 링크로 바꾸려면 어떻게 해야할까? 최근에 사용한것 (Leas Recently Used, LRU)는 우리 시스템에 합리적인 정책이 될 수 있다. 이 정책에 따르면, 우리는 가장 최근에 사용하지 않은 URL을 먼저 폐기한다. 우리는 linkedhashmap 이나 비슷한 데이터 구조를 사용하여 URL과 해시를 저장할 수 있는데, 이것은 또한 최근에 접속한 URL을 track할 것이다.

효율성을 더욱 높이기 위해서는 caching server들을 복제하여 부하를 분산시킬 수 있다.

각 Cache 복제본을 없데이트하는 방법은 무엇인가? Cache miss가 있을 때마다, 우리의 서버는 backend database에 접속할 것이다. 이런 상황이 나올때마다 Cache를 업데이트 하고 모든 cache 복제본에 새로운 항목을 전달할 수 있다. 각 복제본들은 새 항목을 추가하여 Cache를 업데이트 할 수 있다. 이미 해당 항목이 있으면 이 항목에 대해서 무시 할 수가 있다.

cache

Load Balancer (LB)

시스템의 세 곳에 로드 밸런싱을 추가할 수 있다.

  1. Clients와 Application servers 사이
  2. Application servers와 Database servers 사이
  3. Application servers와 Cache servers 사이

처음에는 수신 요청을 backend servers 사이에 균등하게 배분하는 단순한 Round Robin 방식을 사용할 수 있었다. 이 LB는 구현이 간단하며 overhead를 도입하지 않는다. 이 접근법의 또 다른 장점은 서버가 정지되었을 경우, LB는 서버를 rotation에서 빼내고 그쪽으로 트래픽 전송을 중단한다는 것이다.

Round Robin LB의 문제는 서버 부하(server load)를 고려하지 않는다는 것이다. 서버에 과부하가 걸리거나 속도가 느린 경우 LB는 해당 서버에 대한 새 요청 전송을 중지하지 않는다. 이를 처리하기 위해 backend server의 부하에 대해 주기적으로 queries하고 이를 기반으로 트래픽을 조정하기 보다 지능적인 LB솔루션을 배치할 수 있다.

제거 또는 DB CleanUp

항목들이 영구적으로 유지되어야 하는가? 아니면 삭제되어야 하는가? 사용자가 지정한 만료 시간에 도달하면 링크는 어떻게 처리 해야 하는가?

만약 우리가 그것들을 제거하기 위해 만료된 링크를 적극적으로 검색하기로 선택했다면, 그것은 우리의 데이터베이스에 많은 부하를 가할 것이다. 대신, 우리는 천천히 만료된 링크를 제거하고 게으른 DB정리를 할 수가 있다. 일부 만료된 링크는 더 오래 살 수 있지만 사용자에게 반환되지 않을지라도, 우리의 서비스는 만료된 링크만 삭제되도록 할 것이다.

  • 사용자가 만료된 링크에 액세스하려고 할 때마다 링크를 삭제하고, 사용자에게 오류를 반활할 수 있다.
  • 별도의 CleanUp 서비스를 주기적으로 실행하여 만료된 링크를 당사의 storage 및 cache에서 제거 할 수 있다. 이 서비스는 반드시 매우 경량이어야 하며 사용자 트래픽이 적을 경우에만 실행되도록 예약 할 수 있다.
  • 각 링크에 대한 기본 만료 시간(예를들어 2년)을 가질 수 있다.
  • 만료된 링크를 제거한 후 키를 다시 Key-DB에 넣어 재사용할 수 있다.
  • 우리가 어느 정도 오랫동안 방문하지 않은 링크를 제거해야 할까? 예를들면 6개월? 이런 까다로운 결정을 해야한다. Storage가 점점 싸지기 때문에, 우리는 영원히 계속 유지하기로 결정 할 수 있다.

Cleanup Service

원격 측정

짧은 URL을 몇 번 사용했는지, 사용자 위치는 무엇이었는지? 등 이 통계를 어떻게 저장하면 좋을까? 각 보기에서 업데이트 되는 DB 행의 일부인 경우 인기 있는 URL이 많은 concurrent requests충돌하면 어떻게 될까?

추적할 가치가 있는 통계 : 방문자의 국가, 접속 날짜 및 시간, 페이지가 액세스된 곳에서 클릭, 브라우저 또는 플랫폼을 참조하는 웹페이지

보안 및 사용권한

사용자가 개인 URL을 만들거나 특정 사용자 집합이 URL에 액세스 하도록 허용할 수 있는가?

각 URL을 데이터베이스로 하여 권한 수준을(public/private) 저장할 수 있다. 또한 사용자를 저장하기 위한 별도의 테이블을 만들 수 있다. 특정 URL을 볼 수 있는 권한이 있는 UserIds. 사용자가 권한이 없어 URL에 액세스하려고 하면 오류(HTTP 401)를 다시 보낼 수도 있다. 우리가 우리의 데이터를 Cassandra와 같은 NoSQL wide-column 데이터베이스에 저장하고 있기 때문에, 사용 권한을 저장하는 테이블의 Key는 ‘Hash’ (또는 KGS가 생성한 ‘Key’)가 될 것이다. Columns에는 UserId들이 저장될것이고 그 ID들은 URL을 볼 수있는 권한이 있는 ID들이다.