Rate limiting

intermediateCommon atAnthropicStripeOpenAICloudflareGoogleRead firstSliding windowQueues and dequesHash mapsPractise in the Sandbox →

A rate limiter answers one question per request: has this client used up its allowance for the recent past? The algorithms differ in what they remember. A sliding log stores every accepted timestamp and is exact but costs O(limit) memory per client. A fixed window stores one counter and is cheap but lets through up to 2× the limit across a window boundary. A token bucket stores two numbers, allows a controlled burst, and refills lazily in O(1).

The idea in plain words

Think of a nightclub with a fire-code capacity. The bouncer can enforce it in several ways:

• Fixed window: “100 people per hour, counter resets on the hour.” Simple, but 100 people can arrive at 7:59 and another 100 at 8:00.
• Sliding log: the bouncer writes down the time of every entry and counts the entries in the last 60 minutes. Exact, but the notebook grows with the limit.
• Sliding window counter: keep only this hour’s count and last hour’s count, and estimate the last 60 minutes by weighting last hour by how much of it still overlaps.
• Token bucket: the bouncer has a jar of wristbands. One wristband per entry. A new wristband drops into the jar every 36 seconds, up to a jar of 100. Quiet periods let wristbands pile up, so a group can enter at once, but the long-run rate is fixed.
• Leaky bucket: people queue at the door and are let in at a steady one every 36 seconds. If the queue is full, newcomers are turned away. Output is perfectly smooth; latency is the price.

Every one of these is a trade between accuracy, memory per client, burst tolerance and smoothness of output.

See it

All five limiters get exactly the same traffic. Run the clock and watch the default pattern: four requests just before the boundary at t = 10 and four just after. The fixed window accepts all eight inside a 10-tick span, so its worst burst goes red. Try the other patterns, change L and W, click the top row to add requests, or press Fire now while the clock runs.

Same traffic, five limiters

simulate

Fire now (t=0)UndoClear

limit L = 4 reqwindow W = 10 ticks

algorithm	state at t = 0	ok	rejected	worst 10-tick burst
Fixed window	window [0, 10): count 0/4	0	0	0
Sliding log	log []: 0/4	0	0	0
Sliding counter	0×1.00 + 0 ≈ 0.00 of 4	0	0	0
Token bucket	tokens 4.00 / 4, +0.40 per tick	0	0	0
Leaky bucket	queue 0/4, drains 1 per 2.5 ticks	0	0	0

Press Run (or step). Click the top row to add requests at any tick, or press "Fire now" while the clock runs.

request sentaccepted / sent onqueued (delayed)rejectedcurrent window

↺◀▶ Run▶t = 0

Things to look for:

• Sliding log never exceeds L in any span of W ticks. That is what “exact” means.
• Sliding counter usually agrees with the log, but it is an estimate. It assumes the previous window’s requests were spread evenly.
• Token bucket starts full, so a client that was idle can burst L requests at once, then is held to L/W per tick. Its worst burst can exceed L: a full bucket plus what refills during the window. That’s its contract, not a bug.
• Leaky bucket rejects little but delays a lot: the yellow lines are time spent queued.

When to reach for it

The problem says…	Why this fits
“at most N requests per client in any rolling T seconds”	A precise rolling-window rule: a sliding log, or a counter if approximation is allowed.
“allow short bursts but cap the average rate”	Token bucket: capacity is the burst, refill rate is the average.
“protect a downstream service that can only take X per second”	Leaky bucket / queue: smooths output to a steady rate.
“millions of clients, memory is tight”	Fixed or sliding window counter: O(1) numbers per client.
“different tiers get different limits”	Store the limit (or rate and capacity) per client next to its state.
“return how long the client should wait”	You need the arithmetic for when capacity frees up (Retry-After).

How it works

The five algorithms

