System requirements

Functional:

• when user provides a long URL, the service returns a shortened URL.
• when user provides a shortened URL, the service should return the corresponding long URL if it exists
• user may be allowed to set a expiry timestamp
• allow customized shortened URL

Non-Functional:

• store the mapping of shortened URL to long URL for certain time period reliably.
• high availability for customers trying to create or use shortened URL with burst loads being 10k / second
• Generate/Retrieval latency should be relatively low around <300ms

Capacity estimation

• Storage:
  • Assume we stored the mapping of shortened URL to long URL in database with expiry being one day. Each record will take about 30 Bytes. Assume we have 1M active users and each of them make two shortened URL per day, we would have 2M * 30 bytes = 60 MBs per day in a single storage node. Given we'd like to achieve high availability and store our data reliably, we would replicate our database into two different data zones. This gives 180MBs / day.
  • We shall also consider the cache , assume our cache is same size as Database.
• Request:
  • Given we assume we have 1M active users, the request rates for our service is about 1M / 24 / 60 /60 = 10 requests per second. However, given our user will grow and the request is usually not spreading across the day equally, let's say we need to handle burst rate 100 requests per second.

API design

post /shorten/

request body:

longurl (required), shorturl (optional), expiry date(opional)

response body (json):

long urL

The user would use this API to get a shortened URL by providing a long URL

get /getLongURL/

request body:

shortenedURL (required)

response body:

longURL or a redirect.

This user would use this api to get a or redirect to long URL.

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

ShortenedURL:

primary Key: shortenedURL

Column: LongURL (required)

Column: Expiry Date (optional)

Column: createdAt (required)

Column: user (optional)

I'd like to go with C* nosql database given its scalability, ease to use, native support for TTL

shortenedURL should be unique.

High-level design

Note that we could horizontally scale both urlShorten server and Database.

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

What algorithm do we use for generating the shortenedURL.

option1:

• We could to a hash function of long URL and do Base 62 (a-zA-Z0-9) encoding. Then take the first 6 or 7 letters as shortened url. in case of a collision, we would add some "salt" to the original long URL and repeat the above process. The chance of collision shall be low.

option2:

• We could self maintained a counter that is monotonically increased so that we could ensure no collision from database perspective. However, maintain a centralized counter during high peak traffic can be challenging and jeopardize user experience by adding more latency

SQL vs NoSQL

go with NoSQL given we opts for high availability

cache:

it could fasten the latency that retrieves commonly accessed shortenedURL, but of course we need to afford the cache

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?