Art of Codeartofcode
Lesson 3 of 14

25. Rate Limiting

1
The picture to keep in your head
2
25.1 Why limit?
3
25.2 What are the algorithms?
4
25.3 How do the algorithms compare?
5
25.4 How does distributed rate limiting with Redis work?
6
25.5 Where should the limiter go?
7
25.6 What do 429 and rate-limit headers look like?
8
25.7 How do you handle bots and abuse?
9
Memory card and where the analogy breaks
10
Practice: five levels
11
Interview questions
12
Solutions
13
Sources
14
Code lab
25. Rate Limiting

25.2 What are the algorithms?

5 min read+10 XP

At the club: Different clubs use different door systems: a bowl of passes, a queue that lets one in every few seconds, a clicker that resets on the hour, a guest book with entry times. Each handles a rush of guests differently.

In the system: Five algorithms come up again and again. All answer one question per request: allow or reject?

25.2.1 Token bucket

At the club: The bowl holds up to 100 passes and gets one new pass every 0.6 seconds. Each guest takes one. A group that arrives after a quiet hour can all walk in at once, as long as there are passes. Then they come in at the refill pace.

In the system:

  • A bucket holds up to capacity tokens (the burst size).
  • Tokens are added at a steady refill rate (100 per minute = one every 0.6 s), up to capacity.
  • Each request takes a token (or more, for expensive calls). No token: reject.

token bucket allows a burst up to its capacity, then the refill rate; leaky bucket drains at a fixed rate.

Figure: token bucket lets quiet clients burst; leaky bucket smooths everything into a steady stream.

You don't need a timer: store tokens and last refill time per client, and on each request add (now − last) × rate tokens, capped at capacity. In the chapter's code, a full bucket of 100 allows 100 of 150 instant requests; the next token arrives 0.6 s later.

  • Good: allows natural bursts (a page load firing 20 calls), simple, tiny state (two numbers per client), easy to give different costs to different calls. Very widely used; Stripe has written about using it for its API.
  • Watch: capacity and refill rate are two knobs; a big capacity means a big burst can hit you at once.

25.2.2 Leaky bucket

At the club: Guests join a queue at the door. The bouncer lets one in every half second, no matter how fast they arrive. If the queue is longer than 10 people, newcomers are turned away.

In the system: Requests enter a queue of limited size and leave at a fixed rate. If the queue is full, new requests are dropped. The output is perfectly smooth, whatever the input looks like. In the chapter's code, 12 instant requests into a queue of 10 draining 2 a second: the first goes immediately, the next after 0.5 s, then 1 s, and the last 2 are dropped.

  • Good: protects a downstream that can't take bursts at all (an old system, a partner with a strict rate, a payment gateway). NGINX's limit_req uses this method.
  • Costs: adds delay (requests wait in line), and a burst fills the queue so later requests are dropped even if the client was quiet before.

(Some texts describe the leaky bucket as a "meter" that rejects rather than queues; then it behaves much like a token bucket.)

25.2.3 Fixed window

At the club: A clicker counts guests, and resets to zero on the hour. Limit: 100 per hour.

In the system: Count requests per client per window (for example, per calendar minute): key ratelimit:key42:2026-10-08T10:15. If the count is over the limit, reject. The key expires after the window.

  • Good: very simple, one counter per client, cheap in Redis (INCR + EXPIRE).
  • The boundary problem: a client can send 100 requests at 10:15:59.9 and another 100 at 10:16:00.0. Each window sees only 100, so 200 pass in a fraction of a second. In the chapter's code, exactly that happens: 200 allowed.

100 requests just before the minute boundary and 100 just after all pass a fixed-window limit of 100.

Figure: two windows, each "within the limit", together let through double.

25.2.4 Sliding log

At the club: The bouncer writes down every guest's entry time. When someone arrives, they count entries in the last 60 minutes, from right now, not from the top of the hour.

In the system: Keep a log of timestamps for each client (in Redis, a sorted set). On each request, remove timestamps older than the window, count the rest, and allow if under the limit.

  • Good: exact: no boundary problem. In the chapter's code, the boundary burst gets exactly 100 through.
  • Costs: memory grows with the limit: one entry per request in the window. At 100 per minute for 1 million keys, that's 100 million timestamps, about 0.8 GB for the timestamps alone, versus about 16 MB for two counters per key.

25.2.5 Sliding window counter

At the club: The bouncer keeps just two clicker readings: last hour's total and this hour's so far. Halfway through this hour, they estimate the last 60 minutes as "half of last hour's total plus all of this hour's".

In the system: Keep counts for the current and previous fixed windows, and estimate the sliding window as:

estimate = previous × (fraction of the previous window still inside the last 60 s) + current

halfway through the minute, 80 from the previous window counts half: 40 + 30 = 70.

Figure: two counters and a weight give a close estimate of the true sliding window.

In the chapter's code: previous window 80, current 30, halfway through: 80 × 0.5 + 30 = 70, under 100, so allow. The boundary burst gets 100 through, like the exact log.

  • Good: nearly as accurate as the log, nearly as cheap as fixed windows (two counters per client). It assumes the previous window's requests were spread evenly; Cloudflare reported that only 0.003% of requests were wrongly allowed or limited this way in an analysis of 400 million requests.
  • Watch: an approximation; slight over- or under-counting when traffic is very uneven.

Memory code: "Passes refill, queues drip, clickers reset, logs remember, and two clickers estimate."