System requirements

Functional:

• Shorten the URL's

Non-Functional:

• scalable
• availability
• Write and ready heavy

Capacity estimation

• Throughput
• 10million request/86,4200*30 = 40url's/sec
• Memory
• 100 million request*500bytes = 50gb
• 50(.2*20) = 10gb
• Storage
• 10million writes*1.5mb = 15TB
• 15tb*365days*10years = 55PB
• memory for cache - 170gb

API design

• Get
• requestor id
• URL link
• date
• time
• Put
• requestor id
• URL link
• Short URL
• date
• time

Database design

• NoSQL DB
• Dynamo DB
• DynamoDB is a fully managed, serverless, key-value, NoSQL database designed to run high-performance applications at any scale. DynamoDB offers built-in security, continuous backups, automated multi-Region replication, in-memory caching, and data export tools.
• For scaling lets use NoSQL
• for high volume
• we cannot store user id
• create a third table to store user id
• Encoding 8 letter
• with 8 letter encoding 64
• 64^8 = 281 trillion string
• 64.8 billion unique 8 letter will suffice
• Data partition & replication
• Range based partitioning
• inconsistently distributed across servers
• Hash based partitioning
• easy to read
• faster
• consistent hashing to distribute across servers
• Linked hash map
• store URL's with hash for easy retrieval

High-level design

• client
• loadbalancer
• API gateway
• DB
• Cache
• LFU
• Expired ones
• KGS
• encoding

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...

Detailed component design

1. The long URL's will be converted to short URL by using the key generation service
2. What is Key Generation Service?
3. The KGS is a standalone Database by itself which will generate a key for each URL every time we get a request
4. This way it will prevent the duplicate keys or eliminate the collion of keys
5. base 64 algorithm
6. The Base 64 Encoding algorithm has 64 characters, hence the name. By implementing the Base 64 Encoding, it became possible to transmit 8 bit ASCII
7. base 64 generates 8 letter code which will generate 281 billion unique strings
8. we will use 6 letter code which will generate 68 billion unique strings and that will suffice this requirement
9. How to generate 6 letter keys offline
10. By generating offline we might miss some of the key's
11. if the server goes down then we might waste some of the keys
12. concurrency issue might be a concern
13. Keeping all keys in one server will be single point of failure hence its good to have one in each server
14. How to find the key
15. we can look up the key-value and then redirect it using http 302 code and if not available then use the code 404 - as not found

Caching

1. Redis

• No longer need to perform management tasks such as hardware provisioning, software patching, setup, configuration, and failure recovery
• Have access to monitoring metrics so you can diagnose and react to issues quickly
• Can take advantage of cost-efficient and resizable hardware capacity

1. store full url's with hash
2. we will store 20% of the cache which will fit into one server
3. hotspots
4. LFU

Purging/clean up

• expired one's can be removed and new ones inserted

Load balancers

• round robin method
• what comes in will go out and sequentially processed one at a time

Rate Limiter

• We will use the rate limiter to limit the request coming from the same server

Fault tolerance

• KGS is a single point of failure
• Horizontal sharding to include leaders/followers servers
• if the leader dies then follower will take it over
• distribute the servers across multi-locations and incase of dynamo db they are multi-region

Trade offs/Tech choices

MD5 algorithm

• 128bit will make 16 characters which will generate trillions of strings
• since billions are good enough at this point lets use the basic 64 bit algorithm
• maximum of 16 characters long key

load balancer

• we can use more intelligent lb to handle the traffic and route it appropriately based on the load

Failure scenarios/bottlenecks

1. KGS is single point of failure

Future improvements

• user create private url's
• restrict them through user login