System requirements

Functional:

• Given a long URL, the system returns a short URL.
• Given a short URL, the system redirects users to the original long URL.
• The short URL should be as short as possible.
• The short URL must be unique.
• The short URL should be non-predictable (random).
• The short URL should contain only letters (a-z, A-Z,) and digits (0-9).

Non-Functional:

• High availability (to minimize redirection failures)
• High scalability (to support lots of redirection requests)
• Low latency (to redirect quickly)
• High durability (to ensure that redirection mappings are not lost)

Capacity estimation

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

API design

POST /url/{short url}

GET /url/{long url}

flowchart TD A[Client] --POST /url/--> B[URL Shortening Service] B --Generates short URL--> C[Database] C --Returns short URL to--> B B --Returns short URL to--> A A --GET /url/{short_url}--> D[URL Shortening Service] D --Fetches long URL from--> C D --Redirects User to long URL A --DELETE /url/{short_url}--> E[URL Shortening Service] E --Removes short URL from--> C E --Returns confirmation to--> A

Database design

We first check if the generated short URL is already present in the database, and return a new URL to the client only when the uniqueness constraint is honored. To check URL presence in the database quickly and cheaply, we should utilize a Bloom filter, a memory-efficient probabilistic data structure to quickly (O(1)) check whether an element is present in a set.

The URL shortening system is read-heavy. Any database that scales well for reads will work. And as we already know, both SQL databases (e.g. using solutions like Vitess) and NoSQL databases can scale reads very well. NoSQL database (e.g. MongoDB) will be a better choice

High-level design

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

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

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?