Rate limiter

Every request you send goes to all three limiters at the same moment. Each lane shows the last ten seconds: a green dot got through, a red cross was refused, which in a real API is a 429 Too Many Requests response. All three enforce the rule in the sentence at the top, and they still disagree about which requests to refuse.

The bucket holds up to the limit in tokens and refills at a steady rate: a full bucket's worth every window. Each request takes a token, and an empty bucket refuses. A full bucket lets a burst straight through, then the refill rate takes over. That is why it is the usual choice for APIs: short bursts are fine, sustained floods are not.

It keeps two numbers per client, the tokens left and when it last refilled, and works the refill out on the next request rather than with a timer. AWS API Gateway documents its throttling as a token bucket.

It counts requests per window of the clock (the dashed lines) and starts again from zero at each line. One counter per client, which can simply expire with its window, makes it the cheapest of the three.

Its flaw is at the edges. A burst just before a dashed line and another just after it both fit their own window, so twice the limit gets through within moments. Watch the middle lane, wait until a dashed line is about to arrive, and press Burst of 10 on either side of it.

It keeps the time of every request it let through, and before letting another through it counts the ones inside the last window, the shaded band. No stretch of that length ever holds more than the limit, so there is no burst at an edge.

The price is memory: up to the limit in timestamps per client, rather than one number. A common compromise, the sliding window counter, keeps only this window's count and the last one's, and weights the last one by how much of it still overlaps the sliding window. It is nearly as smooth for two numbers.

“Design a rate limiter” is a standard round. Beyond choosing an algorithm, the points that score are:

• Where it runs: in the API gateway or a middleware in front of the service, keyed by API key or user id, or by IP address for traffic that isn't signed in.
• Where the counts live: with more than one app server, in a shared store such as Redis, updated atomically (a Lua script, or INCR with EXPIRE for a fixed window). Otherwise two servers can both let the last request through.
• What the client gets back: 429 with a Retry-After header, and headers saying the limit and what is left of it.
• What happens when the store is down: fail open (let traffic through and protect the user's experience) or fail closed (protect the backend). Pick one and say why.
• Different limits per endpoint: a login or OTP endpoint needs a much tighter limit than a read.

The token bucket from the lab. The two window limiters on this page work the same way, with a counter and a list of timestamps in place of the tokens.

1class TokenBucket {2  private tokens: number;3  private last: number;4 5  constructor(private capacity: number, private windowMs: number, now: number) {6    this.tokens = capacity;7    this.last = now;8  }9 10  // Tokens refill continuously: a full bucket's worth every window.11  level(now: number) {12    const refill = ((now - this.last) * this.capacity) / this.windowMs;13    return Math.min(this.capacity, this.tokens + refill);14  }15 16  allow(now: number) {17    this.tokens = this.level(now);18    this.last = now;19    if (this.tokens < 1) return false;20    this.tokens -= 1;21    return true;22  }23}