Loading...
The application takes input an url and shortens it. The shortened url points to riginal url and user can use this shortened url to access originl url.
The url shortener should haave a minimum length of url such that it generates a unique url for long and there is no collision.
There can be n^26 combination for any number n. So we need to caculate n based on our traffic to make sufficient unique url.
Suppose we need to shorten 50,000 URLs.
If the shortened URL consists of lowercase English alphabets only, then for a string of length n, the total possible combinations are:
26n26^n26nFor:
we will have a cdn before lb so latency can be reduced globally.
We will have multiple servers behind a load balancer to manage traffic.
Load balancer will choose the server with least load managing the traffic.
Now to avoid collision we will assign a range in which each server can make shortened url.
The shortened url will be generated based on algorithm. There will be a tracker, which will be on incremental basis, to be used by our url generator to make the string based on the tracker to avid collision. we can incrementally increase the string for url.
The url should handle generation of unique url even on simultanious request.
if simultaneous request comes, we will pick any
The application should cache the shortened url so it do not regenerates url and there is less read and writes on db.
The application should scale horizontally to handle large number of requests.
now for availability, if a server goes down the range in wich server could have generated data becomes unavailable. We can do two things here based on initial aassumption.
if we took n very large, so that even after losing some range leaves sufficient range, we can ignore it. This is most optimal approach we can have as increasing n by even 1 , range becomes too wide but computation does not inncrease significantly.
Secondly we can redestribute the range in remaining in remaining servers, but we will need a health checker and additional server for this.
For accessing origina api from shortened url, we need aaccess to datbase or cache only.
If cache mises, we have a ratelimited before databse to handle spike. as soon as db is read, cache is updated again and new request are redirected there.
We will have a rwaad replicat for our database, so if our db goes down we can use our replica for it
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
POST API
The user sends the originaal url in post request body and gets shortened url in return.
post request firt checks cache, it cache is missed, t checks in db aand if the url is not in db too, it genertes a new shortened url and returns it.
design
post: /shorten-url
body:{ long_url}
GET API
User tries to access the datbase via get api. The body contains shortened url and when made request, user is redirected to original url.
it is done by reading ache, if it missed then by reading database.
user requests the shortened url
the post request is made to our server with long url in its body
first shortened url is checked in cache , if found returns shortened url
if cache is missed, it reads database and if shorned url is found there, it returns the shortened url. Cache is updated accordingly.
if it is also not present in database, it goes to least bust server via load balancer.
Each server is assigned a range in which they can generate url string, so they are independent of each other while generating shortened url.
The server generates the shortened url.
It is wrote down in database and cache is updated.
finally the url is returned to user.
when user clicks on the shortened uurl, cache is checked if it is present there user is redirected to original url. else original url is fetched from db and user is redirected there.
A unique ID is required for every URL.
Instead of generating random strings (which may collide), every server receives a unique range of IDs.
Example:
Server 1:
1 - 100000
Server 2:
100001 - 200000
Server 3:
200001 - 300000
Each server maintains an incrementing counter within its assigned range.
we will have unique key for both short aand original url so we do not face collision
CREATE TABLE UrlMapping (
id BIGINT PRIMARY KEY,
original_url TEXT UNIQUE,
short_url VARCHAR(10) UNIQUE
);
Low latency
Flow:
Instead of generating random strings, every server is assigned a unique ID range.
Example
Server 1
1 - 100000
Server 2
100001 - 200000
Server 3
200001 - 300000
Each server maintains an atomic counter.
For every request
counter++
ID → Base26/Base62 Encoding
Generated Short URL
Since
two servers can never generate the same ID.
Additionally, the database has
short_url UNIQUE
original_url UNIQUE
If two users shorten the same URL simultaneously,
Therefore,
The system is read-heavy because URL redirection is much more frequent than URL creation.
To support increasing traffic,
Application Layer
Cache Layer
Database Layer
We will use sql database. The reason is we have definite schema so we can use sql db.
The model have schema as tabular format where we have two columns shor_url long_url.
we can easily query the short and corresponding long url and vice versa.
Key component:
URL shornner service: Shortens the url and writes in database.
It will take original url as input, checks if it present in cache or db and if not then following an incremental id, gets a shortened url assigened to it.
we have n already decided so we bave 26^n possible combinations.
URL fetching service: Redirects user to original URL
It will take shortened url as input and checks if key value pair is found in cache. iff not then it is checked in db and user is redirected to original url.
database: Stores the mapping of shortened url to original url. The database has ratelimiter to avoid its crashing.
Cache: Reduces read and writes on database.
CDN : A CDN can cache popular redirect responses close to users worldwide, reducing latency for frequently accessed URLs.
Load Balancer: Manages and redestributes traffic