System requirements

Functional:

1. 22 qps for write operation
2. 110 qps for read operation
3. Short url consists of letters and numbers
4. 5 years of service, 2 billion urls in total

Non-Functional:

1. prioritize fast read over fast write
2. Strong consistency of data

Capacity estimation

1. 2 billion urls translated in base62 encoding - we'll need 6 digits per url (62 ^ 6 = 56 billion)
2. 6 bytes * 2 billion = 12 GB of data
3. 3 replica of the db.
4. distributed servers

API design

write operation:

POST https://api.tinyurl.com/v1/url

{

long_url: "google.com"

auth_token: "*"

}

Read operation

GET https://tinyurl.com/url/jIkND9

reponse code 302, because we might want to track user activity for analytics (301 will cache the url and redirect automatically without routing the api to our system.)

Database design

short_url(key) | long_url | hash_value | created_by | created_at

jIkND9 | google.com

High-level design

Request flows

Write flow:

1. User send request from the client which includes a longURL
2. API Gateway helps with authentication & rate limiting
3. Load balancer helps distribute the workload evenly into the servers
4. Server receive the request, and get a unique id from ID generator
5. Encode the id to base 62
6. write into database

Read flow:

1. user send request from the client which includes a short URL
2. API Gateway helps with authentication & rate limiting
3. Load balancer helps distribute the workload evenly into the servers
4. Server receive the request check the cache
5. return if found in cache
6. otherwise look up in db and return

Detailed component design

DB consistency strategy:

1. Prioritize consistency over avalibility (the request can be slow at times)
2. Prioritize read availability over write availability

By using quorum theorem

• Total replica: 3
• Write quorum: 3
• Read quorum: 1

We guaruntee strong consistency of the system and fast read.

Load balancer: We use consistent hashing to guarantee even distribution

ID generator:

To avoid clashing, we can use a simliar strategy to Twitter snowflake ID generator system by puting the ID into different part like timestamp, machine id, cluster id, namespace etc.

Trade offs/Tech choices

By using quorum theorem

• Total replica: 3
• Write quorum: 3
• Read quorum: 1

We guaruntee strong consistency of the system and fast read.

reponse code 302, because we might want to track user activity for analytics (301 will cache the url and redirect automatically without routing the api to our system.)

etc.

Failure scenarios/bottlenecks

If user try to read an non existing short url, we should return 404.

To avoid single point of failure, we need redundancy of different parts of the system like servers, id generators, data base

Future improvements

If our service is to be expanded to global, we might want a different data center for faster response.

The Server Cluster is set to be easily scaled horizontally.

We might want to introducing sharding if the traffic is beyond expection and storge spacc gets challenged.

(also introduce 7 digits short url when we are scaling out)