Rate Limiting Algorithms: Token Bucket, Windows, and Their Trade-offs

Every public API eventually meets a client that calls it in a tight loop — a buggy retry storm, a scraper, or just an enthusiastic integration. A rate limiter is the bouncer at the door: it decides, per client, which requests get in and which get 429 Too Many Requests. The interesting part is that "5 requests per second" turns out to be ambiguous, and each way of making it precise is a different algorithm with different failure modes.

Token bucket

The industry default. Picture a bucket holding up to capacity tokens, refilled at a steady rate. Each request takes a token; no token, no entry.

The elegant property: it enforces an average rate while permitting bursts up to the bucket size. A client that's been quiet accumulates tokens and may legitimately fire 5 requests at once — usually exactly what you want, since real traffic is bursty (a page load fires several API calls together).

Implementation is a few lines, and it doesn't even need a timer — refill lazily, computed from the elapsed time on each request:

class TokenBucket {
  constructor(capacity, refillPerSecond) {
    this.capacity = capacity;
    this.refillPerSecond = refillPerSecond;
    this.tokens = capacity;
    this.lastRefill = Date.now();
  }

  allow() {
    const now = Date.now();
    const elapsed = (now - this.lastRefill) / 1000;
    this.tokens = Math.min(
      this.capacity,
      this.tokens + elapsed * this.refillPerSecond
    );
    this.lastRefill = now;
    if (this.tokens >= 1) {
      this.tokens -= 1;
      return true;
    }
    return false;
  }
}

State per client: two numbers. That frugality is a big reason AWS, Stripe, and most API gateways describe their limits in token-bucket terms.

(Its sibling, the leaky bucket, flips the metaphor: requests queue in the bucket and drain at a perfectly constant rate. Choose it when the downstream needs smooth, even flow; choose token bucket when clients deserve their bursts.)

Fixed window

The version everyone invents first: count requests per calendar window — per minute, per hour — and reset the counter at each boundary. One counter per client, trivially easy. It has a famous flaw. Watch the boundary:

A client that bursts at the end of one window and the start of the next gets up to 2× the intended limit in a fraction of the window length. If the limit exists to protect capacity, the protection fails exactly when it's needed — under aggressive traffic.

Sliding window

Fix the boundary problem by measuring the trailing interval instead of calendar-aligned ones.

Sliding window log — keep a timestamp per request, drop those older than the window, count the rest:

class SlidingWindowLog {
  constructor(limit, windowMs) {
    this.limit = limit;
    this.windowMs = windowMs;
    this.timestamps = [];
  }

  allow() {
    const now = Date.now();
    const cutoff = now - this.windowMs;
    while (this.timestamps.length && this.timestamps[0] <= cutoff) {
      this.timestamps.shift();
    }
    if (this.timestamps.length < this.limit) {
      this.timestamps.push(now);
      return true;
    }
    return false;
  }
}

Perfectly accurate, but it stores one timestamp per request per client — memory grows with the limit, which hurts at scale.

Sliding window counter — the pragmatic middle ground: keep just the current and previous fixed-window counts, and estimate the trailing window by weighting the previous count by its remaining overlap:

estimate = current + previous × (overlap fraction of previous window)

Two counters per client, no timestamp log, and the boundary-burst loophole is closed (approximately — it assumes requests spread evenly across the previous window, an error bounded well under the 2× of fixed windows). This is the algorithm behind Cloudflare-style rate limiting.

Choosing

Default to token bucket for client-facing API limits, and sliding window counter when the limit is a hard promise (billing tiers, abuse thresholds).

Going distributed

One server is the easy case. With twenty instances behind a load balancer, a per-instance limiter quietly multiplies every limit by twenty — so the state has to live somewhere shared, usually Redis.

That introduces the classic read-modify-write race: two instances read count = 4, both decide 5 ≤ limit, both increment — the limit leaks. The fix is making the check-and-update atomic on the Redis side, either with a Lua script or by structuring the update so a plain atomic op suffices:

-- fixed/sliding window counter, atomically
local count = redis.call("INCR", KEYS[1])
if count == 1 then
  redis.call("PEXPIRE", KEYS[1], ARGV[1]) -- window length
end
return count -- caller compares against the limit

A token bucket can live in Redis just as easily — store the two numbers in a hash, and do the lazy refill inside the script so it's atomic:

-- KEYS[1] = bucket key
-- ARGV: capacity, refill_per_ms, now_ms, cost
local b = redis.call("HMGET", KEYS[1], "tokens", "ts")
local capacity, rate = tonumber(ARGV[1]), tonumber(ARGV[2])
local now, cost = tonumber(ARGV[3]), tonumber(ARGV[4])
local tokens = tonumber(b[1]) or capacity
local ts = tonumber(b[2]) or now

tokens = math.min(capacity, tokens + (now - ts) * rate)
local allowed = tokens >= cost
if allowed then tokens = tokens - cost end

redis.call("HSET", KEYS[1], "tokens", tokens, "ts", now)
redis.call("PEXPIRE", KEYS[1], math.ceil(capacity / rate) * 2)
return { allowed and 1 or 0, tokens }

Two details are easy to miss. Pass now from the caller or read it inside Redis with TIME — but be consistent, because app servers' clocks disagree by milliseconds or more, and a limiter fed skewed clocks refills unevenly. And set an expiry, so buckets for clients who never come back don't accumulate forever; a full bucket and a missing key mean the same thing.

