System Design of Url Shortener
URL shortener is a service that takes a long URL and converts it into a shorter one. URL shorteners are widely used for sharing links on platforms where character count is limited, such as Twitter, or to make links easier to remember and share.
Questions to ask:
1. What the system does, if a user enters an url, and should get the shortened
url, is that correct.
2. what characters can be used for the hash. Can I assume it's a-z, A-Z and 0–9.
How short you want the short URL being.
If my hash has a-z, A-Z and 0–9 . 26 + 26 + 10 = 62^N combinations.
3. In 10years how many unique URL 400B. URLS needed unique hash key.
400B * 10B = 4TB
4TB storage to keep all urls for 10years.
4. Collision Prevention: With multiple servers for [W], how to avoid encoding
collisions from different servers?
5. When the URL shortening result becomes too large to be stored in one
machine, how to shard the DB?
6. How to scale [R] for both concurrent request volume and speed?Functional Requirement
- Shortened url/link against a long url.
- Click the short url should redirect to original long url.
- Users can create custom url with maximum character limit of 16.
- service should collect metrics like no. of clicks.
- Shortened link should stay in system for lifetime. Users should able to specify the lifetime.
Non-functional Requirement
- service should be highly available.
- URL redirection should be fast (even during peak loads).
- Shortened links shouldn’t be predictable.
Back of the Envelope
Shortened URL generated = 40/s
shortened URL generated in 100years = 120B
total URLs requests / redirected = 8000/s
so 700M requests per day.
Average URL length: 100 characters.
Short URL length: 7 characters.
Each mapping requires storage for the long URL, short URL, and metadata
(e.g., creation date).
Estimated storage per mapping: 150 bytes.
1 million URLs: 150 MB of storage.
To cache 20% of these requests, need
0.2 * 700M * 150bytes = 20GB cache memory.
Total storage 700M * 150bytes = 35TB
Expected lifetime of service = 100years , 100M shortened link created per month
, total no of data points or objects are :
100M / month * 100 years * 12 months = 120B
assuming size of each objects (short url, long url, created date, etc.)
500bytes long. total storage required 60TB.
Traffic estimation: 500M new url shortening requests per month.
10:1 read/write ratio, 50B redirections during same perion.
Can calculate query per second and URL redirection per sec.Extended Goals:
1. User should able to customize short url using REST API.
2. each URL expiration time can be configured.
3. Encoded URL.REST APIS Endpoint
createTinyUrl - POST
Expected parameters -
(api_dev_key string,
original_url string,
custom_url string,
user_name string,
expiry_data string)
returns: url_keys (string)
DeleteTinyUrl - DELETE
Expected parameters -
(api_dev_key string)
returns: boolDatabase Schema
url mapping table: // The primary table to store the mapping between short
// URLs and long URLs.
CREATE TABLE urls (
id SERIAL PRIMARY KEY,
short_url VARCHAR(10) UNIQUE NOT NULL,
long_url TEXT NOT NULL,
created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);
CREATE TABLE clicks ( // Tracks clicks for analytics, storing information
// like the user agent, referer, and IP address.
id SERIAL PRIMARY KEY,
short_url VARCHAR(10) NOT NULL,
clicked_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
user_agent TEXT,
referer TEXT,
ip_address VARCHAR(45),
FOREIGN KEY (short_url) REFERENCES urls (short_url)
);
CREATE TABLE users ( // Manages user accounts if the service
// includes user authentication.
id SERIAL PRIMARY KEY,
username VARCHAR(50) UNIQUE NOT NULL,
password_hash TEXT NOT NULL,
created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);
Most data being stored in mysql databases. High Level System design
Url shortener has microservice based architecture to handle different aspects URL shortening, redirection and analytics. The user submits a long URL via the frontend to the backend. Backend has the responsibility to generated to shortened url, manages URL mappings, handling redirecti-ons. The result URLs are in the format of https://short.ed/[hash]. “hash” is a six character string consists of [a-zA-Z0–9]. Backend generates a unique short URL using a hash function or base62 encoding. The short URL must be unique by every user ID and original URL combination. That means if two users short the same URL, they must get two different short URLs.
Backend stores the mapping in the database. Two databases manage by backend, 1. URL Mapping Table that stores long URLs and their corresponding short URLs, 2. analytics Table to stores data for tracking clicks and user engagement. Separate load balancers to distribute traffic across multiple instances.
Low Level Design
Since url shortener service has been developed based on highly distributed microservice based architecture, it’s divided into multiple smaller services.
The Encoding receiver buffers received requests before sending them to the Encoder in batch. This throttles the QPS to Encoder by sending a batch every XXX second (like every one second). In this way, Encoder won’t have the Denial of Service concern. Splitting/aggregating the request receiving and request processing is for a high throughput and high concurrency that addresses challenge of speed and volume. Speed means the maximum time a user can tolerate while waiting for the response. Volume means how many users will be concurrently use the shortened service.
Encoding service is to hold the large number of user connections which their requests are being processed by the Encoder. The Encoder does the heavy-lifting work. There are two critical elements: the encoding algorithm and the serialization mechanism.
This one-by-one processing of concurrent request is called serialization. The Encoder achieve serialization by putting each incoming requests from the encoding Receiver in the request queue. The enqueued task element has the request data (user_id, original_url, etc) and the socket of the Encoding Receiver. When a enqueued task is executed, the Encoder dequeue the task and use its socket to send the result to the corresponding Encoding Receiver.
We can deploy the enocoder in one webserver, but that may result in single point of failure and also the system will not be scalable. Single database not sufficient for 60TB of storage space and high load of 8K RPS.
To cater above limitation:
- We can add secondary webserver with loadbalancer infront of webservers.
- Sharded the database to handle huge object data.
- Added cache system to reduce load on the database.
While designing we have the options of different type of database to store URL information. In our case the requests are not the relational queries. We should go for nosql as easy to scale.
Since we know the databases will be read-heavy to handle large requests on a single link we need cache. Our cache should store 20% of most used urls. Load balancer is needed as we might have multiple access systems, and having multiple/distributed loadbalancer addresses the issue of any single point of failure.
The incoming volume scaled by adding more URL Redirector instances and load balance between them. They are stateless. Distribute the load among server using least connection method. Separate zookeeper service to ensure central configuration management with health check. Zookeeper solves some problem like:
- It gives our application servers unused range.
- Zookeeper also avoid single point of failure by running in multiple instances.
- If new server added, it can go and request zookeeper for unused ranged.
To handle the addition of new server or to load balance requests we can use consistent hashing for balanced distribution.
Generate Unique short url
To generate unique short url: original url needs to be encoded using base64. If we use MD5 algorithm, it will produce 128bit hash vale. Base64 will generate seven characters for the key. Sequentially generated urls are the security threat. We can add random 10–15 bits after the counter number to increase the randomness. Different shortening algorithm for url encoding and key generation service, since our hash consists of [a-z][A-Z][0–9] base64 has been used. With the base64 , that will have 7 characters can generate 350 unique URLs. By selecting encoding technique of base64 addresses design goals of:
- Able to store lots of short links (120B).
- Tinyurl should be as short as possible.
- Application resillient to load spike (for both url redirections and short link generations. ).
Sharding is a scale out approach for database table to get partitioned and each partition put on a separate RDBMS server. Before RDBMS can be sharded, several design decisions, like:
- What Sharding key must be choosen.
2. What Schema changes.
3. Mapping between sharding key, shards and physical servers.
Finally key generation service that will generate random 7 letter key (strings) before hand and stores them in a database. Whenever we want to shorten URL, we can take one of the generated keys and use it. The key generation service or KGS made sure that all the keys inserted into key DB are unique. one instance of KGS is a single point of failure. So we should have multiple instances of KGS (standby replica). We can use memcached which can store full urls with respective hashes. Before hitting backend storage the application servers can quickly check if the cache has desired urls. Cache also solves eventual consistency problem. since the data (newly inserted data) in cache, the user get most updated response consistently. For this we need correct cache invalidation time period that should be more than maximum time needed for all the nosql databases eventually get updates.
Serving [R] Redirecting URL Flow
Error Handling
When the DB write fails we should return proper error codes with error messages. If DB write fails, put the request to a queue that will be processed when DB write issue get resolved. DB persistor component takes care of all DB operations. URL shortner component send all the requests to a queue and DB persister picks the message from the queue and process them.
We should have separate hash lookup service that sits before the DB and answer hash look up queries.
- It serve as a “buffer” to DB. When there are too many connections, DB failure will result in the whole system (whole shard) down time. With this buffer, DB read loads are mostly shared by the lookup service.
- The Hash Lookup Service can have in-memory DB cache to speed up the query. Unlike the writing flows, users have much lower speed tolerance for reading flows.
- The Hash Lookup Service acts as the read scalability of the DB. This allows us to scale only the reading capacity of DB. The resource requirement of such machine is much lower than DB instances.
Analytics service
Separate analytic service to analyze click specific telemetric data collected.
- No of times short url clicked.
- Geographical location.
- Time of the day url clicked.
- Demographic of person who clicked the short url.
Click Aggregator is the service that tracks user clicks. Tracked data is aggregated and used for analysis. When user clicks the particular short url, we’ll send a request to our /click endpoint. Our server then track the click and respond with a redirect to the longer url via a 302 (redirect) status code. These raw events stored in an event database. Then, in batches, process the raw events and aggregate them into a separate database that is specially optimized for querying. It uses Cassandra, which is optimized for a large number of writes. Cassandra is not optimized for aggregations or range queries, which is why we need to perform batch processing to pre-aggregate. We’ll use Spark for the batch processing to produce aggregations. For range queries, we need something that is optimized for reads. OLAP databases like Redshift, Snowflake, or BigQuery are good choices.
But batch processing introduces significant delays. To address the delay issue, introduces stream for real time processing. System allows us to process events as they come in, rather than waiting for a batch job to run. This can be done by immediately writing the event to a stream like Kafka or Kinesis. A stream processor like Flink or Spark Streaming reads the events from the stream and aggregate them in real-time. The aggregated data can then be flushed to OLAP database.
The above diagram shows the complete flow of how our analytics service would able to work and get telemetric result based on the data url shortener service collect. I hope this would help to design your own url shortener service and further optimize it for better result.
