Tiny URL 설계 레퍼런스

Tiny url 로 기존 url을 짧게 디자인하는 시스템을 만든다고 생각해보자. 주로, 카카오톡의 오픈 채팅 링크 생성 등이 tiny url로 shortening 되는 시스템이라고 볼 수 있다. 각설하고, 아래와 같은 flow로 시스템 디자인에 대한 생각을 해보자.

1. 왜 우리가 URL Shortening 이 필요할까? (Why do we need it?)
   • URL shortening은 long URLs 의 alias 를 만들기 위해 사용된다. Short link라고도 불리움.. short link를 타고 가면, original link로 redirect 된다. URL Shortening 을 쓰는 이유는, 우선 짧으니까 display, print, message 등에서 공간을 아낄 수 있음. 그리고 또한, 디바이스들간 link를 최적화 하는데 사용되고, 개인의 링크들을 트래킹할 수 있다 -> 캠페인 성과 측정이나, 유저들을 분석할 수 있게 됨.
2. 요구사항과 시스템의 목표(Requirements and Goals of the system)
   • URL Shortening 시스템은 아래와 같은 기능적/비기능적 요구사항을 충족해야 한다고 가정하자.
     • 기능적인 요구 사항
       • 주어진 URL 에 대해 더 짧고 unique alias 된 link를 만들어야 한다.
       • 유저들이 short link에 접근할 때, 서비스가 오리지널 링크에 리다이렉트 되어야 한다.
       • 유저들이 선택적으로 custom short link를 고를 수 있도록 한다.
       • 링크는 스탠다드 디폴트 timespan 이후에 만료될 것이다. 유저는 또한 만료 시간을 구체적으로 설정할 수 있다.
     • 비기능적인 요구 사항
       • 시스템은 Highly Available 해야만 한다. 왜냐하면 서비스가 다운되면 모든 URL Redirections 가 fail이 시작될 것이기 때문에 매우 크리티컬한 영향을 줌..
       • URL 리다이렉션은 최소한의 Latency 로 실시간으로 발생해야한다.(short link 누르자마자 빨리 들어가져야하니까..)
       • Shortened links 는 not guessable(not predictable)해야 한다.
     • 확장된 요구 사항
       • Analytics: 얼마나 많은 리다이렉션이 발생하는지를 분석할 만하 로깅 작업?
       • 우리 시스템이 다른 서비스에 의한 REST APIs 를 통해서도 접근 가능해야 하는지?
3. 수용량 예측과 제약 사항(Capacity Estimation and Constraints)
   • 기본적으로 Short url은 Read Heavy 할 것이다. New Url Shortening 생성을 요청하는 횟수에 비해 Read(즉, short link를 타고 Redirect 요청 횟수) 가 100:1 이라 가정하자. 즉, read & write 비중이 100:1 이라 가정하자.
     • Traffic Estimates: url shortening 생성이 한달에 5억 건, redirection 은 *100인 동기간 대비 500억건이라고 가정하자. (100 * 500M = 50B) 단위시간당 새 url 생성 요청 초당 write 쿼리는 500M / (30days * 24hr * 3600sec) = 200 URLs /sec 정도이고, 초당 read 쿼리는 200 * 100 = 20K/ sec 정도이다.
     • Storage Estimates: 모든 URL Shortening 요청을 5년 동안 저장해야 한다고 가정하자. 그럼 500M * 5yr * 12 month = 30B 건(300억 건) 을 저장해야 한다. 그리고, 각 데이터 오브젝트의 용량은 500bytes라고 가정하면, 30B * 500 bytes = 15TB
     • Bandwidth Estimates: 먼저, write request는 매초 당 200개의 short url 생성 요청이 있기 때문에, 초당 200 * 500 bytes = 100KB/s 의 Bandwidth가 예상 된다. 그다음 read request는 200 * 100 * 500 bytes = 10MB/s 이 예상됨
     • Memory Estimates: 만약 자주 접근되는 hot urls 을 우리가 캐싱하기를 원한다면, 얼마나 많은 메모리가 필요할까? Hot url이 8:2 법칙을 따른다면, (즉, 20%의 상위 hit url이 전체 url read의 80%를 차지한다고 가정) 20% url이 80%의 트래픽을 발생 시키는 셈이다. 그렇기 때문에 url 의 20%를 이런 hot url로 캐싱을 해둘 수 있다.현재 단위 초 당 20K read request가 오므로 하루 당 약 17억건 발생한다. 이 중 20%만 캐싱해두기 위해 필요한 용량은 17억(1.7B) * 20% * 500 bytes = 약 170GB다. 중복된 url 요청이 발생하기 때문에 실제 캐싱 용량은 170g 보다 더 적을 것이다.
     • High level Estimates: 즉, 500M new URLs per month, 100:1 read write ratio에서 추론해 볼 때, 하이레벨 단에서의 총 측정치는 아래와 같다.
       • New URLs: 200/s
       • URL Redirections: 20K/s
       • Incoming Data: 100KB/s
       • Outgoing Data: 10MB/s
       • Storage for 5 years: 15TB
       • Memory for Cache: 170GB
