Rate Limiting Algorithms: Token Bucket, Leaky Bucket & More

🔵 Fundamentals · Fresher-friendly → 🔴 goes deep

Every public API needs a bouncer. Without one, a single buggy client — or a malicious one — can hammer your server with thousands of requests a second, run up your bill, and knock the service over for everyone else. Rate limiting is that bouncer: it caps how many requests a user can make in a given window. Simple idea, but the algorithm you choose has real trade-offs, and "which rate-limiting algorithm would you use?" is a classic interview question. Let's build all of them up from scratch.

Why rate limit at all?

Three reasons, and naming them shows you understand the why:

• Protect the service: stop one client (or a traffic spike) from exhausting CPU, memory, or database connections and taking everyone down.
• Fairness: make sure no single user hogs shared capacity — everyone gets a fair slice.
• Cost & abuse control: block brute-force login attempts, scraping, and spam, and keep your cloud/API bill predictable.

When a client exceeds the limit, you return 429 Too Many Requests, ideally with a Retry-After header telling them how long to wait. That's the polite, standard way to say "slow down."

Algorithm 1: Fixed window counter

The simplest approach. Divide time into fixed windows (say, one minute) and count requests per window. Limit is 100/min? Keep a counter; each request increments it; over 100, reject; at the top of the next minute, reset to zero.

count["user42:12:03"]++         // key = user + minute
if count > 100:  reject (429)
// at 12:04 a brand-new key starts at 0

Loved for: it's trivial to build and needs almost no memory (one number per window). The flaw: a burst at the boundary. A user can send 100 requests at 12:03:59 and another 100 at 12:04:01 — 200 requests in two seconds, because they straddle two windows. So the limit isn't really enforced across the seam.

Algorithm 2: Sliding window log

🟠 Fix the boundary problem by tracking the timestamp of every request in a log, and counting only those within the last 60 seconds from now — a window that slides continuously instead of snapping to clock minutes.

Pro: perfectly accurate — no boundary bursts. Con: expensive. You store a timestamp for every single request, so a heavy user costs a lot of memory, and you're constantly trimming old entries. Accurate but doesn't scale cheaply.

Algorithm 3: Sliding window counter

🟠 The practical compromise most real systems use. Keep per-window counters (cheap, like fixed window) but smooth the boundary by weighting the previous window. Roughly: count = current_window + previous_window × (overlap fraction).

If you're 25% into the current minute, you count all of this minute's requests plus 75% of last minute's. This approximates a true sliding window with almost the memory of fixed window — no per-request log. It's the sweet spot of accuracy vs cost, which is why it's a strong default answer in interviews.

Algorithm 4: Token bucket (the favourite)

🟠 The most popular algorithm in practice — and the one to reach for in an interview. Picture a bucket that holds up to N tokens. Tokens are added at a steady refill rate (say 10/second). Each request must take one token; if the bucket has one, the request proceeds; if it's empty, reject.

The beauty: it allows bursts. If a user was quiet, tokens accumulate (up to the cap N), so they can briefly send a burst — which feels natural — while the long-run average is still capped at the refill rate. And it costs just two numbers per user (token count + last refill time). Steady average, friendly bursts, tiny memory — that's why token bucket wins.

Algorithm 5: Leaky bucket

🔴 A close cousin with the opposite personality. Requests pour into a queue (the bucket) and are processed at a fixed, constant rate — they "leak" out steadily. If the bucket overflows, new requests are dropped.

The difference from token bucket: leaky bucket smooths output to a perfectly even rate (no bursts pass through), whereas token bucket allows bursts. Use leaky bucket when a downstream system needs a steady, predictable flow (e.g. protecting a fragile legacy service); use token bucket when short bursts are fine and you want responsiveness.

Side by side

The senior gotcha: distributed rate limiting

🔴 Here's where interviews get real. Your limit is "100/min per user," but you run many app servers behind a load balancer. If each server keeps its own in-memory counter, a user hitting 10 servers gets 10× the limit. The counter must be shared.

The standard answer: keep the counters in a fast central store — usually Redis — so every server reads and writes the same count. To avoid race conditions when many servers update the same key at once, do the check-and-increment atomically (a Redis INCR with an expiry, or a small Lua script). Mentioning "shared counter in Redis, updated atomically" is exactly the depth that separates a senior answer from a junior one.

One more nuance: put the limiter at the edge — in an API gateway or reverse proxy — so bad traffic is rejected before it ever reaches your application servers, saving them the work entirely.

The interview-ready summary

If asked "how would you rate limit an API?", a crisp answer: "I'd use a token bucket per user — it caps the average rate but allows small bursts, and needs just two numbers per user. Over-limit requests get a 429 with Retry-After. Since we run multiple servers, I'd store the buckets in Redis and update them atomically so the limit is global, and enforce it at the API gateway so abusive traffic never reaches the app." That single paragraph hits the algorithm, the response, the distributed problem, and placement — everything they're listening for.

What to read next

• API Design: REST, gRPC & GraphQL — the APIs you're protecting
• Caching Strategies — Redis, the store behind distributed limiting
• Load Balancing — why counters must be shared across servers
• ← The complete System Design guide (hub)

← API design · Distributed transactions & saga →