...
...
...
...
...
...
...
...
...
...
| Tip |
|---|
The Framework proposed in this space (Alex Xu) is applied to propose a design : Getting started - a framework to propose... |
On this page.
| Table of Contents |
|---|
Introduction
URL shortening is used to create shorter aliases for long URLs. We call these shortened aliases “short links.” Users are redirected to the original URL when they hit these short links. Short links save a lot of space when displayed, printed, messaged, or tweeted. Additionally, users are less likely to mistype shorter URLs.
| Code Block | ||
|---|---|---|
| ||
//Shorten long URL through TinyURL
from https://www.educative.io/courses/grokking-the-system-design-interview/m2ygV4E81AR
to https://tinyurl.com/rxcsyr3r |
Step 1 - Understand the problem and establish design scope
How it works ? | URL https://www.blablablabla.com/q=chatsystem&c=logged&cl=long is the original URL and we create un alias with shorter length: https://tinyurl.com/y7keocwj |
|---|---|
Traffic volume ? | 100 Million URLs per day |
How long is the shortened url ? | As short as possible. |
Characters in the shortened URL ? | Combination of numbers and characters (a-z, A-Z). |
Can it be deleted or updated ? | CANNOT be deleted or updated. |
Back-of-the-envelope calculation
For Traffic
Write operations: 100 million URLs are generated per day
Write operation per second: 100 million / 24 / 3600 sec = 1160 operation per sec.
Read operation: Assuming 1160 * 10 = 11600 read per sec.
Assuming the URL shortener service runs for 10 years, this means we must support 100 Million * 365 * 10 = 365 billion records.
Assuming average length is 100
For Storage
Storage requirement over 10 years : 365 billion * 100 bytes = 36.5 TB.
Step 2 - High-level design
API endpoints
A URL shortener primary needs 2 API endpoints :
URL Shortening : to create a new short url, a client sends a POST request which contains one parameter: the original long URL.
POST api/v1/data/shorten : return short url.
URL redirecting : to redirect a short URL to the corresponding long URL, a client sends a GET request.
GET api/v1/shortUrl : return long url for http redirection.
URL redirecting
...
301 redirect Shows that the request URL is permanently moved to the long URL. So, the browser caches the response, and subsequent requests for the same URL will not be sent to the URL shortening service. Instead, requests are redirected to the long URL server directly.
URL shortening
How do we encode the actual URL ? www.tinyurl.com/{hashValue}.
...
Requirements :
Each longURL must be hashed to one hashValue.
Each hashValue can be mapped back to the longURL.
Step 3 - Design deep dive
Data Model
Everything is stored in a hash table, but in the real world systems, it’s limited and expensive. A better option is to store <shortURL, longURL> mapping in a relational DB.
URL | |
|---|---|
PK | id |
shortURL | |
longURL | |
URL Shortening
...
It’s expensive to query the DB to check if shortURL exists for every request. We can cache URLs that are frequently accessed.
Scenario 1: URL is expired or user do not have permission
...
Scenario 2: URL not found and find original URL
...
Scenario 3: URL found and return error or redirect to original url
...
URL Redirecting
As there are more reads than writes, <shortURL, longURL> mapping is stored in a cache to improve performance. However, Load Balancer play a role in the URL redirecting.
...
Step 4 - Pros & Cons
Pros: higher click-through rate; people are used to them; promote sharing; offer ability to track performance.
Cons: need rate limiter (control traffic); web server scaling (stateless); database scaling (replication and sharding)