4. System APIs
   • 우리가 요구사항 파악을 완료하면, 이제 system api를 정의해야 한다. 시스템 인터페이스 api 는 시스템으로부터 기대하는 바를 명시적으로 서술해야 한다.
   • 아래와 같이 api의 정의를 해보자.
     • createURL(api_dev_key, original_url, custom_alias=None, user_name=None, expire_date=None)
     • parameters
       • api_dev_key(string): 등록된 계정의 api 개발자 키다. 이 키를 사용해 url을 만들기도 하고, 유저가 무분별하게 url을 생성하는 것을 제한할 수도 있을것이다.
       • Original_url(string): shorten하고자 하는 original URL이다.
       • custom_alias(string): Optional Custom Key for the URL
       • user_name(string): 인코딩에 사용되는 Optional 유저네임이다.
       • Expire_date(string): optional Expiration Date for the short url
     • Returns : (string)
     • deleteURL(api_dev_key, url_key)
   • Successful insertion 시, 생성 성공한 short url 을 리턴 받는다.
   • Delete success 시, ‘URL Removed’를 리턴 받는다.
   • 어떻게 어뷰징을 감지하고 방지할 것인가?
     • Api_dev_key 를 통해서 유저들의 url 생성 max 횟수를 제한을 건다. Api_dev_key당 redirections 횟수도 제한을 건다.
5. Database Design
   • 먼저 우리가 저장할 데이터를 생각해보자.
     • 수십억 데이터를 저장해야 함
     • 각 데이터 object의 용량은 작음(less than 1K)
     • 기록들 간 relationships 없음
     • Read-Heavy
   • 위를 바탕으로 데이터베이스 스키마를 정해보자.
     • URL Table
       • PK: Hash(varcher(16))
       • originalURL(varcher(512))
       • CreationDate(datetime)
       • ExpirationDate(datetime)
       • UserId(int)
     • User Table
       • PK: UserId(int)
       • Name(archer(20))
       • Email(varchar(32))
       • CreationDate(datetime)
       • LastLogin(datetime)
   • 즉 두 개의 테이블이 필요하다. 하나는 URL 매핑 정보를 담을 테이블, 또 하나는 어떤 유저가 short link를 만들었는지 정보를 담을 테이블이다.
   • 그럼 무슨 데이터베이스를 써야 할까? -> 수십억의 rows를 쌓아야 하고, 데이터간 relationships 관계는 필요 없으므로 NoSQL을 쓰자. 왜냐하면 NoSQL은 스케일이 쉽다.
6. Basic System Design and Algorithm
   • 우리가 여기서 해결하고자 하는 것은 short 하고, 주어진 original url에 대해 unique key를 생성하는 것이다. http://tinyurl.com/jlg8zpc 와같이 마지막 뒤 7자리 캐릭터가 우리가 만들고자 하는 short key이다. 이와 관련해 2가지 솔루션을 생각해보자.
   • Encoding Actual URL: 이제 원 URL 을 인코딩한 후 , Unique 해쉬를 만들어야 함
     • 우리는 주어진 URL 로부터 unique hash를 계산할 수 있다. (MD5, or SHA256 등으로) 그럼 short key의 길이는 몇이 좋을까?
     • Base64 encoding을 사용한다고 가정했을 때, short key의 길이가 이면 64^6 = 약 68.7B 가능한 unique key를 생성할 수 있고, 8로 하면 64^8 = 약 281 trillion 가능한 unique string을 만들 수 있을 것이다. 근데, 68.7B로도 충분하므로, 6으로 하자.
     • 근데 여기서 주의할 점이 있음
       • 여러명의 유저가 같은 URL 로 tiny URL 을 만들고자 한다면? -> 이렇게 되면, 같은 URL 에 대해 인코딩 결과 값도 같으므로, 만들어진 Hash도 동일하게 되고, 이는 각 만드는 유저마다의 Unique Hash 값을 못갖는다. (즉, 문제가 생김)
       • 해결책으로는 input url 마다 ever increasing number를 하나 덧붙이는 것이다. 하지만, 이 역시 서비스 퍼포먼스에 영향을 준다.(Hash 연산이 좀 더 오래걸리겠지?)
       • 또다른 해결책으로는 생성하는 주체 유저의 user id를 input URL 에 덧붙이는 것이다.
   • Generating keys offline
     • 우리는 random 6 strings 를 사전에 만들어놓고 db 에 저장해두는 Key Generation Service를 생각해볼 수도 있다. 이때 db는 Key -db라 하자. 우리가 Shortened url를 원할때면, 이 db 에서 꺼내서 써도 될 것이다. 이렇게 되면, 빠르고, 중복이나 collision 위험이 없을 것이다.
     • 만약 Concurrency 한 경우라면? 즉, db에 동시에 쿼리가 접근하여, 같은 데이터를 내어준다면? 어떻게 concurrency 문제를 해결할 것인가? -> db에 두 테이블을 만드는 것이다. 즉, 사용안한 키를 담은 테이블에서 키를 서버에 준다면, 이 키는 이미 사용을 했으므로, used_table로 옮기는 것이다.
     • 그럼 key db 사이즈는 얼마나 될 것인가? key가 1바이트라 가정하면, 412gb 필요.
       • 6 (chars per key) * 68.7B(unique keys) * 1 bytes = 412 GB
     • 그럼 이 KGS 시스템에 single point of failure(단일 장애 지점)이 없는지?
       • 물론 있다. 그러므로, standby replica of KGS 를 갖고 있어야 한다. Primary server가 죽으면, 스탠바이하고 있던 레플리카 서버가 이를 떠맡아서 키를 생성하고 제공한다.
     • 그럼 각 앱 서버가 key-db로부터 키들을 캐싱할 수도 있음
