Loading...
1. Upload full link and get the shortened link
2. Ensure the short URL is unique
3. When user falls into the shorted URL, the user should be redirected to the original URL
1. Available
2. Scalable
3. Fast, low latency
1,000,000 links are generated each day
The link should expire after 3 years (~ 1000)
System should be able to store over 1,000,000,000 link generation requests in 3 years.
Assuming that each link has the max length of 12 characters. Max number of characters for unique url id is 6.
sh.io/123456
We should be able to store 12*8*10^9 = 96*10^9
255^6 >= 96*10^9,
274 941 996 890 625 >= 96 000 000 000
Memory requirements: 96 * 10^9 bits or ~ 12 Gb
96*10^9 / (8 * 10^9) = 12 Gb
8 for converting bits into bytes, 10^9 division is converting bytes into Gigabytes
For each day, we should be able to handle:
12 000 Mb / 1000 = 12 Mb a day
/upload-link/{original_url}
should return the shortened link in the response consisting 12 characters max
MongoDB schema:
key value store
key -> original_link
value -> shortened_link
Keeping like an array of objects would be slower solution in terms of time and memory complexity
{
original_link: string;
shortened_link: string;
}
Keeping as key - value store, it would be much more efficient
{
original_link: shortened_link; # reference to a shortened link
}
10 same hash_strings. 10 collisions
The first will take the initial hash value.
The second will take the second hash value. (We rehash it one more time)
In case of hashing collisions, we generate new hash based on the following formula:
hash_1_str = hash(original_link)
if hash_1_str is already present in MongoDB store, then
hash_2_str = hash(hash_1_str + original_link)
1. In case of keeping only two MongoDB instances - read only and write only worldwide, it may lead to the latency.
2. Adding caching layer may add some additional costs
Try to discuss as many failure scenarios/bottlenecks as possible.
1. In case of even higher demand, if ten billion requests are made per day, then we may have more collisions and get out of all possible unique hash strings to encode the shortened url. For that case, we need to extend the length of a hashing string. Example, we can extend it from 6 to 10.
1. To reduce the latency, it is better to store caching mechanisms or database instance near the user's location. We can use CDN like AWS Cloudfront for that. Our caching, primary and database servers would be located nearby users. Let's say, one group of servers in North America, one in South America, one in Asia and on in Europe.