Implement a token bucket rate limiter. Make it thread-safe, and explain what the two parameters actually control.

TL;DR: A bucket holds up to capacity tokens and refills at rate tokens per second. A request takes a token if one is available and is rejected otherwise. The two parameters control different things and conflating them is the common bug: rate is the sustained throughput allowed over time, and capacity is how much of an unused allowance can be spent at once, which is the burst. Refill lazily, computing elapsed time on each call rather than running a background thread, because a thread per bucket does not scale to thousands of tenants and adds a scheduling dependency for no benefit. Use a monotonic clock rather than wall time, since a clock adjustment with wall time either freezes the bucket or grants unlimited tokens. Take the lock around refill and deduction together, because doing them separately is a race that over-issues under concurrency. And return a retry-after value alongside the rejection, computed as the deficit divided by the rate, so a client backs off by the right amount instead of guessing.

How to approach it

State what the two parameters mean before writing, since the interview is partly about whether you know that capacity is burst and rate is throughput. Write the lazy-refill version with the lock in the right place. Then the clock choice and the retry-after value, both of which are the difference between a toy and something usable. Close with the tests, particularly the concurrency one, which is the only way to know the lock is correct.

A strong answer

A typical situation: a limiter is configured at 100 requests per second with a capacity of 100, and a client that has been idle for an hour sends 100 requests instantly and is allowed. The team calls it a bug and reduces capacity to 10, which breaks every client that legitimately batches. Capacity and rate were doing different jobs and only one of them was the problem.

What the two parameters control:

rate      tokens added per second. This is the sustained throughput the client may use.
          Over a long window, a client cannot exceed rate x window regardless of capacity.
capacity  the maximum tokens the bucket holds. This is how much unused allowance can be
          spent at once, which is the burst.

worked
  rate 2/s, capacity 10, client idle for a minute
  bucket is full at 10, so 10 requests are allowed instantly, then 2 per second thereafter
  over 60 seconds the client can do 10 + 120 = 130 requests, not 120

what each is for
  rate protects the backend's sustained capacity
  capacity decides how forgiving you are to a client that batches, and it is the parameter
  to tune when clients complain about bursts being rejected
setting them: rate from the backend's sustained capacity divided by the number of tenants
  plus headroom; capacity from how long a client may reasonably idle and then burst, often
  one to a few seconds of rate
sanity: with capacity equal to rate x 5 seconds, a client that idles for any length of time
        can burst at most 5 seconds' worth, so the backend's worst case is 5 seconds of every
        tenant arriving at once. That product, capacity times tenant count, is the number to
        check against what the backend can absorb

The implementation:

import threading, time

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)
        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 take(self, n: float = 1.0) -> bool:
        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:
        """Seconds until n tokens will be available. 0 if they are available now."""
        with self._lock:
            self._refill()
            if self._tokens >= n:
                return 0.0
            return (n - self._tokens) / self.rate

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

The three decisions worth defending:

lazy refill rather than a background thread
  a thread per bucket does not scale: 10,000 tenants is 10,000 threads
  a single sweeper thread refilling all buckets adds a scheduling dependency and a period
    below which the limiter is inaccurate
  lazy refill computes exactly the tokens elapsed time has earned, at the moment of use, with
    no background work at all

monotonic clock rather than wall time
  wall time can jump: NTP corrections, daylight saving in a naive implementation, manual
    changes
  a backward jump makes elapsed negative, which the guard catches but which freezes the
    bucket until wall time catches up
  a forward jump grants tokens for time that did not pass, which is a free burst
  monotonic time never goes backward and is not adjusted, which removes the whole class

lock around refill and deduction together
  the race if they are separate: two threads both refill, both see enough tokens, both
    deduct, and the bucket goes negative or over-issues
  the lock is held for a few microseconds of arithmetic, so contention is not a concern until
    very high rates, where the answer is sharding buckets rather than removing the lock

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 covers what a client should do with the retry-after value, which is the other half of a working limiter. The concurrency test is the one that matters and the one candidates skip. It works because the rate is zero, so the bucket cannot refill during the test and the total issued must equal the initial capacity exactly. Any race shows up as a number other than 1,000, deterministically enough to catch in a few runs.

The reversal condition: a single-process bucket is correct for one server and wrong for a fleet, because each server has its own bucket and a tenant's effective limit is the configured rate times the number of servers. Distributing it means either a shared store on the request path, which adds latency and a dependency, or local buckets with periodic synchronization, which is approximate with a bounded error. The API rate-limiting design works through that trade; the point here is to notice that the correct single-node implementation is not the whole answer and to say so.

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

• A background refill thread, which does not scale past a few hundred buckets.
• 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.