Rate Limiting Algorithms
Concept
Rate limiting caps how many requests a client (or the system as a whole) can make in a given window, and the algorithm chosen decides exactly how "how many, in what window" gets enforced — the difference shows up as real behavioral gaps at burst boundaries, not just implementation detail.
- Fixed Window Counter — count requests in discrete, non-overlapping windows (e.g., a counter reset every 00:00:00). Trivial to implement and cheap to store, but it lets a client burst up to 2x the limit by timing requests around the window boundary — e.g. 100 requests at 0:59:59 and another 100 at 1:00:00 both pass a "100/minute" limit despite landing within one real second of each other.
- Sliding Window Log — store a timestamp per request and count how many fall inside a trailing window that slides continuously with the current time. Precise (no boundary burst problem) but memory cost scales linearly with request volume, since every individual timestamp must be retained until it ages out.
- Sliding Window Counter — an approximation that blends the previous and current fixed windows, weighting the previous window's count by how much of it still overlaps the trailing window. Gets most of the sliding log's boundary accuracy at fixed-window-like memory cost — the practical middle ground most production rate limiters converge on.
- Token Bucket — a bucket holds up to N tokens, refilled at a steady rate; each request consumes one token, and requests are rejected once the bucket is empty. Naturally allows bursts up to the bucket size while still enforcing a long-run average rate — the shape most API rate limiters actually want, since real traffic is bursty, not smooth.
- Leaky Bucket — the inverse framing: requests queue into a bucket and drain out at a constant rate regardless of arrival pattern. Great for shaping traffic into a steady downstream rate (e.g., smoothing bursty producer traffic before it hits a fixed-capacity consumer), but a poor fit for user-facing API fairness since it can't express "allow occasional bursts."
Tradeoffs
| Algorithm | Burst handling | Memory cost | Precision at window edges |
|---|---|---|---|
| Fixed Window Counter | Allows up to 2x limit at boundary | O(1) per key | Poor |
| Sliding Window Log | Exact, no burst leakage | O(requests) per key | Exact |
| Sliding Window Counter | Close approximation | O(1) per key | Good (approximate) |
| Token Bucket | Bursts allowed up to bucket size, then smooths to refill rate | O(1) per key | Good, burst-aware by design |
| Leaky Bucket | Bursts get queued/delayed, not allowed | O(1) per key (+ queue) | Good, but no burst allowance |
The real tension is between precision and cost at scale: exact accounting (sliding window log) is easy to reason about but doesn't survive high request volume cheaply, while the cheap O(1) approximations (fixed window, sliding window counter, token/leaky bucket) all accept some inexactness at the margins in exchange for constant memory per client — the right choice depends on whether "occasionally 5% over the limit" is a real problem or a rounding error nobody will notice.
When to use / when not to
- Use token bucket as the default for public/partner-facing APIs — it matches how real clients behave (idle, then a burst of calls) and is what most gateway products (Kong, Envoy, AWS API Gateway) implement as their primary algorithm.
- Use leaky bucket when the goal is protecting a fixed-capacity downstream (a legacy system, a queue consumer with hard throughput limits) from bursty upstream producers — traffic shaping, not client fairness.
- Use sliding window counter when boundary bursting is a real, exploited problem (abuse/DoS-adjacent scenarios) but the cost of a full request log is unacceptable at scale.
- Avoid fixed window counter for anything abuse-sensitive — the 2x boundary burst is a known, easily-triggered gap, not a theoretical edge case.
- Avoid a hand-rolled sliding window log at high request volume — the per-request timestamp storage becomes the bottleneck the rate limiter itself is supposed to be protecting the system from.
- In a distributed system, all of these need a shared, low-latency store (Redis is the default) to keep counters consistent across instances — a per-instance in-memory limiter just multiplies the effective limit by the instance count.
Common pitfall
Implementing rate limiting per-instance instead of against a shared store in a horizontally scaled service — a "100 requests/minute" limit enforced independently on each of 10 instances behind a load balancer is actually a 1,000 requests/minute limit in practice, and nobody notices until the system is already being hammered past its real capacity.
Engineering Lens
Rate limiting decisions surface a recurring Principal-level pattern: picking the algorithm is the easy 20%, and defending the limit value itself (calls/second, burst size) against actual measured downstream capacity is the harder 80% that separates a real design from a checkbox. In a review, the strong answer isn't "we use token bucket" — it's showing the limit was derived from the downstream dependency's actual throughput ceiling (a database's max connections, a payment processor's per-merchant rate cap) rather than picked as a round number. This reasoning transfers directly to Fintech/Capital Markets contexts — an exchange's per-client order-submission throttle and a payments gateway's per-merchant API cap are the same token-bucket problem wearing different clothes, and the interesting design conversation (multi-tenant fairness, priority tiers for premium clients, graceful degradation vs hard rejection) is domain-independent.