System requirements

Functional:

1. given a normal url, covert and return a shorten url
2. give a shorten url, redirect to the normal url.

Non-Functional:

High availability

Low latency

prevention from the attackers

stats like the url clicks ratio per shorten url

Capacity estimation

Assume:

200 requests per second for creating short urls

20, 000 requests per second for viewing short urls (redirecting short URL to long URLs)

Store 1 year data

Storage to save 1 year's data:

1 year: 200 * 60 * 60 * 24 * 365 ~ 6 Billion urls to generate. Assume the short url only contains A-Za-z0-9. So a string with 6 chars should be sufficient as 6^65 > 65 Millions. Assume the long url length is 100 Bytes on average. So the total disk space for 1 year's data is (100 + 6) * 6 Billion ~ 636GB. So at the disk level, capacity/scaling is not a concern.

Cache

Assume average lifetime of a shorten url is 30 days.

So total number of alive urls ~ 200 * 10^5 * 30 = 600 million. The total size is about 50GB. Easy to fit into the redis on a normal machine

QPS:

20,000 requests per second is not a big challenge to a normal machine. And the server could scale out easily by adding new machine. So we could easily figure out that when the QPS increases in the future, our solution could scale out promptly and elastically via horizontal scaling.

API design

api to create a shorten url. It follows REST

POST: https://tinyurl.com/api/create

Return: http.ok with a generated shorten url

api to redirect to normal url from shorten url

GET: https://tinyurl.com/{short_url}

Return: 302 and redirect to the normal url

Database design

a normal SQL database. A table called shortURL with the following columns:

shortenurl: shorten url with 6 character long

normalUrl: normal url

createdTimestamp: time

High-level design

has a loadbalancer to distribute the traffic

stateless API service could scale out easily

cache helps to improve the response time and reduce the workload overhead from database

Request flows

Detailed component design

Generate logic:

We could use a MD5 to hash the normal url. And we only take the first 6 characters. Then check with DB if the shorten url exists. If not, we save it to the DB and return to the users. If it exists, we could take the next 6 characters, repeat the previous step, until we find the one.

During this process, we introduce the way to detect the collision by checking the data in DB. It should handle our current traffic. If in the future we find the response is delayed due to the DB call, we could have a bloom filter service. Bloom service is very compact and we could easily fit it into the memory and it could speed up the query.

Trade offs/Tech choices

Failure scenarios/bottlenecks

Future improvements

If we want to enable auth, we could add an auth micro service.

Introduce Message Broker like Kafka, so other services could consume the data like url click for further process (data aggregation). For example, a service could subscribe to the kafka to aggregate the click count per url. It will help to identify the hot data. So we could further adjust our solution based on the aggregated data.