Loading...
The system should generate a unique shortened URL for every original URL without collisions.
The length of the shortened URL should be chosen based on the expected number of URLs.
If only lowercase English alphabets are used, the total number of possible combinations for a URL of length n is:
26n26^n26nFor example:
In production systems, Base62 encoding (A–Z, a–z, 0–9) is generally preferred because it provides many more combinations while keeping URLs shorter.
The service should provide low latency for both URL creation and URL redirection. Frequently accessed URLs should be served from a cache or CDN to minimize response time.
The service should remain available even if individual application servers, cache nodes, or database instances fail. This can be achieved using multiple stateless application servers, replicated caches, and database replicas.
The application should scale horizontally by adding more application servers, cache nodes, and database replicas to handle increasing traffic.
The system should continue serving requests during component failures. If the cache is unavailable, requests should fall back to the database. If an application server fails, the load balancer should route traffic to healthy servers.
The system should ensure a unique mapping between the original URL and the shortened URL. Concurrent requests for the same URL should not create duplicate mappings.
Since URL redirection is expected to be much more frequent than URL creation, the system should optimize read operations using caching, CDN support, and database read replicas.
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
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:
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
Simply saying "we have a replica database" is not enough. High availability should cover every major component.
The range allocator should use leader election (e.g., ZooKeeper, etcd, or Consul) so only one leader assigns ID ranges.
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