Loading...
Give a long url, return the short URL
Given a short URL, get the long URL and redirect to the website
scalable, available, robust
1 billion searches per day.
10% new URLs every day are new.
Read QPS=1000 URLs/sec
Peak Read QPS=2*1000
Data storage: 1 URL=500KB
10 million new URLs every day = 500*10million KB per day
=5TB per day.
2PB storage space to store URLs for 1 year
POST/v1/url (params: longURL)
response: shortened URL
GET/v1/url (params shortURL)
response: longURL
Hashmap with longURL as key and shortURL as value and vice versa.
There are various methods to undertake URL shortening.
We will try to convert the URL in which the shortened URL will only contain alpha numeric letters.
Possibilities of conversion: base 62, SHA, MD-5 hash
We will use base62 as it suites our requirement.
total URLs that can be stored: 62^7 if we are planning to make a hash value of length 7.
This will be able to store all possible conversions without collision.
Client through load balance approaches the web serves.
Web server checks the request of the client if it is asking for a GET url or POST url.
If it is get, it will check in the cache if the URL already exists, if not, a URL is generated using base 62 conversion and stored in the cache and database and tiny URL is returned to the user.
If URL already exists in the database, the short URL is returned to the user.
There are multiple ways as describes above in the high level design. Lets have a look at each of them.
If I will use SHA1 or MD5 hash, I might have to deal with collision. In that case my conversion to short URL will complex. Here I have to check if the calculated hash exists in the DB, if yes then it is a collision and I need to rehash by adding a random string after the long URL. Also these methods will not satisfy out requirements. Hence it is ideal to choose base 62 conversion.
The data base can be a key-val store (NoSQL) database something like cassandra. Cache can be a Redis cache.
As the system is distributed, I will be using multiple web servers and the load balancer will distribute the load across the servers.
How much data needs to be stored in the Database, accordingly we have to make a choice for storage space.
How much data needs to be stored in the cache.
We want our application to be cross regional, if yes then multiple instances across different availability zones and regions are to be setup.
There are possibilities of Single Point of Failure in case we do not thing of having redundancy. So we need to have redundancy at network level, server level, domain level, AZ level and regional as well.
Rate limiting is critical to avoid DDOS attacks.