Loading...
High availability
Low latency
prevention from the attackers
stats like the url clicks ratio per shorten url
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 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
a normal SQL database. A table called shortURL with the following columns:
shortenurl: shorten url with 6 character long
normalUrl: normal url
createdTimestamp: time
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
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.
Rational DB works based on the current assumption. If we want to store more DB and QPS inceases significantly, Switching to a NoSql DB could be a option.
Also we could introduce a CDN, but it may increase the cost.
If our hash runs out, we will no longer be able to provide any shorten URL. We could choose to increase the URL length, but a long URL may not satisfy user's requirment. Hence we should determine the length carefully.
Under some cases, when the hash collision keeps happening, it would increase the response time.
We have DB in one region. If the disaster happens in that region, we will lose all data. We could introcude replica in multiple regions, but it would increase the write latency
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.
We could also allow user to customize the shortenUrl.