System requirements

Functional:

1. Shorten the URL. Convert the original long URL to a short URL.
2. User can customize the shorten URL. User provides a preferrable shortened URL. If this shortened URL already exists, the service returns error. If this shortened URL doesn't exist, the service should map original long URL to this customized shortened URL.
3. For a short URL, redirect users to the original long URL.

Non-Functional:

1. Performance: low latency. it should be fast to shorten the URL and redirect users to the long URL.
2. Availability: It should be always available to users. No down time.
3. Scalability: It should be scalable. It can support the case when more and more users use this service.

Capacity estimation

assume 10 million shortening requests daily

assume 1 URL mapping entry needs 500 bytes storage

for storage, 10 M * 500 bytes = 5GB daily, 5GB * 400 = 2000 GB = 2TB yearly

assume 1000 million redirect request daily

for QPS, 1000 M / 86400s = 1000000K / 100000 = 10K/s

throughput:

incoming: 5GB/86400

outgoing: 500GB/86400

API design

shortenURL(user_id, original_url)

• it returns shortened URL

shortenURL(user_id, original_url, customized_url)

• it returns error if the customized_url has been used now.
• it returns 200 OK if the customized_url has not been used.

redirectURL(user_id, short_url)

• if the short url exists, redirect users to the original long url.
• if the short url doesn't exist, returns error.

Database design

We should have a database that maps from short_url to original_url.

The schema looks like

• short_url
• original_url
• user_id

High-level design

All the requests will first go through load balancer to evenly distribute the workload among services. We can also add a rate limiter there to restrict user requests to mitigate abuse.

The shortenURLService is handling the request of shortening the URL. It stores the shortened URL to original long URL mapping in the database. The database will push the frequently accessed URLs in the cache.

The redirectURLService is handling the request of redirecting to original URL. It looks up the cache first and then check database if cache is missing this data to get the original URL. It then redirect users to the original URL.

Request flows

To shorten the URL, a request will first go through rate limiter to make sure that not a high burst of requests go to the service. It can go through the load balancer to be served by a server. If a customized short url is not provided, it generates the unused short URL and stores the mapping from short URL to long URL in the database. Then server returns short URL to user.

If a customized short url is provided, the server should first check if the short url exists. We can utilize bloom filter functionality to check if a short URL exists. If it exists, the server returns error. If it doesn't exist, the server stores the mapping in the database and returns success.

To redirect the URL, the request also goes through rate limiter and then load balancer to be served by a server. The server checks the cache (then database if needed) to get the mapping original URL. If it exists, then redirect. If it doesn't exist, then return 404 NOT FOUND.

Detailed component design

How should we shorten the url and also make sure the url is unique?

And we also need to make sure that users cannot see the pattern.

To shorten the URL, we should have a sequencer to generate a unique 64-bit id. This id is globally unique even in this distributed environment. Then we can use base62 encoding (including 0-9, a-z, A-Z) to encode this unique id.

The sequence id is a combination of worker id, timestamp and sequence number. Then we shouldn't have collision problem. Two requests won't generate the same short URL.

We also need to check if a customized URL is already used. We can use bloom filter. For bloom filter, we have multiple hash functions and we maintain an array. We calculate hash values using those hash functions and mark those hash values in the array. For a given URL, we also check the corresponding hash values, if all of them are marked, then it's very likely that the URL is already used. Otherwise, we can use this URL. Using bloom filter can guarantee that a URL wasn't being used before.

For quick access and getting low latency, we should use cache.

For database, we can use no-sql database - key value store. The database should be partitioned where the partition key is shortened url. MongoDB is suitable for this use case since our system is a read-heavy system. The database should also be replicated, following primary and secondary replication strategy. The write is written to primary. And read operation can be done through both primary and secondary nodes.

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?