Design a URL Shortener
A deep dive into the system design and architecture.
Designing a URL shortening service is a classic system design interview question. It seems simple on the surface but touches on nearly every critical aspect of building a large-scale, distributed system: scalability, availability, data modeling, and latency.
In this deep dive, we'll walk through the process of designing a service like TinyURL or bit.ly, from clarifying the requirements to scaling it for millions of users.
1. Understanding the Problem: Requirements and Goals
The first step in any system design interview is to understand the problem and clarify the requirements. Let's define the core features and constraints.
Functional Requirements
Shorten URL: Given a long URL, the service must generate a much shorter, unique alias.
Redirect URL: When a user accesses the short alias, they must be redirected to the original long URL.
Custom Alias (Optional): Users should be able to choose their own custom alias, which must be unique.
Analytics: The system should track the number of clicks for each short link.
Non-Functional Requirements
High Availability: The service must be highly available. Redirection is a critical path; it cannot fail. We'll aim for 99.99% availability.
Low Latency: The redirection process must be extremely fast. A P99 latency of under 100ms is a good target.
Scalability: The system must be able to handle a high volume of traffic, both for creating new links and for handling redirects.
Scale and Constraints (The "Back-of-the-Envelope" Calculation)
Let's assume some numbers to guide our design:
New URLs per month: 100 million
Read/Write Ratio: 100:1 (For every link created, it will be accessed 100 times)
Total Redirects per month: 100 million * 100 = 10 billion
Queries Per Second (QPS) for Redirects: (10,000,000,000 redirects / 30 days / 24 hours / 3600 seconds) ≈ 3,850 QPS
QPS for Writes (Shortening): 3850 / 100 ≈ 40 QPS
This calculation immediately tells us our system is read-heavy, and the redirection path must be heavily optimized.
2. High-Level Design (The Whiteboard View)
A high-level architecture would consist of several decoupled services to handle the different responsibilities.
Client: A user's browser or mobile app.
Load Balancer: Distributes incoming traffic across our services.
API Service (Write Path): Handles requests to create new short URLs.
Redirect Service (Read Path): Handles incoming short URLs and performs the redirection. It is optimized for speed.
Key Generation Service (KGS): A dedicated service responsible for providing unique, short keys.
Database: A persistent storage layer for the URL mappings.
3. Deep Dive: Core Components
A. The Key Generation Service (KGS)
This is one of the most interesting parts of the problem. How do we generate short, unique keys that are not easily guessable?
Approach 1: Hashing (e.g., MD5/SHA256)
How: Hash the long URL and take the first 6-8 characters.
Problem: Collisions. Two different long URLs could potentially produce the same hash prefix. You would need a complex collision resolution strategy. This is generally not a good approach.
Approach 2: Base62 Encoding (Recommended)
How: Our character set is [a-zA-Z0-9], which has 62 possible characters. We can use a large, distributed counter (like a database sequence or a dedicated service like Zookeeper). When a new URL comes in, we get the next number from the counter (e.g., 1001). We then convert this number to Base62.
Example: 1001 in Base62 is g5.
Benefit: This guarantees that every key is unique and the keys are a fixed length. With 7 characters, you can have 62^7 (around 3.5 trillion) unique combinations, which is more than enough.
Implementation: To avoid a single point of failure, the KGS can pre-generate millions of keys in batches and store them in a fast key-value store like Redis. The API Service can then fetch a key from this pool when needed.
B. The Database
Given our scale (100M writes/month) and read-heavy nature, the choice of database is critical.
SQL (e.g., PostgreSQL):
Schema: A simple table urls (short_key VARCHAR(8) PRIMARY KEY, long_url TEXT, created_at TIMESTAMP).
Pros: Reliable, well-understood, ACID compliant.
Cons: Scaling writes across multiple servers (sharding) can be complex to manage.
NoSQL (e.g., DynamoDB, Cassandra) (Recommended):
Schema: A key-value model where the short_key is the partition key.
Pros: Built for horizontal scalability and extremely high throughput, which is perfect for our write and read requirements.
Cons: Less flexibility for complex queries (though we don't need them here).
A NoSQL database is a better fit for this specific problem due to its massive scale requirements.
C. The Read Path: Caching is King
Our calculation showed ~4000 reads per second. Hitting the database for every single redirect is inefficient and will not meet our latency goals. We need an aggressive caching strategy.
Cache: We can use a distributed in-memory cache like Redis or Memcached.
Flow:
When a request for short.url/xyz123 comes in, the Redirect Service first checks the cache for the key xyz123.
Cache Hit: If the key exists in the cache, the service retrieves the long URL and immediately returns the 301 redirect. This is extremely fast.
Cache Miss: If the key is not in the cache, the service queries the main database.
It retrieves the long URL, writes it to the cache for future requests, and then returns the 301 redirect.
Eviction Policy: We can use a Least Recently Used (LRU) policy. If the cache is full, it will automatically remove the links that haven't been accessed in the longest time.
4. Putting It All Together & Follow-Up Questions
Analytics: The click tracking should be done asynchronously. The Redirect Service, after serving the redirect, can publish an event (e.g., { "short_key": "xyz123", "timestamp": "..." }) to a message queue like Kafka or SQS. A separate fleet of analytics workers can then consume these events and update a data warehouse or analytics database in batches, ensuring the critical redirect path remains fast.
Rate Limiting: We should implement rate limiting on the API Service (write path) to prevent abuse, such as a single user creating millions of links.
Custom Alias: When a user requests a custom alias, we simply check if that key already exists in our database. If it does, we return an error. If not, we use their provided key instead of one from the KGS.
This design provides a scalable, highly available, and low-latency solution that meets all our initial requirements.
You've read the solution. Now, can you design it yourself?
Reading is a great first step, but the real learning happens when you put your knowledge into practice. Use our AI-powered workspace to tackle this exact problem. Clarify requirements, draw your design on the whiteboard, and get instant, expert-level feedback on your solution.