Shortening Url Service Design

Similar Services

bit.ly, ow.ly, short.io

Service Key Point

1. 긴 url을 짧게 만들어 준다.
2. 짧은 url을 browser에 붙이면 긴 url로 redirection 시킨다.
3. 장치별 link를 최적화 가능하다.
4. 접근 url의 history를 분석가능하다.
5. AD에 해당 url을 붙임으로써 AD의 효용성을 분석할 수 있다.

요구사항 분석

기능 요구사항

• 긴 url을 짧고 unique하게 url로 제공 가능해야 한다.
• 충분히 복사 붙여넣기 등이 쉽게 될 수 있는 짧은 길이로 제공해야한다.
• 사용자가 short link를 접근 할 경우 original link로 redirect 시켜줘야 한다.
• 사용자가 필요할 경우 특수한 custom url을 제공 할 수 있어야 한다.
• 일정 시간이 지나거나 만기일이 지나면 해당 url은 사용할 수 없어야 한다.

비 기능 요구사항

• 시스템은 고가용(Highly Available) 해야한다. 본 시스템이 죽으면 다른 시스템으로 넘어가지 못하기 때문이다.
• URL redirection은 짭은 지연 시간(latency)내에 실시간으로 변화 가능해야 한다.
• 만들어질 url은 예측 가능하면 안된다.

추가 요구사항

• url별 redirection 분석이 가능해야 한다.
• REST APIs를 통해서도 접근 가능해야 한다.

 

용량 평가 및 제약 (Capacity Estimation and Constraints)

이 서비스는 write보다는 read의 발생 확률이 매우 높다.

이것을 1 : 100 (write : read)의 비율이라고 예상하자.

 

Traffic Estimates

한달에 5억 (500M) 개의 신규 url이 생성된다고 했을 때, Read 예상치는 

$$ 500억 = 100 * 5억 $$

 그럼 이것을 초당으로 나누어 보자.

$$ 500억 / 60초 / 60분 / 24시간 / 30일 = ~19,290 URLs/s $$

초당 20K/s 정도의 Transaction 발생이 가능하다.

 

Storage Estimates

매달 5억개의 신규 URL이 생성되고 이 URL을 5년 주기로 Storage에서 지운다고 하면

$$  300억(30 billion) = 5억 * 12개월 * 5년 $$

의 데이터를 유지 해야한다. 하나의 Url을 유지 하기 위한 Data row의 용량이 500bytes라고 했을 경우

$$ 15,000,000,000,000(15TB) = 300억 * 500 bytes $$

총 15TB의 Data를 유지 가능해야 한다.

 

Bandwidth Estimates

write 요청은 한달에 5억개 요청이 옮으로

$$  192/sec = 5억 / 30일 / 24시간 / 60분 / 60초 $$

초당 192개의 요청이 온다고 볼수 있다. 계산상 편의를 위해서 200/sec 가 온다고 할 경우 한번의 요청이 500B를 담고 있다고 하면, 

$$ 100 KB/s = 200 * 500 bytes $$

초당 100 KB/s 가 필요하다. Read는 이에 100배가 필요함으로

$$ 10,240,000 (~10MB/s) = 100KB * 100 $$

초당 10MB/s의 Band width가 필요하게 된다.

이것을 bit 단위로 변경을 하면

$$ 81,920,000 bit/sec $$

기가단위로 변경하면

$$ 10,240,000 Byte / 1024 * 1024 * 1024 $$

0.01 Gigabyte가 된다. 약 10 MB/s가 된다.

(기가 인터넷이 1,000,000,000 bit/sec니까 8로 나누면 125,000,000 byte/sec 이고 KB로 바꾸면 125,000 KB/sec이고 MB로 바구면 123 MB/sec이니까 shorturl 서비스는 upload 기준으로 가능할 것 같다.)

 

Memory Estimates

위에서 만든어진 5억개의 url이 다 자주 불리워질 이유는 없다. 80:20 Rule을 사용해서 가장 많이 불리워지는 20에 대해서는 cache 서버를 만들어서 즉각 반응 가능하게 만들어주자.

cache 서버는 일단위로 계산을 진행한다.

초당 20K/sec가 필요함으로

$$ 1,728B = 20K * 60 * 60 * 24 $$

이중에 20%만 cache가 필요 함으로

$$ 172GB ~= 1,728B / 5 * 500bytes $$

 

