System requirements

Functional:

• Given a URL, generate a shorter and unique alias of it called short link.
• Users are redirected to original URL when they click on this short link.
• users able to custom pick short link for their url
• short link expires after timespan (provided by user)

Non-Functional:

• high availability
• url redirection should happen in real-time -> low latency
• short link should not be guessable
• analytics - how many redirections happened?
• make service accessible through Rest APIs by other services

Capacity estimation

• system will be read-heavy, 100:1 read/ write ratio

traffic estimation:

• 500 million url shorten requests / month
• Redirections/month = 500 million * 100 = 50 billion
• QPS :
• writes: 500 million * (30 * 24 * 3600) = ~200 URLs/sec
• reads: 100 * 200 urls/sec = 20K/sec

storage estimation:

• store every url shorten request (along with short url) for 5 years
• 500 million requests / month
• total requests / 5 years = 500 million * 5 years * 12 months = 30 billion
• per req memory : 500 bytes
• total memory = 500 * 30 billion = 15 TB

Bandwidth estimate:

• write : 200 url/sec * 500 bytes = 100 KB
• read : 20000 K/sec * 500 bytes = 10 MBps

Cache Memory estimates (per day):

• cache 20% requests (hot urls)
• req/day = 20k/sec * 3600 * 24 hours =1.7 billion
• 20% of that -> 0.2 * 1.7 billion * 500 bytes = 170 GB

API design

• REST API to expose functionality

API methods :

createURL(api_dev_key, original_url, custom_alias=None, user_name=None, expire_date=None) => returns shortened URL or error

deleteURL(api_dev_key, url_key) => url_key is key representing shortened URL => return success/unsuccess deletion of url

To prevent abuse by user, each api_dev_key has limit on url creation and redirections per some time period

Database design

Key observations:

• Read-heavy
• store billions of objects
• no relation among different url requests
• object size is small (< 1Kb)

Tables:

1. User : stores user data
2. userID, name, email, creationDate, lastLogin
3. URL : mapping or original -> shortened URL
4. originalURL, newURL
5. userID, creationDate, expiryDate

DB : NoSQL (dynamoDB, Cassandra) -> easier to scale

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

flowchart TD

B[client] --> C{server}

C --> E[Key generation service]

E --> D[Database]

D --> C

C --> B

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

sequenceDiagram

Client->>+Server: shorten a url

Server->>+Encoding: encode the url

Encoding->>+Database: store encoded url

Database->>Server: url stored/failed

Server->>Client: Return shortened url

Detailed component design

Summary : We need to generate last 8 (or 6, 10?) chars in the shortened URL, for example: “https://tinyurl.com/vzet59pa”.

Here are possible ways -

Option 1 - Encoding actual URL:

• compute unique hash of given url (MD5, SHA256 etc) and then encode the hash
• for base64 encoding : 64 ^ 6 => 68 billion unique 6 char strings
• we can use 6 chars instead of 8
• MD5 hash:
• generates 128 bit hash value
• each base64 char encodes 6 bits -> we will get 21 chars in encoding
• how to choose 6 chars out of 21?
• pick first 6 -> possible key duplication
• to avoid -> choose other chars or swap chars in string
• Possible issue:
• multiple users with same URL request will get same shortened URL
• Resolve ways:

1. append increasing seq number to each url before hashing -> may overflow
2. append user_id (unique) to input url -> user may not be logged in, need to prompt user to provide unique key
3. keep generating urls until we find unique one

Option 2 - Generating Keys offline :

separate key generation service (KGS) to generate the 6 letter unique keys offline and store them into a separate DB (key-DB).

• Fast and simple
• no encoding url -> hence no collisions and duplications

KGS:

• concurrency : if multiple servers try to read same key from KGS ?
• KGS maintains two tables -> used keys, unused keys
• once kgs provides key to server, it moves it to used_keys to avoid dupliction
• kgs always maintains new keys generation as needed
• key-DB size: 6 (chars per key) * 68.7 billion keys -> 412 GB
• KGS single point of failure? -> yes, keep a replica of KGS
• Application server can cache keys from key-DB -> speeds things up

Database key lookup:

• check if key is present in DB
• if yes -> return FULL URL -> send user "HTTP 302 redirect" browser -> pass shortened URL to "location" in request
• if no -> send 404 not found -> redirect back to homepage

Custom alias:

• impose size limit (max 16 chars) for better consistency in DB.

Data Partitioning:

• needed to store info on billions of URLs
• Range based : use the start letter of hash key to define partition, for ex. 'a' or 'A' is one group, 'B' is another group etc
• issue : partition overloading if too many keys with fixed start letter
• Hash based : take hash of key or short link and build a hash function to map it to [1 ... 256]. Then partition the key to that group.
• issue : partition overloading
• Consistent hashing : (better solution)
• Use consistent hashing to evenly distribute keys across a changing set of servers without the need for rehashing all keys.

Caching:

• store hot URLs and their respective hash
• use memcached with LRU cache eviction policy
• start with 20% of daily traffic stored in cache
• 170 GB memory in total -> need one machine with 256 GB capacity
• easily scalable to more machines as required
• replicate caching servers for high availability, reduced latency.
• Cache updates:
• if there is cache miss -> servers go to DB to get the new entry -> new entry is then added to cache and its replica

Load balancing:

• between client & app servers -> round robin strategy
• simple to implement, remove unresponsive servers
• issue : we don't consider server load
• solution: periodically check server load and route requests based on that
• between app servers & db
• between app servers & cache

Removing expired links :

• user defined expiry date or set a manual deadline (2 years)
• cleanup service :
• lightweight service, should be run in non-peak hours
• when user tries to access expired link -> remove from db OR
• periodically runs to remove expired links
• once link is removed -> add key to the key DB to reuse

Full components diagram:

flowchart TD

C[client] --> LB1{load balancer}

LB1 --> S[Server]

S --> LB2{load balancer}

LB2 --> Ca[cache]

LB2 --> D[database]

S --> KGS[key generation service]

KGS --> kdb[Key dB]

Cleanup --> kdb

Cleanup[cleaup service] --> D

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?

• add permission level (public/private) for each URL in DB
• key -> hash (or key generated by KGS) and columns -> user_ids with permission to that URL