Token bucket vs sliding window vs fixed window — which rate limiter when?

Q: Token bucket vs sliding window vs fixed window — which rate limiter when?

**Target Audience:** Developers preparing for system design interviews. You know what an HTTP request is; no rate limiting background assumed. **Difficulty:** Medium **Verified with:** Node 22.22, Python 3.12, Go 1.24 and Java 21 (all four print identical output). > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. All behaviour shown comes from running the example; the **Verified** section quotes the full output. ## 1. Why This Even Matters — A Story First A gym allows each member 10 visits a month. Three gyms enforce it three ways: - **Gym 1** resets everyone's count on the 1st of each month. A member visits 10 times on the 30th and 31st, then 10 more times on the 1st and 2nd — 20 visits in four days, all legal. - **Gym 2** keeps a diary of every visit and, at the door, counts the visits in the last 30 days. Perfectly fair, but the diary is long for busy member

The problem

Question presented to candidate: "You need to limit each API key to 10 requests per minute. Walk me through fixed window, sliding window and token bucket. What does each one let through in a burst, how much state does it keep per key, and which one would you pick?"

What a strong answer should cover:

Fixed window counter: one counter per key per clock-aligned window; tiny state, but a boundary burst lets through up to 2x the limit within a few seconds across a window edge
Sliding window log: store every accepted timestamp, count the last W seconds; exact, but memory grows with the limit (one entry per request in the window)
Sliding window counter: weight the previous window count by its overlap; a few numbers of state, close to exact, but an approximation that can over- or under-admit when traffic inside a window is uneven
Token bucket: capacity (burst) plus refill rate; allows a controlled burst up to capacity and then the steady rate; two numbers of state; the usual default for APIs. Leaky bucket paces output at a constant rate
Choosing: token bucket for APIs that should tolerate short bursts; sliding log where exactness matters and limits are small; sliding counter at very large scale; fixed window only when the boundary burst is acceptable
Know the parameters: a token bucket "10/min" with capacity 10 admits more than 10 in the first minute

Code / implementation expected: Yes — implementing at least one algorithm; the example runs all four on the same traffic in four languages.

rate-limiting
system-design
redis

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Developers preparing for system design interviews. You know what an HTTP request is; no rate limiting background assumed. Difficulty: Medium Verified with: Node 22.22, Python 3.12, Go 1.24 and Java 21 (all four print identical output).

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. All behaviour shown comes from running the example; the Verified section quotes the full output.

1. Why This Even Matters — A Story First

A gym allows each member 10 visits a month. Three gyms enforce it three ways:

Gym 1 resets everyone's count on the 1st of each month. A member visits 10 times on the 30th and 31st, then 10 more times on the 1st and 2nd — 20 visits in four days, all legal.
Gym 2 keeps a diary of every visit and, at th

The solution is hidden so you can try first

13 min read · 10 sections

Read the code

Fixed window vs sliding log vs sliding counter vs token bucket on five traffic patterns

Open in playground

// Four rate-limiting algorithms, limit = 10 requests per 60 s, on the same traffic.
// Time is a fake clock in milliseconds; all arithmetic is integer.
const LIMIT = 10;
const W = 60000;

class FixedWindow {
  constructor() { this.win = -1; this.count = 0; }
  allow(t) {
    const w = Math.floor(t / W);
    if (w !== this.win) { this.win = w; this.count = 0; }
    if (this.count < LIMIT) { this.count++; return true; }
    return false;
  }
  state() { return "2 numbers"; }
}

class SlidingLog {
  constructor() { this.log = []; this.peak = 0; }
  allow(t) {
    while (this.log.length > 0 && this.log[0] <= t - W) this.log.shift();
    if (this.log.length < LIMIT) {
      this.log.push(t);
      this.peak = Math.max(this.peak, this.log.length);
      return true;
    }
    return false;
  }
  state() { return this.peak + " timestamps"; }
}

class SlidingCounter {
  constructor() { this.win = 0; this.curr = 0; this.prev = 0; }
  allow(t) {
    const w = Math.floor(t / W);
    if (w !== this.win) {
      this.prev = w === this.win + 1 ? this.curr : 0;
      this.curr = 0;
      this.win = w;
    }
    const e = t - w * W; // ms elapsed in the current window
    // estimate = prev * (W - e) / W + curr, compared without division
    if (this.prev * (W - e) + this.curr * W < LIMIT * W) { this.curr++; return true; }
    return false;
  }
  state() { return "3 numbers"; }
}

class TokenBucket {
  // capacity 10 tokens, refill 10 tokens per 60 s; 1 token = W units, refill = LIMIT units per ms
  constructor() { this.units = LIMIT * W; this.last = 0; }
  allow(t) {
    this.units = Math.min(LIMIT * W, this.units + (t - this.last) * LIMIT);
    this.last = t;
    if (this.units >= W) { this.units -= W; return true; }
    return false;
  }
  state() { return "2 numbers"; }
}

const ALGOS = [["fixed window", FixedWindow], ["sliding log", SlidingLog],
  ["sliding counter", SlidingCounter], ["token bucket", TokenBucket]];

function range(start, n, step) {
  const out = [];
  for (let i = 0; i < n; i++) out.push(start + i * step);
  return out;
}

function scenario(name, times, from) {
  console.log("== " + name);
  for (const [label, Cls] of ALGOS) {
    const lim = new Cls();
    let marks = "";
    let ok = 0;
    times.forEach((t, i) => {
      const a = lim.allow(t);
      if (i >= from) { marks += a ? "#" : "."; if (a) ok++; }
    });
    console.log("  " + label.padEnd(16) + marks + "  allowed " + ok + "/" + (times.length - from) + "  state " + lim.state());
  }
}

scenario("A. boundary burst: 10 at 59.0-59.9 s, 10 at 60.0-60.9 s",
  range(59000, 10, 100).concat(range(60000, 10, 100)), 0);
scenario("B. steady 1 request every 3 s for 3 minutes (20/min against 10/min)",
  range(0, 60, 3000), 0);
scenario("C. idle, then a burst of 15 at t=200 s",
  range(200000, 15, 10), 0);
scenario("D1. old burst at 0.0-0.9 s, new burst of 10 at 90 s (show only new)",
  range(0, 10, 100).concat(range(90000, 10, 10)), 10);
scenario("D2. old burst at 59.0-59.9 s, new burst of 10 at 90 s (show only new)",
  range(59000, 10, 100).concat(range(90000, 10, 10)), 10);

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.