Token Bucket Rate Limiter

Start from brute force

The obvious approach is what the word “refill” suggests: a timer that adds rate · dt tokens every dt seconds, simulated in a replay by stepping a clock tick by tick up to each request. It works when every timestamp lands on a tick. It costs O(n + T/dt) time for n requests spanning T seconds, and O(1) state. It is too slow and also wrong: times = [0, 1000000] with 1-second ticks runs a million ticks for two requests, and with capacity = 1, rate = 1, times = [0, 1.5, 2.2] it accepts all three, because the tick at t = 2 credits a whole token where only 0.7 seconds have passed since the last request.

The approach

Nothing spends tokens between two requests, so the level at a request is a closed-form function of the level at the previous one: add the elapsed time times the rate, then cap at capacity. Refilling and capping continuously would give exactly the same number, which is why the lazy formula needs no timer. The invariant: after each request, tokens is the exact level a continuously refilling bucket would hold at time last.

The reference keeps that state in two variables, tokens = float(capacity) (the bucket starts full) and last = times[0] if times else 0. For each t it computes tokens = min(capacity, tokens + (t - last) * rate), then sets last = t whether or not the request passes, because the refill already happened. If tokens >= 1 it subtracts one and appends True to out; otherwise it appends False and leaves tokens alone, so a rejection spends nothing.

Walk through an example

Tracing the first example, capacity = 2, rate = 1, times = [0, 0, 0, 1, 3], one request per row.

Complexity

Lazy refill: O(n) time for n requests, one multiplication, one min and one comparison each, and O(1) state (two numbers) besides the O(n) output list. Tick simulation: O(n + T/dt) time for a span of T seconds with tick dt, because it also pays for every quiet tick, and the same O(1) state.

Edge cases to test

• Empty times: return []. The reference guards times[0] with if times else 0; reading the first timestamp unguarded crashes.
• A long idle gap, capacity = 2, rate = 10, times = [0, 100, 100, 100]: [true, true, true, false]. The cap holds the bucket at 2 tokens; without it, 100 idle seconds bank 1,000 tokens and all four pass.
• rate = 0 with capacity = 1, times = [0, 0, 0]: [true, false, false]. The bucket never refills, and rejections leave it at 0, not negative.
• Equal timestamps are a burst: three requests at t = 0 against capacity = 2 give [true, true, false], because zero elapsed time refills nothing.
• A capacity below one token, e.g. capacity = 0.5, rate = 1, times = [0, 1, 2]: [false, false, false]. The level can never reach a whole token, so nothing is ever accepted.
• A rejection still moves last: capacity = 2, rate = 0.5, times = [0, 0, 1, 1.5] must give [true, true, false, false]. Updating last only on accept credits the interval from 0 to 1 a second time at t = 1.5 and wrongly accepts that request.

Common mistakes

• Refilling with a background loop instead of lazily on access — needless work and clock coupling.
• Not capping accrued tokens at capacity, which lets a long-idle client burst past the limit.
• Floating-point drift when accumulating fractional tokens: ten refills of 0.1 add up to 0.9999999999999999, not 1, so a tokens >= 1 check rejects a request that exact arithmetic would accept.
• Updating last only when a request is accepted. The refill for a rejected request already happened, so the next request is credited for the same interval twice.

Follow-ups an interviewer asks next

Many API servers enforce one shared limit per client.

Keep (tokens, last) per key in a shared store such as Redis and run refill, check and spend as one atomic step, for example a Lua script executed by the server. Two servers doing a plain read, modify and write can both read 1 token and both accept. Take timestamps from one clock, such as the store’s, so skew between servers cannot mint extra tokens.

Requests have different costs, such as tokens per LLM call.

Spend the cost instead of 1: accept when tokens >= cost and subtract cost. Then decide what happens to a request that costs more than capacity, because it can never pass: reject it with a clear error, or admit it by letting the level go negative and repaying the debt from future refills.

Fractional rates drift. How do you make the arithmetic exact?

With capacity = 1, rate = 0.1 and one request per second, ten refills of 0.1 sum to 0.9999999999999999, so this reference rejects the request at t = 10 that exact arithmetic accepts. Store the level in integer units chosen so that rate times elapsed time is always whole (tenths of a token here), or use Python’s fractions.Fraction. An epsilon in the comparison also works but hides the cause.

Tell a rejected client when to retry.

The level is short by 1 - tokens and grows at rate per second, so if nothing else spends from the bucket first, a retry can pass after (1 - tokens) / rate seconds (never, if the rate is 0). Send it rounded up in a Retry-After header so well-behaved clients wait instead of hammering the limiter.

Where this shows up

Token bucket is the standard rate-limiting algorithm: capacity sets the allowed burst, refill rate sets the sustained limit. It is used in API gateways, network traffic shaping, and anywhere you need to smooth bursty load while still permitting short spikes.

Reference solution

def token_bucket(capacity, rate, times):
    tokens = float(capacity)
    last = times[0] if times else 0
    out = []
    for t in times:
        tokens = min(capacity, tokens + (t - last) * rate)
        last = t
        if tokens >= 1:
            tokens -= 1
            out.append(True)
        else:
            out.append(False)
    return out


print(token_bucket(2, 1, [0, 0, 0, 1, 3]))   # -> [True, True, False, True, True]

function tokenBucket(capacity: number, rate: number, times: number[]): boolean[] {
  let tokens = capacity;
  let last = times.length ? times[0] : 0;
  const out: boolean[] = [];
  for (const t of times) {
    tokens = Math.min(capacity, tokens + (t - last) * rate);
    last = t;
    if (tokens >= 1) {
      tokens -= 1;
      out.push(true);
    } else {
      out.push(false);
    }
  }
  return out;
}

console.log(tokenBucket(2, 1, [0, 0, 0, 1, 3]));   // -> [true, true, false, true, true]