Why this matters: the rate limiter's implementation act is an arithmetic exam wearing a design problem's clothes. The lazy-refill formula is four lines, and every line has a bug variant an interviewer has seen: floating-point drift, refill past capacity, elapsed time double-counted. This walkthrough builds it with integer nanosecond arithmetic and narrates the traps as it steps past them.
The decision and the interface
enum Decision { ALLOW, DENY }
interface KeyLimiter {
Decision tryAcquire(long nowNanos); // time injected — never read inside
long retryAfterNanos(long nowNanos); // 0 if a request would be allowed
}Say the design claim as you write it: the algorithm behind an interface, and time as a parameter. Both were justified in lesson 02; here they become the two signatures everything else builds on.
The token bucket, in integers
Fractional tokens invite floating-point drift over millions of operations. The standard dodge: scale everything so arithmetic stays integral — track nano-tokens (one token = 1e9 nano-tokens), and refill in nano-tokens per nanosecond of elapsed time.
class TokenBucket implements KeyLimiter {
final long capacityNano; // capacity * 1e9
final long refillPerNano; // (rate/sec * 1e9) / 1e9 = rate nano-tokens per nano
long tokensNano; // current balance
long lastRefillNanos; // when we last accounted
public Decision tryAcquire(long nowNanos) {
refill(nowNanos);
if (tokensNano >= ONE_TOKEN) { // ONE_TOKEN = 1_000_000_000
tokensNano -= ONE_TOKEN;
return Decision.ALLOW;
}
return Decision.DENY;
}
private void refill(long nowNanos) {
long elapsed = nowNanos - lastRefillNanos;
if (elapsed <= 0) return; // monotonic clock, but belt-and-braces
tokensNano = Math.min(capacityNano, tokensNano + elapsed * refillPerNano);
lastRefillNanos = nowNanos; // account for time exactly once
}
}Three narration points, each a defused bug. The min against capacity is what makes an idle hour refill to full and no further — forget it and long-idle keys accumulate unbounded credit. Advancing lastRefillNanos to now (not by some computed amount) means elapsed time is counted exactly once — the double-count bug lives in designs that try to be clever here. And a denied request changes nothing: no partial charge, no state churn — deny is read-only apart from the refill accounting.
The retry hint: one division on existing state
public long retryAfterNanos(long nowNanos) {
refill(nowNanos);
if (tokensNano >= ONE_TOKEN) return 0;
long shortfall = ONE_TOKEN - tokensNano;
return shortfall / refillPerNano; // time until the next full token
}Lesson 02 claimed the token bucket makes the retry hint nearly free — this is the receipt. The shortfall is already in hand; the wait is one division. Worth saying: the hint is advisory (another caller may take that token first), which is exactly the honesty level an interviewer wants attached to it.
The keyed store: resolution cached, hot path clean
class RateLimiter {
final Config config; // default + pattern overrides
final Map<String, KeyState> states;
Decision allow(String key, long nowNanos) {
KeyState s = states.get(key);
if (s == null) {
Limit limit = config.resolve(key); // ONCE per key: exact > pattern > default
s = new KeyState(new TokenBucket(limit), nowNanos);
states.put(key, s);
}
s.lastSeenNanos = nowNanos; // feeds idle eviction
return s.limiter.tryAcquire(nowNanos);
}
}The narration: config.resolve runs on first sight only — after that, the hot path is one map lookup and one tryAcquire, no chain of override maps in the loop. lastSeenNanos is the eviction bookkeeping, one assignment.
Idle eviction: the lossless sweep
void evictIdle(long nowNanos) { // called periodically, or amortized
long idleThreshold = fullRefillNanos(); // capacity / refillRate — bucket is full past this
states.values().removeIf(s -> nowNanos - s.lastSeenNanos > idleThreshold);
}The threshold isn't arbitrary — it's the lossless-eviction argument from lesson 02 made executable: past capacity / refillRate of idle time, the bucket is provably full, so evicting it and rebuilding on next sight produces an identical state. Say that sentence when you write this method; it converts "I clean up old entries" into "eviction is correct by construction."
What you'd say about complexity
allow() is O(1): a map lookup, integer refill arithmetic, a compare — the enumeration's promise, kept. State is O(1) per key — three longs and a reference, order-of-fifty bytes with object headers; a million active keys is tens of megabytes, a number worth saying out loud since memory was a requirement. The sweep is O(active keys) per pass, amortizable. And the honest footnote from the enumeration: the exact-counting alternative pays O(events in window) per key for its precision — our choice traded that exactness for these constants, and both halves of that trade should be sayable.
Key takeaway
Integer nano-scaled arithmetic keeps a million refills drift-free; the refill's min-against-capacity and advance-to-now lines each defuse a classic bug; denials are read-only; config resolves once onto key state so the hot path is a lookup and a compare; and idle eviction is lossless at exactly the full-refill threshold — a cleanup routine with a correctness proof attached. O(1) time and state per key, with the numbers to back it.