A rate limiter sits on the hottest path in your architecture — every request from every client passes through it — and its latency budget is brutal: it must decide allow/reject in well under a millisecond, because it is a tax on every request, not a feature of one. The algorithm choice determines burst behavior, memory cost, and how much traffic slips past the limit.
Token bucket: burst-aware and memoryless
The token bucket is two numbers per client: capacity b (the bucket size) and refill rate r (tokens per second). Each request consumes one token; tokens accumulate up to b. A client can burst b requests instantly, then settles into r sustained. It is the default for API gateways (Kong, AWS API Gateway, nginx limit_req with burst) because one integer per key is cheap and the burst semantics match real APIs — mobile clients reconnect and need to catch up.
Its weakness is memorylessness: a client idle for an hour has a full bucket and can dump b requests at once. If the limit exists to protect a downstream with real per-second capacity, a full-bucket burst of 10,000 at t+0 is not gentler than 10,000 spread evenly — it's worse.
Fixed window: Redis INCR, one atomic script
The fixed window is a counter per key per window; in a distributed system it is usually one Redis key:
-- fixed window counter, atomic in Lua
local wkey = KEYS[1] .. ":" .. math.floor(tonumber(ARGV[2]) / 60)
local c = redis.call("INCR", wkey)
if c == 1 then redis.call("EXPIRE", wkey, 61) end
if c > tonumber(ARGV[1]) then return 0 else return 1 endINCR is atomic, and pairing it with EXPIRE inside one Lua script closes the check-then-act race of a naive INCR-then-check. The failure mode is the boundary burst: limit requests at 59.999s plus limit more at 0.001s — 2× the limit in two seconds. Acceptable for most APIs; exactly what attackers look for otherwise.
Redis is the workhorse for a reason: a single instance does 100k-1M ops/s, and the limiter's full cost is one network round trip (0.1-0.5ms in-region, ~1-2ms across AZs). At 100k req/s that's a dedicated instance — real deployments shard the keyspace or accept per-node approximation instead.
Sliding log: exact, and exactly as expensive as it sounds
The sliding log stores every request timestamp per client (a Redis sorted set) and counts entries inside the true sliding window. It is the only algorithm here that's exact — no boundary burst, no approximation. The cost is memory proportional to traffic, not clients: one client at 1,000 req/s against a 60-second window holds 60,000 timestamps (~4MB in a sorted set with score and member). Multiply by the number of abusive clients and the limiter becomes the biggest consumer in your fleet. It's the right choice only when exactness is a product requirement — quota billing, compliance — and traffic per key is low.
The sliding window counter is the pragmatic middle: keep the current and previous window counters and weight them linearly by time elapsed into the current window. Two keys per client, constant memory, no boundary burst (the approximation error is bounded by one window of rate). Most commercial gateways that claim "sliding window" actually ship this.
Distributed limits: exactness vs latency
A single-node limiter is trivial. The distributed problem is real: N gateway nodes behind a load balancer, each with its own token bucket, and a client can hit any of them. Three honest options:
- Shared state (Redis): exact global limits; every request pays 1-2ms and one dependency. The dependency is the catch — if Redis dies, you must decide fail-open (limits vanish) or fail-closed (all traffic blocked). Fail-open plus a local fallback limiter is the sane default.
- Per-node shards: each node enforces limit/N independently. Zero coordination, zero extra latency, and N× the actual limit when the fleet is imbalanced — plus the effective limit silently changes whenever N changes (a scaling event shifts the limit mid-flight).
- Approximate gossip / periodic sync: nodes exchange local counters every few seconds. Smooths the error to a few percent, adds a background channel, and still lets any single node be hammered within a sync window.
The engineering truth: exact global limits at internet scale cost either latency or coordination. Production systems almost always pick option 1 for strict quotas (billing) and option 2 for protective limits (abuse defense), because an approximate 10% overrun by real users is cheaper than a 1.5ms tax on every request.
What survives to production
The algorithm is the visible part; the operational contract is the hidden one. Log only rejects, not passes (passes are 100x the volume). Return Retry-After on 429s so clients back off in sync instead of retry-storming at t+0. And remember the limiter's real job: it's not fairness, it's protecting a shared resource from its own users — which is why the limit should be derived from the downstream's measured capacity, not a round number from a design doc.
Production cost model and latency numbers
To apply Rate Limiters at Scale effectively in production systems, engineers must move beyond qualitative diagrams and quantify the exact hardware and network costs at each boundary:
| Operation / Boundary | Typical Latency | Dominant Bottleneck | Production Mitigation |
|---|---|---|---|
| L1 / L2 Cache Access | 1 ns – 4 ns | Register dependency chains & pointer chasing | Contiguous memory layouts, cache-line alignment (64 B), and batch iteration |
| Main Memory (DRAM) Fetch | 60 ns – 100 ns | TLB misses, random heap indirection, NUMA hops | HugePages (2 MB), arena/slab allocators, and pre-allocated ring buffers |
| Kernel Syscall / Context Switch | 1 µs – 5 µs | User-to-kernel mode switch, page-table flush, lock contention | Non-blocking readiness loops (epoll / io_uring), batching, and zero-copy I/O |
| NVMe SSD Random Read / fsync | 50 µs – 500 µs | Block I/O queue depth, write amplification, WAL flushes | Group commit, sequential append logs, and bounded buffer-pool pinning |
| Intra-Region RPC Roundtrip | 0.5 ms – 2.5 ms | Serialization, TCP/TLS framing, tail queueing ($L = \lambda W$) | Connection pooling, deadline propagation, and p95 hedged requests |
Failure modes, debugging, and operational checklist
In real incidents, systems rarely fail at average (p50) load—they fail when a slow dependency, skewed hot key, or resource leak pushes concurrency across a non-linear saturation cliff. When reviewing code or architecture that relies on Rate Limiters at Scale, walk through three verification questions:
- What is the invariant under partial failure or contention? If a worker crashes mid-operation, a network packet is delayed and reordered, or two threads race on the same state transition, prove which atomic primitive, version number, or idempotency key prevents silent corruption.
- How is backpressure enforced when demand exceeds capacity? Unbounded in-memory queues, unthrottled retries, and blocking calls without explicit deadlines turn a localized
100 msslowdown into a fleet-wide Out-Of-Memory (OOM) cascade. Always bound queue depths, propagate caller deadlines, and shed excess load early. - Which metrics and traces isolate the bottleneck in under 60 seconds? Instrument saturation, queue wait time vs service execution time, cache hit/miss ratios, and error rates by failure reason so on-call engineers can immediately distinguish a compute bottleneck from an I/O or lock-contention stall.