# How rate limiters actually work when you have more than one server

Source: https://www.techinterview.org/post/3233476391/rate-limiter-system-design-multiple-servers/
Updated: 2026-07-16 · techinterview.org

The interviewer says: cap each API key at 100 requests per minute, return HTTP 429 on the ones over the line, and make it work across a fleet of servers behind a load balancer. That last clause is the whole interview. A rate limiter on a single box is a hash map and a timer. The moment there are ten boxes and one user's requests land on all of them, every naive design falls apart, and the interviewer is watching to see how fast you notice.

## The algorithm choices, and what each one gets wrong

The simplest counter keys on the pair (user, current minute) and increments. Under the limit, allow; over it, reject. It uses almost no memory, one integer per user per window, and it resets cleanly. The flaw shows up at the boundary. A user who sends 100 requests in the last second of 10:00 and another 100 in the first second of 10:01 has pushed 200 requests through in a two-second span, double the intended rate, because the window reset in the middle. This fixed-window failure is easy to state and easy to miss, which is exactly why it comes up.

A sliding window log fixes it by storing a timestamp for every request in a sorted structure. On each new request you drop everything older than the window, count what remains, and allow only if the count is under the limit. This is exact. It also costs one stored entry per request, so a client hammering an endpoint at 10,000 requests a minute leaves 10,000 timestamps sitting in memory for the length of the window. Accurate and expensive.

The sliding window counter is the compromise most large APIs actually run. Keep a count for the current window and the previous one, then weight the previous window by how much of it still overlaps the sliding period. If you're 30% into the current minute, you count all of this minute's requests plus 70% of last minute's. It stays within a percent or two of the exact log and costs two integers instead of thousands of timestamps.

Token bucket takes a different shape. A bucket holds up to N tokens and refills at a fixed rate, say 100 tokens topping up at 100 per minute. Each request removes a token; an empty bucket means rejection. The property that made it the default at AWS API Gateway and Stripe is burst tolerance. A client that stayed quiet for a minute has a full bucket and can fire 100 requests at once, then settles into the steady refill rate. That matches how real clients behave, quiet for a while and then a flurry, better than a flat per-second cap does.

Leaky bucket is the mirror image. Requests enter a queue that drains at a fixed rate, and overflow is dropped. Token bucket lets bursts through and smooths the average; leaky bucket smooths the output itself, so the downstream service sees a constant trickle no matter how spiky the input. You reach for leaky bucket when the thing you're protecting cares about a steady arrival rate more than about being fair to bursty clients.

| Algorithm | Burst handling | Memory per user | Accuracy at the window edge | Best fit |
| --- | --- | --- | --- | --- |
| Fixed window counter | Allows up to 2x the limit across a boundary | One integer | Poor (boundary doubling) | Rough limits where occasional overshoot is acceptable |
| Sliding window log | Exact, no boundary burst | One timestamp per request | Exact | Low-volume endpoints that need precision |
| Sliding window counter | Weights the previous window to smooth the edge | Two integers | Within ~1% of exact | General-purpose API limiting at scale |
| Token bucket | Allows bursts up to bucket capacity | Two values (tokens, last-refill time) | Rate-based, no window edge | Bursty clients, steady-rate-plus-burst quotas |
| Leaky bucket | No bursts; output held to a constant rate | Queue plus counter | Rate-based, no window edge | Protecting a downstream that needs steady input |

## Why it breaks the instant you add a second server

Every algorithm above assumes one place to keep the count. Put that count in each server's local memory and a user spread across four servers by a round-robin load balancer gets four times the limit, because no server sees the others' traffic. This is the pivot the whole question is built around, and the fix is a shared store that every server reads and writes. In practice that store is Redis, because it's fast and it expires keys for you with TTL, so stale windows clean themselves up.

Moving the counter to Redis introduces a subtler bug that trips up most candidates. The obvious code reads the count, checks it against the limit, then writes the increment. Two requests from the same user hit two servers in the same millisecond. Both read 99, both decide they're under 100, both write 100, and 101 requests got through. Check-then-act across a network is a race every time. The naive read, modify, write is wrong even though it reads correctly on the whiteboard, and a sharp interviewer will ask you to trace exactly this interleaving.

