System requirements

Functional:

• client should be able input an URL and the URL service must generate a unique URL corresponding to the given URL.
• client must be able to view his mapped URLs.
• when a short URL is accessed the service should redirect the request to the original URL.
• If the URL is not found then the server should be given the correct error response to the client.

Non-Functional:

• Scalability: The system should be able to serve millions of requests per second without failing.
• Performance: URL redirect should be fast under 100ms.
• Availability: service should be highly available.

Capacity estimation

let's say the shortened URL may contain only 26 English lowercase chars and 26 English uppercase chars and numbers 0-9.

The total number of available chars will be 26 + 26 + 10 = 62.

If I take the length of the URL to be 32 chars. then the available URLs should be 62^32 = 2.27e+57. which should be enough. for handling large amounts of customers.

Now for storage, each character is 1 byte. also I am allowing the input length of input URL to be about 200 chars.

so 200 + 62 = 262 chars per URL should be stored.

so in total, it is 262 * 2.27e+15 = 5.9e+59 bytes. so about 5.4e+47 petabytes of storage. in the worst case.

API design

for functional needs following APIs should be done.

• Request for mapping of the given URL.
• Redirecting a client to the mapped URL.

Database design

The database should contain Key-Value pair of the URLs along with their time of assignments. also a reverse mapping should be stored.

the time of assignments can help when cleaning the database is required.

For this, we can use DynamoDB for storing the above schemas.

High-level design

For high-level design, we can simply have a server setup which have access to the database storing the URLs.

for the corresponding APIs. the server can either store new entries in the database or retrieve the URLs from database and send the response to client.

Request flows

Use case 1: url request.

The client requests a generation of shorter URLs for a given URL.

The server uses a hashing function to calculate the hash of the given URL.

then it checks if the hash is already present in the database.

in case it is not present then the server takes a lock on the database and then writes the newly generated URL and its corresponding URL in the database.

in case it is already present the server may need to generate a new hash and then repeat the above steps until it gets a new URL.

this process might create a problem in availability issue.

for this problem we can give generation service to an extra server which manages generation. it can simply keep a counter and generates a new URL using it. and coordinates it to the requesting servers.

the server then returns the generated URL to the client.

in another requirement. the client asks for redirection for a give URL. this simply requires a lookup in the database and returning corresponding redirection.

Detailed component design

for greater availability we need to deploy a load balancer which will forwards the request from client to multiple servers based on their load.

the services are stateless and hence any server can handle any request.

for database we can use DynamoDB. which is key-value pair database. and use sharding to distribute it in multiple storage spaces for scalability as per demand. also a load balancer would be needed which will take request from servers and forward to databases.

also some sites may have more hits than others so we can have a simple caching between server and databases which can use memchached.

an extra server which can be used for generation of URLs is deployed which is also a distributed server. and with a load balancer so that this server is highly available.

Trade offs/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?