7. Data Partitioning and Replication
   • 이러한 디비에 대한 파티셔닝이 필요함
     • Range Based Partitioning: A로 시작하는 URL, B로 시작하는 URL 등의 규칙으로 범위를 나눈 파티셔닝
       • 단점은 unbalanced db서버가 될 수 있다는 것임
     • Hash Based Partitioning: url 들을 랜덤하게 1~256 사이 의 정수 key값으로 매칭되는 해쉬 키값을 기준으로 파티셔닝하는 것이다. 하지만, 이 역시 overloaded partitions 가 생길 수 있으며, consistent Hashing을 통해 해결해야 한다.
8. Cache
   • 우리는 자주 엑세스되는 url을 캐싱해야 한다. Memcached 같은 규격화된 솔루션을 사용할수도 있다.
9. Load Balancer(LB)
   • 아래와 같이 세 지점에 LB 레이어를 추가할 수 있다.
     • Between Clients And Application Servers
     • Between Application Servers and DB Servers
     • Between Application Servers and Cache Servers
   • 먼저, Round Robin 접근 방식으로 오는 요청들을 백엔드서버로 동등하게 보낸다. 라운드 로빈의 장점은 서버가 하나 죽으면, LB는 이 서버를 로테이션에서 빼고, 트래픽을 나머지 서버들에게 고르게 분산할 수 있다. 하지만, Round Robin LB의 문제점은 서버의 로드를 생각할 수 없는것이다. 만약 서버가 오버로드 되있거나, 느린 상황이라면, LB는 이 서버에 새로운 요청을 보내는걸 중단하고, 리퀘스트를 다른 서버로 보내야할 것이다. 이걸 핸들링하기 위해, 더 똑똑한 LB 솔루션이 사용될 수 있는데, 주기적으로 백엔드 서버에 로드를 체크하는 쿼리를 날려서, 이를 확인하고, 이걸 기반으로 트래픽을 조절한다.
10. Db 청소 혹은 제거( Purging or DB Cleanup)
    • Expired 된 링크들을 계속해서 찾아서 지우기보다는, 천천히 클린업을 한다. 따라서, 서비스의 expired 링크가 살아있어도, 유저한테는 어떤것도 리턴해주면 안된다.
    • 유저가 만료된 링크에 접근을 시도할때는 언제나, 우리는 link를 지울 수 있고, 유저에게 에러를 리턴해준다.
11. Telemetry
    • Shortened URL 이 얼마나 많이 사용되고, user location 은 어떻게 될까? 어떻게 통계 데이터를 적재할 것인가? 만약 이것이 DB Row 의 파트가 해당 url의 뷰마다 업데이트가 된다면, 인기있는 URL이 많은 양의 동시 리퀘스트를 받을 때, 무슨 일이 일어날 것인가? 몇 몇 통계 데이터는 트래킹할 가치가 있을 것이다. Country of visitor, date and time of access, web page that refers the click, browser, of platform from where the page was accessed 등 등
12. 보안과 허용(Security and Permissions)
    • 유저들이 private URL을 만들거나, 특정 층의 유저에게만 URL 접근을 허락할 수 있게 옵션을 줄 수 있는지? 이를 위해 each URL in Database 에서 permission level(public/private)도 함께 저장하는 아이디어를 생각해 볼 수 있다. 또한, 특정 url에 대해 허가 받은 userids 들을 별도 db에 저장해둘 수 있다. 이때 특정 url 에서 KGS에 의해 생성된 Hash 값을 키로 두고, 벨류로는 userids들을 저장해두면 된다. 그럼 url 기준으로 허용 userids들을 찾기 때문에 빠를듯. 즉, 이런 경우에 NoSql로 적재하여, wide_column 하게 user id들을 저장하자.