The fix is to make the decision atomic. Redis INCR returns the new value in one round trip, so you increment first and reject afterward if the result came back over the limit. For anything more involved than a plain counter, you push the whole decision into a Lua script, which Redis runs to completion with no other command interleaved. Prune, count, and add happen in one atomic call.

Here is a token bucket that lives entirely inside Redis and refills lazily, so you never run a background job to top up idle buckets. It stores the token count and the last refill time, computes how many tokens accrued since the previous request, and either spends one or rejects.


```
-- KEYS[1] = bucket key   ARGV = capacity, refill_per_sec, now_ms, requested
local cap  = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now  = tonumber(ARGV[3])
local need = tonumber(ARGV[4])

local state  = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or cap
local ts     = tonumber(state[2]) or now

-- add tokens for the time elapsed, capped at capacity
tokens = math.min(cap, tokens + (now - ts) / 1000 * rate)

local allowed = tokens >= need
if allowed then tokens = tokens - need end

redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(cap / rate * 1000))
return allowed and 1 or 0
```


The lazy refill is the part worth pointing at. You never wake a timer for an idle bucket; the arithmetic runs only when a request arrives, and the PEXPIRE lets untouched buckets evict themselves once enough time has passed to refill fully. One network hop, one atomic decision, correct under concurrency.

## The Redis hop is now your bottleneck

Every request paying a round trip to a central Redis is a real cost. At a few thousand requests per second it's invisible. At a million it becomes a hot shard and an extra millisecond on every call, and Redis itself turns into the thing that falls over first. There are two ways out, and the interviewer usually wants the tradeoff named rather than a single right answer.

Sticky routing sends every request for a given key to the same shard, so that key's counter lives in one place and stays fast. It holds up until a single key gets hot, the classic case being one abusive client or one very popular API consumer whose shard now carries load out of proportion to the rest. Consistent hashing spreads keys evenly across shards but does nothing for a single hot key; that one still lands on one machine.

The other approach lets each server keep a local token bucket sized to its slice of the global limit and reconcile in the background. With 10 servers and a global limit of 1000 per minute, each starts with 100 and they periodically exchange how much they've spent, borrowing unused budget from quiet peers. This is close to how edge networks like Cloudflare enforce limits across hundreds of points of presence, because a synchronous call to a central store from every edge would add latency nobody accepts. The cost is approximation: for a few seconds a client might get slightly more or less than the exact limit. For abuse protection that's a fine trade. For a billing-critical quota where every call is metered, it is not, and you should say which one you're solving.

## Where the limiter sits and what it tells the client

Most systems run rate limiting at the edge, in the API gateway or a sidecar proxy like Envoy, before the request reaches application code. Rejecting there means a blocked request never takes a database connection or a worker thread, which is the entire point during a spike. Envoy ships a rate-limit filter that calls out to a gRPC service backed by Redis; that pattern shows up all over real infrastructure and is worth naming instead of hand-waving about "the gateway."

The response matters as much as the decision. A 429 with a Retry-After header tells a well-behaved client exactly how long to back off, and an X-RateLimit-Remaining header lets it self-throttle before it hits the wall. GitHub, Stripe, and Twitter's API all return headers shaped this way. A limiter that just drops requests with no signal turns polite clients into retry storms, which makes the overload it was meant to prevent worse. Plenty of candidates design the counter perfectly and forget the client on the other end, so mention the headers.

## What the interviewer is actually scoring

The counter is the easy 20 minutes. The signal is whether you reach for a shared store the moment a second server shows up, whether you catch the check-then-act race before it's pointed out, and whether you can talk about the Redis hop as a bottleneck with a concrete plan for a million requests a second. Say out loud which algorithm you'd pick and why: token bucket when clients are bursty and you want to allow it, sliding window counter when you want near-exact fairness cheaply, fixed window only when you genuinely don't care about the boundary doubling. Pick one, defend it, and know what it costs. That's the gap between someone who memorized the diagram and someone who has run this in production.