Rate Limiting

In plain words

A rate limiter decides, for every request, whether this caller has done too much recently — and says "not now" if so. It is the bouncer with a clicker: so many people per minute, and the rest wait outside. It protects your system from abuse, from a buggy client stuck in a loop, and from itself.

The algorithms, judged by what they do to a burst

Under steady traffic below the limit every algorithm behaves the same. They differ in how they treat a burst — a quiet client that suddenly sends a lot.

Implementing a token bucket

The trick that makes it cheap: do not run a timer that adds tokens. Work out how many tokens would have arrived since the last request, when the next request comes in.

import time

class TokenBucket:
    def __init__(self, capacity: int, refill_per_sec: float):
        self.capacity = capacity          # burst size
        self.refill = refill_per_sec      # steady rate
        self.tokens = capacity
        self.updated = time.monotonic()

    def allow(self) -> bool:
        now = time.monotonic()
        # tokens that arrived while we were not looking
        self.tokens = min(self.capacity, self.tokens + (now - self.updated) * self.refill)
        self.updated = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

Two numbers per key (tokens, updated), one small calculation, no background work. Burst size and refill rate are separate dials: "up to 20 at once, 100 a minute sustained".

Making it correct across many servers

Ten API servers each running the bucket above, each allowing 100 a minute, allow 1,000 a minute in total. The count has to be shared.

The check must be atomic — done in one indivisible step. GET the count, decide, SET it back is a race: two requests read 99 at the same instant and both pass. Use a single command, or a small script Redis runs as one unit.

-- KEYS[1] = ratelimit:{api_key}:{minute}   ARGV[1] = limit
local n = redis.call('INCR', KEYS[1])        -- count and read back in one step
if n == 1 then
  redis.call('EXPIRE', KEYS[1], 120)         -- keep this minute and the previous
end
if n > tonumber(ARGV[1]) then return 0 end   -- over: reject
return 1

What to send back

1. Reject with 429 and say when to come back

   429 Too Many Requests with a Retry-After header. Add a little randomness to the value, or every rejected client retries in the same second.

2. Tell clients how much room they have — on every response

   X-RateLimit-Limit: 100, X-RateLimit-Remaining: 37, X-RateLimit-Reset: 1726300800. A client that can see the number slows down before it is rejected. This, more than the algorithm, is what produces well-behaved clients.

3. Decide what happens when the counter store is down

   Fail open — let traffic through and page someone — unless the limit is about money or correctness (a metered API), in which case fail closed. A limiter that takes the service down to protect it has failed at its job.

HTTP/1.1 429 Too Many Requests
Retry-After: 23
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1726300823

Where it goes wrong

• Keying on IP. Everyone behind one office or mobile carrier address (NAT) shares a bucket; an attacker with many addresses gets many buckets. Key on the API key or user; IP is a last resort for anonymous traffic.
• Hot keys. One huge customer's counter is one Redis key on one shard. Split their key by server (key:{server}) and sum, or give them a bucket per region.
• Many limits per key. 100/min, 5,000/hour and 50,000/day is three counters. Send the three commands in one batch (a pipeline) so it is still one round trip.
• Retry storms. Every rejected client retrying at exactly Retry-After is a synchronised wave — see retries and backoff.

Take this with you

• The one idea: judge a limiter by what it does to a burst. Steady traffic under the limit looks the same under every algorithm.
• In an interview, pick token bucket, explain the fixed-window edge case, and say where the counter lives across many servers.
• At work, send the limit headers on every response, and know whether your limiter fails open or closed when its store is down.