System requirements

Functional:

• Take in a long URL and generate a short URL
• Given a short URL, redirect / map to the original long URL
• When accessing the short URL, browser should be redirected to the long URL (301 vs 302)

Non-Functional:

List non-functional requirements for the system...

• Both create and get operations should be fast
• Shortened links should last about 3 years
• Perhaps automatically expiring URLs that are old
• Same long URL should give the same short URL if it has been generated before

Capacity estimation

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

• More reads than writes
• ~ 100M links shortened per month
• 100M / 30days / 24 hours / 60 min / 60 sec = 38 req per sec
• Each letter in the short URL can be [a-zA-Z0-9] , which is about 62^n possibilities, let's say n = 7, 3.5 trillion unique links; 100M per month * 12 months, 1.2 billion per year, so this will last us about 3 years of storage
  • Each n increase will give us exponentially more

API design

Define what APIs are expected from the system...

• POST /api/v1/shortening
• GET /api/v1/shortening/<short_url>

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

• Since this will mostly be read heavy compared to being write heavy, we can go with a single leader SQL database
• To keep things simple, let's go with MySQL
• We can have a table that stores the long url, short url, date created as columns and use the long url as the primary key

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

We definitely need a URL service that is stateless, so that it's horizontally scalable for high load; a load balance will also help balance traffic to the different servers

For commonly fetched short URLs, we want a cache that the server can access that will return the long URL

A couple ways to do this - we can either have the requests cache in the service itself in memory and have requests go to specific servers based on potentially a hash of the short URL - but that has its own issues (ie. when a server goes down, we'll instantly get a bunch of cache evictions & misses on the new server that handles this)

Better way to scale is to use redis

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

Short URL creation Req:

• client makes request to load balancer, which sends request to URL service (server)
• Server will check the database for any entries that have the same long URL
• If there already exists a short URL, return that; if not, use the URL shortening logic to shorten the URL and store it in the database & update it in the cache

Short URL access req:

• client makes request to load balancer, which sends request to URL service (server)
• server will check cache for entry of short url
• if it's in the cache, return the long url with a 301 permanently moved status (so the client browser will always go to the long URL when entering the short url)
  • We can also return a 302 temporarily moved status, if we always want requests to hit the server (for analytics), otherwise, 301 is preferred to reduce load
• If it's not in the cache, go to the database and look up the short 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...

We need a secondary index on the database to quickly look up based on short URL.

Also for the URL shortening logic, we have a couple of options.

1) Use a hashing function to hash the long URL to a short URL; but this could create hash collisions, so when that happens we need to pad the long URL with additional characters until the collision is gone

2) Use a base62 conversion on an auto incrementing ID in the database table; this won't have any collisions as we're converting on the auto ID which is guaranteed to be unique; a couple of changes to the database schema for this to work: we need an auto incrementing ID as the primary key, and then an secondary index on the long URL

Trade offs/Tech choices

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

load balancer -> api gateway to handle rate limiting & if we ever want user accounts can use that for auth

stateless server w/ a distributed redis cache to scale horizontally

sql over no sql for acid & transactions; more reads than writes so single leader replication is fine

Failure scenarios/bottlenecks

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

With multiple servers there could be a race condition when the same requests come in to create a short URL for the same long URL; these servers don't see the entry for the long URL so they all attempt to write into the database table

We can solve this by putting a unique constraint on the long URL column, so any server thaat attempts to insert the same long URL the second one will fail

Future improvements

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