Rate Limiting: Token Buckets and Sliding Windows in Practice

Introduction

A rate limiter is a component that caps how many requests a client can make within a period of time. Every incoming request is checked against that client's recent usage: requests inside the allowance proceed, and requests beyond it are rejected, usually with an HTTP 429. Services rate limit to protect shared capacity from overload, to keep one heavy client from degrading service for everyone else, and to put a ceiling on cost.

The design question inside every rate limiter is how "recent usage" is measured, and the standard answers form a neat progression. This post builds the four of them in order: the fixed window, the sliding window log, the sliding window counter, and the token bucket. Each one fixes a specific weakness of the one before it, and each is a few dozen lines of TypeScript with an injected clock, the same testing habit we used in the LRU cache post. The closing sections cover what to send back with a rejection and what changes when the limiter runs on more than one server.

The Fixed Window and Its Boundary Problem

A fixed window counter divides time into consecutive windows of equal length (say, one minute each) and counts requests in the current window. When the count reaches the limit, further requests are rejected until the next window starts.

// src/utils/fixed-window.ts
export class FixedWindowCounter {
  private count = 0;
  private windowStart: number;

  constructor(
    private readonly limit: number,
    private readonly windowMs: number,
    now = Date.now()
  ) {
    this.windowStart = now;
  }

  allow(now = Date.now()): boolean {
    const windowsPassed = Math.floor((now - this.windowStart) / this.windowMs);
    if (windowsPassed >= 1) {
      this.count = 0;
      this.windowStart += windowsPassed * this.windowMs;
    }
    if (this.count >= this.limit) return false;
    this.count += 1;
    return true;
  }
}

This is the cheapest possible limiter: one counter and one timestamp per client. Its weakness sits at the window boundary. With a limit of 100 requests per minute, a client can send 100 requests in the last second of one window and 100 more in the first second of the next. Both bursts are legal, and the service absorbs 200 requests in about two seconds, double the rate the limit was meant to enforce.

Whether that matters depends on what the limit protects. As a coarse guard on a cheap endpoint, a fixed window is often fine. As protection for an expensive resource, the boundary burst is exactly the traffic spike the limiter was supposed to prevent.

The Sliding Window Log

A sliding window log removes the boundary problem by storing the timestamp of every recent request. A request is allowed if fewer than the limit's worth of timestamps fall inside the last window, measured backward from the current moment rather than from a fixed boundary.

// src/utils/sliding-window-log.ts
export class SlidingWindowLog {
  private timestamps: number[] = [];

  constructor(
    private readonly limit: number,
    private readonly windowMs: number
  ) {}

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

The log is exact: no matter how requests align with wall-clock boundaries, a client can never exceed the limit within any window-sized span. The price is memory. The limiter stores one timestamp per allowed request per client, so a limit of 1,000 per minute across 100,000 clients is up to a hundred million timestamps. Two implementation notes at scale: Array.prototype.shift is O(n), so a high-volume version should use a ring buffer or a head index instead, and per-client state needs an expiry story, which is a job for the LRU cache from last week.

Use the log when limits are small and precision matters, such as login attempts or password resets, where the difference between 5 and 10 tries actually changes your security posture.

The Sliding Window Counter

A sliding window counter approximates the log at a fraction of the memory. It keeps only two counters per client: the count for the current fixed window and the count for the previous one. The estimate assumes the previous window's requests were evenly spread, and weights them by how much of that window still overlaps the sliding span.

// src/utils/sliding-window-counter.ts
export class SlidingWindowCounter {
  private current = 0;
  private previous = 0;
  private windowStart: number;

  constructor(
    private readonly limit: number,
    private readonly windowMs: number,
    now = Date.now()
  ) {
    this.windowStart = now;
  }

  allow(now = Date.now()): boolean {
    const windowsPassed = Math.floor((now - this.windowStart) / this.windowMs);
    if (windowsPassed >= 1) {
      this.previous = windowsPassed === 1 ? this.current : 0;
      this.current = 0;
      this.windowStart += windowsPassed * this.windowMs;
    }
    const elapsedFraction = (now - this.windowStart) / this.windowMs;
    const estimated = this.previous * (1 - elapsedFraction) + this.current;
    if (estimated >= this.limit) return false;
    this.current += 1;
    return true;
  }
}

Worked example, with a limit of 10 per second: the previous window used all 10, and we are 25% into the current window. The estimate is 10 × 0.75 + current, so the client gets 3 more requests before the estimate reaches 10. A perfectly timed burst can still land slightly over the true limit, but the error is bounded and small; Cloudflare, which runs this algorithm at their edge, measured the practical error on real traffic at a fraction of a percent. For general API limiting, this is the accuracy of the log at the cost of the fixed window, and it is the algorithm to reach for by default.

The Token Bucket

A token bucket frames the limit as a budget instead of a window. The bucket holds up to a fixed number of tokens; each request spends one token, and tokens refill continuously at a steady rate. A full bucket lets a client burst up to its capacity at once, and after a burst the refill rate becomes the sustained ceiling.

// src/utils/token-bucket.ts
export class TokenBucket {
  private tokens: number;
  private lastRefill: number;