Algorithm	State per client	Decision for a request at now	Accuracy
Fixed window	window id, count	reset count if now is in a new window; allow if count < limit	up to 2× limit at boundaries
Sliding log	timestamps of accepted requests	drop timestamps older than now − window; allow if fewer than limit remain	exact
Sliding window counter	previous count, current count, window id	estimate = prev × overlap + curr; allow if estimate + 1 ≤ limit	approximate, usually close
Token bucket	tokens, last refill time	refill by elapsed × rate (capped); allow if tokens ≥ 1, then spend one	exact for its own rule (burst + rate)
Leaky bucket (queue)	queue, last drain time	drain at a constant rate; enqueue if not full, else reject	smooth output, adds delay

Two rules that sound the same

“At most 5 per rolling 10 seconds” (a window rule) and “5 burst, refill 0.5 per second” (a bucket rule) are different contracts. After a burst of 5, the window rule allows nothing until the oldest request is 10 s old; the bucket allows one more every 2 s. Ask which one the problem means.

Token bucket: lazy refill

The key trick: you never run a background timer to add tokens. You store the token count and the time you last updated it, and when a request arrives you credit the whole gap at once.

1. Compute elapsed = now − last. Clamp at 0 so a clock that steps backwards can’t remove tokens.
2. tokens = min(capacity, tokens + elapsed × rate), then set last = now. Capping is what makes idle time worth at most one full burst.
3. If tokens ≥ cost, subtract cost and allow. Otherwise reject, and don’t charge for it.
4. If you reject, the wait until a token exists is (cost − tokens) / rate. That’s the Retry-After value.

Python

token bucket arithmetic.py

"""Token-bucket arithmetic: lazy refill and Retry-After. Pure functions, no clock reads."""


def refill(tokens: float, last: float, now: float, rate: float, capacity: float) -> float:
    """Tokens in the bucket at `now`, given `tokens` at time `last` (seconds)."""
    elapsed = max(0.0, now - last)  # 1. a clock that steps back must not drain the bucket
    return min(capacity, tokens + elapsed * rate)  # 2. credit the whole gap at once, capped at capacity


def take(tokens: float, cost: float = 1.0) -> tuple[bool, float]:
    """3. Spend `cost` tokens if there are enough. Returns (allowed, tokens_left)."""
    if tokens >= cost:
        return True, tokens - cost
    return False, tokens  # a rejected request costs nothing


def retry_after(tokens: float, rate: float, cost: float = 1.0) -> float:
    """4. Seconds until `cost` tokens will be available (what a 429 Retry-After header reports)."""
    return 0.0 if tokens >= cost else (cost - tokens) / rate


if __name__ == "__main__":
    cap, rate = 5.0, 2.0  # burst of 5, sustained 2 requests per second
    t = refill(0.0, last=0.0, now=1.5, rate=rate, capacity=cap)
    assert t == 3.0  # 1.5 s x 2 tokens/s
    assert refill(t, last=1.5, now=100.0, rate=rate, capacity=cap) == cap  # idle time is capped
    assert refill(t, last=1.5, now=1.0, rate=rate, capacity=cap) == t  # clock went backwards
    ok, left = take(t)
    assert ok and left == 2.0
    assert take(0.5) == (False, 0.5)
    assert retry_after(0.5, rate) == 0.25
    print("ok")

TypeScript

token bucket arithmetic.ts

import assert from "node:assert/strict";

/** Token-bucket arithmetic: lazy refill and Retry-After. Pure functions, no clock reads. */

/** Tokens in the bucket at `now`, given `tokens` at time `last` (seconds). */
export function refill(tokens: number, last: number, now: number, rate: number, capacity: number): number {
  const elapsed = Math.max(0, now - last); // 1. a clock that steps back must not drain the bucket
  return Math.min(capacity, tokens + elapsed * rate); // 2. credit the whole gap at once, capped
}

/** 3. Spend `cost` tokens if there are enough. Returns [allowed, tokensLeft]. */
export function take(tokens: number, cost = 1): [boolean, number] {
  if (tokens >= cost) return [true, tokens - cost];
  return [false, tokens]; // a rejected request costs nothing
}

/** 4. Seconds until `cost` tokens will be available (what a 429 Retry-After header reports). */
export function retryAfter(tokens: number, rate: number, cost = 1): number {
  return tokens >= cost ? 0 : (cost - tokens) / rate;
}

