Token Bucket Rate Limiting.

🪣The mental model

Picture a bucket that holds up to N tokens. It refills at a steady rate (r tokens/sec). Every request must take 1 token. No token? Rejected (or queued).

• capacity N → how big a burst you allow
• refill rate r → your steady-state limit

Decoupling these two is the whole trick.

🛠️Build it (no background timer needed — lazy refill)

class TokenBucket:
    def __init__(self, capacity, refill_per_sec):
        self.capacity = capacity
        self.rate = refill_per_sec
        self.tokens = capacity
        self.last = time.monotonic()

    def allow(self):
        now = time.monotonic()
        # add tokens for the time that elapsed, cap at capacity
        self.tokens = min(self.capacity,
                          self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

⏱️Why "lazy refill" is the key line

You don't run a loop adding tokens every second. You compute how many would have accrued since the last request: elapsed × rate. One subtraction, no scheduler, O(1) memory per client. This is exactly how you'd store it in Redis (a value + timestamp per user key).

🎛️Tuning it in practice

• capacity=10, rate=1/s → normal users cruise; someone can spike 10 at once, then throttles to 1/s.
• Want NO bursts? Set capacity == rate window. Want generous bursts? Raise capacity, keep rate low.
• Return HTTP 429 + a Retry-After header = (1 - tokens) / rate seconds, so clients back off politely.

🆚vs its cousins

• Fixed window (the naive counter) → the boundary-burst bug above.
• Sliding window log → accurate but stores every timestamp (memory heavy).
• Leaky bucket → smooths output to a constant drip, but forbids bursts entirely.

Token bucket is the sweet spot most APIs (Stripe, AWS) actually ship.

⚠️Gotchas intermediate folks hit

• Use a MONOTONIC clock, not wall-clock — NTP adjustments can jump time backward and hand out free tokens.
• In a multi-server fleet, an in-memory bucket per box means your real limit is N × servers. Centralize state (Redis) or the limit is a lie.
• Refill uses fractional tokens — don't round tokens to an int between requests or you leak capacity.

🎯Your exercise

Set capacity=5, rate=1/s. A client sends 8 requests instantly, then waits 3 seconds, then sends 4 more. Exactly how many of the 12 get through — and why? Trace the token count after each phase.