Rate Limiting at Scale

Ashok Dey

21st Mar, 2023

2.2k words • 13 min read
system-design › hld

Background

In the previous part, we looked at the most common rate-limiting algorithms and, more importantly, the trade-offs behind choosing one. We saw that there isn’t a universally “best” algorithm; the right choice depends on the nature of the traffic, whether bursts are acceptable, how much state we can maintain, and how much latency we are willing to introduce.

A rate limiter that works perfectly for a few thousand requests per second can behave very differently when it needs to protect a system handling hundreds of thousands or millions of requests per second, across millions of clients.

Choosing the algorithm is only the beginning, and at that point, the problem stops being just about counting requests.

Where do we store the state? How do multiple rate-limiter instances coordinate with each other? What happens when millions of clients become active at the same time? How do we deal with hot keys, atomicity, network latency, failures, and the sheer volume of state being created?

These are the problems that don’t usually show up when we first learn the algorithms.

So in this part, we’ll take the rate limiter out of the algorithm discussion and put it into a real distributed system. We’ll look at what starts breaking at scale, why seemingly simple implementations become bottlenecks, and what design decisions are needed to make a rate limiter reliable under production traffic.

Distributed State Management

What happens to your token bucket state when you have multiple instances of your rate limiter service running behind a load balancer, and the same client’s requests get routed to different instances?

I jumped to the answer - We can use REDIS for state management to avoid any issues without answering the actual question. I quickly paused and then answered the question properly.

If we have N instances of rate-limiters in each pod behind the load balancer, then each instance will have its own copy of the state, which will make the rate limiting scoped to each pod rather than a global limit. If the limit is 10 req/sec, then with 20 pods the effective rate limit becomes 200 req/sec.

That’s not a minor bug, it’s the rate limiter completely failing at its one job as you scale horizontally, which is exactly when you need it most.

State in REDIS

The obvious reason we use REDIS is to keep the state global instead of local and that’s the naive choice for any state management challenge, but it comes with its own caveats.

REDIS gives us shared, low-latency state across gateway instances, but at 100K req/sec, we’d treat REDIS as part of the distributed system design, not just as a key-value store. The important questions are atomicity, latency, failure behavior, hot keys, memory, and how the state is partitioned.

Let’s explore all the aspects of it.

Maintaining Atomicity

The Token Bucket algorithm at the high level does: GET → calculate → SET. When there are concurrent requests, we can run into a race condition which can defeat the purpose of rate limiting. Let’s look at the example:

Initial tokens = 10

Request A                 Request B
   │                         │
   │ GET → 10                │
   │                         │ GET → 10
   │                         │
   │ consume 2               │ consume 2
   │                         │
   │ SET → 8                 │ SET → 8
   │                         │
   ↓                         ↓
 ALLOW                     ALLOW

Read Write Race

Let’s suppose we have a total of 10 tokens available for a given period, and the cost of each API call is 2 tokens.

Two concurrent requests, A and B, both read the state and see that 10 tokens are available. They each consume 2 tokens and independently calculate the new balance as 8 tokens.

Both then write 8 tokens back to REDIS. The race causes the system to lose one decrement, so REDIS says 8 tokens remain even though 4 tokens were actually consumed and the correct remaining balance should be 6 tokens.

Individual Atomic Operations

Why don’t we just use REDIS DECR? DECR is atomic, so haven’t we solved the race?

At first glance, using REDIS INCR or DECR seems like an obvious solution to the race condition we discussed. REDIS guarantees that commands such as INCR and DECR are atomic, so two concurrent requests cannot corrupt the counter itself.

If we have 10 tokens and every API request costs 2 tokens, we could simply decrement the counter whenever a request arrives. But this only solves one specific problem: the lost-update race.

However, we also need to verify whether a request should be allowed before it consumes the tokens.

If there are only 2 tokens remaining and two requests arrive concurrently, both requests need to check whether 2 tokens are available. We need this operation:

Initial tokens = 2

Request A                 Request B
   │                         │
   │ GET → 2                 │
   │                         │ GET → 2
   │                         │
   │ consume 2               │ consume 2
   │                         │
   │ SET → 0                 │ SET → -2
   │                         │
   ↓                         ↓
 ALLOW                     ALLOW

We discover that the second request should never have been allowed. We would have to compensate for the invalid decrement, which brings us back into another read-modify-write problem. We therefore need the check and decrement to happen atomically as one operation.

But even that isn’t the biggest problem.

A Token Bucket is fundamentally time-based. Tokens continuously become available according to a refill rate. We are simultaneously doing a time calculation, capacity calculation, conditional check, token consumption, and timestamp update. These operations must be consistent with one another. If concurrent requests perform them independently, we can reintroduce races even though the final decrement itself is atomic.

Atomic LUA Transaction

INCR and DECR give us an atomic primitive, but what we need for Token Bucket is an atomic conditional state transition.

REDIS executes the Lua script atomically with respect to other commands, so the read, calculation, conditional check, and state update can be performed as a single server-side operation without another command interleaving between them.

Timeouts & Retries

I was almost lost in the atomicity part, and my brain was running combinations and permutations of what else could go wrong, since we had already covered the critical case. But the next question almost left me blank.

How do you handle a timeout when you don’t know whether the token was already consumed?

I did not really understand it in one go, so I asked again.

Imagine REDIS consumed the token but the gateway crashed before receiving the response. What happens when the request is retried?

I understood only after a diagram was provided, which was something similar to the following:

