System requirements

Functional:

• The service should allow users to input a URL and then return a unique short URL.
• When the user clicks on this short URL, they should be redirected to the original page.
• Short URLs that are produced will expire after a standard lifespan, in this case, we will use 10 years

Non-Functional:

• The system should be able to store a large number of URLs for 10 years
• The system should be highly available, we don't want our URL redirections to fail
• The shortened URLs should not be guessable
• URL redirection should happen with minimal latency

Capacity estimation

Assuming that in a day, we have 1 million new URLs.

Storage Estimates:

• Assuming that each URL + shortened URL pair is about 500 bytes.
• 1 Day - 1 million x 500 bytes = 500GB
• 1 Month = 500GB x 31 = 15 TB
• 1 Year = 182 TB
• 10 Years (Maximum lifetime of a URL) = 182 x 10 = 1820 TB

Traffic Estimates:

• Assuming Read : Write ratio is about 10 : 1
• Write Traffic:
• Writes Per Day: 500 bytes x 1 million = 500 GB
• Writes Per Hour = 21 GB
• Writes Per Second = 900 MB
• Read Traffic:
• Reads Per Day: 500 bytes x 1 million x 10 = 5000 GB
• Reads Per Second = 9000 MB = 9GB

Cache Storage Estimates

• We want to follow the rule of 20:80 ratio, which means 20% of our URLs accounts for 80% of the activities in our service, hence we want to try to cache 20% of our data
• Cache Size = 1 million x 500 bytes x 20% = 100 GB

API design

• We can use REST APIs to expose the functionality of our service
• createURL(string url, api_dev_key) : will return a unique shortened URL that will redirect to the original page
• redirectURL(string shortenedURL) : will redirect the shortened URL to the original page

Database design

We will keep two types of data:

• URL - original_url, shortened_url, expiry_date
• Users - name, email, creation_date, last_login

We will be anticipating millions of data inputs into our DB. We also realise that there isn't relationships between objects. Hence, a NoSQL key-value store like Cassandra and DynamoDB would work best. NoSQL would also be easy to scale

High-level design

We should have two servers

1. Server 1: receiving and processing the client's read and write requests
2. Server 2: generates unique shortened URLs

Server 2: What kind of algorithm should we use to generate the unique shortened URLs? One way to do that is to generate a random sequence of about 8 characters using letters a - z, A - Z and 0 - 9. In total, there are about 3x10^9 total combinations. When a shortened URL is generated, the service should check whether the URL is in use before storing it in a separate DB ( we will call it key-DB)

Service 1: If this server receives a write request, what we can do is request for an unused URL from server 2, once retrieved, Server 1 will store the original URL and the shortened URL in the DB before returning it to the client. When the server receives a read request, simply look for the shortened URL in the DB, and return the corresponding original URL.

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

The client can either send a read request or write request.

If this server receives a write request, what we can do is request for an unused URL from server 2, once retrieved, Server 1 will store the original URL and the shortened URL in the DB before returning it to the client. When the server receives a read request, simply look for the shortened URL in the DB, and return the corresponding original URL.

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

In terms of load balancing, we can have multiple servers that does the same thing as Server 1, and then have a few servers that does the same thing as Server 2. This is to ensure that the servers do not get overloaded, it also ensures that if a single server fails, we have other servers that will continue serving the clients. We can have a load balancer between the client and the servers and we can do it in a Round Robin format. Round Robin is good because it is easy to implement, and it would also divert requests away from servers that are not working. We can also have load balancers between Server 1s and Server 2s.

For the database, we can have multiple databases that to store the URLs. However, this means that we must come up with an algorithm to ensure that the URLs are distributed evenly throughout the databases. The easiest way would be to distribute our URLs based on the first letter of the shortened URL. Since the shortened URL's first letter is random, we can easily partition them equally across the databases. For each of the database, we should also have back-up databases for them

In terms of caching, we should have a cache between the client and Server 1, the client first checks whether the requested URL is in the cache, if so, retrieve the original URL from there, also we will continue on to Server 1. We will employ the Least Recently Used policy for our caching system.

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?