Rate Limiting Algorithms

Rate limiting protects a system from being overwhelmed, whether the threat is a runaway client, a scraping bot, or just more legitimate traffic than the backend can absorb. Every API worth calling has some form of it, but the algorithm chosen underneath that limit changes its behavior in ways that matter a lot in practice — bursty traffic gets handled differently, boundary conditions leak differently, and memory cost scales differently. Picking the wrong one for the use case produces either a system that lets through damaging bursts or one that infuriates well-behaved clients with false rejections.

Fixed window counter

The simplest approach: divide time into fixed windows (e.g., one-minute buckets), count requests in the current window, and reject once the count exceeds the limit. The counter resets to zero at the start of each new window.

Strengths: Trivial to implement, minimal memory (one counter per client per window), easy to reason about.

Weakness — the boundary problem: A client can send the full limit right at the end of one window and the full limit again right at the start of the next. Two allowed bursts landing a few seconds apart on either side of a window boundary means a client can send up to 2x the intended limit in a short span. For a limit of 100 requests/minute, that's 200 requests in a couple of seconds around the :00 mark — not a rare edge case, it's a normal pattern for any client retrying near a deadline.

Fixed window is fine for loose, best-effort limits where occasional bursts aren't dangerous — for example, limiting how often a dashboard can refresh — and poor for anything protecting a resource that can actually be hurt by a burst, like a database write path or a third-party API with hard quotas.

Sliding window log

Instead of a single counter, store a timestamp for every request in a rolling log. To check a new request, drop timestamps older than the window and count what's left; if under the limit, allow and log the new timestamp.

Strengths: Perfectly accurate — no boundary problem, because the window slides continuously rather than resetting at fixed points.

Weakness: Memory cost scales with request volume, since every request needs a stored timestamp until it ages out. At high request rates or with many distinct clients, this becomes expensive fast, both in memory and in the cost of trimming the log on every check.

Sliding window log is the right choice when precision genuinely matters and volume is low-to-moderate — think an internal admin API or a small number of high-value enterprise clients — and the wrong choice for consumer-facing APIs handling large numbers of clients at high request volume.

Sliding window counter (approximation)

A practical middle ground: keep counters for the current and previous fixed windows, and estimate the sliding count as a weighted combination of the two based on how far into the current window you are. For example, if you're 25% into the current window, the estimated count is current_window_count + (previous_window_count * 0.75).

Strengths: Fixes most of the fixed-window boundary problem while keeping memory cost to just two counters per client, not a full log. This is the algorithm most production API gateways actually use by default, because it gets close-to-accurate results at fixed-window's memory cost.

Weakness: It's an approximation, not exact — under specific, unevenly distributed traffic patterns it can still slightly over- or under-count. In practice this is rarely significant enough to matter.

Token bucket

Each client has a bucket that holds up to N tokens, refilled at a steady rate (e.g., 10 tokens/second) up to the bucket's capacity. Each request consumes one token; if the bucket is empty, the request is rejected or queued. Because tokens accumulate when a client is idle, this algorithm naturally allows short bursts up to the bucket's capacity, then throttles to the steady refill rate.

Strengths: Models real-world traffic well — most clients aren't sending a perfectly steady stream, they're bursty (a page load fires ten requests at once, then goes quiet). Token bucket accommodates that burst without needing a separate "burst allowance" mechanism bolted on, because the bucket capacity is the burst allowance. It's also simple to implement and cheap to run — one counter and one timestamp per client.

Weakness: Requires tuning two parameters (bucket size and refill rate) rather than one, and getting the bucket size wrong in either direction either defeats the burst tolerance or allows bursts large enough to still cause damage.

Token bucket is the most widely used general-purpose algorithm for public APIs — it's what AWS, Stripe, and most major API providers use in some form — because it matches how real clients actually behave.

Leaky bucket

The inverse framing of token bucket: requests enter a queue (the bucket) and are processed — "leaked out" — at a constant, fixed rate, regardless of how bursty the input was. If the queue fills up faster than it drains, new requests are rejected.

Strengths: Produces a perfectly smooth, constant output rate no matter how bursty the input is. This matters when the downstream system genuinely cannot tolerate variable load — for example, a legacy backend that chokes on uneven request rates even if the average is within capacity.

Weakness: It smooths out bursts rather than allowing them, which is the opposite trade-off from token bucket. A client that legitimately needs to send occasional bursts (a bulk upload, a batch sync) gets throttled to the same steady drip as any other traffic, even if their overall usage is well within budget.

Choosing between them

Algorithm	Best for	Memory cost	Handles bursts
Fixed window	Loose, low-stakes limits	Lowest	Poorly (boundary bypass)
Sliding window log	Small volume, needs precision	Highest	Accurately
Sliding window counter	General production APIs	Low	Well (approximate)
Token bucket	Public APIs, bursty clients	Low	Well (by design)
Leaky bucket	Protecting a fixed-capacity downstream	Low	Not at all (by design)

For most teams building or exposing an API, the practical answer is: sliding window counter or token bucket for general rate limiting, leaky bucket only when there's a specific downstream system that truly needs a constant rate, and sliding window log reserved for the rare case where a small number of clients need airtight precision.

Where distributed systems make this harder

All of the above gets more complicated the moment rate limiting has to work across multiple servers instead of one process. A counter stored in local memory on one server doesn't know about requests hitting a different server behind the same load balancer — a client could get the full limit on each of three servers and triple their effective allowance. The standard fix is a shared, fast store (typically Redis) holding the counters or token buckets centrally, with atomic increment operations to avoid race conditions between concurrent requests landing on different servers at the same instant. That shared store then becomes its own point of latency and failure that needs its own resilience plan — usually a short local cache with a conservative fallback limit if the shared store is briefly unreachable, so a Redis blip doesn't either let all traffic through unchecked or block all traffic entirely.

Rate limiting is one of those pieces of infrastructure that looks trivial until traffic patterns get real — the algorithm choice, not just the limit number, is what determines whether the system behaves the way the team actually intended under load.