Every team that exposes an API eventually writes a rate limiter. The first version is usually a counter in a database with a WHERE timestamp > now() - interval clause, and it works fine until it does not. The interesting questions are not about the algorithm — they are about coordination, failure modes, and how the system behaves when the part of it that owns the counter is having a bad day.
The three algorithms you actually meet
A token bucket refills at a fixed rate and has a capacity; each request consumes a token. It is forgiving of bursts up to the capacity and produces predictable steady-state behavior. Most production systems end up here, because most rate limits are about smoothing a noisy caller, not enforcing a strict window.
A sliding window log keeps every request timestamp and counts the ones inside the window. It is the most precise option and the most expensive one. In practice nobody stores every timestamp; everyone approximates. The approximation is a moving counter that combines the previous window’s total with the current one, weighted by how far into the current window we are.
A leaky bucket enforces a constant outflow rate regardless of inflow. It is the right shape for downstream systems with a hard capacity limit, and the wrong shape for almost everything else. If the limit is a courtesy to the caller, leaky bucket feels punitive; if the limit is a protection for an internal queue, leaky bucket is exactly right.
Coordination is the actual problem
The algorithm is the easy part. The hard part is that the limiter is a distributed system with the usual distributed-system properties. A client in region A and a client in region B both have to be counted against the same tenant budget, and the count has to stay correct when the network between regions is unhappy.
Three patterns show up over and over:
- Centralized counter. One store, one source of truth, every request goes through it. Simplest to reason about, easiest to fall over.
- Local counters, periodic sync. Each region maintains its own counter and reconciles with peers on an interval. Better latency, weaker guarantees, and the reconciliation logic is its own bug surface.
- Hierarchical. A regional limiter for fast decisions, a global limiter for budget enforcement. The regional limiter is allowed to be approximate; the global limiter is the one that says no.
The pattern you pick is shaped more by your latency budget than by your traffic shape. If the decision has to be sub-millisecond, you are doing local counters whether you like it or not.
Backpressure is the part people skip
A rate limiter that returns 429 and then forgets about it is half a system. The other half is backpressure: what does the client do with the rejection, how does the limiter communicate its remaining budget, and how does the system handle the case where every client gets a 429 at once.
The cheapest thing you can do is give the client a useful Retry-After. The second cheapest is to expose the remaining budget in a header so a well-behaved client can pace itself without polling. The expensive thing — and the right thing, eventually — is to make the limiter part of the system’s load-shedding story, not a separate concern bolted on top.
Redis as a coordination primitive
For most teams, Redis is the right substrate for the limiter. The data model is a counter; the operations are O(1); the cluster model lets you scale by sharding. The two failure modes to design for are hot keys (a small number of high-volume tenants overwhelming a single shard) and partial network partitions (one region’s Redis is unreachable but the service is otherwise up).
Hot keys are usually fixed with key tagging — putting related counters inside a hash tag so they colocate — combined with a small in-process cache for the noisiest decisions. Partial partitions are usually fixed by being explicit about the trade-off: when the limiter cannot reach its counter, does it fail open (allow everything) or fail closed (reject everything)? Either answer is defensible; not picking one is not.
Picking one
For most APIs, the right answer is a token bucket per (tenant, scope) with a small in-process cache, backed by Redis with Lua scripts for atomicity, behind a gRPC service that does no policy evaluation on the hot path. The algorithm is the line on the diagram; the work is everything around it.