Rate Limiting Algorithms Explained: Token Bucket vs Sliding Window vs Fixed Window

Quick Answer

Fixed window counters are the simplest to build but let a client burst up to double its stated limit right at the window boundary. Sliding window logs fix that exactly but cost memory per request. Sliding window counters approximate the log cheaply, and token buckets decouple burst size from sustained rate using two numbers instead of a timestamp list. We proved the boundary-burst problem with a real, runnable simulation rather than just describing it.

The Four Algorithms We're Actually Comparing

If you've read our piece on why rate limiting exists in the first place, you already know the problem: one client — a buggy retry loop, a scraper, or a plain traffic spike — can eat capacity meant for everyone else. This post skips that pitch entirely and goes straight into the part that actually trips people up: the algorithms used to enforce a limit, and how picking the wrong one quietly changes what your API is actually promising.

Four algorithms show up in real systems, over and over: the fixed window counter, the sliding window log, the sliding window counter (a weighted approximation of the log), and the token bucket. They all claim to do the same job — cap a client at N requests per time period — but they enforce that cap in genuinely different ways, with different memory costs and different failure modes at the edges.

Instead of describing this abstractly, we implemented all four in plain JavaScript and ran the exact same burst of simulated requests through each one, using explicit timestamps instead of real sleeps so the results are exact and reproducible. Every number and every code sample below is real output from that run — you can paste the logic into a Node REPL and reproduce it yourself.

Fixed Window Counter: Simple, Fast, and Secretly Broken

A fixed window counter divides time into fixed-size blocks — say, every calendar-aligned 1000ms — and keeps one counter per block. Every request inside a block increments that counter; once it passes the limit, further requests in the same block get denied. When the clock ticks into the next block, the counter resets to zero, regardless of how many requests just went through right before the reset.

function makeFixedWindow(limit, windowMs) {
  let windowStart = null;
  let count = 0;
  return function check(t) {
    if (windowStart === null || t - windowStart >= windowMs) {
      windowStart = Math.floor(t / windowMs) * windowMs;
      count = 0;
    }
    count++;
    return count <= limit;
  };
}

That reset-to-zero-at-the-boundary behavior is the entire problem. Nothing stops a client from spending its whole budget in the last few milliseconds of one window, then immediately spending its whole budget again in the first few milliseconds of the next window. The limiter never sees a violation, because it only ever looks at one window in isolation.

We proved this with a real run. Limit: 5 requests per 1000ms window. We sent 5 requests at 900ms, 920ms, 940ms, 960ms, and 980ms — the tail end of window one — then 5 more at 1010ms, 1030ms, 1050ms, 1070ms, and 1090ms — the start of window two. That's 10 requests inside a 190ms span. Here's the actual output:

Fixed Window Counter:
  900ms:A  920ms:A  940ms:A  960ms:A  980ms:A  1010ms:A  1030ms:A  1050ms:A  1070ms:A  1090ms:A
  Allowed: 10 / 10

All 10 requests got through. A limiter that's supposed to cap this client at roughly 5 requests per second let through double that, concentrated into under a fifth of a second, without a single reported denial. That's not a rare edge case — it's the guaranteed worst case the moment your traffic isn't perfectly smooth, and in production it never is.

The upside is real too: fixed window needs exactly one integer and one timestamp of state per client, the check is O(1), and it's trivial to implement with a single Redis INCR plus EXPIRE. For coarse, non-adversarial limits — like capping how many emails an internal cron job can trigger per minute — that simplicity is worth more than boundary precision.

Sliding Window Log: Perfectly Accurate, Expensive to Keep

A sliding window log fixes the boundary problem by throwing away the idea of a fixed calendar window entirely. Instead, it stores the timestamp of every accepted request. On each new request, it discards timestamps older than windowMs and counts what's left. If that count is still under the limit, the request is accepted and its timestamp is added to the log.

