Implement a per-user token bucket rate limiter. Then make it work across several processes.

In FDE work, this is how you stop one user’s batch job from eating a model quota everyone shares, so say early that cost can be the request’s token count, not always one. A correct single-process bucket is the entry ticket. The round turns on what you say when two processes race for the last token, and when the shared store goes away. Keep the first half short and correct, so you have time for the second. Pin the contract before any code. Say it back: “allow(user_id, cost=1) -> bool, a capacity for bursts, a refill rate in tokens per second, and a refused request spends nothing. I’ll inject the clock so I can test refill without sleeping.” Ask whether a user who is refused should be told when to retry; that decides whether you return a wait time too. State the arithmetic out loud. No timers and no background thread. Each bucket stores its tokens and the time it was last touched. On each call: add elapsed time multiplied by the rate, cap at capacity, then spend if there is enough. Constant time per call, one small record per active user. Write it, then test it by moving the fake clock. A burst up to capacity, the next call refused, a partial refill that is not yet enough, and a long idle that must not overflow the cap. Then test refill in steps that floating point cannot represent exactly, such as clock steps of 0.1 at rate=10, because float accumulation is where a correct-looking bucket goes wrong. Distribute it by moving state, not logic. The same arithmetic runs inside the shared store as one atomic step, using the store’s clock so processes with skewed clocks agree. Then say what happens when that store is slow or down, and pick fail-open or fail-closed with a reason. The trap is the read-modify-write race. If each process reads the bucket, decides, and writes it back, two processes can both see the last token and both allow. Name the race before the interviewer does, then close it.

Implement a token bucket rate limiter

A practice prompt we wrote. No company or candidate report names it, so it carries no company tag.

How to answer

In work, this is how you stop one user’s batch job from eating a model quota everyone shares, so say early that cost can be the request’s token count, not always one. A correct single-process bucket is the entry ticket. The round turns on what you say when two processes race for the last token, and when the shared store goes away. Keep the first half short and correct, so you have time for the second.

Pin the contract before any code. Say it back: “allow(user_id, cost=1) -> bool, a capacity for bursts, a refill rate in tokens per second, and a refused request spends nothing. I’ll inject the clock so I can test refill without sleeping.” Ask whether a user who is refused should be told when to retry; that decides whether you return a wait time too.
State the arithmetic out loud. No timers and no background thread. Each bucket stores its tokens and the time it was last touched. On each call: add elapsed time multiplied by the rate, cap at capacity, then spend if there is enough. Constant time per call, one small record per active user.
Write it, then test it by moving the fake clock. A burst up to capacity, the next call refused, a partial refill that is not yet enough, and a long idle that must not overflow the cap. Then test refill in steps that floating point cannot represent exactly, such as clock steps of 0.1 at rate=10, because float accumulation is where a correct-looking bucket goes wrong.
Distribute it by moving state, not logic. The same arithmetic runs inside the shared store as one atomic step, using the store’s clock so processes with skewed clocks agree. Then say what happens when that store is slow or down, and pick fail-open or fail-closed with a reason.

The trap is the read-modify-write race. If each process reads the bucket, decides, and writes it back, two processes can both see the last token and both allow. Name the race before the interviewer does, then close it.

Follow-ups

What the interviewer may ask next, once your first answer is on the table.

What happens when two processes read the same bucket at the same moment?
The shared store times out. Do you allow the request or refuse it, and who decides?
How would you add a global cap on top of the per-user one, so that a request refused by one bucket spends nothing from the other?
How do you test refill without calling sleep?

Where answers go wrong

Refilling with a background timer per user instead of computing the refill from elapsed time on each call.
Reading the bucket from the shared store and writing it back as separate calls, so two processes both spend the last token.

Answer this in two minutes

Write the answer you would say out loud. The clock starts with your first word.

Compare with the model answer

Model answer

“I’ll start with one process, lazy refill, and an injected clock. Tokens are floats because refill is continuous. If you’d rather have no epsilon at all, store integer micro-tokens and integer nanoseconds from time.monotonic_ns(), and carry each refill’s remainder forward so every comparison is exact; I’m using floats because the code is shorter and the epsilon is one line. You said refused callers should be told when to retry, so allow returns the wait too.”

import threading
import time
from dataclasses import dataclass
from typing import Callable

EPS = 1e-9  # a float refill can land a hair under a whole token


@dataclass
class _Bucket:
    tokens: float
    last: float


