Rate Limiter Design

Token bucket, leaky bucket, fixed window, sliding log and sliding counter as code you can trace, plus how to make one limit hold across many servers.

Overview

A rate limiter decides, for each request, whether a client has used up its allowance for a period of time. It protects a service from overload and abuse, and it is how an API sells tiers. HTTP has a status code for the refusal, 429 Too Many Requests (RFC 6585), with an optional Retry-After header.

The interview has two halves. The first is the algorithm: what state you keep per client, how much memory that is, and how the limiter behaves at the edges of a window. The second is the deployment: a limit that must hold across many API servers needs a shared counter, and a shared counter needs an atomic update. This topic builds each algorithm as a few lines of Python with a trace you can check, then moves the state into Redis.

Five algorithms

Fixed window — One counter and a window number — Twice the limit around a window edge — Rough — Simple in-process limits
Sliding log — A timestamp per request — None beyond the limit — Exact — Low limits where memory is fine
Sliding counter — Two counters — Small overshoot near the edge — Close (Cloudflare reports 0.003% of 400 million requests wrongly allowed or blocked) — Cloudflare's rate limiting
Token bucket — Token count and last refill time — Up to the bucket size, then the refill rate — Exact for its own rule — Stripe (buckets in Redis), Envoy's local rate limit, AWS API Gateway
Leaky bucket — A queue or a level and a drain time — Absorbed into a queue, drained at a fixed rate — Exact — Nginx limit_req

Token bucket

A bucket holds up to capacity tokens and gains rate tokens per second. A request takes one token or is refused. Tokens are not added by a timer; the count is computed lazily from the time since the last request, which is why the state is only two numbers.

A trace with capacity 3 and 1 token per second. The first four calls come at t=0.

0.0 — 3 — 0 — 3 — allow — 2
0.0 — 2 — 0 — 2 — allow — 1
0.0 — 1 — 0 — 1 — allow — 0
0.0 — 0 — 0 — 0 — refuse — 0
0.5 — 0 — 0.5 — 0.5 — refuse — 0.5
1.0 — 0.5 — 0.5 — 1.0 — allow — 0
10.0 — 0 — 9 — 3 (capped) — allow — 2

The time is passed in rather than read from a clock so the trace is exact and the tests are deterministic; production code passes time.monotonic().

Windows: fixed, log, counter

The three window algorithms answer 'how many requests in the last W seconds' with different amounts of state. The trace uses a limit of 3 per 60 seconds and a client that sends three requests at t=59 and more at t=61.

Fixed window — allow, allow, allow — allow (and two more) — t=61 starts a new window: 6 requests in 2 seconds
Sliding log — allow, allow, allow — refuse — Three timestamps in the last 60 s
Sliding counter — allow, allow, allow — allow, then refuse — Estimate 3 × 59/60 = 2.95 is under 3, so one slips through; the next sees 3.95

Leaky bucket

A leaky bucket is the token bucket seen from the other side: requests pour in, and they drain at a fixed rate. Requests that arrive faster than the drain wait in the bucket (a queue) up to its size, and overflow is rejected. Nginx's limit_req works this way: excess requests are delayed so that they are processed at the configured rate, up to burst of them; beyond that they are rejected, and nodelay rejects instead of delaying. Its default rejection status is 503, which you usually change to 429.

Output shape — Bursts up to the capacity pass at once — Smooth, one per interval
Waiting — None: allow or refuse now — Requests can queue, adding latency
State — Two numbers — A queue, or a level plus a time
Fits — User-facing APIs (bursts are normal) — Protecting a downstream that must see a steady rate

The interface

Whatever the algorithm, the caller sees one method and one decision. Return enough for the client to behave: whether it may proceed, how many requests remain, and when to retry.

allowed — Status 200 or 429 — 429 Too Many Requests
retry_after — Retry-After header (RFC 6585 allows it on 429) — Retry-After: 2
remaining — An informational header of your choosing — X-RateLimit-Remaining: 0

What you will be able to do

Implement token bucket, fixed window, sliding log and sliding counter, and trace each on a tiny input.
Say what state each keeps per client and how that scales to millions of clients.
Explain the window-edge burst and which algorithms fix it.
Move the state into Redis with an atomic script, and say what to do when Redis is slow or down.
Return a decision the client can act on: 429 plus Retry-After.

Interview questions

Compare token bucket, leaky bucket, fixed window and sliding window rate limiting.
Implement a distributed rate limiter using Redis.
How do you make an in-process limiter safe for many threads and many clients?
How do you handle rate limiting across multiple data centers?
What should the API return when a client is limited?