System requirements

Functional:

• Client can submit long URL and get shortened URL.
  • Check validity
  • Check if already shortened
• Custom alias
  • Check if too long
  • Check if collision
• Time to expire
• With a shorted URL, redirect the client to the original long URL

Optional:

• Analytics
• 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, and its format, for example, we can exclude then if they can collide with an automatically generated alias, 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
• Check if expired, remove from the database and 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

For the alias generation, we can use base62 encoding with a counter. Counter can be a Redis counter, so no race conditions. Every time a new alias is requested, we INCR counter, and encode it into base62. We need log_62(10^8)~=7chars. Quite short. Note that we may need to contact the database to see if it is already in the database given that we support custom alias.

Handling invalid URLs: we can use is-url to check, or a simple regex based solution.

Handling invalid custom alias: too long, collide with existing

Trade offs/Tech choices

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

Failure scenarios/bottlenecks

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?