Rate limiting a public API without punishing honest bursts

This is the demo fixture for the micro-blog format. The problem and solution are real; there is no published audio episode yet.

The use case

You run a public payments API. One afternoon a single integrator ships a bug: every failed webhook is retried immediately, in a tight loop, from forty worker processes. Within a minute they are sending 3,000 requests per second. Your database connection pool fills up, p99 latency for everyone goes from 80 ms to 6 s, and the on-call phone rings.

The fix is not "block that customer". The fix is a rule every caller understands: you get N requests per minute; go past it and we say no, quickly and cheaply, before the request touches anything expensive.

That rule is a rate limiter. The interesting part is choosing the algorithm and making it work when your API runs on twenty servers behind a load balancer.

Requirements

1. Per API key: 600 requests per minute on average.
2. Honest bursts are fine. A dashboard that loads 30 requests at once should not be punished; a client that sends 30 per second forever should be.
3. The decision must cost microseconds, not a database query.
4. All servers must agree. A client should not get 20× its quota by spraying requests across 20 machines.
5. Rejected requests get a 429 Too Many Requests with a Retry-After header so well-behaved clients back off instead of hammering.

Candidate algorithms

Token bucket wins here because requirement 2 is literally its knob: the bucket capacity is the burst you tolerate, and the refill rate is the long-term average.

How a token bucket works

Every API key owns a bucket that holds at most C tokens. A refill process adds r tokens per second, but never above C. Each request must take one token. Empty bucket, rejected request.

For our numbers: r = 10 tokens per second (600 per minute) and C = 30 lets a dashboard fire 30 requests instantly, then settle to 10 per second.

The trick that makes it cheap: you do not run a refill timer. You store only tokens and lastRefill, and compute the refill lazily when a request arrives.

type Bucket = { tokens: number; lastRefill: number };
 
const buckets = new Map<string, Bucket>();
 
export function allow(
  key: string,
  now = Date.now(),
  capacity = 30,
  refillPerSec = 10,
): { ok: boolean; retryAfterMs: number } {
  const bucket = buckets.get(key) ?? { tokens: capacity, lastRefill: now };
 
  const elapsedSec = (now - bucket.lastRefill) / 1000;
  bucket.tokens = Math.min(capacity, bucket.tokens + elapsedSec * refillPerSec);
  bucket.lastRefill = now;
 
  if (bucket.tokens >= 1) {
    bucket.tokens -= 1;
    buckets.set(key, bucket);
    return { ok: true, retryAfterMs: 0 };
  }
 
  buckets.set(key, bucket);
  const deficit = 1 - bucket.tokens;
  return {
    ok: false,
    retryAfterMs: Math.ceil((deficit / refillPerSec) * 1000),
  };
}

Walk through the retry storm with this code. The first 30 requests from the buggy integrator drain the bucket in about 10 ms. From then on only 10 per second get through, and the other 2,990 per second are rejected in a few hundred nanoseconds each, before touching the database. Everyone else's p99 goes back to 80 ms.

Making twenty servers agree

The in-memory Map above breaks requirement 4: each server has its own bucket, so the effective limit is 20 × 600. You need one shared bucket per key, and the read-modify-write must be atomic or two servers will both see one token and both spend it.

Redis is the standard answer. Store tokens and lastRefill in a hash, and run the whole check as a single Lua script so it executes atomically on the Redis server:

-- KEYS[1] = bucket key, ARGV = capacity, refill_per_sec, now_ms
local capacity  = tonumber(ARGV[1])
local refill    = tonumber(ARGV[2])
local now       = tonumber(ARGV[3])
 
local state  = redis.call("HMGET", KEYS[1], "tokens", "last")
local tokens = tonumber(state[1]) or capacity
local last   = tonumber(state[2]) or now
 
tokens = math.min(capacity, tokens + (now - last) / 1000 * refill)
 
local allowed = 0
if tokens >= 1 then
  tokens = tokens - 1
  allowed = 1
end
 
redis.call("HSET", KEYS[1], "tokens", tokens, "last", now)
-- expire idle buckets so memory is bounded by *active* keys
redis.call("PEXPIRE", KEYS[1], math.ceil(capacity / refill * 1000) + 1000)
 
return { allowed, tokens }

Two details worth noticing:

• now comes from the caller, not from Redis. Lua scripts must be deterministic across replicas, and passing the clock in also lets your tests freeze time.
• PEXPIRE bounds memory. A bucket that has been idle long enough to fully refill is indistinguishable from a fresh one, so deleting it is free.

One round trip to Redis per request costs roughly 0.2 to 0.5 ms inside a data centre, which satisfies requirement 3 for an API whose real work is a payment.

Telling the client what to do

A rejection is only useful if the client can act on it:

HTTP/1.1 429 Too Many Requests
Retry-After: 1
RateLimit-Limit: 600
RateLimit-Remaining: 0
RateLimit-Reset: 1

Retry-After is the retryAfterMs we already computed, rounded up to seconds. The RateLimit-* headers follow the IETF draft that most API gateways now emit, and they let a well-written SDK slow down before it gets rejected.

What we did not do, and why

• No global limit across all keys. That is a different problem (capacity protection) and belongs in the load balancer.
• No queueing of rejected requests. Holding a request in memory while waiting for a token is exactly the resource exhaustion we set out to prevent.
• No fairness between endpoints. If /reports is 100× more expensive than /ping, give it its own bucket with its own numbers rather than weighting tokens. Weighted tokens are hard to explain to integrators.

Recap

Token bucket gives you two honest numbers to publish: burst size and sustained rate. Lazy refill keeps the state to two fields. A Redis Lua script makes those two fields atomic across every server. And a 429 with Retry-After turns a rejection into an instruction.