const cap = 5, rate = 2; // burst of 5, sustained 2 requests per second
const t = refill(0, 0, 1.5, rate, cap);
assert.equal(t, 3); // 1.5 s x 2 tokens/s
assert.equal(refill(t, 1.5, 100, rate, cap), cap); // idle time is capped
assert.equal(refill(t, 1.5, 1.0, rate, cap), t); // clock went backwards
assert.deepEqual(take(t), [true, 2]);
assert.deepEqual(take(0.5), [false, 0.5]);
assert.equal(retryAfter(0.5, rate), 0.25);
console.log("ok");

C#

token bucket arithmetic.cs

// Token-bucket arithmetic: lazy refill and Retry-After. Pure functions, no clock reads.

const double cap = 5, rate = 2; // burst of 5, sustained 2 requests per second
double t = Bucket.Refill(0, 0, 1.5, rate, cap);
if (t != 3) throw new Exception("expected 3 tokens after 1.5 s");
if (Bucket.Refill(t, 1.5, 100, rate, cap) != cap) throw new Exception("idle time must be capped");
if (Bucket.Refill(t, 1.5, 1.0, rate, cap) != t) throw new Exception("backwards clock must not drain");
var (ok, left) = Bucket.Take(t);
if (!ok || left != 2) throw new Exception("expected to spend one token");
if (Bucket.Take(0.5) != (false, 0.5)) throw new Exception("rejected request must cost nothing");
if (Bucket.RetryAfter(0.5, rate) != 0.25) throw new Exception("expected 0.25 s");
Console.WriteLine("ok");

static class Bucket
{
    // Tokens in the bucket at `now`, given `tokens` at time `last` (seconds).
    public static double Refill(double tokens, double last, double now, double rate, double capacity)
    {
        double elapsed = Math.Max(0, now - last);            // 1. a backwards clock must not drain the bucket
        return Math.Min(capacity, tokens + elapsed * rate);  // 2. credit the whole gap at once, capped
    }

    // 3. Spend `cost` tokens if there are enough.
    public static (bool Allowed, double Left) Take(double tokens, double cost = 1) =>
        tokens >= cost ? (true, tokens - cost) : (false, tokens); // a rejected request costs nothing

    // 4. Seconds until `cost` tokens will be available (a 429's Retry-After).
    public static double RetryAfter(double tokens, double rate, double cost = 1) =>
        tokens >= cost ? 0 : (cost - tokens) / rate;
}

Sliding window counter: the weighted estimate

Cloudflare popularised this: keep the count for the current fixed window and the previous one. If you are 15 s into a 60 s window, the last 60 s covers 45 s of the previous window, so weight its count by 45/60.

1. weight = (window − elapsed) / window is how much of the previous fixed window the rolling window still covers.
2. Estimate prev × weight + curr, assuming the previous window’s requests were evenly spread.
3. Count the incoming request: allow if estimate + 1 ≤ limit.

Python

window_estimate.py

"""Sliding-window counter: estimate the rolling count from two fixed-window counters."""


def window_estimate(prev_count: int, curr_count: int, elapsed: float, window: float) -> float:
    """Approximate requests in the last `window` seconds.

    `elapsed` is how far we are into the current fixed window (0 <= elapsed < window).
    """
    if not 0 <= elapsed < window:
        raise ValueError("elapsed must be inside the current window")
    # 1. the rolling window still overlaps this fraction of the previous fixed window
    weight = (window - elapsed) / window
    # 2. assume the previous window's requests were spread evenly across it
    return prev_count * weight + curr_count


def would_allow(prev_count: int, curr_count: int, elapsed: float, window: float, limit: int) -> bool:
    # 3. count the incoming request too: allow only if the estimate stays within the limit
    return window_estimate(prev_count, curr_count, elapsed, window) + 1 <= limit


if __name__ == "__main__":
    # 42 requests last minute, 18 so far this minute, 15 s in: 42 * 45/60 + 18
    assert window_estimate(42, 18, 15, 60) == 49.5
    assert not would_allow(42, 18, 15, 60, limit=50)  # 50.5 would exceed 50
    assert would_allow(42, 18, 30, 60, limit=50)  # 21 + 18 + 1 = 40
    assert window_estimate(10, 0, 0, 60) == 10  # at the boundary the old window counts fully
    print("ok")