GCRA: a token bucket in one number

The generic cell rate algorithm is equivalent to a token bucket but stores a single timestamp per client — the "theoretical arrival time" of the next request. Each request pushes that time forward by one emission interval (window ÷ limit); a request is allowed if it arrives no earlier than the stored time minus the burst allowance. One value per key, one comparison per request, and it computes Retry-After for free. Several Redis rate-limiting modules and libraries use it for exactly that reason.

Remaining realities of distributed limiting: every request now pays a Redis round trip (often mitigated by letting each instance keep a small local token allowance and syncing in the background), and if Redis goes down you must pick a posture — fail open (let traffic through, protect availability) or fail closed (reject, protect the backend). For most public APIs, fail open is the right default; for a payments endpoint, maybe not.

What to limit, and by what key

The algorithm is the easy part. The design questions are about keys and layers.

Choosing the key. A limit is always "N per T per something":

• API key or user ID — the fairest key for authenticated traffic; one customer's bug doesn't affect another.
• IP address — the only key available before login, but crude. A whole office or mobile carrier can share one IP behind NAT, and an attacker can rotate through thousands. Use it for login and signup endpoints, with generous limits.
• Endpoint + key — expensive endpoints (search, exports, report generation) get their own, tighter limits, separate from cheap reads.
• Global — a total cap across all clients that protects the backend itself, regardless of who is calling.

Real systems layer several: a global limit, per-customer limits by plan, and per-endpoint limits on top. A request must pass all of them.

Cost, not count. Not all requests are equal. A token bucket generalises naturally: charge each request a cost in tokens — 1 for a lookup, 10 for a search, 100 for a bulk export. The Lua script above already takes a cost argument. GitHub's GraphQL API limits by computed query cost for the same reason.

Concurrency, not rate. For slow operations, "how many at once" protects the backend better than "how many per second". Ten report exports a minute is fine if each takes a second, and a disaster if each takes ten minutes. A concurrency limiter is a counter incremented on start and decremented on finish (with a timeout in case the decrement never comes).

Where to enforce it

• At the edge (CDN or WAF) — cheapest place to drop abusive traffic, before it costs you anything. Coarse keys only: IP, path, headers.
• At the API gateway — knows the authenticated client and plan, so it can enforce per-customer limits consistently for every service behind it.
• In the service — for limits that need domain knowledge: "5 password reset emails per account per hour", "3 failed OTP attempts".
• Around outbound calls — limit your own calls to a third-party API so you stay under their limit. Same algorithms, pointed the other way.

Rate limiting protects against misuse by clients. It's a different tool from load shedding, which protects the server from overload regardless of who's calling, by dropping work when the server itself is saturated. You usually want both.

Testing a limiter

Limiters fail in quiet ways — a limit that's twenty times too loose because it's per-instance, or a clock bug that refills too fast. Test them like any other correctness-critical code:

• Inject the clock. Pass now into allow() instead of calling Date.now() inside, so tests can step time precisely and check the boundary cases: exactly at the window edge, just after a refill, after a long idle period.
• Hammer it concurrently. Fire 1,000 parallel requests against a limit of 100 through several app instances, and assert that exactly 100 succeed. This is the test that catches the read-modify-write race.
• Watch it in production. Graph allowed and rejected counts per key class. A limit nobody ever hits might be too loose to protect anything; one that legitimate customers hit daily is a support burden.

Be polite about it

A rejection is part of your API's interface. Return 429, include Retry-After (seconds until it makes sense to try again), and ideally the de facto standard headers — X-RateLimit-Limit / X-RateLimit-Remaining / X-RateLimit-Reset — so well-behaved clients can pace themselves instead of hammering you to find the edge. The best rate limiter is one clients rarely hit, because you told them where the line is.

A complete rejection looks like this:

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 12
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 12

{ "error": "rate_limited", "message": "100 requests per minute; retry in 12s" }

The unprefixed RateLimit-* names come from an IETF draft that's gradually replacing the X- versions; sending both during a transition is harmless. Put the limit in the error body too — humans reading logs don't look at headers.

The other side: being a good client

If you call someone else's rate-limited API, the same ideas apply in reverse. A client that reads the headers and paces itself almost never sees a 429; one that retries immediately turns a brief limit into a long lockout.

async function callWithRateLimit(fn, { maxAttempts = 5 } = {}) {
  for (let attempt = 1; ; attempt++) {
    const res = await fn();
    if (res.status !== 429 || attempt === maxAttempts) return res;

    // Prefer the server's instruction; fall back to backoff with jitter.
    const retryAfter = Number(res.headers.get('Retry-After'));
    const waitMs = Number.isFinite(retryAfter) && retryAfter > 0
      ? retryAfter * 1000
      : Math.random() * Math.min(30_000, 500 * 2 ** attempt);
    await new Promise((r) => setTimeout(r, waitMs));
  }
}

Better still, don't wait to be told. If you know the partner's limit is 100 requests a minute, put your own token bucket in front of your calls with a slightly lower rate, so your requests are spread out instead of arriving as a burst that trips their limiter. When many of your workers share one API key, that bucket has to be shared too — in Redis, exactly as above. Rate limiting is symmetric: the algorithm that protects your API from clients is the same one that protects you from being cut off by someone else's.