Design a URL shortener? — System Design for Product Managers

 URL Shortener

URL shortener is the way by which we can reduce the size of the big URL into a smaller one and clicking on the smaller URL will take you the original one. The smaller URL is easy to share and doesn’t occupy much space. It is very useful while doing some tweets.

Design Requirement

Functional Requirement

1. URL shortener should be able to shorten any URL given to it, and it should be unique alias of it.
2. When the user clicks on the shortened link, the user should get directed to the original link.
3. The user should be able to define the time till which it is available.

Non Functional Requirement

1. The availability of the system should be high because if our system goes down, then all the URLs will start failing.
2. URL should be available in minimal time; minimum latency should be there.
3. The URL shouldn’t be predictable.

Capacity Estimation

1. We can assume that for every URL shortening service, there would be 100 reads. So basically, there would be a 100:1 read/write ratio to the system.
2. Assume that our URL shortening service is handling 500M requests for shortening.
3. We need to retain every URL shortening request and shortened URL for around 5 Years.

Traffic Estimation

Since every month, 500M request comes and read/write ~ 100, so there would be around 500*100M ~50000M or 50B redirections per month. Assuming 30 days,

No. of shortening requests per second ~ 200URLs/sec

No. of reads to shortened URL per second ~ 20K URLs/sec

Storage Estimation

Assuming that size required to store the shortened URL and the requested URL is ~ 0.5KB

Storage estimate ~ 0.5*5*12*500M ~ 15TB

Bandwidth estimation

For a write request, there is around 200 Requests per second, so required bandwidth is ~ 200*0.5KB
~100KB/sec

For a read request, there is around 20K Requests per second, so the required bandwidth is ~ 20K*0.5
~10MB/sec

Memory Estimation

Since we want to store some hot URLs in Cache, we will be using the 80–20 rule. 80% of the traffic comes from 20% of the URL, so we want to cache those URLs.

Total cache memory = 0.2*20K*3600*24*0.5 ~ 170GB

Since there will be a lot of duplicates in the read request, so the actual Cache memory required will be much lesser than 170GB.

API Interface

String getURL(String URL, String Time, String UserID);
This function will take the original URL as a string and give the shortened URL.

Void deleteURL(String URL_KEY)
If the user wants to delete the URL, in that case, the person can select the URL he wants to delete, so this function takes the URL_KEY and delete it.

Database Design

Since we need to store billions of records and it is read-heavy, so we should use the NoSQL database, which will be easy to scale.

System Design and Algorithm

When a client request for URL shortening service, we can compute the unique hash key of the requested URL. Since we need to store around 50M*12*5 ~ 3B URLs, they need to be unique. We can use Base64, length of 6 or length of 8. In the case of a length of 6, we will be able to have 64⁶ (68 Billion) unique URLs, and in the case of a length of 8, we will be having 64⁸(380 Trillion) unique URLs. So we can go ahead and have Base 64 of length 6 URLs.

High Level System Design

-- Technomanagers