Rate limiting algorithms

The problem: one customer creating 50,000 links a minute

Snip's API lets paid customers create links programmatically. One customer's buggy script loops, creating 50,000 links a minute. The database slows for everyone, and the free plan's spammers are also hammering link creation to churn out phishing links. Snip needs to say: each API key may create at most 100 links per minute, and turn away the rest with a 429 Too Many Requests.

The question is what "100 per minute" means precisely, and how cheaply it can be checked on every request.

Four algorithms

Fixed window. Keep a counter per key per calendar minute. Allow while the counter is below the limit; reset at the start of each minute. One number per key, trivially cheap. Its flaw is the boundary: 100 requests at 12:00:59 and 100 more at 12:01:00 are both allowed, so 200 get through in one second.

Sliding log. Keep the timestamp of every allowed request in the last minute; allow if there are fewer than the limit. Exact, with no boundary problem, but it stores up to the limit's worth of timestamps per key: fine for 100, too costly for 10,000.

Sliding window counter. Keep only two counters, this minute and the previous one, and estimate the last 60 seconds as the current count plus the previous count weighted by how much of the previous minute is still inside the window. Cloudflare's example: 42 requests last minute and 18 so far this minute, 15 seconds in, estimates 42 × 45/60 + 18 = 49.5. Two numbers per key, nearly as smooth as the log.

Token bucket. Each key has a bucket holding up to capacity tokens, refilled at a steady rate. A request takes a token; with no token, it's rejected. The capacity sets the largest burst allowed; the rate sets the long-run average. Stripe uses token buckets for its request rate limiter.

Try it

With a limit of 10 per 10 seconds and 30 requests crowded around the 10-second mark, the fixed window let 20 through within ten seconds, twice the limit; the sliding log allowed at most 10; the sliding window counter at most 12. The token bucket allowed up to 14 there, and 17 to 19 in other patterns: by design, it permits a full bucket's burst plus whatever refills during the window. That's a feature, not a bug: real clients are bursty, and a bucket lets them burst while capping the average.

Tested code

export class TokenBucket {
  private tokens: number;
  private last: number;

  constructor(readonly capacity: number, readonly refillPerSec: number, now = Date.now()) {
    this.tokens = capacity;
    this.last = now;
  }

  allow(now = Date.now()): boolean {
    this.tokens = Math.min(this.capacity, this.tokens + ((now - this.last) / 1000) * this.refillPerSec);
    this.last = now;
    if (this.tokens < 1) return false;
    this.tokens -= 1;
    return true;
  }
}

/** Cloudflare-style approximation: this window's count plus the previous window's, weighted by overlap. */
export class SlidingWindowCounter {
  private window = -1;
  private current = 0;
  private previous = 0;

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

  allow(now = Date.now()) {
    const w = Math.floor(now / this.windowMs);
    if (w !== this.window) {
      this.previous = w === this.window + 1 ? this.current : 0; // a gap of more than one window resets it
      this.current = 0;
      this.window = w;
    }
    const estimate = this.previous * (1 - (now % this.windowMs) / this.windowMs) + this.current;
    if (estimate >= this.limit) return false;
    this.current++;
    return true;
  }
}

Tested on a burst of 20 requests straddling a window boundary, with a limit of 10 per 10 seconds: a fixed window allowed all 20, the sliding log 10, the sliding window counter 11, and a token bucket of capacity 10 refilling one per second allowed 10. Against a steady 2 requests a second for 20 seconds, the token bucket allowed its 10-token burst and then about one a second: 29 of 40.

Telling the client

Reject with 429 Too Many Requests, defined in RFC 6585, which may include a Retry-After header saying how long to wait. Many APIs also return the limit and what's left on every response, as GitHub does with x-ratelimit-limit, x-ratelimit-remaining and x-ratelimit-reset, so well-behaved clients can slow down before they hit the wall.

Recap

Interview questions