System requirements

Functional:

1. User is able to give a long uri, and get a short url.
2. The short url is able to redirect to the long url.
3. User is able to manage the short url created and able to view, add, delete and modify.

Non-Functional:

1. High consistency
2. High availability
3. Able to scale to serve 500M DAU
4. Able to scale to serve 1M QPS

Capacity estimation

1. 500M DAU
2. 1M average QPS
3. 3M peak QPS
4. User can be globably distributed

API design

• POST /getShort/:longUrl, Response: string: shortUrl

Create a short url for the input long url. Returns a short url that can redirect to this long url.

• GET /getLong/:shortUrl, Response: string: longUrl

Return the mapped longUrl by giving a short url

Database design

cache database 1: used for storing a pool of available short url:

{

string shortUrl,

Int offSet

}

cache database 2: used for speeding up the read of frequently access shortUrl

{

string shortUrl, key

String longUrl, value

}

main database short to long mapping table: (noSQL)

{

string shortUrl, key

value {

string longUrl,

TimeStamp creatdAt,

TimeStamp updatedAt,

String userId

}

}

High-level design

• Write flow (creat short url based on long url)

client -> load balancer -> cache -> database

server

• Read flow (read long url based on short url)

client -> load balancer -> cache -> database

server

• short url pre-generator service - a cron job that periodically flush new generated short urls to cache. Can write a hard-coded backup file if the cache fails, so that we can restore the cache immediately.

Request flows

• Write flow (creat short url based on long url)

Client sent a request to create a short url based on long url.

Request reaches load balancer to go to the nearest and available cache db(Redis).

Cache db stored a bunch of available short urls ready to be used and they are generated by a shortUrl generator service with a cron job.

When a create request comes in, we will pick up a short url in the short url pool in cache db, write the mapping to another table (short to long mapping table )

And then we can have a cron job periodicolly flush the new url mapping to its main database

Note: since redis is single threaded, we resolve the potential collision naturally. Since when a write request comes in, the request will be queued to access redisc cache to retrieve the pre-generated short url, thus no collision will happen in this design.

• Read flow (read long url based on short url)

Client sent a request to read a long url based on a short url.

Request reaches load balancer to go to the nearest and available cache db(Redis).

If cache hit, returns the long url.

If cache miss, query the main db and add to cache.

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

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?