function makeSlidingLog(limit, windowMs) {
  let log = [];
  return function check(t) {
    log = log.filter(ts => t - ts < windowMs);
    if (log.length < limit) {
      log.push(t);
      return true;
    }
    return false;
  };
}

Run the identical 10-request boundary burst through it:

Sliding Window Log:
  900ms:A  920ms:A  940ms:A  960ms:A  980ms:A  1010ms:D  1030ms:D  1050ms:D  1070ms:D  1090ms:D
  Allowed: 5 / 10

Exactly 5 allowed, exactly 5 denied — the actual limit, no matter where a fixed calendar boundary happens to fall, because there is no fixed calendar boundary. The window is always "the trailing 1000ms from right now," recalculated on every single request. This is the algorithm you reach for when correctness matters more than anything else — think login-attempt limiting or OTP requests, where letting a client double its budget is a security problem, not just an inconvenience.

The cost is memory and CPU: you're storing a timestamp per accepted request inside the trailing window, and every check has to trim and count that list. For a limit of 5 that's nothing. For a limit of 50,000 requests per minute per API key, spread across a million active keys, storing and re-filtering that many timestamps on every single request stops being free — which is exactly the problem the next algorithm exists to solve.

Sliding Window Counter: The Practical Middle Ground

A sliding window counter keeps the fixed-window's cheap O(1) state — just two integers and a window-start timestamp — but corrects for the boundary problem by blending in the previous window's count, weighted by how much of it still overlaps the trailing window. The formula is: estimated = currentCount + previousCount × (1 − elapsed / windowMs).

This isn't a made-up compromise for this post — it's publicly documented as the exact approach Cloudflare uses to rate-limit traffic across millions of domains, described in their own engineering blog as an approximation of the sliding log that needs roughly 24 bytes of state per client instead of a growing list of timestamps.

function makeSlidingCounter(limit, windowMs) {
  let currentWindowStart = null;
  let currentCount = 0;
  let previousCount = 0;
  return function check(t) {
    const bucket = Math.floor(t / windowMs) * windowMs;
    if (currentWindowStart === null) {
      currentWindowStart = bucket;
    } else if (bucket !== currentWindowStart) {
      previousCount = (bucket - currentWindowStart === windowMs) ? currentCount : 0;
      currentCount = 0;
      currentWindowStart = bucket;
    }
    const elapsed = t - currentWindowStart;
    const weight = (windowMs - elapsed) / windowMs;
    const estimated = previousCount * weight + currentCount;
    if (estimated < limit) {
      currentCount++;
      return true;
    }
    return false;
  };
}

Same boundary burst, same limit:

Sliding Window Counter (weighted):
  900ms:A  920ms:A  940ms:A  960ms:A  980ms:A  1010ms:A  1030ms:D  1050ms:D  1070ms:D  1090ms:D
  Allowed: 6 / 10

Six allowed instead of the log's exact five — the approximation let one extra request through at 1010ms, because at that instant 99% of the previous window still weighed into the estimate and the math came out to 4.95, just under the limit of 5. That's the trade-off in one number: a small, bounded overcount right at the boundary, in exchange for O(1) memory that doesn't grow with request volume. For a high-traffic public API, that trade is almost always worth it.

Token Bucket: Built for Bursts, Tuned by Two Numbers

A token bucket works completely differently from the previous three: there's no window at all. Instead, a bucket holds tokens up to some capacity, tokens refill continuously at some rate, and every request consumes one token. If the bucket is empty, the request is denied. This is precisely the terminology AWS API Gateway uses in its own throttling documentation — a "burst limit" (the bucket's capacity) and a "rate limit" (the refill rate) are configured as two separate numbers for exactly this reason.

function makeTokenBucket(capacity, refillPerMs) {
  let tokens = capacity;
  let last = null;
  return function check(t) {
    if (last === null) last = t;
    tokens = Math.min(capacity, tokens + (t - last) * refillPerMs);
    last = t;
    if (tokens >= 1) {
      tokens -= 1;
      return true;
    }
    return false;
  };
}

