Case Study: Rate Limiter

Step 1: Requirements

Functional: limit each client (by API key, user ID, or IP) to N requests per time window; reject requests beyond the limit (typically with 429 Too Many Requests).

Non-functional: the limiter itself must add negligible latency to every request it checks; it must work correctly across multiple API server instances sharing the same limit for a given client, not per-instance limits that multiply the effective limit by the number of servers.

Step 2: Algorithms

Four common algorithms, each with a different behavior at the boundary between windows — this is the actual differentiator, not just "which one is fastest":

Fixed window counter: count requests in a fixed time bucket (e.g. "this minute"), reset to 0 at each new minute. Simple, O(1) per check. Flaw: a client can send N requests in the last second of one window and another N in the first second of the next — 2N requests in under 2 seconds, double the intended limit, because the algorithm only sees two separate windows, not the sliding 1-second reality.

graph LR w1["Window 1: 0:00-0:59<br/>N requests at 0:59"] --- w2["Window 2: 1:00-1:59<br/>N requests at 1:00"] note["2N requests in ~1 second, straddling the boundary"]

Sliding window log: store a timestamp per request; on each check, count timestamps within the last N seconds (a true sliding window, no boundary artifact). Accurate, but storage grows with request volume — a high-traffic client needs many stored timestamps.

Sliding window counter: a compromise — keep counts per smaller sub-window (e.g. per 10-second bucket within a 60-second limit) and compute a weighted estimate across the last N seconds using the current and previous sub-windows. Approximate but bounded storage, avoiding the fixed-window boundary flaw well enough for most practical purposes.

Token bucket: a bucket holds up to B tokens, refilled at rate R tokens/second; each request consumes one token, rejected if the bucket is empty. Allows controlled bursts (up to B requests instantly, if the bucket was full) while enforcing a steady-state rate R over time — often the preferred choice specifically because bursts (a client legitimately sending a batch of requests) are common and a strict per-second cap would reject bursts that a token bucket correctly allows within its budget.

graph LR bucket["Bucket: up to B tokens"] -->|"refills at R tokens/sec"| bucket req["Request arrives"] -->|"consume 1 token"| bucket bucket -->|"empty"| reject["429 Too Many Requests"]

Step 3: Where to enforce it, and why distributed state is required

graph TD c1["Client"] --> gw["API Gateway / middleware"] gw --> redis["Redis: shared counter<br/>per client key"] gw --> api1["API server 1"] gw --> api2["API server 2"] gw --> api3["API server 3"]

Enforcing the limit inside each API server's own process memory reproduces exactly the stateless-scaling pitfall covered earlier: with 3 server instances behind a load balancer, a per-instance in-memory counter lets each instance independently allow up to N requests, for an effective limit of 3N, not N. The counter must live in shared state every instance can reach — Redis is the standard choice, given its speed (sub-millisecond) keeps the rate-limit check from adding meaningful latency to the request path.

Step 4: Deep dive — implementing it correctly and atomically

A naive Redis implementation — GET the current count, check it against the limit, INCR if under — has a race condition: two concurrent requests from the same client can both GET the count before either INCRs, both see "under the limit," and both proceed, letting the client briefly exceed the limit under concurrent load.

The fix is to make check-and-increment a single atomic operation:

INCR client:123:window:1699999980
EXPIRE client:123:window:1699999980 60   -- only needs to run once, on first INCR

INCR is atomic in Redis — there's no gap between reading the current value and updating it that a second concurrent request could land in. The key includes a window identifier (here, a bucket boundary timestamp) so the counter naturally resets by simply using a new key for the next window, with EXPIRE cleaning up old window keys automatically instead of requiring an explicit reset step. For token bucket specifically, a small Lua script run via EVAL is the standard way to make "check remaining tokens, refill based on elapsed time, consume one" atomic in a single round trip, since token bucket's refill logic doesn't reduce to one built-in atomic Redis command the way a fixed counter does.

Step 5: Bottlenecks and trade-offs

Redis becomes a single shared dependency every request now passes through — if it's unreachable, the design must decide explicitly whether to fail open (allow all requests, risking overload during a Redis outage) or fail closed (reject all requests, turning a rate limiter outage into a full outage). Neither is "correct" in the abstract; it's a decision that depends on which failure mode the specific system can tolerate better, and it should be stated explicitly rather than left as whatever the client library happens to do by default on a connection error.

Common pitfall

Choosing a fixed window counter for its simplicity without checking whether the boundary-doubling flaw actually matters for the specific use case is a common shortcut that works fine in casual testing (which rarely happens to send traffic exactly straddling a window boundary) and fails exactly when a client intentionally or accidentally times requests around the reset — token bucket or sliding window counter close this gap for close to the same implementation cost, so the simplicity argument for fixed windows is weaker than it first appears once the actual failure case is understood.