Tiny URL

What is Tiny URL

This service will provide shortened aliases redirecting to long URLs. Users are redirected to longURL as they hit short URL.
Short links save a lot of space when displayed, printed, messaged, or tweeted. Additionally, users are less likely to mistype shorter URLs.

This would be Read-Heavy, Read:Write=100:1

1. Requirements

Functional

CRUD(Create=POST, Read=GET, Update=PUT, Delete=DELETE)

1. (Create=POST) Create shorturl from long url

2. (Read=GET) Read Big URL From tinyurl

3. (Update) When bigurl is updated, old tinyurl should be updated

4. (Delete) Delete existing tinyurl

Non Functional

S³:(Scalable,Secure,SOA), L³:(Latency, Load, Logging), A³:(Accurate, Available, Authenticated), C²:(Cache), R²:(Reliable, Redundant) F²:(fast, Fault Tolerant)

1. Scalable. if user creates, 100k urls at same time, system should not delay

2. Reliable: Everytime user hits shorturl, it should provide same bigurl

3. Available: On high load, system should be available. (CRUD=READ)

2. BOE

QPS Estimates: //Ask Interviewer. Incoming requests/sec

- 25000/86400 req/sec. 1 request/4 seconds
- 25000 requests/day
- 25000 x 30 = 750,000 requests/month
- 750,000 x 12 x 5 = 450 Million requests/5years

Storage Estimates:

Shortened URL: 6 bytes Long URL: 250 bytes Storage for 5 years: 260 x 450M = 117 GB

Bandwidth Estimates:

- 1 request/4 seconds
- 1 GET request = 2KB
> Incoming bytes = 1 x 2k = 2000Bytes/5 sec
> Outgoing bytes = same

3. System APIs

1. (Create=POST) Create shorturl from long url


POST /api/v1/api_name(get_short_url) HTTP/1.1    //Check other fields in HTTP POST
request parameter: {longUrl: longURLString}

2. (Read=GET) Read Big URL From tinyurl


GET /api/v1/api_name(get_long_url) HTTP/1.1    //Check other fields in HTTP POST
request parameter: {shortUrl: shortURLString}

4. Databases

5. High Level Design

Req1. (Create=POST) Create shorturl from long url

1 user, 1 server


          client                             Server
          ---------POST api/v1/longurl--------->
                                             longurl => |Hash_Fun| => shorturl
                                             shorturl
                                              |----> unordered_map (In memory)
                                              |----> file (on disk)

10 M Users

Generating short-url for Long-url. There are 2 methods:
a. Runtime: As we get request, generate short-url. This makes system slow.
b. Offline(We take this): Fast. KGS will keep generating shorturls offline and keep pushing on DB.

          @startuml
          participant browser as b
          box "Datacenter" #Khaki
           participant AppServer as as
           participant Cache as c
           participant HashGenerator as hg
           participant KeyGenerationSystem as kgs
           database SQL_DB as db
          end box
          
          note over c #Cyan
           
          end note
          
          note over hg #Cyan
           longurl->
             |256Hash|->
                 Hash
          end note
          
          note over kgs #Azure
          Generates 
          keys=shorturl
          offline
          end note
          
          note over db
          longurl, Hash, shorturl, timeout
          end note
          
          b -> as: longurl
          as -> hg: longurl
          hg -> as: hash
          as -> c: does hash exist
          c -> as: Yes(shorturl)
          as -> b: shorturl
          c -> as: No
          
          as -> kgs: Hash
          
          kgs -> c: shorturl
          note over c #Gold
          Writethrough Cache
          
          end note
          
          c -> as: 
          as ->db: Hash, longurl, shorturl, timeout=1 year
          as -> b: shorturl
          
          @enduml

Key Generating System

Only 8 character shorturl would be generated

For 8 character short URL. Total possible combinations: 64⁸ = 2.8 x 1014 = 280 Trillion. //Huge Enough


1. Get Hash of long URL
long-url > |SHA3 or MD5 Hash|  > XXX

2. Convert 128bit(16 bytes=16 characters) hash to (Base 64 Format = 8 characters)
Return 1st 8 characters from 21 characters.
Problem: Differnt long URL's can produce same 1st 8 characters.
Solution: Append timestamp or userId with longURL and then generate the short url