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

TL;DR: Keep a token count and a last-refill timestamp. Per request, add elapsed * fill_rate tokens lazily (capped at capacity) before the check, which avoids any background thread burning CPU. Protect the state with a lock for thread safety. That absorbs bursts up to capacity while holding a steady long-run rate.

How to approach it. Pin down the contract: tokens per second, burst capacity, and whether consume blocks or returns right away (returning a boolean is the usual ask). Name the central design decision early: lazy refill derived from elapsed time rather than a timer thread. Then code it and walk through 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.