Token bucket or counter

Every user gets 100 requests a minute. How does the API decide, request by request, whether to let one through?

In 30 seconds

The problem: The API must reject a user's requests once they pass their limit, without slowing down everyone else.
Option A: fixed window: Count requests per user per minute and reject past the limit. One key and one INCR, but a burst at the edge of two windows can pass twice the limit.
Option B: token bucket: A bucket refills at a steady rate and each request takes a token. It allows short bursts and holds the average, but check and spend must be one atomic step.
Common choice: A token bucket in Redis, shared by every API server, with the check and spend as one atomic script.
In an interview: Use a token bucket per user in a shared store like Redis. Make check-and-spend one atomic step, give every key an expiry, and fail open when the limiter itself breaks.

Why it matters

Without a limit, one runaway script can use up capacity for everyone. Stripe says its request rate limiter is by far the most important of the four limiters it runs, and that it rejected millions of requests in a single month, often from scripts running in test mode.

The question behind the question is three choices: which algorithm decides, where the count lives (one server's memory or a shared store), and what happens when the limiter itself breaks. Each of the next traps is one of those choices going wrong.

Words you need

Rate limit: A cap on how many requests one user can make in a period. Past it, the API answers 429 Too Many Requests.
Fixed window: Count requests in each clock minute and reset at the edge. Simple, but a burst that straddles the edge can pass twice the limit.
Sliding window: Count the requests in the last 60 seconds, measured back from now, so there is no edge to exploit. Exact versions store every timestamp; cheaper ones blend two windows.
Token bucket: A bucket holds up to N tokens and refills at a steady rate. Each request takes one, and an empty bucket means reject. It allows short bursts and holds the average.
Atomic: Done as one step that nothing can interrupt. Another request sees it either not started or fully finished.
Fail open: When the limiter itself breaks, let traffic through instead of blocking it, so a limiter outage does not become an API outage.

Picture it

The limit is 10 requests a minute.

Option A: fixed window

Count requests in this minute
10 requests at 0:59 are allowed
The window resets at 1:00
10 more at 1:00 are allowed

20 requests in about one second, twice the limit. Simple, but the edges leak.

Option B: token bucket

The bucket holds up to 10 tokens
Each request takes one
Tokens refill steadily
An empty bucket means 429

Short bursts are fine and the average holds. This is what Stripe uses.

The options

Option A: fixed window counter

INCR count:{user}:{minute}

Good: One key and one INCR. Easy to build and easy to run.

Cost: The count resets at the window edge, so a user can send the whole limit at the end of one window and again at the start of the next.

Option B: token bucket

tokens = min(max, tokens + elapsed × rate); take 1

Good: Allows short bursts and holds the average rate. No edge to exploit.

Cost: Check and spend must be one atomic step, or two requests can spend the same token. That is the next trap.

The choice and its cost

Use a token bucket per user. The bucket lives in Redis, so every API server sees the same count, and the check and spend run as a Lua script inside Redis. Stripe describes this design.

Other options worth naming: a sliding window log is exact but stores one entry per request; a sliding window counter blends this window and the last and is close to exact with two counters; a leaky bucket smooths the output but adds queueing delay.

What it costs

More moving parts than one counter: a script to maintain, and Redis on the path of every request. That is why the limiter has to decide what to do when Redis is down.

Interviewers also listen for: what Stripe adds

Stripe runs four layers: the request rate limiter, a limiter on concurrent requests, and two load shedders that drop non-critical traffic when the fleet is busy. Its advice: fail open, return 429 for over-limit and 503 for shedding, dark-launch a limiter by logging what it would block, and keep a kill switch.

Check yourself

1Why can a fixed window let through twice the limit?Show answerHide
The count resets at the window edge. A user can use the whole limit at the end of one window and the whole limit again at the start of the next.
2Why must the count live in Redis and not in each server's memory?Show answerHide
A user's requests are spread over every API server. With a count per server, four servers allow four times the limit.
3If Redis is down, should the limiter block or allow?Show answerHide
Fail open and alert. A bug in the limiter should not take the whole API down.

The code

GitHub

fixed-window.ts

import type Redis from "ioredis";

// Option A: fixed window. One counter per user per minute.
export async function allow(redis: Redis, user: string, limit: number) {
  const key = `count:${user}:${Math.floor(Date.now() / 60_000)}`;
  const count = await redis.incr(key);
  // These are two calls. That gap is a trap of its own (Day 5).
  if (count === 1) await redis.expire(key, 60);
  return count <= limit;
}

Example code. The tested versions land in the repo with each trap.

Every trap in this world is runnable

The design notes are in the repo, and each trap that follows ships with the bug, the fix and a test that proves it.

Star the repo Design notes

Remember

A fixed window is easy and leaks at the edges. A token bucket holds the average, and its check and spend must be one atomic step.