Designing a High-Throughput URL Shortener

Welcome to your next lesson in our module on Practical System Design Interviews. In our previous session, we constructed a complete design for a distributed rate limiter, focusing on atomicity and state management with Redis. That exercise gave us a solid foundation in handling distributed state and protecting services from overload.

Today, we'll tackle another cornerstone of system design interviews: designing a high-throughput URL shortener like TinyURL or Bitly. Your goal for this lesson is to design a high-throughput URL shortener service, focusing on read performance and storage optimization. This problem is a favorite in interviews because it appears simple on the surface but hides significant challenges in scalability, data management, and performance at scale—perfect for assessing your ability to think about systems that serve millions of users.

We'll follow the same interview-style approach: starting with requirements and estimations, moving to high-level architecture, and then diving deep into the critical components, trade-offs, and scaling strategies.

Step 1: Understanding the Problem and Estimating Scale

Just like in a real interview, our first step is to clarify the requirements and scope. This demonstrates structured thinking and ensures we're solving the right problem. A URL shortener's core job is to take a long URL and generate a much shorter, unique alias. When a user accesses the alias, they are redirected to the original URL.

Let's begin by establishing the core functional and non-functional requirements and then performing some back-of-the-envelope calculations to understand the scale we're designing for.

To solidify this, let's look at more detailed calculations. Estimating traffic and storage needs is crucial for justifying our architectural choices later.

Let's summarize the key requirements based on these readings:

Functional Requirements:

• URL Shortening: Users can submit a long URL and receive a unique, shorter URL.
• URL Redirection: Users accessing a short URL are redirected to the original long URL.
• (Optional Extensions) We'll acknowledge but defer custom aliases and analytics.

Non-Functional Requirements:

• High Availability: The service must be highly available; broken links are unacceptable.
• Low Latency: Redirects must be extremely fast (e.g., under 50-100ms).
• Scalability: The system must handle a massive number of links (billions) and a high read throughput (tens of thousands of redirects per second).
• Durability: Once created, a link should persist indefinitely unless explicitly expired.

With these requirements in mind, we can move on to the high-level design.

Step 2: High-Level Architecture and API Design

A core principle in designing such a system is to separate the write path (creating a short URL) from the read path (redirecting a short URL). Their performance characteristics are completely different. The read path must be optimized for speed above all else, while the write path can tolerate slightly higher latency.

Our high-level architecture will look familiar, as it's a standard pattern for many scalable web services.

API Endpoints

A simple RESTful API would suffice:

1. URL Creation: POST /api/v1/shorten
   • Request Body: { "long_url": "https://example.com/very/long/path?param=value" }
   • Success Response: 201 Created with { "short_url": "https://short.ly/xyz123" }
