System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

1. The user can get a short Url with a long URL
2. User accessing the short URL will be directed to long URL

Non-Functional:

List non-functional requirements for the system...

1. Availability: The request should receive a response without error.
2. Partition tolerance: the system should still operate even if some messages are dropped due to the network between nodes

Capacity estimation

For Data storage:

1. Each long URL is around 100bytes
2. Each short URL is 10bytes
3. Around 100M URLs are generated per day

So the total data storage is around 11 GB per day

For bandwidth estimates, let's assume we have 100 million DAUs and 100 million URLs visited per day. So the bandwidth is around 100M * (110bytes) /86400 = 110kb/s

API design

1. shortenURL():

• Input: short url
• Output: the shortened url

1. redirectURL():

• Input: shortened URL
• output: HTTPS 301 with redirect to the original URL

Database design

here we use Mongo DB, as it's high performance and scalability.

The database contains one table: which might include fields:

Primary Key: Short URL: varchar(10)

Long URL: varchar(100), indices.

Their relationship is 1:1.

High-level design

Request flows

The shortening request will firstly go to load balancer and then the load balancer will decide which server to go to, and then the URL shortening service will encode the URL and then add the shortened URL to database and cache.

The redirecting request will firstly go to load balancer and then served by retrieving URL service, then it will try to get the corresponding URL in the cache, if not found, then it will do the data base query.

If the requesturl doesn't exist at all, it will return a Not found 404.

Detailed component design

For the Mongo DB database structure, we use key-value store form like, in this way, the shorten URL can find the corresponding long URL very quickly. And we will do sharding by its Id, to minimizing the hot-spot problem.

For the Cache, we will use Redis, and use LFU as its eviction policy to try to reduce the load to database, besides that, we can add other fields like expiration time to better control its life cycle.

Trade offs/Tech choices

For database, we use NoSQL database MongoDB, although it's not strong for reading request but it has high performance especially for write heavy scenario.

And for cache, we use Redis, as it's key-value store and performs well as a cache level,

For scalability, I used load balancer, trying to distribute evenly the request to it service, and we could combine region-based and weighted round-robin for load balancing

Failure scenarios/bottlenecks

The bottle network maybe inside the shortening service, which might takes long time and resources, as we need a good encoding algorithm.

Besides that, due to our great request number, we need consider a good sharding policy.

Future improvements

I will try to optimize the efficing for shortening service and support more functionalities like editing shortend URLs and customized urls