Case A:
Gateway → REDIS
         ↓
      request lost
         ↓
      never executed


Case B:
Gateway → REDIS
         ↓
      Lua executed
         ↓
      token consumed
         ↓
      response lost

For both the cases above, from the client’s or the gateway’s perspective, they look identical, i.e. a timeout. Suppose the gateway says, “I’ll retry because I don’t know whether it succeeded.”

Attempt 1
Gateway ─────────→ REDIS
                   ↓
                consumed 2
                   ↓
              response lost
                   ↓
                TIMEOUT

Attempt 2
Gateway ─────────→ REDIS
                   ↓
                consumed 2

Now the logical request consumed 4 tokens even though there was only one API request. The Lua script was completely correct, there was no race, no concurrent corruption. REDIS did exactly what we asked but the problem happened outside the atomic operation:

Atomicity protects the state transition. It doesn’t tell the caller whether that state transition happened when the response is lost.

The solution can be:

Retry and accept the possibility of double consumption because a rate limiter isn’t a financial transaction.
Make the operation idempotent by giving every logical request an ID

Hot Key Problem

A hot key is a key in a distributed data store that receives a disproportionately large amount of traffic compared with other keys.

Even if we’ve distributed our data across 10 REDIS shards, if all requests for a particular key X are routed to the same shard, that one shard can become a bottleneck while the other 9 shards are mostly idle. This can lead to:

High latency
Increased CPU/network usage on that node
Timeouts
Cascading failures
Poor utilization of the overall cluster

Token Bucket makes this particularly interesting. We’re deliberately making that operation atomic via the LUA script; good so far, but atomicity has a side effect: operations against the same bucket can’t safely execute as independent concurrent mutations.

Atomicity gives us correctness, but a highly contended atomic key can become a scalability bottleneck.

Local State to the Rescue

This is where high-scale systems often become more sophisticated. This may sound like the anti-pattern we started this conversation with, and now we are coming back to the same point.

We can allocate a chunk of capacity to each pod, and the pods will maintain the local buckets, all the API call checks will not go to REDIS, and we will periodically sync the changes with REDIS, but there are some gotchas!!

Local State Leakage

How can the leakage happen? Suppose we have 3 pods doing the rate limiting for a particular user and we allocated 100 tokens to each of them. Let’s try to visualize this:

Pod A → 100 tokens
Pod B → 100 tokens
Pod C → 100 tokens

For some reason (sticky sessions, maybe), Pod A is getting more hits than the rest of the pods, and because of this Pod A will start rejecting requests while the tokens of Pod B & Pod C are stranded locally. So we have a capacity fragmentation issue here.

Pod A → exhausted | start rejecting the requests 
Pod B → 80 unused
Pod C → 90 unused

Pod failure/crash can also make tokens effectively disappear, for example when Pod C crashes after consuming only 30 tokens.

Leakage Control

Local state leakage can be solved via on-demand token allocation. But this should be a data-driven decision, not an arbitrary number. Remember that

Larger allocations → less REDIS traffic but more potential leakage
Smaller allocations → better global accuracy but more REDIS traffic.

Hot Key vs Hot Shard

I want to highlight a critical point that even I used to get confused about: a hot key is not a hot shard. A single shard can have multiple keys.

The question isn’t simply how do we distribute the hot key, it’s how much global rate-limit accuracy we are willing to trade for lower contention and cost?

Latency & Failure

We already covered that to battle the hot shard issue we can rely on local state with periodic sync, batching or request coalescing, or a fast-reject local pre-filter.

The above also helps us mitigate the latency issues we encounter at peak traffic. It is not necessary to route all the traffic to REDIS, because that adds an extra network hop; even though REDIS is an in-memory store, the command and data still have to make a network round trip. At 100K qps, even a 5ms round trip per request adds up to a noticeable, system-wide delay.

There was another question which we already answered via local state. Can you guess the question? The question was:

What if REDIS goes down? Will rate-limiting take a toss?

No. Since we have local state in the pods, rate limiting as a feature will not go down, but the sync from local state to REDIS will break, and that will degrade the performance and efficiency of the rate limiting.

Summary

Though there can be many more cases involved in the atomicity aspect, the scope of our conversation was limited to the following:

Race - “Can two requests incorrectly consume the same capacity?”
Timeout - “What if I don’t know whether my atomic operation succeeded?”
Hot key - “What if the atomic operation itself becomes the bottleneck?”
Latency - “What about the network round trip latency we are adding to every request?”
Failure - “If REDIS goes down, will the rate-limiting stop working?”

There were a few more questions that came up, but due to time constraints we parked them. I will write about them in the subsequent parts of this series.

Reflections

The algorithm was never the hard part. The hard part is the state at scale: one shared source of truth, accessed concurrently, under load, over a network that occasionally fails. Almost every “obvious” fix quietly breaks something else.

REDIS solves the local vs global problem and introduces a race.
Atomicity solves the race and introduces a hot key.
Local state solves the hot key and introduces leakage.
None of these are mistakes, they’re trade-offs, and at scale there’s no version of this design without one.

What stayed with me from this part of the conversation is that a lot of these questions don’t have a “correct” answer at all.

They have a correct set of questions. Those aren’t things we can memorize. They’re judgment calls we can only really make once we’ve felt what happens when we get them wrong. That’s probably the real difference between rate limiting on a whiteboard and rate limiting in production.

Production doesn’t ask us for the right algorithm, it asks us which failure mode we’re willing to live with. Conversations like this taught me more than any amount of interview cramming would have.