Distributed Rate Limiting with Redis and Atomicity

Hello! Welcome to your next lesson on Rate Limiting and Traffic Shaping.

In our last session, we built a comprehensive framework for comparing rate limiting algorithms, focusing on the trade-offs between accuracy, memory, and burst handling. We concluded that while we now understand the core logic, real-world systems like those at AWS or Anthropic are distributed, and this introduces a new set of challenges.

Today, we'll tackle that complexity head-on. Our learning outcome is to design a distributed rate limiting system using an external store like Redis, focusing on atomicity. This is a classic system design question that tests your understanding of concurrency, scalability, and fault tolerance in a practical context. Your experience building and operating high-throughput services like Rudi will provide a strong foundation for a deep dive into these concepts.

---

1. The Challenge: From Single Server to Distributed System

In our previous implementations, we could assume the rate limiter ran as a single process. In a large-scale system, this is rarely the case. An API is typically served by multiple instances of an application or an API gateway, sitting behind a load balancer.

A typical distributed architecture where multiple identical service instances (e.g., API Gateways) handle incoming traffic.

If each gateway instance maintains its own in-memory counters, the rate limit becomes ineffective. A client could send requests that are distributed across different gateways, with each gateway only seeing a fraction of the total traffic. This allows the client to bypass the intended global limit.

To enforce a global limit, all gateway instances must share and coordinate on a single source of truth for the rate limiting state (e.g., token counts, window timestamps). This requires a centralized, external data store.

---

2. Centralizing State with Redis

For a rate limiter, the state store must be extremely fast to avoid adding significant latency to every request. This makes a fast, in-memory data store like Redis an ideal choice.

A common architecture involves placing the rate limiting logic at the edge (in an API Gateway or middleware) and having it communicate with a central Redis instance to check and update rate limit counters.

The video below briefly introduces this architecture.

This setup seems straightforward, but it hides a critical flaw that can completely undermine the rate limiter's correctness.

---

3. The Atomicity Crisis: Race Conditions in Distributed Systems

When multiple gateway instances read and write to the same key in Redis concurrently, we can encounter a race condition. This is the central problem you must solve when designing a distributed rate limiter.

Let's consider the token bucket algorithm. The logic for processing one request involves three steps:

1. Read: Fetch the current token count and last refill timestamp from Redis.
2. Modify: In the application's memory, calculate the new token count after refilling and consuming one token.
3. Write: Update Redis with the new token count and timestamp.

Now, imagine two requests for the same user arrive at Gateway A and Gateway B at nearly the same time, and there is only one token left.

1. Gateway A reads from Redis: tokens = 1.
2. Gateway B reads from Redis: tokens = 1.
3. Gateway A checks locally: 1 > 0, so it allows the request. It calculates the new count will be 0.
4. Gateway B checks locally: 1 > 0, so it also allows the request. It calculates the new count will be 0.
5. Gateway A writes to Redis: tokens = 0.
6. Gateway B writes to Redis: tokens = 0.

The result? We allowed two requests when only one token was available, violating our rate limit. This is a classic read-modify-write problem. From your experience with Rust, this is the distributed systems equivalent of two threads accessing shared data without a Mutex, leading to incorrect state.

To solve this, the entire read-modify-write sequence must be atomic. It must execute as a single, indivisible operation.

---

4. The Solution: Achieving Atomicity with Lua Scripting

How can we make this operation atomic in Redis? You might first think of Redis Transactions (MULTI/EXEC), but they have a limitation: you cannot use the result of a command inside the transaction block to make a decision. You can't read the token count and then conditionally decide whether to write back.

The standard and most powerful solution is to use Lua scripting. Redis can execute Lua scripts atomically. You send the entire read-modify-write logic to Redis as a single script, and Redis guarantees that no other command will run while your script is executing.

The following diagram illustrates this concept. The rate limiter logic is encapsulated in a Lua script and executed atomically within Redis.

Now, let's see how this is discussed in a system design interview context.

By moving the logic into a Lua script, we ensure that each rate limit check is correct and consistent, no matter how many gateways are calling Redis simultaneously.

---

5. Designing for Scale and Resilience

Solving the atomicity problem gives us a correct distributed rate limiter. Now, we must ensure it is also scalable and highly available, especially for a system that needs to handle 1 million requests per second, as discussed in the video.

Scaling with Sharding

A single Redis instance can handle 100k-200k operations per second, but our check involves multiple operations. This means a single instance will become a bottleneck well before 1M requests/second.

The solution is to shard (or partition) the data across multiple Redis nodes. We can use a consistent hashing scheme based on the client identifier (user ID, IP address, etc.) to determine which shard holds that client's data. This ensures all requests for a given client consistently hit the same shard.

Production systems often use Redis Cluster, which abstracts this away. It automatically shards keys across nodes and handles routing, so the application logic remains simple.

High Availability with Replication

What happens if a Redis shard goes down? Each shard is a single point of failure for the users mapped to it. We must decide on a failure strategy:

• Fail-closed: If the rate limiter can't contact Redis, it rejects all requests. This protects backend services but causes an outage for users.
• Fail-open: It allows all requests through. This maintains availability but risks overwhelming the backend—the very thing the rate limiter was meant to prevent. Your experience with Game Day testing at AWS highlights the importance of understanding and testing these failure modes.

The better solution is to prevent the failure in the first place using master-replica replication. Each primary shard has one or more replica shards that asynchronously copy its data. If the primary fails, a replica is automatically promoted to be the new primary.

The architecture below illustrates a sharded and replicated Redis Cluster.

The following resources provide a deep dive into these scaling and availability patterns.

---

Conclusion

In this lesson, we designed a robust, distributed rate limiting system. We went beyond the core algorithms to address the practical challenges of concurrency, scale, and fault tolerance that arise in real-world systems.

Key Takeaways:

• Centralized State is Necessary: Distributed rate limiters require an external, shared store like Redis to maintain a global state.
• Atomicity is Non-Negotiable: Concurrent read-modify-write operations create race conditions. Using Redis Lua scripts is the standard way to bundle these operations into a single, atomic unit, ensuring correctness.
• Scale with Sharding: A single Redis node is a bottleneck. Sharding data across a Redis Cluster distributes the load, allowing the system to handle millions of requests per second.
• Ensure Resilience with Replication: To prevent outages, each Redis shard should use master-replica replication for automatic failover. You must also have a clear strategy (fail-closed or fail-open) for when the data store is unreachable.

Next Lesson Preview

Our current design enforces static, pre-configured rules. However, a sophisticated system might need to adjust limits dynamically based on the current health of backend services. If a downstream service is struggling, you might want to tighten the rate limits automatically.

In our next lesson, we will explore this advanced topic: Implement an adaptive rate limiting strategy that adjusts limits based on system health metrics. This moves from simple traffic policing to intelligent traffic shaping, a key component of modern, resilient infrastructure.