Rate limiting algorithms

What it is

A rate limiter restricts how many requests a client can make in a time window, protecting the system behind it from abuse, retry storms, and cost overruns. When a client exceeds the limit it gets an HTTP 429 with a Retry-After header — the limiter's job is to shed load cheaply at the edge before it becomes expensive load in the core.

It shows up in interviews two ways: as a standalone question (a top-five classic) and as a component you're expected to sprinkle into any public API design. Either way the scoring is the same — can you name the algorithms, articulate the burst-vs-smoothness trade, and handle the distributed case where counters live across many gateway nodes.

Say this out loud

I'd put a token bucket per API key at the gateway, counters in Redis with atomic operations, and I'd fail open if Redis dies — a broken rate limiter shouldn't take the product down with it.

The picture

tokens drip in at the refill rate; each request spends one. the burst empties the bucket and the last request bounces — that × is a 429, not an error.

The variants and when to pick each

Token bucket — the default, because bursts are normal

A bucket holds up to B tokens and refills at r tokens per second; each request spends one, and an empty bucket means 429. The average rate is capped at r, but a client that's been quiet can burst up to B at once — which matches real traffic, where a page load fires ten calls together. State is two numbers per client (token count, last refill time), refilled lazily on each request.

This is what AWS API throttling and Stripe run, and it's my default answer. The two parameters map directly to product language: r is the sustained rate you sell, B is the burst you forgive.

Trade-offThe burst is a feature until it isn't — B requests can land on a fragile downstream in one instant, so a token bucket protects your average capacity, not your instantaneous peak.

Leaky bucket — when the downstream can't take a burst

Requests enter a FIFO queue that drains at a constant rate; overflow is dropped. The output is perfectly smooth regardless of input shape, which is exactly what you want when feeding a fragile third party — a payment provider, a partner API with its own strict limits.

The distinction from token bucket is the one interviewers probe: token bucket shapes the average and permits bursts; leaky bucket shapes the instantaneous rate and forbids them.

Trade-offSmoothness is bought with latency — queued requests wait, and during a spike a request can sit behind hundreds of others or overflow entirely. Wrong choice for interactive traffic, right choice for traffic shaping.

Fixed window — cheap, and broken exactly at the boundary

One counter per client per window: increment on each request, reject past the limit, reset when the window rolls. In Redis it's INCR plus EXPIRE — the cheapest possible implementation and often good enough.

The flaw to name unprompted: the boundary problem. With 100 requests per minute allowed, a client can send 100 at 0:59 and 100 more at 1:01 — 200 requests in two seconds, all technically within limits. If you present fixed window without saying this, the interviewer says it for you, and that's worse.

Trade-offYou get O(1) memory and trivial code in exchange for the limit being wrong by up to 2× at every window edge — acceptable for coarse abuse protection, not for a limit you contractually sell.

Sliding window: log for accuracy, counter for practicality

The sliding window log stores a timestamp per request and counts those within the trailing window — perfectly accurate, but memory grows with request rate: 8 bytes per request versus 16 bytes per client for a token bucket, which at scale is the whole decision.

The sliding window counter blends two fixed windows instead: previous window's count weighted by its overlap with the trailing window, plus the current count. It assumes requests were evenly spread across the previous window — approximate, but smooth, tiny, and it kills the boundary problem. This is Cloudflare's published approach and, alongside token bucket, the best interview default.

Trade-offThe counter's estimate is wrong when traffic within the previous window was lumpy — you trade perfect accuracy for constant memory, and for rate limiting (unlike billing) that's almost always the right trade.

Numbers worth memorising

Canonical config to quote	100 req/min per user; bucket size = limit, refill 100/60 tokens per second
Redis limiter overhead	~1 ms added to each request (same-DC round trip)
Memory: token bucket	~16 B per client (two numbers)
Memory: sliding window log	~8 B × every request in the window — grows with traffic
Real-world anchors	GitHub API 5,000 req/hr authenticated · Twitter v2 ~450 req/15 min

Where the interviewer pushes

First push: "two requests hit two limiter instances at the same instant — how do you not double-count, or under-count?" The strong answer names the spectrum. Centralised counters in Redis with atomic ops (INCR, or a Lua script when check-and-decrement must be one step) are accurate and add ~1 ms; per-node local counters with periodic sync are faster and slightly leaky. Then commit: for API quotas I take the Redis hop, because a limit you sell should be a limit you enforce — and for pure DoS protection I'd accept approximate local counting.

Second push: "the limiter's Redis is down — do you block everyone or let everyone in?" Fail open, and say why: the rate limiter exists to protect availability, so a limiter that fails closed converts its own outage into a full product outage — strictly worse than a few minutes of unmetered traffic. Fail open, alert loudly, and optionally degrade to coarse in-process limits as a backstop. The exception worth naming: if the limiter is guarding spend (an expensive paid API) or fraud, failing closed can be the cheaper failure — the answer is per-limit, not global.