System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

1. A user should be able to provide a long URL and corresponding short URL should be returned to the user.
2. A user enters a short URL then the user should be re directed to long URL.
3. If user enters non-existent short URL, they are redirected to an error page/ thrown HTTP 404.
4. A user should be able to provide a custom short URL along with long URL.
5. A user should be able to provide expiration time along with long URL.

Non-Functional:

List non-functional requirements for the system...

1. Latency for both creating short URL and redirecting short URL should be low.
2. This system should scale for millions of users.
3. Reliabilty: Once a URL is shortened, the URL should not be lost.

Capacity estimation

Estimate the scale of the system you are going to design...

We receive 10K shorten URL requests per day.

Read to write ratio: 10:1

QPS for write: 10000/10000 =1 QPS avg

Peak= 10 QPS avg

QPS for read: 10 QPS avg

Peak= 100 QPS avg

No of URLs to generate total= 1 trillion

short URL length= 7 chars

Long URL length= 100 chars

Expiration time= 4 bytes

Id= 4 bytes

Row size~ 120 bytes per row

Total storage= 120 TB

API design

Define what APIs are expected from the system...

1. POST

/shortenURL

Req parameter:

{ url: url_value,

shortURL: url_value,

expirationTime: epoch,

}

Response:

{ statusCode: 200

shortURL: url_value,

expirationTime: epoch,

original_url: url_value}

1. GET

/V1/fetch/{URL}

Req parameter:

{ url: shortened_URL}

Response:

HTTP 301/ 302 (for permanent redirection or temporary redirection)

It redirects to original UTL

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

Data Model:

Short URL => Primary

Long URL

expirationTime

We can use a NoSQL Db like Casandra or Amazon DynamoDb.

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

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

URL Generation Service

Approach 1:

Hashing + Encoding + Collision Handling

1. We take long URL and create a hash with any hashing algo eg: MD5, SHA256 etc
2. now eg: MD5 generates hash of 16 bytes
3. Take some bytes of hash so that if base 62 encoded they generate length 7 for 3.5 triliion URLs.
4. We encode that hash with base 62 encoding.
5. Now we check if the shortURL already exists, means there is a collision.
6. In case of collision we need to generate shortURL again by resolving collision using one of these techniques:
   1. Add a predefined string to long URL and rehash
   2. Change seed of hashing algo.
   3. Add a incremental id to short URL.
7. Check if this short URL exists in DB, and repeat this process till a new short URL is found.
8. Store this in DB.
9. Return response to user.
10. In case of custom URL check if custom URL exists if yes then throw error else do steps 8 and 9.

Approach 2:

Unique ID Generator

1. Use a unique Id Generator to generate a URL.
2. Map this short URL to original URL

URL Redirection Service

1. Check short URL in DB.
2. If does not exists throw an error like HTTP 401. (resource moved).
3. Return long URL with HTTP 301/ 302.
4. Which browser translates as redirect and translates to original site.
5. We can also cache top 20% URLs to improve latency with cache-aside pattern.

Trade offs/Tech choices

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

Comparison

Hashing + Encoding + Collision Handling

Pros:

1. Unpredictable URLs.

Cons:

1. Inconsistency latency to generate URLs to because of collision resolution.

Unique ID Generator

Pros:

1. Consistent latency as URLs are pre-generated by Unique ID Generator.
2. No colliison

Cons:

1. Predictable URLs

Failure scenarios/bottlenecks

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

1. We will use replication in DB layer to ensure durability and availability.
2. With 1 trillion records we don't want to store all URLs in one node, so we can shard into multiple shards using hash-based partitioning based on shortURL.
3. For redis we want to store top 20% URLS. Storage in Redis=120 * 120 * .2 TB = 2.88 PB. So we need to implement sharding and replication in redis as well. ShortURL can be used as hash key.
4. All servers are stateless and can be scaled by adding more instances dynamically.

Future improvements

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