System requirements

Functional:

• Generate unique shorten url using algorithm like md5, hashing
• Store mapping of shorten url with long url
• Less collision while generating shorten url
• Redirect to long url efficiently using short url. Redirecting should be seamless and fast.
• Expiry and management of urls(Optional)

Non-Functional:

• Availability of the system
• Scalability of the system
• Latency should be minimal for retrieving the long url with short url using caching.
• Consistent
• Rate limiting the request to prevent server overload

Capacity estimation

1 billion users:->

1 user do average 5 request per day:-> 1billion * 5

Request/sec :-> 1billion*5*/24*60*60 :-> 50000 req/sec

Let say, we want to store data for 1 year-->

Average url size-> 2000 characters --> 2000 * 2 bytes --> 4kb

Shorten url size -> 64 characters --> 64 * 2 bytes --> 128bytes

Total 4128 bytes * 100000000 * 365 = 2.064e+13 bytes

API design

Define what APIs are expected from the system...

generate url api :-> /api/shortUrl/service/generate/shortUrl/{url}

Response :-> string

get url from short url:-> /api/shortUrl/get/longUrl/{shortUrl}

Response: -> String

Database design

Url Mapping table

id, short_url, long_url, created_at, created_by_user_id, access_count

Create indexes:

on short_url colum

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

Create two micro services like URL generate Shorten Service and Get Shorten Url

Database, we can use postgres/Mysql database for consistency.

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

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...

We can use sql database to store and get shorten url.

We can use MD5 and base62 algorithm to get shorten url. To avoid collision we can use counter technique to store the data.

Trade offs/Tech choices

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

Using sql database, it can give you consistency, but it is heavy calls to get exact url in the database from large set of data.

Creating indexes will reduce search query and reduce latency.

But it will use more space to store the data.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Single point of failure of database, multiple replica of database should be running with availability and consistency.

Collision can happen, for that we can use counter hashing technique

Future improvements

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