Token Bucket vs Leaky Bucket vs Sliding Window

Overview

Production gateways are not one algorithm. AWS API Gateway and Stripe-style APIs are token-bucket flavored (rate + burst). NGINX limit_req is leaky / delayed. Redis tutorials teach sliding counters because they are cheap and fair enough. Interviews score you on burstiness, memory, boundary fairness, and whether you can implement the debit atomically.

By the end of this lesson you should be able to:

• Draw token refill, leaky drain, and sliding-window weight on a whiteboard
• Pick an algorithm from burst vs smoothness vs memory, not from a blog title
• Walk a 60-second window with numbers (2× seam, sliding estimate)
• Cost a GraphQL field as N tokens without inventing a second limiter
• Say what is still true if the client “already paces”

Scorecard

Diagrams - step by step

Three small diagrams for token bucket, leaky bucket, and sliding window. Step numbers in the labels give the animation order. The lesson map under Diagram 1 plays those steps.

Diagram 1 - Happy path: token bucket check and debit

Read the balance and the last refill time, add tokens for the elapsed interval, and cap at capacity. Debit the cost when the balance covers it, then save the new balance and timestamp. Otherwise return 429 with Retry-After. If the wall clock jumps backwards, elapsed time goes negative: use a monotonic clock.

flowchart TB
  A["Step 1 Request with cost c Ready"]
  B["Step 2 Read tokens and the last refill time Ready"]
  C["Step 3 Refill - tokens = min of capacity and tokens + rate x elapsed Ready"]
  D["Step 4 tokens at least c? Ready"]
  E["Step 5a Debit c and allow Ready"]
  F["Step 5b Reject with 429 and Retry-After Ready"]
  G["Step 6 Save tokens and timestamp Ready"]
  X["Failure path - negative elapsed time, use a monotonic clock Ready"]
  A -->|continues| B
  B -->|continues| C
  C -->|continues| D
  D -->|yes| E
  D -->|no| F
  E -->|continues| G
  B -->|wall clock jumps backwards| X

Diagram 2 - Failure path: leaky bucket shaping on an interactive API

Shaping interactive traffic through a leaky queue holds the last request for seconds. Users time out and retry, which refills the queue, so latency stays high. Use a token bucket for interactive APIs. Keep leaky shaping for egress to SMS or payment partners.

Diagram 3 - Decision: token vs leaky vs sliding

Bursty clients that may burst get a token bucket. A downstream that needs a smooth rate gets a leaky bucket: drop the excess (policing) or delay it (shaping). Fairness over a rolling window is a sliding window, and the counter form is an approximation, not an exact log. A fixed window is the tempting shortcut, and it admits about 2x at the boundary.

Fixed window — why it loses as the only gate

Partition time into aligned buckets. Count in the current bucket; reset at the boundary.

A client sends limit at 11:59:59 and limit again at 12:00:00. Downstream sees 2× in about two seconds. That is not a burst you designed — it is a clock artifact.

Use it for “1000/day” sitting under a per-second token bucket, not as the only limiter on /v1/search.

Sliding log vs sliding counter

Log: store a timestamp per request (Redis sorted set). Prune older than now - W, count, admit if < limit. Exact over any rolling interval. Memory is O(RPS × W) per key. Unique members: timestamp + sequence, or same-ms requests collide and vanish.

Counter (hybrid): keep previous and current fixed-window counts.

estimated = prev × (1 − elapsed/W) + curr

Admit if estimated + cost ≤ limit. O(1) memory. Approximate: it assumes the previous window was roughly uniform. Cloudflare-class deployments publish tiny wrong-decision rates at huge volume. Do not claim bit-exact.

Token bucket — burst is a feature

A bucket holds up to capacity tokens. Tokens refill at rate r. A request costs cost (usually 1). Empty → 429 (or wait, which is leaky-adjacent).

• Burst = capacity (idle → full).
• Sustained = r.
• Capacity heuristic: b ≈ r × burst_seconds. 10 RPS with 2s of burst → capacity 20.

AWS API Gateway throttling is this pair: rate = refill, burst = bucket size. Stripe’s public limiter writeup is the same family.

A full-bucket burst can still smash a fragile partner. If downstream needs a smooth line, you wanted leaky on the egress, not a bigger token bucket on the ingress.

Leaky bucket — police vs shape

Requests enter a bucket that leaks at constant r. If full: drop (police) or queue (shape).

Some texts treat “leaky as a meter” as a token drain with no stored burst. Say which one you mean. Token bucket when controlled bursts are a feature. Leaky when the partner SLA is “N per second, no spikes.”

Weighted cost

GraphQL depth, /search, and LLM tokens are not one request. Debit cost tokens (or cost slots) with the same algorithm.

allow(key, cost=10)   # search
allow(key, cost=1)    # health / cheap GET

Do not invent a second limiter for “expensive routes” unless you also need a separate fairness key. One bucket, different debit. Tenant fairness on top: noisy neighbors.

Client pacing does not replace the server

SDKs should run a client-side token bucket to avoid 429 storms. Attackers and buggy retries will not. The server limiter is the SoT. Return 429 + Retry-After. Honor jitter on the client.

Clocks: in-process time.monotonic() / performance.now() are fine for a local bucket. Distributed refill must not trust N client wall clocks — Redis TIME inside Lua.

Working sketches

Sandboxes are in-memory. Redis stays on the next page.

Press Run. Snippets must be self-contained — no network, files, or native modules.

Press Run. Snippets must be self-contained — no network, files, or native modules.

Interview Q&A

Pitfalls

Go Deeper

• AWS API Gateway throttling
• Stripe Engineering — rate limiters
• Redis — five rate limiters
• NGINX limit_req

Cluster: hub · next Redis + Lua