결론적으로 Summary는 다음과 같다.

신규 URL 생성	200/s (1%)
Redirection URL 횟수	20K/s (200 * 100)
Incoming Data	100KB/s (200*500bytes)
Outgoing Data	10MB/s (100KB * 100)
Storage for 5 years	15TB (300억 * 500B)
Memory for cache	172GB

 

API Design

핵심이 되는 API를 중점적으로 만들면 된다. SOAP이나 REST정의 하면 된다.

createURL(api_dev_key, original_url, custom_alias=None, User_name=none, expire_date=none)

파라메터 설명

input

• api_dev_key : 등록된 사용자의 API key, 어떤 사용자가 url이 많이 불리웠을 때 quota나 throttle 처리를 위해서 유용하다.
• original_url : 실제 redirection이 될 URL
• custom_alias : 개발자가 필요할 경우 Optional하게 넣을 수 있음
• expire_date : shortened URL이 expire되는 시점

output

• url_key : 성공하면 발행되는 key, 만약 0이하이면 error code

 

 deleteURL(api_devkey, url_key)

• api_devkey : account에 연동된 key
• url_key : createurl시 받은 성공 키

 

Abuse를 어떻게 대처 할 것인가?

api_devkey의 api 요청횟수를 초당 제한 시키고, 일정 횟수 이상 초과되면 Blocking시킴

 

Database Design

우리가 위의 디자인을 진행 함을로써 다음과 같은 내용이 필요 하다는 것을 알 수 있었다.

• 300억(30 billion)의 row를 사용하는 Table을 유지함
• 각 Row는 500bytes를 사용함
• 각 Row는 서로간의 관계가 없음
• 주로 Read 용도의 서비스임

두개의 Table로 설계가 가능함, URLs 와 User의 관계로 나타낼 수 있다.

SQL을 사용해도 괜찮긴 하지만 데이터 구조가 단순하고 굉장히 많은 양의 데이터를 저장해야 함으로 NoSQL을 고려해 보는 것이 적합하다.

 

기본 System 기능 Design and Algorithm

가장 기본적인 기능은 주어진 url을 어떻게 6자리에서 8자리 사이의 값으로 짧게 표현 할것인가? 이다.

쉽게는 Hash알고리즘을 사용하면 되는데 가장 유명한 알고리즘은 MD5 or SHA0, SHA1, SHA-256 등이 된다.

이중에 가장 짧은 Algorithm을 구해야 하는데 MD5의 경우 128bits의 output을 갖는다.

https://en.wikipedia.org/wiki/Template:Comparison_of_SHA_functions

url을 표시하는 base64는 한자를 6bit로 표현함으로

https://en.wikipedia.org/wiki/Base64

$$ 21 chars = 128/6 $$

21자 이상 표현됨으로 적합하지 않다. SHA 알고리즘은 더욱 그러하다.

참고로 base64는 binary 값을 64개의 char중 하나로 선택함으로써 url에 문자로 표시하는 형식이다.

우리는 약 300억개의 길이만 필요함으로 $  68 billion = 64^6 $ 최대 6문자 정도면 목표를 달성 가능한 상태이다.

그런데 이런 hashing 처리 방법은 다음과 같은 문제를 야기하게 된다.

• 사용자별로 동일한 URL을 넣으면 동일 shorten url 결과 값을 얻게 된다.
• 동일 url에 파라메터를 encoding해서 추가 하면 결과는 다르지만 같은 url을 pointing하게 됩니다.
  • https://enumclass.tistory.com/211#%EC%9A%94%EA%B5%AC%EC%82%AC%ED%95%AD
  • https://enumclass.tistory.com/211#요구사항

다른 방법은 사용자의 key를 추가하는 것이다.

• https://enumclass.tistory.com/211#요구사항?userkey=username

이런식으로 url을 변경심킴으로써 특수성을 만족 시키게 할 수 있다.

다시 원론으로 돌아와서 Unique key를 어떻게 6자리 이내로 발번 가능한가?

미리 6자리 키를 Table로 만들어 놓는 것도 좋은 방법 이다.

Short Table의 크기는 Base64를 기준으로 최대 6자의 키를 생성할 수 있다고 보면 

글자 하나를 계산하기 편하게 1byte(6bit이지만)라고 가정하면 

$$  412GB = 6byte * 64^6B $$

