Distributed Rate Limiting with Redis and Token Bucket

Welcome to the first lesson of our module on Practical System Design Interviews. In the previous module, we explored specific advanced distributed concepts like unique ID generation, cache stampedes, and cache penetration. Now, we'll shift our focus to synthesizing these and other concepts to solve a complete system design problem, just as you would in a high-stakes technical interview.

This lesson tackles a classic interview question that is fundamental to building scalable and resilient services. Our goal is to design a distributed rate limiter using Redis and the Token Bucket algorithm. Mastering this design demonstrates your ability to manage system load, protect services from abuse, and handle the complexities of distributed state management—all critical skills for the senior engineering roles you're targeting.

We will approach this problem as if we were in an interview: starting with requirements, moving to high-level design and algorithm selection, and then diving deep into the technical challenges of implementation, scalability, and fault tolerance.

Step 1: Understanding the Problem and Establishing Scope

In any system design interview, the first step is to clarify the requirements. A rate limiter's primary function is to control the amount of traffic a client can send to a service within a specific time frame. This protects backend systems from being overwhelmed, reduces costs, and prevents abuse.

Let's begin by watching a brief segment from the Hello Interview channel. An ex-Meta Staff Engineer will walk us through the typical functional and non-functional requirements for this problem, setting the stage for our design.

To summarize and consolidate, here are the core requirements we'll design for:

Functional Requirements:

1. Limit Requests: Accurately limit the number of requests based on configurable rules (e.g., 100 requests per minute per user).
2. Identify Clients: The system should be able to apply limits based on various identifiers like user ID, IP address, or API key.
3. Inform Clients: When a request is blocked, the system should respond with an appropriate HTTP status code (e.g., 429 Too Many Requests) and informative headers (X-RateLimit-Remaining, Retry-After).

Non-Functional Requirements:

1. Distributed: The rate limiting logic must work correctly across multiple servers or processes.
2. Low Latency: The check must be extremely fast (e.g., < 10ms) to avoid adding significant overhead to user requests.
3. High Availability: The system should be fault-tolerant. If the rate limiter fails, it shouldn't take down the entire application.
4. Scalability: The system must handle a high volume of traffic, such as the 1 million requests per second (RPS) mentioned in the video.
5. Memory Efficiency: The solution should not consume excessive memory, especially when tracking limits for millions of users.

Step 2: High-Level Design and Algorithm Choice

With the requirements clear, we need to make two key architectural decisions: where the rate limiter will live and which algorithm it will use.

Placement of the Rate Limiter

A rate limiter can be implemented in a few places:

• Within each microservice: This is simple but leads to duplicated effort and, more importantly, lacks a global view of the rate limit. A user could bypass the limit by sending requests to different services.
• As a separate service: Each microservice calls this central rate limiter service. This centralizes logic but adds a network hop and latency to every request path.
• At the edge (Middleware): The rate limiter is placed in the API Gateway or Load Balancer. This is the most common and effective approach. It intercepts all incoming traffic, enforces limits before requests hit your backend services, and keeps the logic centralized.

We will proceed with the edge placement, as it provides the best balance of concerns.

Choosing the Right Algorithm

Several algorithms can be used for rate limiting. While you don't need to implement them all in an interview, knowing the trade-offs is crucial.

While other algorithms have their uses, the Token Bucket algorithm is an industry standard (used by AWS, Stripe, etc.) for its flexibility and effectiveness. It allows services to handle temporary bursts of traffic while enforcing a steady average rate.

Here’s how it works:

• Each user (or client) has a "bucket" with a certain capacity of "tokens".
• Tokens are added to the bucket at a fixed refill rate.
• Each incoming request consumes one token.
• If the bucket is empty, the request is rejected.

The bucket size defines the maximum burst capacity, and the refill rate defines the sustained throughput. This combination is perfect for many real-world use cases where you want to allow a user to perform several actions quickly (a burst) but prevent them from hammering the system over the long term.

Step 3: Deep Dive into a Distributed Implementation

Now for the core of the design: how do we implement the Token Bucket algorithm in a distributed environment? Since our rate limiter runs on multiple gateway instances, they must share state. If each instance had its own local token bucket for a user, the rate limit would be effectively multiplied by the number of instances.

This is where Redis comes in. As a fast, centralized, in-memory data store, it's the perfect tool to hold the token bucket state for all users. For each user, we need to store two pieces of information:

1. tokens: The current number of tokens in their bucket.
2. last_refill: The timestamp of the last time the bucket was refilled.

The Race Condition Problem

Here's the critical challenge: a simple "read-then-write" approach from our gateway to Redis will fail under concurrency. Imagine this sequence:

1. A user has 1 token left.
2. Request A hits Gateway 1. Gateway 1 reads the token count from Redis: 1.
3. Simultaneously, Request B hits Gateway 2. Gateway 2 also reads the token count: 1.
4. Gateway 1 sees 1 > 0, allows the request, and writes the new count 0 back to Redis.
5. Gateway 2 sees 1 > 0, also allows the request, and writes its new count 0 back to Redis.

The user got two requests processed when they should have only gotten one. This is a classic race condition.

The Solution: Atomic Operations with Lua

To solve this, the entire sequence—read the bucket state, calculate refills, check tokens, decrement tokens, and write the new state back—must be executed as a single, atomic operation. Redis allows us to achieve this beautifully using Lua scripts. The script is sent to Redis, which guarantees its atomic execution without interruption.

Given your proficiency in Go, let's look at a concrete implementation. The official Redis documentation provides a fantastic guide that combines a Go application with a Lua script for a production-grade token bucket limiter.

This combination of a stateless Go application and a stateful, atomic Redis backend is the standard pattern for building a distributed rate limiter.

Step 4: Ensuring Scalability and Availability

Our design works, but we need to address the non-functional requirements for a large-scale system. A single Redis instance will become a bottleneck and a single point of failure.

Let's watch the final segments of the Hello Interview video, where the presenter discusses how to scale the Redis layer and ensure the system is fault-tolerant.

By using Redis Cluster, we get both sharding and replication out of the box. Redis Cluster automatically distributes the keys (e.g., our user:123 keys) across multiple nodes and can be configured to maintain replicas for each node, ensuring both scalability and high availability.

Conclusion

In this lesson, we have designed a complete distributed rate limiter, a common and important component in modern systems and a frequent topic in system design interviews.

Key Takeaways:

• Problem Framing: A successful design starts with clearly defined functional and non-functional requirements.
• Algorithm Choice: The Token Bucket algorithm offers a great balance, handling both sustained load (via refill rate) and traffic bursts (via bucket capacity).
• Distributed State: For a distributed system, state must be managed centrally. Redis is an excellent choice due to its speed and feature set.
• Atomicity is Key: To prevent race conditions in a distributed environment, operations that modify shared state must be atomic. Redis Lua scripting is the standard solution for this.
• Scalability and Resilience: For high throughput and fault tolerance, the data layer must be scaled. Sharding and replication, often managed by a system like Redis Cluster, are the primary patterns to achieve this.

You have now walked through the entire design process for a critical piece of infrastructure, from initial requirements to a scalable, fault-tolerant architecture. This thinking process is exactly what interviewers are looking for.

In our next lesson, we will continue our interview preparation by tackling another classic problem: designing a high-throughput URL shortener service, focusing on read performance and storage optimization.