@dataclass(frozen=True)
class Decision:
    allowed: bool
    retry_after: float = 0.0  # seconds until the request would pass

    def __bool__(self) -> bool:
        return self.allowed


class TokenBucketLimiter:
    def __init__(self, capacity: float, refill_per_sec: float,
                 clock: Callable[[], float] = time.monotonic):
        if capacity <= 0 or refill_per_sec <= 0:
            raise ValueError("capacity and refill rate must be positive")
        self.capacity = capacity
        self.rate = refill_per_sec
        self.clock = clock
        self._buckets: dict[str, _Bucket] = {}
        self._lock = threading.Lock()

    def allow(self, user_id: str, cost: float = 1.0) -> Decision:
        if cost > self.capacity:
            raise ValueError("cost exceeds capacity; it can never pass")
        with self._lock:
            now = self.clock()
            b = self._buckets.setdefault(
                user_id, _Bucket(self.capacity, now))
            elapsed = max(0.0, now - b.last)  # never refill backwards
            b.tokens = min(self.capacity,
                           b.tokens + elapsed * self.rate)
            b.last = now
            if b.tokens + EPS >= cost:
                b.tokens = max(0.0, b.tokens - cost)
                return Decision(True)
            return Decision(False, (cost - b.tokens) / self.rate)

“I use time.monotonic because wall-clock time can jump when the host syncs. The lock matters only if handlers run in threads. retry_after is the value for a Retry-After header, and a cost above capacity is a caller bug, so it raises instead of being refused forever.”

import pytest


def test_burst_refill_and_cap():
    t = [0.0]
    lim = TokenBucketLimiter(capacity=3, refill_per_sec=1,
                             clock=lambda: t[0])
    assert [bool(lim.allow("u")) for _ in range(4)] == [
        True, True, True, False]
    t[0] = 0.5
    d = lim.allow("u")
    assert not d and d.retry_after == 0.5   # half a token is not enough
    t[0] = 1.0
    assert lim.allow("u")                   # the halves add up
    t[0] = 1000.0
    assert sum(bool(lim.allow("u")) for _ in range(10)) == 3  # capped
    assert lim.allow("other")               # buckets are independent
    with pytest.raises(ValueError):
        lim.allow("u", cost=4)


def test_refill_in_steps_floats_cannot_represent():
    t = [0.0]
    lim = TokenBucketLimiter(capacity=1, refill_per_sec=10,
                             clock=lambda: t[0])
    for step in range(1, 51):
        t[0] = round(step * 0.1, 10)   # 0.3 - 0.2 == 0.09999999999999998
        assert lim.allow("u")          # fails without EPS
        assert not lim.allow("u")

“Memory grows with every user ever seen. A bucket idle for capacity / rate seconds is full, and a full bucket behaves exactly like a missing one, so I can evict idle buckets without changing any answer.”

“Across processes, the bucket lives in Redis and the arithmetic moves into a Lua script. Redis runs a script atomically, which closes the read-modify-write race. The script reads the store’s TIME, so no process’s clock matters. Reading TIME before a write needs Redis 5.0 or later, where a script replicates its effects rather than itself; on 3.2 and 4.0 it must call redis.replicate_commands() first. The TTL uses the same equivalence as eviction: once a key would be full, deleting it changes nothing. The script returns the wait in whole milliseconds, because Redis truncates a Lua number to an integer in the reply.”

import redis

BUCKET_LUA = """
local cap, rate = tonumber(ARGV[1]), tonumber(ARGV[2])
local cost = tonumber(ARGV[3])
local t = redis.call('TIME')
local now = tonumber(t[1]) + tonumber(t[2]) / 1e6
local s = redis.call('HMGET', KEYS[1], 'tokens', 'last')
local tokens = tonumber(s[1]) or cap
local last = tonumber(s[2]) or now
tokens = math.min(cap, tokens + math.max(0, now - last) * rate)
local ok, wait_ms = 0, 0
if tokens + 1e-9 >= cost then
  tokens, ok = math.max(0, tokens - cost), 1
else
  wait_ms = math.ceil((cost - tokens) / rate * 1000)
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'last', now)
redis.call('EXPIRE', KEYS[1], math.ceil(cap / rate))
return {ok, wait_ms}
"""


