System requirements

Functional:

1. User should be able to create a shortUrl by supplying a longUrl
2. User should be able to delete/deactivate a shortUrl they created
3. Users should be able to retrieve the longUrl using the shortUrl they supply to the system

Non-Functional:

List non-functional requirements for the system...

1. System should be highly available for the reads (accessing a longUrl from shortUrl)
2. System should be scalable, adding new database servers when current space is exhausted
3. Clean up of archived/deactivated URLs after a threshold time eg. 30 days
4. Should be able to support high burst throughput for reads of highly popular urls

Capacity estimation

Estimate the scale of the system you are going to design...

Storage requirement

Number of create requests per sec= 200

Number of create requests per year = 200 * 60 * 60 * 24 * 365 = 17,280,000 ~ 6205 million

Assuming 10% growth every year, at end of 5 years, number of requests ~ 9082 million which is ~9 Billion

We consider, each request creates a MD5 hash of URL (taking first 7 characters) to represent the short url which will be 7 bytes and also record the long url (average size ~300 Bytes) and the ttl (timetolive in epoch time) ~7 bytes in database.

So we will need a database size of 314 * 9 * 1000000000 Bytes = 2826 GB ~3 TB. Consider we create multiple replicas for durability and availability, lets approximate data size ~10TB.

Throughput Requirement

Also, assuming 200 create requests per second rising by 10% each year leading to ~300 TPS by end of 5 years

For read requests 20,000 TPS

~20k TPS overall

This is not a huge number but will require multiple Application Servers to be hosted

Bandwidth Requirement

For 20k TPS where each request returns ~300 Bytes, bandwidth required = 20 * 1000 * 300 * 8 /1000 Kbps = 48000 Kbps

Considering each 64 Kbit regular server supports 64 KBit instructions/sec processing, number of servers required = 48000/64 ~800 servers

Upper limit of servers to support burst traffic, suppose we encounter that all DAU (845,865 users by end of 5 years) request a read at the same time, number of servers required = 845,865* 300 * 8/(64000 * 8) ~ 4000 servers

API design

Define what APIs are expected from the system...

1. POST: /api/shorturl?url=longUrlValue
   1. parameter url: longUrlValue which will be a String value of the URL supplied by the user to be shortened
   2. This endpoint will be accessed by the client to create a resource of type shorturl using the longUrlValue String supplied by the user
2. GET: /api/shorturl/shortUrlValue
   1. Client uses this endpoint to get the longUrlValue stored in the system by supplying the shortUrlValue as the path variable
3. DELETE: /api/shorturl/shortUrlValue
   1. Client uses this endpoint to archive or delete the shortUrlValue resource they created

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

The loadbalancer provides a way to effectively distribute requests to the

We use a key-value store eg. dynamo db as a database to store our shortUrl as the key and the value is the long url string. We create database shards using consistent hashing technique. The keys (shortUrls) that are hashed by the same function fall under a specific partition and is recorded by the cluster manager.

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

1. CDN: A CDN server is used from locality to check if a frequent shortURL from that region is being accessed. Stores top 10,000 hot shortUrls.
2. Loadbalancer: Provides a way to distribute load between application servers.
3. Application Server: Multiple instances of application servers over different regions provide a way to redistribute incoming requests between themselves to provide high availability and response times
4. DB Nodes: Key-value store type DB . Each db node retains partitions and replicas of the partitions. Partitioning is done based on the consistent hashing of the node ids and the mapping is stored in Cluster Manager. Each shortUrl is hashed by the server and the partition id is assigned based on mapping from Cluster Manager.
5. Cluster Manager: Provides application server the partition id -> Db node mapping so that it can quickly route the user to shortUrl they are looking for.

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

A user sends any request via client.

1. The client checks if the request was recently served by checking the CDN server and returns the result if available
2. Otherwise, the loadbalancer redirects the request to application server (also helps in eliminating any duplicate create requests)
3. Loadbalancer distribution is based on a mix of geolocation and roundrobin. On the first level, requests are routed to specific geolocation, where another level of loadbalancer does routing based on pure round robin since the requests are nearly similar in nature (remember write request initially does a search initially as well)
4. For Create api request
   1. the application server does MD5 hashing of the long URL and takes first 7 characters. This becomes the variable part (shortUrl) of the user accessible short url, for eg. https://www.myshorturl.com/<shortUrl>
   2. it then uses the consistent hashing function to determine the correct partition and db node it should be routed to
   3. if there is a successful insertion into the partition, return success to user, else if there is an error, we let the application automatically retry
   4. The new entry is lazily copied to partition replicas under other nodes after the response is returned.
5. For read requests
   1. steps a through
6. For Delete request, if shortUrl is found, the application deletes the entry which is again lazily deleted from other replica nodes.
7. For read requests, we create scalable shard counters on CDN nodes which will help us determine the top K hot short URLs accessed, we can reset/refresh this list on a periodical basis, eg. every 4 hours.

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Trade offs/Tech choices

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

1. Eventual consistency: On a new shortUrl creation/deletion, we lazily update other database nodes, this provides us with higher availability but can lead to few inconsistent reads at times. Considering, often times the shortUrl is accessed within a region and replicating locally will be done quicker than globally, it should not result in a bad user experience.

Failure scenarios/bottlenecks

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

1. Due to eventual consistency of the database nodes, it might be possible that application misses the shortUrl newly created in other node on read requests. Having a retry mechanism where the cluster manager provides a different node address for the given partition can lower the chance of complete failure but can reduce availability, if this retry is limited to n times and t seconds, this should not be a big problem.

Future improvements

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