TypeScript

window_estimate.ts

import assert from "node:assert/strict";

/**
 * Sliding-window counter: approximate requests in the last `window` seconds from two
 * fixed-window counters. `elapsed` is how far we are into the current window.
 */
export function windowEstimate(prevCount: number, currCount: number, elapsed: number, window: number): number {
  if (!(elapsed >= 0 && elapsed < window)) throw new RangeError("elapsed must be inside the current window");
  // 1. the rolling window still overlaps this fraction of the previous fixed window
  const weight = (window - elapsed) / window;
  // 2. assume the previous window's requests were spread evenly across it
  return prevCount * weight + currCount;
}

export function wouldAllow(prevCount: number, currCount: number, elapsed: number, window: number, limit: number): boolean {
  // 3. count the incoming request too: allow only if the estimate stays within the limit
  return windowEstimate(prevCount, currCount, elapsed, window) + 1 <= limit;
}

// 42 requests last minute, 18 so far this minute, 15 s in: 42 * 45/60 + 18
assert.equal(windowEstimate(42, 18, 15, 60), 49.5);
assert.equal(wouldAllow(42, 18, 15, 60, 50), false); // 50.5 would exceed 50
assert.equal(wouldAllow(42, 18, 30, 60, 50), true); // 21 + 18 + 1 = 40
assert.equal(windowEstimate(10, 0, 0, 60), 10); // at the boundary the old window counts fully
console.log("ok");

C#

window_estimate.cs

// Sliding-window counter: approximate requests in the last `window` seconds
// from two fixed-window counters. `elapsed` is how far we are into the current window.

// 42 requests last minute, 18 so far this minute, 15 s in: 42 * 45/60 + 18
if (Window.Estimate(42, 18, 15, 60) != 49.5) throw new Exception("expected 49.5");
if (Window.WouldAllow(42, 18, 15, 60, 50)) throw new Exception("50.5 would exceed 50");
if (!Window.WouldAllow(42, 18, 30, 60, 50)) throw new Exception("21 + 18 + 1 = 40 fits");
if (Window.Estimate(10, 0, 0, 60) != 10) throw new Exception("old window counts fully at the boundary");
Console.WriteLine("ok");

static class Window
{
    public static double Estimate(int prevCount, int currCount, double elapsed, double window)
    {
        if (elapsed < 0 || elapsed >= window) throw new ArgumentOutOfRangeException(nameof(elapsed));
        double weight = (window - elapsed) / window; // 1. overlap with the previous fixed window
        return prevCount * weight + currCount;        // 2. assume old requests were spread evenly
    }

    // 3. count the incoming request too: allow only if the estimate stays within the limit
    public static bool WouldAllow(int prevCount, int currCount, double elapsed, double window, int limit) =>
        Estimate(prevCount, currCount, elapsed, window) + 1 <= limit;
}

What it costs

Algorithm	Time per request	Memory per client	Burst at a boundary
Fixed window	O(1)	O(1): 2 numbers	up to 2 × limit
Sliding log	O(1) amortized (each timestamp evicted once), O(log n) if you binary-search	O(limit) timestamps	≤ limit
Sliding window counter	O(1)	O(1): 3 numbers	close to limit; error depends on how uneven traffic was
Token bucket	O(1)	O(1): 2 numbers	capacity at once; up to capacity + rate × window in any window
Leaky bucket (queue)	O(1)	O(queue size)	output never bursts

Why the sliding log is amortized O(1): each accepted timestamp is appended once and popped from the front once, the same argument as a sliding window. A single call can pop many, but the total over all calls is bounded by the number of accepted requests.

The memory column matters most at scale. With 10 million clients and a limit of 1,000 per hour, a sliding log could hold up to 10 billion timestamps. Two counters per client is 20 million numbers.

Idle clients are the other memory cost. A client that sent one request and left still has state. Options: evict lazily when you next touch that key, sweep periodically, or keep clients in an order you can expire from the front (by last activity). Each option trades CPU per call for memory, and you should be able to say which you chose and why.

