TL;DR: Capacity limits the burst; refill rate limits sustained use. Refill lazily from a monotonic clock and hold one lock across refill and deduction, then report how long a rejected request would need to wait if no competing request consumes the next tokens.
How to approach it
Explain capacity and rate with one burst example before writing the code. Keep elapsed-time accounting and token deduction in the same critical section. Use an injected clock to test refill without sleeping, then test invalid costs, a zero refill rate and concurrent callers.
A strong answer
A token bucket is a counter that refills at a fixed rate up to a cap; each request spends tokens, and a request that finds too few is rejected or told when to retry. A limiter with capacity 100 and rate 100 tokens per second can admit 100 one-token requests at once after an idle period. That is the configured burst allowance. Reducing capacity to 10 changes how much work a client can submit together; it does not change the long-run refill rate. Decide whether the backend can absorb the combined bursts from all tenants before choosing those values.
The refill rate controls sustained use. Over a window of T seconds, admitted work costs at most the starting tokens plus rate × T. Capacity caps how much unused allowance can accumulate and be spent in a burst.
capacity = 10 tokens; rate = 2 tokens/s
After a long idle period: 10 tokens are available immediately.
Over the next 60 seconds: at most 10 + 2 × 60 = 130 tokens.
Choose the total sustained allowance from backend capacity after reserving headroom, then allocate it across tenants. Capacity controls the burst each tenant can submit. If every tenant can burst at once, check their combined allowance against the backend's queue and latency budget.
The implementation:
import threading, time, math
class TokenBucket:
"""Thread-safe token bucket. capacity = burst size, rate = tokens per second."""
def __init__(self, capacity: float, rate: float, now=None):
self.capacity, self.rate = float(capacity), float(rate)
if not math.isfinite(self.capacity) or self.capacity <= 0 or not math.isfinite(self.rate) or self.rate < 0:
raise ValueError("capacity must be positive; rate must be nonnegative and finite")
self._tokens = float(capacity) # start full
self._clock = now or time.monotonic # injectable for tests
self._last = self._clock()
self._lock = threading.Lock()
def _refill(self): # caller holds the lock
now = self._clock()
elapsed = now - self._last
if elapsed > 0:
self._tokens = min(self.capacity, self._tokens + elapsed * self.rate)
self._last = now
def _check_cost(self, n):
if not math.isfinite(n) or n <= 0 or n > self.capacity:
raise ValueError("cost must be finite, positive and no greater than capacity")
def take(self, n: float = 1.0) -> bool:
self._check_cost(n)
with self._lock: # refill and deduct must be atomic together
self._refill()
if self._tokens >= n:
self._tokens -= n
return True
return False
def retry_after(self, n: float = 1.0) -> float:
"""Wait estimate without competing consumption; infinity if refill is disabled."""
self._check_cost(n)
with self._lock:
self._refill()
if self._tokens >= n:
return 0.0
return (n - self._tokens) / self.rate if self.rate else math.inf
Running it, with an injected clock so the test is deterministic:
capacity 10, rate 2/s, clock at t = 0
burst at t=0: took 10 of 15 attempts (capacity 10)
retry_after now: 0.50s (rate 2/s, so one token in half a second)
advance the clock to t = 3.0
after 3 s at 2/s: took 6 more (expected 6)
concurrency check, 8 threads racing on a bucket of 1,000 tokens with rate 0
8 threads x 500 attempts = 4,000 attempts against 1,000 tokens
issued 1,000, which is exactly the bucket and not one more
Lazy refill avoids a background task for every bucket. Each request calculates how much allowance elapsed time has earned, caps it at capacity and deducts its cost. An idle bucket needs no work. A periodic sweeper is possible, but its timing becomes another part of the limiter's behavior.
Use a monotonic clock for elapsed time. Wall time can jump backward or forward, freezing refill or granting tokens prematurely. A monotonic clock does not move backward with wall-clock updates; the exact clock source and rate-adjustment behavior are platform-dependent.
Hold the lock across both refill and deduction. If those are separate critical sections, two threads can each observe enough allowance and both spend it. Measure contention at the intended request rate. Independent tenants can use independent buckets; splitting one tenant across buckets changes where it can spend its allowance.
Rate-Limiting Algorithms compares this against the alternatives, notably the leaky bucket and sliding-window counters, and Rate Limiting for an LLM API covers what changes when the unit is tokens rather than requests.
The tests:
def test_burst_then_sustained():
t = [0.0]
b = TokenBucket(capacity=10, rate=2, now=lambda: t[0])
assert sum(b.take() for _ in range(15)) == 10 # burst limited by capacity
t[0] = 3.0
assert sum(b.take() for _ in range(10)) == 6 # 3 s x 2/s
def test_never_exceeds_capacity():
t = [0.0]
b = TokenBucket(capacity=10, rate=2, now=lambda: t[0])
t[0] = 10_000.0 # idle for a long time
assert sum(b.take() for _ in range(20)) == 10 # capped at capacity, not 20,000
def test_retry_after():
t = [0.0]
b = TokenBucket(capacity=1, rate=2, now=lambda: t[0])
assert b.take() is True
assert abs(b.retry_after() - 0.5) < 1e-9
def test_concurrent_never_over_issues():
b = TokenBucket(capacity=1000, rate=0, now=lambda: 0.0)
counts = []
def w():
counts.append(sum(b.take() for _ in range(500)))
ts = [threading.Thread(target=w) for _ in range(8)]
[t.start() for t in ts]; [t.join() for t in ts]
assert sum(counts) == 1000
Retry, Backoff and Idempotency explains how clients can use the wait estimate. It is a snapshot, not a reservation: another caller can consume the next token first. The concurrency test disables refill so total admissions cannot exceed the initial 1,000 tokens. Passing it is useful evidence, but a race is not guaranteed to appear in any particular test run; the lock's scope is part of the correctness argument.
A local bucket controls one process. If each server grants the full tenant allowance independently, routing across servers can multiply the effective limit. A shared store can coordinate deductions but adds a request-path dependency. Allocating smaller allowances to local buckets avoids that dependency on each request, at the cost of unused allowance and reconciliation complexity. Choose and test the fleet-wide policy separately from this class.
What interviewers probe next
- "How would you handle variable costs per request?"
take(n)already does: an expensive request takes more tokens. That is exactly how a token-based API limiter charges by prompt size. - "What if a request needs more tokens than the capacity?" It can never succeed, so validate at configuration time and reject the request with a clear error rather than looping forever.
- "Why start the bucket full?" A new client should not be penalized for having no history. Starting empty is defensible for abuse prevention and should be a deliberate choice.
- "How do you shard this at high rates?" Partition tenants across shards, each with its own bucket, or split one tenant's rate across N buckets and route by a hash, accepting the granularity loss.
Common mistakes
- Creating one refill thread per bucket when elapsed-time accounting would avoid that work.
- Wall-clock time, which grants a free burst or freezes the bucket on a clock adjustment.
- Refilling and deducting under separate lock acquisitions, which over-issues under concurrency.
- Rejecting without a retry-after value, so clients guess and retry storms follow.
Key takeaways
- Rate is sustained throughput, capacity is burst; an idle client with capacity 10 and rate 2 does 130 requests in a minute rather than 120.
- Refill lazily from elapsed time, never from a background thread.
- Use a monotonic clock; wall time either freezes the bucket or grants free tokens on adjustment.
- Hold one lock across refill and deduction, and test it with threads racing a zero-rate bucket where the total must equal the capacity exactly.