Requirements

Functional Requirements:

1. Create short URL - given a long url, generate a short alias
2. Redirect - Given a short URL, return the long URL

Non-Functional Requirements:

1. Service must be up at all times
2. low latency in query results
3. In order to incorporate multiple queries, incorporate horizontal(increasing the number of servers) scaling

Capacity Estimation

lets assume there are k = 1M queries / day

in a second, there would be 1000000/24*60*60 QPS

Lets just assume for every 5 reads there is a write

R/ W ratio = 5

DB usage

Egress/bandwidth

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

1. POST /url/add

Request body {

url: string

}

1. GET /url/{shortkey}

Response;

High-Level Design

The HLD for URL shortener has two main flows one for creating and the other for getting the long URL. The first service is the URL shortner service when Client adds any long url it is stored into a DB ( consists of Short -> long url mapping)

The other service is when the User puts in the short URL to get the long key from a cache which is short lived, if not found in cache search in the same DB

Add a load balancer to handle the requests being directed to each of these services, also the URL shortner service has the logic for an ID generation strategy

Database Design

The database can simply be sql with two columns in it 1 is the short url and 2 is the long url.

The data model would look like

Table url-shortener

Columns

id

short-url

long-url

created_date

expires_at

the short-url is the primary key and possibly a SQL index can be created on short-url as it helps the process of read queries which from the Read Write ratio are already very high.

New Url creation requires strong consistency to avoid duplicates, redirect reads can tolerate eventual consistency - a brief phantom read that returns a 404 that can be retried.

Read replicas for read traffic, sharding by short-key hash when the DB outgrows a single node

Detailed Component Design

Ways for ID generation

1. UUID
2. Some bit values in the id reserved based on atomic clock value of when the record was added
3. Hotspot migration - Sharding helps the traffic, although one viral link can hit one shard. In such case a cache would help absorbing the viral hits