  constructor(
    private readonly capacity: number,
    private readonly refillPerSecond: number,
    now = Date.now()
  ) {
    this.tokens = capacity;
    this.lastRefill = now;
  }

  allow(now = Date.now()): boolean {
    const elapsedSeconds = (now - this.lastRefill) / 1000;
    const available = Math.min(
      this.capacity,
      this.tokens + elapsedSeconds * this.refillPerSecond
    );
    if (available < 1) return false; // deny without touching state
    this.tokens = available - 1;
    this.lastRefill = now;
    return true;
  }
}

Note that there is no timer refilling buckets in the background. Refill is computed lazily from the elapsed time on each call, which keeps the state at two numbers per client and makes the whole thing trivially testable with an injected clock.

One detail is load-bearing: a denied request leaves the state untouched. If the deny path wrote back its partial refill and a new lastRefill, each denial would round the token count through a floating-point addition, and a client polling at exactly the refill rate would accumulate enough drift to lose requests it had earned. Computing the refill as a single multiplication from the last successful spend keeps the arithmetic exact. Our test for this class failed until the deny path stopped writing.

The token bucket is the right model when bursts are legitimate. A dashboard that fires six API calls on page load should not be throttled to a crawl by a 1-request-per-second limit; a bucket with capacity 10 refilling at 1 per second serves the page instantly and still holds the long-run rate to 1 per second. Capacity controls the burst you tolerate, refill controls the rate you sustain, and the two knobs are independent. This separation is why token buckets (and the closely related leaky bucket, which smooths output instead of permitting bursts) sit inside most cloud providers' API gateways.

Keying, Rejections, and Response Headers

An algorithm alone is not a rate limiting policy. Three decisions around the algorithm shape how the limiter behaves in production.

What is a client? Limits are tracked per key: an API token, a user id, or, as a last resort, an IP address. IPs are a weak key because corporate NATs put thousands of users behind one address and attackers rotate addresses cheaply. Prefer authenticated identity, and keep a separate, stricter IP-keyed limit for unauthenticated routes. Per-key state lives in a map, and that map grows forever unless idle entries age out, which is again an eviction problem.

What does a rejection look like? Return 429 with a Retry-After header stating when to come back, and send usage headers on successful responses as well: the emerging standard RateLimit-Limit, RateLimit-Remaining, and RateLimit-Reset fields. Well-behaved clients can only pace themselves when told what the budget is and how much of it remains.

What should not be limited? Health checks, and anything a retry storm depends on. A limiter that rejects the requests your own recovery path needs turns a brief incident into a long one.

Rate Limiting Across Multiple Servers

Everything above assumes one process holds the counters. Behind a load balancer, each server sees only its share of a client's traffic, and the client's effective limit becomes the per-server limit multiplied by the server count.

The standard fix is to move the counters into a shared store, usually Redis. The check must be atomic: read-then-write from multiple servers is a race that admits requests over the limit, so implementations use a single Lua script or the atomic INCR plus EXPIRE pattern to make each decision in one round trip. That round trip is the cost, and it lands on every request in the hot path.

The pragmatic middle ground is to accept small error where exactness is not required: run token buckets locally on each server with the refill rate divided by the server count, or sync local counters to the shared store asynchronously. Cloudflare's published design does exactly this, trading a bounded fraction of accuracy for keeping decisions local. Reserve the strict shared-store version for the few limits where being over by a handful of requests is unacceptable.

Conclusion

The four algorithms form a progression of trade-offs. The fixed window is one counter but leaks up to double the limit at boundaries. The sliding window log is exact but stores a timestamp per request. The sliding window counter gets within a bounded error of the log using two counters. The token bucket reframes the limit as burst capacity plus sustained rate, which is usually the policy an API actually wants. All four reduce to a handful of state per client and a decision computed from the current time, which is why the injected-clock habit makes every one of them testable to the millisecond.

Key Takeaways

• A rate limiter caps requests per client per time span; the algorithms differ in how they measure the span and what state they keep.
• Fixed windows admit up to 2x the limit across a window boundary; know whether that burst matters before accepting it.
• The sliding window log is exact at one timestamp per request; use it for small, security-sensitive limits.
• The sliding window counter approximates the log with two counters and a weighted estimate; it is the strongest default for general API limiting.
• Token buckets separate burst tolerance (capacity) from sustained rate (refill); prefer them when clients legitimately burst.
• Pass now into every limiter decision so tests control time, key limits by authenticated identity over IP, tell clients their budget with 429 plus RateLimit headers, and go to a shared atomic store only for limits that must be exact across servers.