System requirements

Functional:

1. User is able to post a long URL and the system can generate a corresponding short URL.
2. When the user is calling a valid short URL, the service will be able to convert it back to the original long URL and redirect the user to the website

Non-Functional:

1. SLA should be at 99.99%

Capacity estimation

1. Assume we have 10m daily active users.
2. Each user makes an average of 10 queries per day.
3. read and write ratio is 1:1
4. qps is estimated at 10m * 10 / 86400 ~= 1000 qps
5. peak qps is assumed to be 2000 qps

API design

GET api/v1/getShortUrl?long_url={long_url}

response

{

short_url: {short_url}

}

GET api/v1/redirect?short_url={long_url}

Database design

we should have two tables.

create table long_to_short{

long_url varchar(60),

short_url varchar(50),

PRIMARY KEY(long_url)

}

create table short_to_long{

short_url varchar(60),

long_url varchar(50),

PRIMARY KEY(short_url)

}

High-level design

Request flows

The user sends a post request with a long URL to a short URL generator server to get a short URL.

The generator will first check the cache and database to see if a corresponding short URL has been generated, if yes, return the result. If not, it will convert the long URL using 'snowflake id' algorithm to generate the the unique short URL and store it into the database and return the response

Detailed component design

Both the generator and redirect servers are stateless which are easy to scale.

Trade offs/Tech choices

we are using SQL server because we dont have update to the existing records and it should have no concurrency issue.

if we experience high DB rps, we could create more replica of DB

Failure scenarios/bottlenecks

The cache could be expired at the same time which could cause a spike in DB qps.

The current design has only a single generator server and redirect server, it may have a single point of failure.

Future improvements

The cache could be preloaded with hot URLs to reduce the workload.

both the generator server and redirect server are stateless, so it is easy to scale horizontally