Give traffic a refillable budget | DSA & Design, Connected

Picture

A bucket holds at most three tokens. Each request spends one. Tokens refill over time, allowing short bursts but limiting sustained traffic.

Predict

Do three independent capacity-ten buckets enforce one global burst limit of ten?

Walk through the small example

No, they may admit thirty. The scope of the stored bucket must match the promised limit.

Mental model and runnable Python model

Token bucket permits bursts up to capacity while limiting long-run refill rate. Fixed windows are simpler but can allow boundary bursts; sliding logs are precise but store more timestamps; sliding counters trade precision for memory. Choose the identity key, cost per operation, fairness, response behavior, and fail-open or fail-closed policy. Global enforcement needs atomic shared updates or a deliberate approximate allocation protocol. Use monotonic time locally; distributed clocks and ownership add complications.

What the function promises: TokenBucket is a single-threaded local model with nondecreasing caller-provided seconds. Floating-point token accounting is illustrative, not an exact distributed quota service.

class TokenBucket:
    def __init__(self, capacity, rate, now=0):
        if capacity <= 0 or rate < 0:
            raise ValueError("Invalid bucket")
        self.capacity, self.rate = capacity, rate
        self.tokens, self.last = capacity, now
    def allow(self, now, cost=1):
        if now < self.last or cost <= 0:
            raise ValueError("Invalid time or cost")
        self.tokens = min(self.capacity, self.tokens + (now-self.last)*self.rate)
        self.last = now
        if self.tokens < cost:
            return False
        self.tokens -= cost
        return True

bucket = TokenBucket(2, 1)
assert bucket.allow(0) and bucket.allow(0)
assert not bucket.allow(0)
assert bucket.allow(1)
assert bucket.tokens == 0

Work and storage: O(1) local bookkeeping per request, with one bucket per tracked identity. Cleanup and hot-key contention need separate planning.

When to recognize it: A separate full bucket on every server multiplies the effective allowance. Decide whether the limit is local, per-user global, or approximate.

Check before applying it: Rate-limit scope, atomicity, clock assumptions, and failure policy must match the promised budget.

Change one rule

The limiter’s shared store fails. Should every request be allowed?

See what changes

It depends on the operation’s risk. A public read may degrade differently from an expensive or sensitive write. State fail-open/fail-closed behavior and monitor the degraded mode.

Connect

Contain failure instead of multiplying it: Bound admission before retries and waiting work exhaust resources.

Estimate the bottleneck before adding servers: Use workload estimates to choose and test capacity and refill assumptions.