Rate Limiting at Scale: Choosing the Right Throttling Algorithm
Why in-memory rate limiting silently breaks under horizontal scaling, and how token bucket, sliding window and fixed window algorithms trade off in production.
When a service scales from one pod to eight, an in-memory rate limiter that caps a user at 100 requests per minute can silently allow 800, since each pod counts independently in its own RAM. Logs show no errors, yet downstream systems get flooded — a failure mode that forces teams to move counters into a shared store like Redis and then decide which throttling algorithm to use.
Fixed window counters are simplest but allow double the limit at window boundaries. Sliding window logs are exact but grow memory linearly with request volume. Cloudflare's sliding window counter approach blends two windows with weighted interpolation for near-exact accuracy at low cost. Token bucket, favored by Stripe and underlying GCRA/redis-cell, maintains a steady average rate while permitting controlled bursts.
Implementing a distributed token bucket with naive GET-then-SET operations introduces classic race conditions, since concurrent requests can both read the same token count before either writes back; the fix is an atomic Lua script executing read-modify-write in one round trip. Because Redis becomes a single point of failure, teams must explicitly choose between fail-open (availability-favoring, but exploitable during outages) and fail-closed (safety-favoring, but turns a Redis blip into a full outage) — commonly paired with short timeouts, alerting, and a coarse L7 safety net (Nginx, Envoy).
These details matter to engineers because rate limiting is prone to silent failure modes that look healthy in logs while offering no real protection; getting the algorithm, atomicity guarantees, and failure strategy right is what keeps the system from collapsing under the very load it's meant to control.