Notes
Requirements
Fix the scope first. The library has one main call, try acquire, with a key such as a user id, an API key or an IP address. Each key gets a rule like five requests per second, and paid tiers get bigger rules. The algorithm is chosen when the limiter is built. A denial says how long to wait. Calls must be fast and safe from many threads. Limiting across many servers is a follow-up, so say it is out of scope for now.
Ask the questions that pick the algorithm. Are short bursts fine? Then a token bucket fits. Must the limit hold over every rolling window, with no exceptions? Then a sliding log or a sliding counter. Should a caller block until allowed, or be rejected? Reject, with a retry-after hint. And how many keys? If it is millions, the state per key must be a few numbers, not a list of timestamps.
- tryAcquire(key): allow or deny
- key: user id, API key, IP
- rule: N requests per window
- different rules per tier
- algorithm chosen at build
- deny says when to retry
- O(1) or close per call
- safe from many threads
- out of scope: many servers
- sharing one limit (later)
- bursts allowed?
- yes, up to the limit at once
- strict over any window?
- sometimes: offer sliding
- blocking or reject?
- reject now, say retry after
- one rule per key or several?
- one now, stacking later
- memory per key?
- small: millions of keys
Entities
The entities. The rate limiter is a facade the callers see. Inside, a concurrent map holds one small limiter object per key, created on first use. A rule source says which rule applies to a key, so free and paid users can differ. A clock is injected so tests can move time. And every call returns a decision: allowed or not, how many are left, and how long to wait before retrying.
Class diagram
Turn them into types. A rule is a record: a limit and a window in milliseconds. A decision is a record too, so it is safe to hand to any thread. The rule source is a one-method interface, so a lambda can map paid keys to a bigger rule. And the limiter interface has one method that takes the current time. Passing time in, rather than reading the clock inside, keeps every algorithm a pure, testable piece of state.
record Rule(int limit, long windowMs)
record Decision(boolean allowed,
long remaining, long retryAfterMs)
interface RuleSource {
Rule ruleFor(String key); }
interface Limiter {
Decision tryAcquire(long now); }
enum Algorithm { TOKEN_BUCKET,
FIXED_WINDOW, SLIDING_LOG,
SLIDING_COUNTER } Strategy: algorithm
The algorithm is a Strategy. Four classes implement the same limiter interface, and the facade only ever calls try acquire. Token bucket allows bursts and stores two numbers. Fixed window is the simplest but leaks at window edges. Sliding log is exact but stores a timestamp per request. Sliding counter is nearly exact with three numbers. Naming the trade-off for each one is what interviewers listen for.
- token bucket: bursts OK,
- 2 numbers per key
- fixed window: simplest,
- 2x burst at the boundary
- sliding log: exact,
- one timestamp per request
- sliding counter: near exact,
- 3 numbers per key
Token bucket
The token bucket. A bucket holds up to five tokens and earns one every two hundred milliseconds. There is no timer thread: on each call we work out how many tokens were earned since the last refill, add them up to the capacity, and move the refill time forward by whole intervals, so partial progress is kept. Spend a token to allow. With none left, the retry time is when the next token lands. Integer math only, so nothing drifts.
earned = (now - lastRefill) / every
if (earned > 0) {
tokens = min(capacity, tokens + earned)
lastRefill += earned * every
}
if (tokens > 0) { tokens--; allow }
else deny(lastRefill + every - now)
5 per second: every = 200 ms
t=0: 5 allowed, then retry in 200 Fixed window
The fixed window keeps one counter per aligned window, say each whole second, and resets it when a new window starts. It is tiny and fast, but it has a famous flaw. Send five requests at nine hundred ninety-nine milliseconds and five more at one thousand: they land in different windows, so all ten pass within two milliseconds. That is double the limit. Always point this out yourself before the interviewer does.
start = now - now % windowMs
if (start != windowStart) {
windowStart = start; count = 0;
}
if (count < limit) { count++; allow }
else deny(windowStart + window - now)
limit 5 per second:
t=999 YYYYY
t=1000 YYYYY (new window) Sliding log
The sliding log fixes the edge. Keep a queue of the times of accepted requests. On each call, drop timestamps older than one window, then allow only if fewer than the limit remain, and record the new time. At one thousand milliseconds the five requests from nine hundred ninety-nine are still in the log, so all five new ones are denied. It is exact, but a limit of ten thousand per hour means up to ten thousand timestamps per key.
Deque<Long> log // accepted times
while (head <= now - windowMs)
log.pollFirst() // too old
if (log.size() < limit) {
log.addLast(now); allow
}
else deny(head + windowMs - now)
memory: up to limit stamps per key Sliding counter
The sliding window counter is the practical middle ground. Keep only two counts: the previous window and the current one. Estimate the rolling count as the previous count, weighted by how much of that window still overlaps the last second, plus the current count. Right at the boundary the overlap is one, so the five earlier requests still count and new ones are denied. Three numbers per key, and the error is small because it assumes the old requests were spread evenly.
overlap = 1 - (now - start) / window
estimate = previous * overlap
+ current
if (estimate + 1 <= limit) {
current++; allow
}
limit 5, previous window had 5,
250 ms into the new one:
5 x 0.75 + 0 = 3.75, allow 1 Factory: per-key state
Per-key state comes from a small factory: a switch over the algorithm enum returns a fresh limiter built with that key's rule. The facade looks the key up with compute if absent on a concurrent map, which runs the factory at most once per key even when two threads see a new key at the same moment. If we used get and then put instead, two threads could each create a bucket, and each would let five requests through.
Decision tryAcquire(String key) {
long now = clock.getAsLong();
return limiters.computeIfAbsent(key,
k -> create(algorithm,
rules.ruleFor(k), now))
.tryAcquire(now);
}
create(): switch over Algorithm,
a fresh object per key Flow: tryAcquire
Walk one call. The facade reads the clock once, finds or creates the state for the key, and asks it. The eighth request in the same instant gets a denial with retry after two hundred milliseconds. The limiter only returns a decision; the caller decides what to do with it. A web filter turns a denial into status four twenty-nine with a retry-after header, and a background job might simply wait that long.
- allowed: handle the request
- header: remaining = 3
- denied: status 429
- header: Retry-After
- the limiter returns data;
- the caller picks the reply
Concurrency
Concurrency. Refill, check and spend must happen as one step, or two threads can both see one token left and both take it. So each limiter's method is synchronized on that limiter only. Different keys have different locks, so user A never waits for user B, and the lock is held for a few nanoseconds. In the demo, sixteen threads make sixteen hundred calls on one key with a limit of fifty, and exactly fifty get through, every run.
- map: ConcurrentHashMap
- new key: computeIfAbsent
- each Limiter: synchronized
- methods, a few fields
- refill + check + spend is
- one atomic step
- test: 16 threads x 100 calls
- on one key, limit 50
- allowed: exactly 50
Extensibility
Now the extensions. Several rules on one key, like ten per second and a thousand per hour, is a composite that allows only if every rule allows. Idle keys must be evicted after a quiet period, or the map grows forever. Across many servers, the state moves to a shared store, with refill, check and spend in one atomic script, or each server takes a share of the global limit locally. A new algorithm is just one new class.
- several rules on one key:
- 10/s AND 1000/hour, all pass
- idle keys: evict after an hour
- of silence (sweep or a cache)
- many servers: state in Redis,
- check-and-spend in one Lua
- script, or local buckets with
- a share of the global limit
- new algorithm: one new class
Follow-up: hit counter
A common follow-up is a hit counter: how many hits in the last five minutes? Storing every hit is the sliding log again, and it grows without bound. Instead keep three hundred buckets, one per second, each with the second it belongs to and a count. A hit finds its bucket by the second modulo three hundred, resets it if it holds an old second, and adds one. Reading sums the buckets that are still inside the window. Memory is fixed.
long[] stamp, count // one per second
hit(sec):
i = sec % 300
if (stamp[i] != sec)
{ stamp[i] = sec; count[i] = 0; }
count[i]++
hits(sec): sum count[i] where
sec - stamp[i] < 300
memory fixed, however many hits Testing
The full code is below the player. The demo uses a fake clock, so a burst of seven at time zero gives five yeses and two nos with a retry of two hundred milliseconds, and four hundred milliseconds later two more pass. It replays the boundary burst against three algorithms: the fixed window lets ten through, the sliding ones only five. Then the sixteen-thread race, and the hit counter. Every result is asserted.
token bucket t=0 YYYYYnn retry after 200 ms token bucket t=400 YYn FIXED_WINDOW -> 10 in 2 ms SLIDING_LOG -> 5 in 2 ms SLIDING_COUNTER -> 5 in 2 ms race: 1600 attempts, 50 allowed hits: at 300 -> 4, at 301 -> 2 all checks passed
Follow-ups
Expect follow-ups. Why not one global lock? Every user would queue behind every other. What if the wall clock jumps back? Use a monotonic clock, like nano time. Expensive calls should cost more? Spend several tokens at once. A client that prefers waiting can sleep for the retry-after time. And across servers, either keep the state in a shared store and update it atomically, or split the limit between nodes and accept a little slack.
- why not one global lock?
- all users would queue
- clock goes backwards?
- use a monotonic clock
- limit by cost, not count?
- spend N tokens per call
- wait instead of reject?
- sleep for retryAfter
- distributed: atomic script
- or split the limit per node
Say it like this
The short version to say out loud. A facade keeps one small limiter per key in a concurrent map, created once by a factory from that key's rule. The algorithm is a strategy: token bucket when bursts are fine, sliding window counter when the limit must hold over any second, and I know why a fixed window leaks double at the edge. Each limiter synchronizes on itself, so keys never contend, and time is injected for tests.
- "A facade keeps one small
- limiter per key in a concurrent
- map, built by a factory from
- the key's rule. The algorithm
- is a strategy: token bucket for
- bursts, sliding counter for
- strict limits. Each limiter is
- synchronized on itself."