System requirements

Functional:

Generate a short link for a URL

Retrieve the long link using the short link

Generating custom links

Important aspects:

Handling link colisions

Length of the short url

Short_url generation algorithm - base 62 encoding

Non-Functional:

High availability - 100 M DAU

Availability over consistency

Response time:

- 1 sec for generating URL

-10 ms for redirecting to long url

Capacity estimation

100 M DAU users

Let's assume 100 M URL read request

and 10 M URL generation requests

10 M * 365 = 4 B per year

read requests = 100 M /24*60*60 = 1 k/s

write requests = 100/s

We should also consider potential spikes in usage e.g.

cater for spikes of 10 times average load so 10k/s for read requests and 1k/s for write requests

base 62 encoding - letters a-zA-Z0-9

Database:

short_url - varchar(100) - 100 bytes

long_url - varchar (max) - 200 bytes

id - bigint - 8 bytes

userId - bigint - 8 bytes

creation date - datetime - 8 bytes

324 bytes * 4B = 1200 B = 1.2 TB per year

if we implement expiry policy for short_urls then we will need less space

API design

POST /shorten/v1/?url=

returns short_url

we should introduce validation of the long_url parameter

rate limiting will help prevent system from overloading if there is request spiki

GET /redirect/v1/

Database design

URL Mapping table

id

user_id

short_url

long_url

creation_time

add index on short_url & user_id

User table

user_id

user_name

user_email

SQL database for storing mapping

NoSQL for fast reads e.g. rRedis

URL Cache

short_url

long_url

expiry policy of 7 days can be implemented

High-level design

Load Balancer will provide a way to distribute the load between multiple instances of both Read and Write Service.

API will be stateless so we can scale both services easily

Read Service will use Redis cache for fast retrieval of the mappings. We will also introduce rate limiting

Write service will save URLs in database so we will have to introduce rate limiting on the number of requests so that database can handle the load, we can store the URL generation requests on a queue and generate response asynchronously

We will need multiple instances of write and readservice for resilience but also for scalability

Request flows

Write flow:

• User call URL shortening API with long_url as parameter
• Load balancer redirects the request to Write Service which generates the short_url

if this short_url already exists in the cache then new one is generated (with additional data like timestamp)

else short_url/long_url mapping is saved in cache and database

• The service returns the shortened URL to the user

Read flow:

• User calls URL read API with short_url
• Load balancer redirects the request to Read Service which calls the cache and retrieves the long_url based on short_url
• The service redirect user to long_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...

Trade offs/Tech choices

We are prioritising availability over consistency, that is why we are introducing Redis cache for read service for low latency of reads, however as cache is updated after the data are stored by write service in database, there might be some lage before new short_urls will be available.

We are introducing expiry of URLs to reduce the amount of space we need to store all urls.

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?