class SharedTokenBucket:
    def __init__(self, r: redis.Redis, capacity: float,
                 refill_per_sec: float, processes: int):
        self.capacity, self.rate = capacity, refill_per_sec
        self._script = r.register_script(BUCKET_LUA)
        # Used only while the store is unreachable: this process's
        # share of the limit, never below one request.
        self._local = TokenBucketLimiter(
            max(capacity / processes, 1.0), refill_per_sec / processes)
        self._down_until = 0.0

    def allow(self, user_id: str, cost: float = 1.0) -> Decision:
        if cost > self.capacity:
            raise ValueError("cost exceeds capacity; it can never pass")
        if time.monotonic() >= self._down_until:
            try:
                ok, wait_ms = self._script(
                    keys=[f"tb:{user_id}"],
                    args=[self.capacity, self.rate, cost])
                return Decision(bool(ok), wait_ms / 1000)
            except redis.RedisError:  # timeouts included
                # Skip the store for a second, then probe it again.
                self._down_until = time.monotonic() + 1.0
        # A legal cost above the local share is charged at the share,
        # so an outage never turns a valid request into an error.
        local_cost = min(cost, self._local.capacity)
        return self._local.allow(user_id, local_cost)

“Each call touches one key, so it works on a cluster too. I build the client with a short socket_timeout and with its own retries off, retry=Retry(NoBackoff(), 0), because by default redis-py retries a failed command several times with exponential backoff (its retry docs), so one failed call can take seconds.”

“On any RedisError, each process falls back to its own bucket with its share of the capacity and rate. That degrades to an approximate local limit instead of failing open or closed. The share can’t drop below one request, or with a capacity of 3 across 4 processes each local bucket would hold 0.75 and every call would raise; the floor over-admits slightly, which is the right way to be wrong during an outage. A weighted request bigger than one process’s share is charged at the share’s size, so a legal request is allowed or refused during an outage, never turned into an error. The share is only right if the load balancer spreads each user’s requests evenly across processes; with sticky routing, a user gets only one process’s share. processes comes from the deployment config at startup; if we autoscale, I’d read it from the orchestrator or accept the error.”

“The breaker matters as much as the fallback. Without it, every request waits out the full timeout while Redis is down, and p99 becomes the timeout. With it, only the probe after each second pays. This one is the simplest breaker that works; the circuit breaker question builds the full one with half-open probing. Falling back suits an API that protects its own capacity. If the limit protects a partner’s metered quota or moves money, I would fail closed instead, and I’d ask who owns that call.”

“If you want a global cap on top of the per-user one, both buckets go in one script: it refills both, checks both, and spends from both only if both allow, so a refusal by either spends nothing.”

BOTH_LUA = """
-- KEYS[1] = user bucket, KEYS[2] = global bucket
-- ARGV = user cap, user rate, global cap, global rate, cost
local t = redis.call('TIME')
local now = tonumber(t[1]) + tonumber(t[2]) / 1e6
local cost = tonumber(ARGV[5])
local caps = {tonumber(ARGV[1]), tonumber(ARGV[3])}
local rates = {tonumber(ARGV[2]), tonumber(ARGV[4])}
local tokens, ok, wait_ms = {}, 1, 0
for i = 1, 2 do
  local s = redis.call('HMGET', KEYS[i], 'tokens', 'last')
  local have = tonumber(s[1]) or caps[i]
  local last = tonumber(s[2]) or now
  have = math.min(caps[i], have + math.max(0, now - last) * rates[i])
  tokens[i] = have
  if have + 1e-9 < cost then
    ok = 0
    local w = math.ceil((cost - have) / rates[i] * 1000)
    wait_ms = math.max(wait_ms, w)
  end
end
for i = 1, 2 do
  if ok == 1 then tokens[i] = math.max(0, tokens[i] - cost) end
  redis.call('HSET', KEYS[i], 'tokens', tokens[i], 'last', now)
  redis.call('EXPIRE', KEYS[i], math.ceil(caps[i] / rates[i]))
end
return {ok, wait_ms}
"""

“The catch is Redis Cluster: a script’s keys must share a hash slot, so I name them with a hash tag. For a cap per tenant that is natural: tb:{acme}:user:42 and tb:{acme}:cap. A cap across all tenants leaves two choices. One global key puts every request on one shard, so the limiter can’t scale out. Or I split the cap into N shares that sum to it, and tag each user to one share, tb:{s7}:user:42 with tb:{s7}:cap; the cost is that one share can refuse while another has room. I’d pick the shares, because a limiter pinned to one shard becomes the bottleneck it was meant to prevent, and I’d measure the uneven refusals in a load test before choosing N.”