With capacity set equal to the window limit (5 tokens, refilling at 5 per second), the boundary burst produces:

Token Bucket (capacity 5, refill 5/sec):
  900ms:A  920ms:A  940ms:A  960ms:A  980ms:A  1010ms:D  1030ms:D  1050ms:D  1070ms:D  1090ms:D
  Allowed: 5 / 10

Same result as the sliding log here, because in only 30ms of refill time the bucket barely regains a fraction of a token — nowhere near enough to grant another full request. But token bucket's real strength shows up on a different kind of traffic: a steady drip of one request every 150ms for three seconds (21 requests total, same 5-per-1000ms limit):

Fixed Window Counter:   Allowed 16 / 21
Sliding Window Log:     Allowed 15 / 21
Token Bucket:           Allowed 20 / 21

Token bucket let through 20 of 21 requests — almost everything — because it doesn't care about calendar-aligned windows at all; it just tracks whether you're within budget right now. Fixed window, by contrast, denied 5 requests purely because they landed in the "wrong half" of a window that had already been spent by earlier, perfectly reasonable traffic. This is why token bucket is the default choice for user-facing APIs: it tolerates the natural burstiness of real usage instead of punishing traffic for bad luck on window alignment.

One more lever worth knowing: capacity and rate are independent. A bucket with capacity 20 and a refill rate of 5/second still averages out to 5 requests per second over time, but it lets a client spend all 20 in one instant burst after being idle — useful for a mobile app that syncs a batch of changes after being offline, where you want to allow a big legitimate catch-up burst without raising the sustained rate.

Head-to-Head: One More Scenario That Settles It

To make sure the boundary burst wasn't a cherry-picked scenario, we ran a third test: fire 20 requests simultaneously at t=0, against the same 5-per-1000ms limit, for all four algorithms.

Fixed Window:     allowed 5 / 20 (all at t=0)
Sliding Log:      allowed 5 / 20 (all at t=0)
Sliding Counter:  allowed 5 / 20 (all at t=0)
Token Bucket:     allowed 5 / 20 (all at t=0)

When every request arrives at the exact same instant, all four algorithms agree and cap it at exactly 5. That's an important sanity check: the differences between these algorithms aren't about whether they enforce a limit — they all do, correctly, for a true instantaneous burst. The differences only show up around boundaries (fixed window's weak spot) and around legitimate burstiness spread over real time (where token bucket is far more forgiving than fixed window, and sliding log is the strictest of all). Which of those matters more depends entirely on what you're protecting.

Which One Should You Actually Use

For most public-facing APIs, token bucket is the right default. It's cheap (two numbers per client), it tolerates real-world burstiness instead of punishing it, and its two knobs — capacity and refill rate — map directly onto a product decision you can explain to a non-engineer: "how big a burst do we allow" and "what's the sustained rate we actually care about." Libraries like rate-limiter-flexible or bottleneck in Node, or a small Lua script run atomically inside Redis, are the standard way to implement it across multiple app servers without race conditions.

• Fixed window — use it for coarse, low-stakes, internal limits where implementation simplicity matters more than precision, and a client briefly doubling its budget isn't a real problem.
• Sliding window log — use it for low-volume, high-stakes limits like login attempts, password resets, or OTP requests, where the per-client request volume is small enough that storing timestamps is cheap and exactness matters more than raw throughput.
• Sliding window counter — use it for high-volume public APIs where you want sliding-window accuracy without sliding-log memory costs; this is the production-grade middle ground.
• Token bucket — use it for user-facing APIs and anything where short, legitimate bursts (page load firing several requests at once, a client catching up after being offline) shouldn't be penalized just because they clustered together.

In practice, production systems often layer two of these: a token bucket for per-second burst tolerance, and a sliding window counter for a per-minute or per-hour sustained cap, so a client can burst briefly but still can't sustain an abusive rate over a longer window. Neither algorithm alone has to do both jobs.

Frequently Asked Questions