Coding interview: implement a burst-tolerant token-bucket rate limiter

Prompt and scope

Implement a per-user token-bucket rate limiter. Each bucket has a maximum capacity, a refill rate refillRate per second, and a current token balance. A request carries a user ID, timestamp, and cost. If the refilled balance covers the cost, consume it and allow the request; otherwise reject it. Explain the API, complexity, time precision, concurrency, and tests.

This fits backend, platform, and infrastructure coding interviews. AWS describes token buckets as tokens representing requests, refilled at a configured rate, with one token consumed per request, and recommends testing limits before increasing them.

What the interviewer evaluates

• Whether you derive lazy refill instead of starting a timer for every bucket.
• Whether you use monotonic time so wall-clock rollback cannot mint tokens.
• Whether tokens are capped and rejected requests leave the balance intact.
• Whether you distinguish single-process memory from distributed shared state.
• Whether you cover concurrency, numeric precision, long idle gaps, and invalid parameters.

Clarifications to ask first

Confirm:

1. Is cost always a positive integer, or can it be fractional?
2. Is time injected for deterministic tests, or read by the limiter itself?
3. Is a single-process implementation enough, or must instances share quotas?
4. Should rejection include remaining tokens or an estimated retry time?

If unspecified, assume one process, non-negative integer costs, a nanosecond monotonic clock, and bursts allowed up to bucket capacity.

Thirty-second answer framework

Store tokens and lastRefillAt per user. On each request, lazily refill with min(capacity, tokens + elapsed * refillRate) using monotonic elapsed time. Allow only when the refilled balance covers cost; otherwise preserve the state and reject. In one process, a per-user lock or atomic critical section makes read, refill, check, and write indivisible. In a distributed deployment, run the same transition in an atomic shared-store script or transaction. Validate parameters, clock behavior, boundaries, and concurrent calls with a controllable-clock model test.

Step-by-step deep dive

1. State and invariants

Store tokens, lastRefillAt, and optionally a version per user. The invariant is 0 <= tokens <= capacity, and lastRefillAt never moves backward. Validate positive capacity and refill rate at creation. Cost must be positive and no greater than capacity; otherwise return a parameter error without changing state.

2. Lazy refill

Let now be the current time and elapsed = now - lastRefillAt. Add elapsed * refillRate, then clamp the balance with min(capacity, tokens + refill). Even when the bucket is full, advance lastRefillAt to now so the interval is not counted again. Integer nanoseconds with rational arithmetic reduce floating-point drift; if floats are used, define rounding and test long runs.

3. Allow and reject

If the refilled balance is at least cost, subtract cost and allow. Otherwise do not subtract anything; return rejection and optionally retryAfter. Estimate the delay as (cost - tokens) / refillRate, rounded up, while handling zero refill rate and cost greater than capacity. A rejection must not look like success or move the cursor backward.

4. Concurrency and storage

Single-process code must keep read, refill, decision, and write in one critical section; sharded per-user locks avoid one global lock. When multiple instances share quotas, application locks are insufficient. Use Redis Lua, a database row lock, or another atomic transaction for the entire state transition. Carry a request ID through network retries so a lost response does not accidentally consume business tokens twice.

5. Expiration and cardinality

Expire inactive user state using lastRefillAt and a lease policy, while ensuring a new request initializes correctly. Protect against high-cardinality users with a state limit, sharding, and an eviction policy. Recreating an evicted bucket at full capacity can create a burst, so the production policy must state whether that is acceptable. Never let attacker-controlled user IDs grow an unbounded map.

6. Testing and observability

Test an initially full bucket, repeated rejection, exact refill, cost equal to capacity, no time advance, clock rollback, long idle gaps, contention, and duplicate calls. With an injected clock, assert that the balance stays within bounds and successful cost never exceeds initial capacity plus theoretical refill. Track allow and reject rates, token distributions, state count, lock wait, atomic-script errors, and memory usage.

High-quality sample answer

I would expose allow(userId, now, cost). A user state contains only tokens and lastRefillAt. Inside one critical section, calculate elapsed time, refill, clamp to capacity, and decide. On success, subtract cost and move the cursor to now; on rejection, keep the refilled balance but consume nothing. All time arithmetic uses a monotonic clock, so state cannot move backward.

For one process I would use sharded per-user locks. For multiple instances I would put the same transition in Redis Lua or an atomic database transaction rather than performing separate network reads and writes. A request ID supports retry idempotency; it does not make the business operation exactly once. Expiration and high-cardinality controls prevent memory abuse.

Tests use a controllable clock for zero elapsed time, exact refill, full-cost requests, long idle periods, clock rollback, and concurrency. A property test asserts that every balance stays between zero and capacity and that cumulative allowed cost never exceeds initial capacity plus refill. In production I would watch rejection rate, token distribution, state growth, lock wait, and storage-script errors; AWS guidance also calls for testing a proposed limit before raising it.

Common mistakes

• Starting a timer for every bucket, making scheduling cost grow with user count.
• Using wall-clock time, so NTP rollback creates extra tokens.
• Forgetting the capacity clamp and allowing unlimited accumulation.
• Charging rejected requests and silently consuming user quota.
• Treating an in-process lock as cross-instance atomicity.
• Accepting cost > capacity, which can wait forever or produce a bogus retry time.
• Using floating point without defining rounding and long-run drift.
• Testing only sequential calls and missing concurrent read-modify-write races.

Follow-up questions and responses

Why not a fixed-window counter?

A fixed window is simple but can allow a short double burst at the boundary. A token bucket expresses permitted burst with capacity and sustained rate with refill. If no burst is acceptable, compare a sliding window or leaky bucket.

How do you return Retry-After?

Divide the missing balance by refill rate and round up. With zero refill or a cost above capacity, return a configuration or non-retryable result rather than an infinite timestamp.

What if Redis is unavailable?

Choose fail-closed, a bounded local budget, or an explicit degradation according to endpoint risk, and record the reason. Do not let every instance fail open without a budget or hide the outage as an ordinary rejection.

How do you change capacity and refill rate?

Refill under the old parameters to the change time, then clamp or convert the balance under an explicit policy and record the configuration version. Lowering capacity must handle an existing balance above the new limit atomically.

How do you prove there is no overselling?

Run a state-machine property test over randomized times and assert that allowed cost in every interval is bounded by initial tokens plus theoretical refill. Add concurrent stress tests to verify the atomic critical section.