System requirements

Functional:

• Client can submit long URL and get shortened URL.
  • Check validity
  • Check if already shortened
• With a shorted URL, redirect the client to the original long URL

Optional:

• Analytics
• Custom alias
• Time to expire
• User account management

Non-Functional:

• Availability > consistency
• Scale to 100M DAU, 1B URLs
• Read >> write (1000:1)
• Short latency redirection

Capacity estimation

• Storage: 1B * 500bytes (100 bytes for long URL + 100 bytes for custom alias ~ 500 bytes) = 500GB -> could be in a single SSD, but we can always scale later
• Write QPS: 100M DAU / 100000(seconds/day) * 0.001 creation ratio * 10 query per user -> 10 creation QPS -> could be handled by most major databases in a single server setting
• Read QPS: 100M DAU / 100000(seconds/day) * 10 query per user -> 10k read QPS

API design

Shorten:

POST /shorten

{

"long_url": url,

"alias": optional str,

"time_to_expire": optional time

}

-> short_code: str

Redirect:

GET /{short_code}

-> 302 temporary redirection to long url

-> 404 not found

Database design

In the database we store the short/long url.

Each entry would be:

• short_code
• long_url
• time_created
• time_to_expire

High-level design

We have a client, a server, and a database in our design. The client send the requests to the servers, the server processes the requests, query the database and update the entries.

Request flows

Shortening:

• Client send POST request
• Server check URL validity, if invalid, return error
• Server check optional alias exists in database, if exists and the long_url does not match, return error
• Server generate alias if no custom alias provided
• Insert into database
• Return short code to the client

Redirect:

• Client GET
• Server queries cache, if not found query database with the short code, if not found, return 404
• Return 302 redirect to the short code.

Detailed component design

Cache can be a Redis, with LRU eviction policy.

Database can be any database.

Server can be horizontally scaled, we need a load balancer

Trade offs/Tech choices

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

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?