Variations you’ll meet

• Per-key limits and tiers. The limit becomes data stored per client (or per API key, IP, route). Decide what happens to existing state when the limit changes: do past requests still count against the new limit?
• Weighted cost. An expensive endpoint costs 5 tokens, a cheap one 1. Token buckets handle this naturally (cost parameter); windows need a sum instead of a count.
• GCRA (generic cell rate algorithm). A token bucket stored as a single timestamp, the “theoretical arrival time”. One number per client, exact, popular in Redis-based limiters.
• Distributed limiting. Many servers, one limit. Centralise counters (for example, in Redis with atomic increments or a script), or give each node a share of the budget and accept some slop. Race conditions between “read count” and “write count” are the classic bug; see concurrency.
• Concurrency limits. “At most 10 in flight”, not “10 per second”. That’s a semaphore, not a rate limiter, and Stripe runs both.
• Shaping vs policing. A leaky bucket shapes (delays traffic to fit). The others police (reject what doesn’t fit).

Pitfalls

• Off-by-one at the window edge. Is a request exactly window ms old still counted? Write it as an inequality (now − t < window) and test the boundary tick.
• Counting rejected requests. If rejections consume allowance, a client hammering you never recovers. Usually only accepted requests count; confirm.
• Floating-point refill drift. 0.1 + 0.2 style errors can make tokens end at 0.9999 and wrongly reject. Store integer milli-tokens, or compute from integer timestamps.
• Reading the clock inside the limiter. It makes tests flaky. Pass now in.
• Unbounded per-client state. Every client that ever called you stays in the map unless you reclaim it.
• Check-then-act races in a concurrent or distributed limiter: two requests both read “4 of 5 used” and both get in.

In the interview

• Ask: rolling window or fixed window? Exact or approximate allowed? Burst allowed? Do rejected requests count? Is time passed in, and can it go backwards? How many clients, and do they go idle?
• Say the trade-off out loud: “A log is exact but O(limit) memory per client; a token bucket is O(1) and allows a burst of capacity. Which contract do we want?”
• State your eviction plan for idle clients before you’re asked.
• Expect follow-ups: per-client limits, weighted costs, a distributed version with several servers, returning Retry-After, and “what happens at 100× the number of clients?”

Check yourself

Check yourself

pick one

A fixed-window limiter allows 100 requests per minute, windows starting on the minute. What is the most requests a client can get through in any 60-second span?

A100B101C199D200

Check yourself

pick one

A token bucket has capacity 10 and refills 1 token per second. The client was idle for 5 minutes. How many requests can it make in the next second?

A1BAbout 10: a full bucket, plus whatever refills during that secondC300DUnlimited until the bucket is empty

Check yourself

pick one

You must enforce 'at most 1,000 requests per client per hour' for 50 million clients, and a 1-2% overshoot is acceptable. Which is the best fit?

ASliding logBSliding window counterCLeaky bucket queue per clientDFixed window with a 1-hour window

Practice on your own

These are classic exercises, not gym questions:

• Implement a token bucket whose cost varies per call, and add a method that returns the exact time the next call of a given cost would succeed.
• Implement GCRA with a single stored timestamp and show it makes the same decisions as a token bucket on a random request trace.
• Write a property test: on random traces, a sliding log never allows more than limit in any window, and a fixed window never allows more than 2 × limit.
• Build a leaky-bucket shaper that returns the time each accepted request will be sent, and measure the worst-case delay for a burst.

Go deeper

• Cloudflare: Counting things, a lot of different things, the sliding window counter and its measured error.
• Stripe: Scaling your API with rate limiters, request rate vs concurrency limiters, and load shedding.
• Brandur Leach: Rate limiting, cells, and GCRA, the single-timestamp token bucket.
• RFC 6585 §4: 429 Too Many Requests, and the Retry-After header it pairs with.

Related

Sliding windowThe rolling-window scan a sliding log is built on.

Queues and dequesWhere the log of timestamps lives.

Concurrency semanticsCheck-then-act races in shared counters.

Memory efficiencyBytes per client when you track millions.