2. URL Redirection: GET /{short_code} (e.g., https://short.ly/xyz123)
   • Success Response: An HTTP redirect.

Choosing the Right Redirect

A subtle but important detail is the HTTP status code used for redirection. This is a classic point of discussion in interviews that shows depth of knowledge.

As the resource explains, a 302 Found or 307 Temporary Redirect is generally preferred. While a 301 Permanent Redirect would offload traffic to the browser's cache, it would also prevent you from collecting click analytics, a primary business driver for such services. Using a temporary redirect ensures the request hits your server every time, allowing for accurate tracking at the cost of higher server load—a load we will design our system to handle.

Step 3: Deep Dive into the Write Path

The main challenge in the write path is generating a unique short code for every new URL. There are two primary approaches.

Approach 1: Hash-Based Generation

You could take the long URL, hash it using a function like MD5 or SHA-256, and then take the first 7 characters of the Base62-encoded hash.

• Pro: It's deterministic. The same long URL will always produce the same short URL, which can be useful for deduplication.
• Con: Collisions. Two different long URLs might hash to the same 7-character prefix. You would need to check the database for existence, and if a collision occurs, you'd have to apply a salt or use a different part of the hash and try again. This adds latency and complexity.

Approach 2: Counter-Based Generation

A more robust method is to use a unique, incrementing number for each URL.

1. Assign a unique ID (e.g., from a distributed ID generator) to each new URL.
2. Convert that ID into a Base62 string. Base62 uses [0-9], [a-z], and [A-Z], giving you 62 possible characters.

This approach is elegant and avoids collisions entirely. Let's see how the math works.

The main challenge with this approach is generating the unique ID at scale. A single database auto-incrementing key becomes a bottleneck. This is where a distributed unique ID generator (like Twitter's Snowflake algorithm, which we'll cover in a future lesson) comes into play. For now, it's enough to state that we need a service that can vend unique, roughly-ordered 64-bit integers without a single point of failure.

Given your experience with Go, you can imagine this as a service that combines a timestamp, a machine ID, and a sequence number to generate a unique ID for every request, which is exactly what Snowflake does.

Step 4: Deep Dive into the Read Path

This is the most critical part of our design, as it must be incredibly fast and handle immense traffic. The flow is: Client -> Load Balancer -> Application Server -> Cache -> Database.

Caching, Caching, Caching

As our estimations showed, reads outnumber writes by at least 100:1. URL access patterns also follow a power law: a small number of URLs get the vast majority of traffic (the "viral" links). This makes our system a perfect candidate for aggressive caching.

We will implement a cache-aside strategy using a distributed in-memory cache like Redis. In our last lesson, we saw how effective Redis is for managing shared state. Here, we'll use it for its raw speed.

The cache-aside logic is simple and effective:

1. The application server receives a request for a short code.
2. It first checks Redis for this code.
3. Cache Hit: If the code is in Redis, the long URL is returned immediately.
4. Cache Miss: If the code is not in Redis, the application queries the main database. It then stores the result in Redis (with a Time-To-Live, or TTL) and returns the long URL.

Subsequent requests for the same code will now be cache hits.

Database Optimization

For the 5% of requests that miss the cache, we need the database lookup to be as fast as possible.

• Data Model: A simple schema in a database like PostgreSQL or MySQL would work. Given your background, this should be straightforward.
  • short_code (varchar, Primary Key)
  • long_url (text)
  • created_at (timestamp)
  • expires_at (timestamp, optional)
  • user_id (bigint, optional)
• Indexing: The short_code column must be the primary key or have a unique index. This ensures lookups are extremely fast, typically O(log n) or O(1) depending on the index type (e.g., B-Tree or Hash).

Step 5: Achieving High Throughput and Storage Optimization

Now, let's address the core of the learning outcome: scaling to high throughput and optimizing storage.

Scaling Reads and Writes

A single database server, even with caching, will eventually become a bottleneck.

1. Read Replicas: The first step is to use database replication. A primary database handles all writes, and one or more read replicas handle reads. This distributes the read load and is a standard feature in databases like PostgreSQL and MySQL.
2. Sharding: When the data size exceeds what a single machine can hold (we estimated terabytes of data over time) or the write throughput becomes too high, we must partition our data across multiple database servers. This is called sharding.
   • Sharding Strategy: We can shard the database based on the short_code. A simple strategy is to take a hash of the short_code and use it to determine which shard stores the data. For example, hash(short_code) % N, where N is the number of shards.
   • This is conceptually similar to how Redis Cluster distributes keys, a concept from our last lesson. Since you've worked with MongoDB, you'll know it has built-in support for sharding, making it a strong contender for this use case as well.

Storage Optimization

As the system scales to billions of URLs over many years, the storage cost can become substantial.

• Data Tiering: We can observe that the vast majority of links are only accessed frequently for a short period after creation. An old link from 5 years ago is likely "cold." We can implement a hot/cold data tiering strategy.
  • Hot Tier: Frequently accessed data lives in our main, high-performance sharded database (e.g., PostgreSQL or MongoDB on SSDs).
  • Cold Tier: After a certain period of inactivity (e.g., 1 year with no clicks), a background job can migrate the URL mapping to cheaper, slower storage like Amazon S3 or a disk-based archive database.
  • If a request for a "cold" URL comes in, the system would fetch it from the cold storage (a slow one-time operation), serve the redirect, and potentially "promote" it back to the hot tier. This significantly reduces costs at massive scale.

This is the kind of advanced optimization that interviewers look for when assessing senior candidates.

Conclusion

We have successfully designed a URL shortener capable of handling high throughput with a focus on read performance and storage optimization. This design journey took us from basic requirements to advanced scaling techniques.

Key Takeaways:

• Separate Read/Write Paths: Optimize each path independently based on its unique performance requirements.
• Smart ID Generation: The choice between hash-based and counter-based ID generation has significant implications for uniqueness and scalability. The counter-based approach using Base62 is generally superior but requires a distributed ID generator.
• Aggressive Caching: For read-heavy systems, a cache-aside pattern with a distributed cache like Redis is non-negotiable for achieving low latency.
• Scale the Database: Start with read replicas, but plan for sharding from the beginning to handle data growth and write load.
• Optimize Storage Costs: At scale, data tiering (separating hot/cold data) is a crucial strategy for managing storage costs without significantly impacting user experience.

This design brings together many fundamental concepts of distributed systems. The patterns we've discussed—caching, sharding, replication, and separating workloads—are applicable to countless other problems you'll encounter.

In our next lesson, we'll shift gears slightly to another common interview topic: comparing real-time communication protocols like WebSockets and long-polling, and understanding their use cases, which will set the stage for designing a scalable chat application.