Cruxly › Low-level design › LLD Exercises
Rate Limiter
algorithm choice, then the check-then-act race
Open the interactive lessonPrompt: design a rate limiter. allow(userId) returns true if this user may make a request now, false otherwise. Limits are configurable per user tier (free: 10/min, pro: 1000/min).
45 minutes. The interesting part is not the data structure.
Applying the five moves (from the method lesson): nouns are User, Tier, and whatever per-user counter state the chosen algorithm needs — that's it, resist inventing more. The invariant is "allow() never lets a user's count exceed their tier's limit, even under concurrent calls" — state that sentence before writing a single method. The interface seam is the algorithm itself (RateLimitStrategy or equivalent), because the prompt's four plausible algorithms is a direct signal that the choice will be questioned. The concurrency sentence is the whole second half of this exercise: allow() is check-then-act, and saying so before being asked is the move.
Scope, then the algorithm menu
In scope: per-user limits, configurable per tier, allow() returns a boolean. Single process, many threads. Out of scope (say it): distributed coordination across machines, persistence across restarts, per-endpoint limits. Each is a genuinely different problem and naming them prevents drift.
Four algorithms. What matters is not knowing them — it is that each one's failure mode is different, and stating the failure mode is how you pick.
Fixed window. A counter per (user, minute).
String key = userId + ":" + (now.getEpochSecond() / 60);
int n = counts.merge(key, 1, Integer::sum);
return n <= limit;Trivial and cheap. Fails at window edges: 10 requests at 11:59:59 and 10 more at 12:00:00 means 20 in one second under a 10/min limit. Disqualifying for abuse prevention, fine for rough quota accounting.
Sliding window log. Keep a timestamp per request; evict what has aged out.
Deque<Long> log = logs.get(userId);
long cutoff = now - windowNanos;
while (!log.isEmpty() && log.peekFirst() <= cutoff) log.pollFirst();
if (log.size() < limit) { log.addLast(now); return true; }
return false;Exact, no edge effect. Memory is O(limit) per user — 1000 timestamps for every pro user, which at scale is the problem.
Sliding window counter. Current and previous fixed window, previous weighted by overlap.
double elapsedInWindow = (now % windowNanos) / (double) windowNanos;
double estimate = prevCount * (1 - elapsedInWindow) + currCount;
return estimate < limit;Two integers per user. Approximates within a few percent. Fails by admitting a slightly wrong number under bursty arrival — usually acceptable, and worth saying so rather than implying it is exact.
Token bucket. Tokens refill at a fixed rate up to a capacity; a request takes one. Two numbers per user. Permits bursts up to capacity by design — a feature for APIs, a bug for abuse prevention.
Choice: token bucket, because tier limits like "1000/min" in practice mean "sustained 1000/min, and a short burst is fine." Say the alternative that would change the answer: "if this were abuse prevention rather than quota, I'd take the sliding window counter, because a burst is exactly what I'd be trying to stop."
The classes — full implementation
Start with the value types and the seam, then the limiter itself.
/** Per-tier configuration. An interface because the prompt named two tiers,
* which is the prompt telling you a third is coming. */
public interface TierPolicy {
double ratePerSec(); // tokens added per second
double capacity(); // max tokens that can accumulate (burst size)
}
public enum Tier implements TierPolicy {
FREE(10.0 / 60.0, 10), // 10 per minute, burst 10
PRO (1000.0 / 60.0, 1000); // 1000 per minute, burst 1000
private final double rate, cap;
Tier(double rate, double cap) { this.rate = rate; this.cap = cap; }
public double ratePerSec() { return rate; }
public double capacity() { return cap; }
}The bucket holds the mutable state. Note it does not know the policy — the limiter passes it in, so one bucket class serves every tier.
final class Bucket {
private double tokens;
private long lastRefillNanos;
Bucket(double initialTokens, long nowNanos) {
this.tokens = initialTokens;
this.lastRefillNanos = nowNanos;
}
/** Refill lazily, then take one token if available.
* Caller must hold this bucket's monitor — see the concurrency section. */
boolean tryConsume(TierPolicy policy, long nowNanos) {
refill(policy, nowNanos);
if (tokens >= 1.0) {
tokens -= 1.0;
return true;
}
return false;
}
private void refill(TierPolicy policy, long nowNanos) {
long elapsed = nowNanos - lastRefillNanos;
if (elapsed <= 0) return; // clock went backwards; do nothing
double added = (elapsed / 1_000_000_000.0) * policy.ratePerSec();
tokens = Math.min(policy.capacity(), tokens + added);
lastRefillNanos = nowNanos;
}
/** Seconds until at least one token is available. Drives Retry-After. */
double retryAfterSeconds(TierPolicy policy, long nowNanos) {
refill(policy, nowNanos);
if (tokens >= 1.0) return 0;
return (1.0 - tokens) / policy.ratePerSec();
}
boolean isFull(TierPolicy policy, long nowNanos) {
refill(policy, nowNanos);
return tokens >= policy.capacity();
}
}And the limiter that ties them together:
public class RateLimiter {
private final ConcurrentMap<String, Bucket> buckets = new ConcurrentHashMap<>();
private final Function<String, TierPolicy> tierOf; // userId -> policy
private final LongSupplier clock; // injected: nanoTime source
public RateLimiter(Function<String, TierPolicy> tierOf, LongSupplier clock) {
this.tierOf = tierOf;
this.clock = clock;
}
public boolean allow(String userId) {
TierPolicy policy = tierOf.apply(userId);
long now = clock.getAsLong();
// computeIfAbsent is atomic: two threads racing a new user get ONE bucket.
Bucket b = buckets.computeIfAbsent(userId,
k -> new Bucket(policy.capacity(), now));
// Lock the bucket, not the limiter: different users never contend.
synchronized (b) {
return b.tryConsume(policy, now);
}
}
public double retryAfterSeconds(String userId) {
Bucket b = buckets.get(userId);
if (b == null) return 0;
TierPolicy policy = tierOf.apply(userId);
synchronized (b) {
return b.retryAfterSeconds(policy, clock.getAsLong());
}
}
}Three decisions worth defending out loud.
clock is injected as a LongSupplier. In production you pass System::nanoTime; in a test you pass a counter you control, so "does a user get exactly 10 requests in a minute" becomes a deterministic assertion rather than a Thread.sleep. A time-dependent component that cannot be tested deterministically is one nobody can safely change.
Refill is lazy, computed on read. No background thread walks a million buckets adding tokens. elapsed x rate, clamped to capacity, O(1), and an idle user costs nothing until they return.
A new bucket starts full (new Bucket(policy.capacity(), now)). That is a deliberate choice: a first-time user gets their full burst immediately. Starting at zero would throttle every new user for their first window, which is almost never what anyone wants — but it is a choice, so say it.
The two races — this is the actual exercise
@@ 1 | The version almost everyone writes first
public boolean allow(String userId) {
Bucket b = buckets.get(userId);
refill(b);
if (b.tokens >= 1.0) { // (A) check
b.tokens -= 1.0; // (B) act
return true;
}
return false;
}@@ 2 | Two threads interleave between the check and the act
:::race The bug has a name This is check-then-act — the same shape as find-and-claim in the parking lot. Any time you read a value, make a decision from it, and write back based on that decision, the whole sequence has to be atomic or another thread can act inside the gap. :::
@@ 3 | Make check and act one atomic step
Three ways, ranked:
1. Lock the bucket (chosen).
Bucket b = buckets.computeIfAbsent(userId, k -> new Bucket(policy.capacity(), now));
synchronized (b) { // <-- per-user monitor
return b.tryConsume(policy, now); // refill + check + decrement, atomically
}Two different users hold two different monitors and never contend. Two threads for the same user serialise for a few nanoseconds. Simple and obviously correct.
:::key Why per-bucket and not per-limiter The state being protected is per-user, so the lock should be per-user. A lock on the limiter would make user A wait for user B for no reason — a global bottleneck guarding state that was never shared. :::
2. CAS loop — lock-free, if contention on one user is genuinely high.
final class AtomicBucket {
// tokens as fixed-point micro-tokens so we can CAS a single long
private final AtomicLong state = new AtomicLong(); // packed: tokens | timestamp
boolean tryConsume(TierPolicy p, long now) {
for (;;) {
long snapshot = state.get();
long refilled = computeRefilled(snapshot, p, now);
if (tokensOf(refilled) < 1_000_000L) return false; // < 1 token
long next = subtractOneToken(refilled, now);
if (state.compareAndSet(snapshot, next)) return true; // won the race
// lost: another thread moved first, recompute and retry
}
}
}Higher throughput when many threads hammer one key, materially harder to read. Reach for it only if the interviewer pushes on contention — and say that trade.
3. One lock on the whole limiter — wrong.
public synchronized boolean allow(String userId) { ... } // <-- global bottleneckEvery user now serialises against every other user to protect per-user state. Being able to say why this is wrong matters more than avoiding it by luck.
@@ 4 | The second race, which most candidates miss
Bucket b = buckets.get(userId);
if (b == null) { // both threads see null
b = new Bucket(policy.capacity(), now); // both construct
buckets.put(userId, b); // one silently overwrites
}Follow-ups they will ask
"Now make it work across 10 machines." The honest answer starts by naming what breaks: per-process buckets mean each machine admits the full limit, so a 10-machine fleet admits 10x. Options: (a) a shared store — Redis with an atomic INCR/Lua script, correct but adds a network hop to every request and a dependency that can fail; (b) allocate each machine limit/N and accept that an uneven load balancer under-admits; (c) approximate coordination — machines gossip counts periodically, converging but briefly wrong. State the trade: (a) costs latency and availability, (b) costs accuracy under skew, (c) costs simplicity. There is no free option and saying so is the answer.
"What does the client see?" 429 with Retry-After. Compute it from the bucket: seconds until one token refills. Cheap, and it is the difference between a limiter that protects you and one that causes a retry storm.
"Memory for millions of idle users?" The map grows forever. Evict buckets that are full and untouched for longer than a window — a full bucket is indistinguishable from a fresh one, so dropping it is free. That observation (full == absent) is the neat part, and it is a genuine invariant of the design rather than a trick.
"Per-endpoint limits too?" Key by (user, endpoint) and the model is unchanged — which is the point of keying rather than hardcoding. Mention the combinatorial memory growth before they do.
How to say it in the interview
"Four algorithms are plausible here and they differ in burst behaviour and memory, so I want to pick one by naming its failure mode. Then the real work: allow() is check-then-act, which is a race unless I make it atomic."
Checklist
- Chose an algorithm by naming its failure mode, not by naming the algorithm
- Said which different requirement would have changed the algorithm choice
- Injected the clock rather than calling wall-clock time inline
- Used lazy refill at read time instead of a background refill thread
- Identified allow() as check-then-act and made find-and-decrement atomic
- Also caught the create-on-first-use race and used atomic insert-if-missing
- Locked per bucket rather than per limiter
- For the distributed follow-up, named the cost of each option rather than picking one
- Noticed that a full bucket is indistinguishable from an absent one, making eviction free