Rate Limiting

Rate limiting caps how many requests a client may make in a window of time, so one user — buggy, abusive, or just popular — can't overwhelm a shared service. When a client exceeds its limit the server throttles it, usually replying HTTP 429 Too Many Requests. The art is choosing an algorithm that allows normal bursts while still enforcing a steady long-run rate.

Token bucket — the workhorse

The token bucket holds up to N tokens (its capacity) and refills at a steady rate of R tokens per second. Each request must spend one token; if the bucket is empty, the request is rejected. A full bucket lets a short burst of up to N requests through instantly, after which the client is smoothed down to the refill rate R.

1. 1Bucket: capacity 10, refill 2 tokens/sec, starts full at 10 tokens.
2. 2t=0s — a burst of 8 requests arrives → 8 tokens spent, 2 left. All allowed (the burst is absorbed).
3. 3t=0s — 3 more requests arrive immediately → only 2 tokens remain: 2 allowed, 1 rejected (429). Bucket now 0.
4. 4t=1s — 1 second passes → refill adds 2 tokens → bucket = 2.
5. 5t=1s — 2 requests arrive → both allowed, bucket back to 0. Long-run throughput settles to the 2/sec refill rate.

function allow(bucket, now, capacity, rate) {
  const elapsed = now - bucket.last;
  bucket.tokens = Math.min(capacity, bucket.tokens + elapsed * rate);
  bucket.last = now;
  if (bucket.tokens >= 1) {
    bucket.tokens -= 1;
    return true;   // allowed
  }
  return false;    // reject -> HTTP 429
}

Leaky bucket

The leaky bucket is the mirror image: requests pour into a queue (the bucket) and leak out at a fixed rate, like water through a hole. It enforces a perfectly smooth *output* rate regardless of how bursty the input is — great for protecting a downstream that needs constant pacing. The trade-off: it does not allow bursts the way a token bucket does, and if the queue overflows, requests are dropped.

Sliding window: log vs counter

Window methods count requests over a rolling time span. The sliding-window log stores a timestamp for every request and, on each new one, counts how many fall inside the last 60 seconds — exact, but the memory grows with request volume. The sliding-window counter approximates it cheaply: it keeps per-bucket counts (e.g. per minute) and blends the current and previous bucket by how far into the window you are — near-exact, with O(1) memory. This also avoids the fixed-window flaw where a client can fire a full quota at 0:59 and another at 1:00, sending double the limit across the boundary.