Rate Limiting Algorithms
Capping how fast one client can hit a service, before that client (accidentally or not) degrades it for everyone else.
Intermediate
TopNotchNote
Notes that matter
why a service needs to police its own traffic
Rate limiting caps how many requests a client (a user, an IP, an API key) can make in a given time window. Without it, a single misbehaving client can degrade service for everyone else — accidentally, from a buggy retry loop, or deliberately.
| Threat | How rate limiting helps |
|---|---|
| Scraping / competitive data harvesting | A competitor programmatically pulling every restaurant's menu and prices can be capped per-IP or per-account before it becomes meaningful load. |
| DoS / DDoS traffic spikes | Capping requests per source keeps a flood from a small set of origins from starving out legitimate users. |
| Runaway retry loops | A buggy client that retries aggressively on every failure gets throttled instead of amplifying an existing incident. |
| Cost control | Fewer wasted requests directly means fewer servers needed to absorb them. |
leaky bucket
Requests fill a bucket of fixed capacity; the bucket "leaks" (processes requests) at a constant rate. If the bucket is full, new requests are dropped or rejected.
bucket_capacity = 10
leak_rate = 2 requests/sec
# the bucket leaks continuously, so output is a steady 2 req/sec no matter
# how bursty the input is -- there are no windows here, and no boundary effect.
# the trade-off is the opposite one: a legitimate burst waits in the bucket
# (added latency) or is dropped once the bucket is full, even if the client
# has been quiet for the last hour
Good for enforcing a hard output rate and protecting a downstream service that can only absorb so much per second. The cost is that it has no memory of good behaviour: a client that sent nothing for an hour gets no credit for it, so a short legitimate burst is queued or rejected exactly like an abusive one. Token bucket, below, is the variant that fixes precisely this.
fixed window counter
Count requests within a fixed time window (e.g. "9:00–10:00"), and reset the count to zero at each window boundary.
limit = 4 requests / hour
# problem: 4 requests at 8:59, then 4 more at 9:00 -> 8 requests in 2 minutes,
# even though each hour individually stayed within the stated limit
Simple to implement (a single counter per window), but allows a burst right at the boundary between two windows to briefly exceed the intended rate by up to 2x.
sliding window
Instead of a hard reset at window boundaries, track individual request timestamps and only count requests that fall within the last N seconds, continuously — the window "slides" with the current time rather than resetting.
limit = 4 requests / hour, sliding
# a request is allowed only if fewer than 4 requests occurred
# in the preceding 60 minutes, measured from right now
This is the most accurate approach and the one to reach for when precise limits matter (e.g. enforcing a paid API tier's exact quota) — at the cost of storing individual request timestamps instead of a single counter, which costs more memory per client.
token bucket
A close cousin of leaky bucket, framed from the opposite direction: a bucket holds tokens, refilled at a steady rate up to a max capacity; each request consumes one token, and a request with no tokens available is rejected. The key advantage over leaky bucket is that it naturally allows short bursts up to the bucket's capacity, as long as the client hasn't been making requests continuously — useful for clients that are idle most of the time but occasionally need to fire off several requests at once.
where to actually implement it
Rate limiting is commonly enforced at the load balancer or API gateway layer, before a request ever reaches application logic — cheaper to reject there than after paying the cost of routing and processing. The counters themselves are usually kept in a fast shared store like Redis (see Distributed Caching), since counting has to be consistent across every server handling that client's requests, not just the one instance that happened to receive this particular request.
Most teams don't build this from scratch — API gateways and cloud load balancers typically offer configurable rate limiting out of the box, and it's worth checking before reimplementing one of the algorithms above.