의 추가 Storage가 필요하게 된다.

Short Table을 사용할때 주의할 점은 다음과 같다.

• 단일 실패 지점이다. 이것이 죽으면 시스템이 죽는다 -> Fail-over 구조 고려가 필요함
• Short Table을 캐슁할수 있는가? 가능은 하지만 Sync가 물리 DB와 완전하다는 전제이다. 캐슁처리 되고 물리 DB에 write되지 않는다면 문제가 발생할 수 있다.
• 키 조회 방법은? DB에 key가 있으면 Http 302 redirection을 이용해서 페이지를 변환하고, 없는경우 Http 402를 발생 시키거나 최초 click된 link가 있는 url로 history back 시킵니다.

 

Data의 분할 및 복제

범위 기반 Partitioning

URL의 uniqueId를 이용해서 DB Partitioning이 가능하다.

예를 들어서 a,b로 시작하는 id는 1번 DB, cd는 2번 DB 등으로 range를 분리해 주면 된다.

문제점은 DB별 Size 불균형이 생길 수 있다. 예를 들자면 'e'로 시작하는 글자가 'z'로 시작하는 글자보다 많을 수 있다.

 

Hash 기반 Partitioning

uniqueId를 발행할때 row 객체의 hashing을 통해서 무작위 처리하게 된다면 DB 별 Size 불균형은 발생하지 않습니다.

이와 같은 방법으로 Consistent hashing기법을 일반적으로 많이 사용하게 됩니다. 이경우 Data를 잃는다고 해도 다시 Recover 가능합니다.

 

Cache

URL을 기반으로 Back-end Server에서 해당 정보를 처리하기 전에 Cache를 통해서 우선 처리 하는 방법이다.

앞아서 약 20%를 캐슁 처리 할 경우의 메모리양에 대해서 알아 보았다.

$$ 172GB ~= 1,728B / 5 * 500bytes $$

약 172GB의 Cache 메모리가 필요하다.

Cache에 있는 URL을 유지하는 정책은 LRU(Least Recently Used)를 사용해서 항상 최신 정책을 유지 시킬수 있다.

(Linked Hash Map을 통해서 이를 만족 시킬 수 있다고 한다. Hash Map에 Order 개념을 넣은 것인데 LRU에서 사용되는 줄은 몰랐다 차후에 알아보고 업데이트 하겠다.)

만약에 Cache 서버에 대상 url이 없다면 back-end 에서 DB를 찾게 되고 궁극적으로 Cache서버들은 업데이트 되게 된다.

 

Load Balancer

Load Balancer를 다음 위치에 둠으로써 시스템 효율성을 높힐 수 있다.

• Client <-> Application Server
• Application Server <-> Database
• Application Server <-> Cache Server

LB서버의 경우 일반적으로 Round Robin을 사용하게 되는데, 들어오는 순서에 따라서 다음, 다음 이런식으로 무조건 Traffic을 날리게 된다. 만약에 이번에 Traffic을 날려야 하는 Servier가 아직도 Busy 상태라면 이것을 알아채지 못하고 그냥 새로운 Traffic을 던지게 된다.

 

Purging or DB cleanup

데이터를 쌓았으면 삭제하는 정책도 필요하다.

본 서비스는 기본적으로 다음의 경우 purging이 가능하다.

• Expired Date가 지났다.
• User가 삭제 되었다

DB cleanup이 언제 일어날지는 다음과 같이 고려해 볼수 있다.

• 주기적으로 Expired Date 확인 및 삭제
• Expired Date가 지났는데 Url 접근
• 삭제와 동시에 short Table에서 해당 url 연결고리 삭제
• 일정 기간동안 접속이 없는 Url 삭제

 

측정 (Telemetry)

Side-Car 패턴을 이용한 API 통계 시스템을 사용해서 URL별 사용량 측정이 가능하다. 

Splunk나 Logstash등 다양한 솔루션이 존재 한다.

 

권한

만약에 shorten url에 개인별 권한을 두고 특정 user만 접근 가능하게 하고싶은 경우 url에 권한 수준을 공개 또는 비공개를 저장함으로써 특정 user로 로그인 된경우만 해당 url을 접근 가능하게 할 수 있습니다.

사용자 권한이 없는경우 http 401 unauthorized error를 발행 시킴으로서 접근을 불가하게 만들 수 있습니다.