Implement a thread-safe token-bucket rate limiter for concurrent API and tool-calling traffic.

TL;DR: Track tokens and a last-refill timestamp. On each request, lazily add elapsed * fill_rate tokens (capped at capacity) before checking, so there is no background thread burning CPU. Guard the state with a lock for thread safety. This handles bursts up to capacity while enforcing a steady long-run rate.

How to approach it. Confirm the contract: tokens per second, burst capacity, and whether consume blocks or returns immediately (return a boolean is the common ask). State the key design choice up front: lazy refill computed from elapsed time, not a timer thread. Then write it and reason about thread safety and monotonic time.

A strong answer. A token bucket fills at a fixed rate up to a capacity; each request spends tokens. Computing refill lazily from a timestamp avoids a polling thread entirely.

import time, threading

class TokenBucket:
    def __init__(self, capacity: float, fill_rate: float):
        self.capacity = float(capacity)      # max burst
        self.fill_rate = float(fill_rate)    # tokens added per second
        self._tokens = float(capacity)
        self._last = time.monotonic()        # monotonic: immune to clock changes
        self._lock = threading.Lock()

    def consume(self, tokens: float = 1.0) -> bool:
        with self._lock:
            now = time.monotonic()
            self._tokens = min(
                self.capacity,
                self._tokens + (now - self._last) * self.fill_rate,
            )
            self._last = now
            if self._tokens >= tokens:
                self._tokens -= tokens
                return True
            return False

Three deliberate choices worth narrating: time.monotonic() (wall-clock time.time() can jump backward on NTP sync and corrupt the refill), refill-before-check (so a request never fails just because the timer had not fired), and the cap at capacity (the bucket cannot accrue infinite credit while idle). Token bucket allows short bursts up to capacity, which is usually what you want for bursty API or agent tool-calling traffic; a leaky bucket or fixed-window would smooth differently.

Key takeaways

• Lazy refill from a timestamp replaces a polling thread: no idle CPU, no timer race.
• time.monotonic() is non-negotiable; wall-clock time can jump and corrupt refill math.
• Refill before the check, and cap at capacity, or you leak bursts at the edges.
• Scale by sharding per-key buckets locally, or a Redis Lua script for atomic distributed limiting.

What interviewers probe next.

• "Make it fair across thousands of concurrent agents." Move to per-key buckets in a sharded map; for distributed limiting, push state to Redis with an atomic Lua script so the check-and-decrement is race-free across nodes.
• "Token bucket vs sliding-window vs leaky bucket?" Token bucket permits bursts and is cheap; sliding-window log is exact but memory-heavy; leaky bucket enforces a strictly smooth output rate. Pick by whether bursts are acceptable.
• "What if consume should block until tokens are available?" Compute the wait as (needed - tokens) / fill_rate and sleep, or use a condition variable; watch for thundering-herd wakeups.
• "Lock contention at high QPS?" The critical section is tiny; if it still bottlenecks, shard by key so locks are independent.

Common mistakes.

• A background thread that refills on a timer: wastes CPU and adds a race with consume.
• Using time.time() instead of time.monotonic(), so a clock adjustment breaks the limiter.
• Forgetting to cap at capacity, letting an idle bucket grant an unbounded burst later.
• Updating _last outside the lock, reintroducing the race you added the lock to prevent.