Low Level Design (LLD) Interview Questions
Design a Rate Limiter
Tier: CommonDifficulty: MediumAsked of: Mid, SeniorAsked at: Stripe, Google, Amazon
There is one method, tryAcquire(key), and it answers yes or no. Every algorithm anyone has ever named for this problem is one implementation sitting behind that method, and the caller never learns which one answered. Say that in the first thirty seconds, because it is the shape of the design and everything else is detail hanging off it.
The algorithm you would actually ship is the token bucket, refilled lazily from elapsed time rather than by a timer thread. The reason to know the other three is that an interviewer will ask why not those, and the answer is a sentence each.
What this really tests
Three things. Whether you know the four algorithms well enough to say the tradeoff rather than the name. Whether the concurrency is per key rather than one lock across the process. And whether you noticed that a map from key to bucket, with user ids for keys, is a memory leak that nobody finds until the heap dump.
What to clarify first
Ask these before drawing anything. Two of them change which algorithm you pick.
- What is the key. Per user, per API key, per device, per endpoint, or a pair of those. This decides whether there is one bucket or millions.
- One process, or a fleet behind a load balancer. If it is a fleet, the state cannot live in a field, and you should say so early rather than be caught by it.
- Are short bursts acceptable. If yes, token bucket. If the thing downstream needs a flat rate, leaky bucket. This is the question that picks the algorithm.
- Does every request cost one. A batch upload of forty events should probably cost forty, and that changes the method signature.
- What should a refused caller do. If it should back off, the refusal has to carry a number, which is why the return type is not a boolean.
- One rule for everyone, or tiers. Free and paid plans mean the rule is looked up per key rather than baked into the limiter.
- If the limiter itself is broken, fail open or fail closed. Ask it out loud. Most people want fail open, and nobody writes it down.
The one interface, and why the answer is a type
tryAcquire(key) returns a Decision, not a boolean. That is the smallest decision here and it earns the most.
A boolean tells the caller it was refused and nothing else, so the caller invents a retry delay. Every client inventing the same delay is how a backend gets hit by a synchronised stampede one second later. A rejection that carries retry after turns a refusal into a schedule. The caller sleeps, or backs off, or hands the number to whatever runs work later, and the server puts the same number in a Retry-After header.
The allowed case carries the count still left in the budget, which is the other half of what a well behaved client wants.
Time is a parameter, not something you read
Nothing in the design calls the system clock. A Clock goes in at construction, the limiter reads it once per request, and hands that instant to whichever bucket answers.
This is not testing theatre. A rate limiter is almost entirely time arithmetic, and the interesting cases are all at boundaries. Without an injectable clock, a test of a one minute window takes a minute, a test of the exact millisecond a window rolls is a coin toss, and you end up not writing them. With ManualClock, an hour of traffic runs in a microsecond and the fixed window boundary burst is a test that either passes or fails rather than a claim.
Use a monotonic source in production, not wall clock time. Wall clock steps backwards whenever a device corrects itself against a time server, and a limiter that sees time run backwards either locks everyone out until the clock catches up or hands out a free window.
The same idea removes the timer. A naive token bucket starts a scheduled task per bucket to add tokens. With a million keys that is a million timers. Instead the bucket stores the instant it was last touched, and on the next request it works out how much refill it missed and adds that, capped at the bucket size. An idle bucket runs no code at all.
The four algorithms, and which one to ship
- FixedWindowCounter. Chop time into aligned windows, count inside the current one, reset when it rolls. Two numbers per key whatever the traffic. The flaw is the boundary burst. A hundred requests in the last millisecond of one window and a hundred in the first millisecond of the next is two hundred requests in two milliseconds, and the counter is perfectly happy, because it saw a hundred and then a hundred. The limit as written is honoured and the limit as meant is doubled.
- SlidingWindowLog. Keep a timestamp for every request still inside the window and drop the ones that aged out. The size of what is left is the answer. It is exactly right, there is no boundary because there is no boundary, and retry after is exact because you know the precise moment the oldest request falls out. It also costs one timestamp per request per key, so ten thousand per minute means ten thousand timestamps held for a minute for every key, and the limiter becomes the biggest thing in the process.
- SlidingWindowCounter. The compromise, and what most large services actually run. Keep the count for this window and the previous one, and weight the previous count by how much of it is still inside the last window's worth of time. Thirty seconds into a one minute window, eighty last minute and twenty this minute reads as sixty. Three numbers per key, no boundary burst. It is an estimate, and its assumption is that the previous window's traffic was spread evenly, which it was not. The error is small and it is in the safe direction.
- TokenBucket. The one to ship. A bucket holds up to a limit's worth of tokens, tokens arrive at a steady rate, a request costs one. A client that has been quiet has a full bucket and may burst. A client that is hammering runs it dry and is metered at the refill rate. That is the behaviour people actually want, and neither window algorithm gives it to you.
LeakyBucket is the token bucket read backwards, and it deserves one paragraph rather than a section. Requests fill a bucket and drain out at a fixed rate. The arithmetic mirrors the token bucket, which is why the two get confused, and the difference that matters is intent. A token bucket lets an idle client spend its saved credit all at once, so a burst gets through. A leaky bucket used as a queue never lets a burst through, it holds requests and releases them at the drain rate, so whatever is downstream sees a flat line. Pick it when the thing you are protecting cares about the shape of the traffic and not just the total.
One trap inside the token bucket is worth naming, because it is a real bug that hides for weeks. Keep tokens as a fractional number. One token per ten seconds is a ten thousandth of a token per millisecond, and if you truncate that to a whole number on every refill while still moving the timestamp forward, a client polling once a second adds zero tokens forever and the bucket never refills.
The classes
Small design, and every class here is carrying something.
- RateLimiter is the interface, and it has one method. Everything else in the design is private to it.
- Decision is the result, allowed with what is left or rejected with how long to wait. Sealed, so a third outcome later is a compile error at every call site rather than a silent default branch.
- Rule is the limit as one value, so many permits inside so long a window. Two loose numbers travelling separately is two chances to pair the wrong pair, and several algorithms need the ratio of the two.
- Clock is the time source, one method. ManualClock is the test one that moves only when a test moves it.
- RateLimitAlgorithm is the strategy and the only extension point. One instance holds the state of one key, time arrives as a parameter, and each implementation owns its own thread safety.
- FixedWindowCounter, SlidingWindowLog, SlidingWindowCounter, TokenBucket and LeakyBucket are the five implementations. None of them knows about keys, maps or eviction, which is why each is thirty lines.
- KeyedRateLimiter is the map from key to bucket, plus the eviction. It takes a factory for new buckets, so changing the whole fleet from a fixed window to a token bucket is one lambda at the wiring site and no class in the package changes.
The one method on the strategy that is not obvious is the idle check. A bucket is idle when it holds nothing that could change a future answer, a refilled token bucket, an expired window, an empty log. Eviction that only removes idle buckets can never accidentally forgive a client, which is what makes it safe to run on a timer nobody supervises.
One request, walked through
A token bucket of ten per second, and a client that has been quiet for a while.
- The limiter reads the clock once. Every decision in this request is now made against one instant, so two buckets consulted in the same request can never disagree about what time it is.
- It looks the key up in a concurrent map, creating a bucket if this key has never been seen. Two threads racing for the same new key get the same bucket back, which is the one thing the map has to guarantee.
- Before the lookup it checks whether an eviction sweep is due, and at most one thread wins that check. A sweep is a walk of the map dropping idle buckets, and it is the only reason the map does not grow forever.
- The bucket reads its own state, one value holding the token count and the instant it was last touched.
- It works out the refill. Elapsed time times the refill rate, added to the tokens, capped at the bucket size. Nothing was scheduled and no thread woke up to do this.
- There is at least one token, so it builds the next state with one token removed and swaps it in with a compare and set. If another thread got there first, the swap fails, the whole calculation is thrown away and it goes round again from step four.
- It returns allowed, carrying the tokens still in the bucket.
- Had the bucket been dry, it would have divided the missing tokens by the refill rate and returned rejected with that many milliseconds. Nothing is written on a rejection, so a client already being refused cannot contend with anybody.
Patterns actually used
Strategy, and only strategy. The algorithm is the axis this design is meant to change on, and every one of the five is a class behind one interface. The interviewer will change the algorithm on you, and the correct answer is a new class and no edits.
Say what you are leaving out, because that reads as more senior than naming one more pattern.
- No singleton. A limiter is a dependency you pass in. Making it a global costs you the test that wants two limiters with different rules and a fake clock, and buys nothing that the code wiring the application up cannot do.
- No factory class. The thing that makes new buckets is a supplier in Java and a function type in Kotlin. Wrapping a one method lambda in an interface called BucketFactory is a class that adds a name and nothing else.
- No decorator stack. It is tempting to layer a per user limiter over a per endpoint limiter over a global one. If you need two limits, ask both and refuse if either refuses. That is a loop over a list, not a pattern.
- No observer for metrics. Real limiters do emit counters, and a listener is the obvious way to do it. It is also decoration in an interview unless you are asked, so mention it and move on.
The implementation
Both trees carry the same design. Java uses a sealed interface with records for the result and a Supplier for the bucket factory. The Kotlin is shorter for reasons that are not cosmetic. The result is a sealed interface with data classes, so an exhaustive when covers it. The two units, milliseconds and permits, are value classes, which costs nothing at runtime and stops a caller passing seconds where milliseconds were meant. The bucket factory is a function type. The clock is a fun interface, so a clock is a lambda. And the algorithms that live in one file each in Java share a file in Kotlin, because thirty lines with no getters does not need its own.
Java
com.androidinterview.ratelimiter.KeyedRateLimiter.java
package com.androidinterview.ratelimiter;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicLong;
import java.util.function.Supplier;
import com.androidinterview.ratelimiter.algorithm.RateLimitAlgorithm;
import com.androidinterview.ratelimiter.core.Clock;
import com.androidinterview.ratelimiter.core.Decision;
// A limit is never global, it is per user, per API key, per device, per
// endpoint. So the limiter is a map from key to one bucket.
//
// The supplier is the seam. Swapping the whole fleet from a fixed window to a
// token bucket is one lambda at the construction site.
public final class KeyedRateLimiter implements RateLimiter {
private final Clock clock;
private final Supplier<RateLimitAlgorithm> newBucket;
private final long sweepEveryMillis;
private final ConcurrentHashMap<String, RateLimitAlgorithm> buckets = new ConcurrentHashMap<>();
private final AtomicLong nextSweepMillis;
public KeyedRateLimiter(Clock clock, Supplier<RateLimitAlgorithm> newBucket) {
this(clock, newBucket, 60_000L);
}
public KeyedRateLimiter(Clock clock, Supplier<RateLimitAlgorithm> newBucket, long sweepEveryMillis) {
this.clock = clock;
this.newBucket = newBucket;
this.sweepEveryMillis = sweepEveryMillis;
this.nextSweepMillis = new AtomicLong(clock.nowMillis() + sweepEveryMillis);
}
@Override
public Decision tryAcquire(String key) {
return tryAcquire(key, 1);
}
// Notice what is not here. There is no lock in this method. The map is a
// ConcurrentHashMap so two threads racing for the same new key get the same
// bucket back, and the bucket owns whatever locking it needs. One lock
// across every key would serialise the whole process behind the busiest
// client, which is the opposite of what a limiter is for.
//
// The clock is read once, so every decision in one request is made against
// one instant.
@Override
public Decision tryAcquire(String key, int permits) {
long now = clock.nowMillis();
sweepIfDue(now);
return buckets.computeIfAbsent(key, ignored -> newBucket.get()).tryAcquire(now, permits);
}
public int size() {
return buckets.size();
}
// Idle buckets carry no information, so removing them is free. Without
// this the map is a slow leak, one entry per key ever seen, and the keys
// are user ids.
//
// There is a race and it is harmless. A thread can read a bucket out of
// the map, get descheduled, and use it after the sweep removed it. That
// request is counted against an object nobody else can see, but the bucket
// was idle, so a fresh one would have allowed the same request anyway.
public int evictIdle(long nowMillis) {
int before = buckets.size();
buckets.entrySet().removeIf(entry -> entry.getValue().isIdle(nowMillis));
return before - buckets.size();
}
// One sweep per interval across all threads. The compare and set is what
// stops fifty threads sweeping at once the moment the interval passes.
private void sweepIfDue(long nowMillis) {
long due = nextSweepMillis.get();
if (nowMillis < due || !nextSweepMillis.compareAndSet(due, nowMillis + sweepEveryMillis)) {
return;
}
evictIdle(nowMillis);
}
}
com.androidinterview.ratelimiter.RateLimiter.java
package com.androidinterview.ratelimiter;
import com.androidinterview.ratelimiter.core.Decision;
// The whole public surface. A caller never learns whether it is talking to a
// token bucket, a sliding window or a Redis script, which is what lets the
// algorithm be swapped in one line.
public interface RateLimiter {
Decision tryAcquire(String key);
// Several permits at once, for a batch that should cost what it costs.
// More permits than the limit itself throws, because waiting cannot fix it.
Decision tryAcquire(String key, int permits);
}
com.androidinterview.ratelimiter.algorithm.FixedWindowCounter.java
package com.androidinterview.ratelimiter.algorithm;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
// Two numbers per key whatever the traffic, and a boundary burst. A hundred
// requests in the last millisecond of one window and a hundred in the first
// millisecond of the next is two hundred inside two milliseconds, and the
// counter sees nothing wrong because it saw a hundred and then a hundred.
public final class FixedWindowCounter implements RateLimitAlgorithm {
private final Rule rule;
private long windowStart;
private int used;
public FixedWindowCounter(Rule rule) {
this.rule = rule;
}
@Override
public synchronized Decision tryAcquire(long nowMillis, int permits) {
RateLimitAlgorithm.checkPermits(permits, rule);
roll(nowMillis);
if (used + permits <= rule.permits()) {
used += permits;
return new Decision.Allowed(rule.permits() - used);
}
// Nothing can help before the window turns over, so that is the wait.
return new Decision.Rejected(windowStart + rule.windowMillis() - nowMillis);
}
// Aligned to the epoch rather than to the first request, so every key rolls
// at the same instant. That makes the boundary burst reproducible instead
// of random, which is what you want from a bug you decided to live with.
private void roll(long nowMillis) {
long start = nowMillis - Math.floorMod(nowMillis, rule.windowMillis());
if (start != windowStart) {
windowStart = start;
used = 0;
}
}
@Override
public synchronized boolean isIdle(long nowMillis) {
return nowMillis - windowStart >= rule.windowMillis();
}
}
com.androidinterview.ratelimiter.algorithm.LeakyBucket.java
package com.androidinterview.ratelimiter.algorithm;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
// The token bucket read backwards, and the arithmetic mirrors it, which is why
// the two get confused. The difference is intent. A token bucket lets an idle
// client spend saved credit all at once, a leaky bucket used as a queue never
// lets a burst through at all, so whatever is downstream sees a flat line.
//
// This is the metering version. Parking requests instead of refusing them
// means owning a queue, a timer and a story about a full queue, and none of
// that belongs behind a method that answers yes or no.
public final class LeakyBucket implements RateLimitAlgorithm {
private final Rule rule;
private final double capacity;
private final double leakPerMillis;
private double level;
private long lastLeakMillis;
public LeakyBucket(Rule rule, long startMillis) {
this.rule = rule;
this.capacity = rule.permits();
this.leakPerMillis = rule.permitsPerMillis();
this.lastLeakMillis = startMillis;
}
@Override
public synchronized Decision tryAcquire(long nowMillis, int permits) {
RateLimitAlgorithm.checkPermits(permits, rule);
leak(nowMillis);
if (level + permits <= capacity) {
level += permits;
return new Decision.Allowed((int) Math.floor(capacity - level));
}
double overflow = level + permits - capacity;
long wait = (long) Math.ceil(overflow / leakPerMillis);
return new Decision.Rejected(Math.max(1L, wait));
}
private void leak(long nowMillis) {
long elapsed = nowMillis - lastLeakMillis;
if (elapsed <= 0) {
return;
}
level = Math.max(0.0, level - elapsed * leakPerMillis);
lastLeakMillis = nowMillis;
}
@Override
public synchronized boolean isIdle(long nowMillis) {
return level - (nowMillis - lastLeakMillis) * leakPerMillis <= 0.0;
}
}
com.androidinterview.ratelimiter.algorithm.RateLimitAlgorithm.java
package com.androidinterview.ratelimiter.algorithm;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
// The strategy, and the only extension point in the design. One instance holds
// the state of one key.
//
// Time arrives as a parameter rather than being read inside, so the caller
// reads the clock once per request and every implementation agrees on what now
// means. Each implementation owns its own thread safety, because the lock that
// matters is the one around a single key.
public interface RateLimitAlgorithm {
Decision tryAcquire(long nowMillis, int permits);
// True when this bucket holds no state that could change a future answer,
// so a fresh one would give the same result. Eviction that only removes
// idle buckets cannot forgive anybody.
boolean isIdle(long nowMillis);
// A request bigger than the whole limit can never be served however long
// the caller waits, so it is a bug and not a rate limit decision.
static void checkPermits(int permits, Rule rule) {
if (permits <= 0 || permits > rule.permits()) {
throw new IllegalArgumentException(
permits + " permits can never fit a limit of " + rule.permits());
}
}
}
com.androidinterview.ratelimiter.algorithm.SlidingWindowCounter.java
package com.androidinterview.ratelimiter.algorithm;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
// The compromise, and the one most large services run. Weight the previous
// window's count by how much of it is still inside the last window's worth of
// time. Thirty seconds into a minute, eighty last minute and twenty this
// minute reads as sixty. Three numbers per key, and no boundary burst. It
// assumes the previous window's traffic was spread evenly, which it was not,
// and the error is small and in the safe direction.
public final class SlidingWindowCounter implements RateLimitAlgorithm {
private final Rule rule;
private long windowStart;
private int current;
private int previous;
public SlidingWindowCounter(Rule rule) {
this.rule = rule;
}
@Override
public synchronized Decision tryAcquire(long nowMillis, int permits) {
RateLimitAlgorithm.checkPermits(permits, rule);
roll(nowMillis);
double estimate = estimate(nowMillis);
if (estimate + permits <= rule.permits()) {
current += permits;
return new Decision.Allowed((int) Math.floor(rule.permits() - estimate - permits));
}
return new Decision.Rejected(retryAfter(nowMillis, permits));
}
// Rolling one window forward carries current back into previous. Rolling
// further means the key went quiet for a whole window, so both go to zero.
private void roll(long nowMillis) {
long start = nowMillis - Math.floorMod(nowMillis, rule.windowMillis());
if (start == windowStart) {
return;
}
previous = (start - windowStart == rule.windowMillis()) ? current : 0;
current = 0;
windowStart = start;
}
private double estimate(long nowMillis) {
long elapsed = nowMillis - windowStart;
double weight = (rule.windowMillis() - elapsed) / (double) rule.windowMillis();
return previous * weight + current;
}
// Waiting works by letting the previous window's weight fall, so solve for
// the weight at which this request fits and turn it back into a time. When
// the current window alone is already over, or there is no previous window
// to shrink, only the next window helps.
private long retryAfter(long nowMillis, int permits) {
long window = rule.windowMillis();
long elapsed = nowMillis - windowStart;
double headroom = rule.permits() - current - permits;
if (headroom <= 0 || previous == 0) {
return window - elapsed;
}
double allowedWeight = headroom / previous;
long needed = (long) Math.ceil(window * (1.0 - allowedWeight));
return Math.max(1L, needed - elapsed);
}
@Override
public synchronized boolean isIdle(long nowMillis) {
return nowMillis - windowStart >= 2L * rule.windowMillis();
}
}
com.androidinterview.ratelimiter.algorithm.SlidingWindowLog.java
package com.androidinterview.ratelimiter.algorithm;
import java.util.ArrayDeque;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
// Exactly right, and that is its only argument. No boundary burst, and retry
// after is exact. It also costs one timestamp per request per key held for a
// whole window, which is why nobody ships it at scale.
public final class SlidingWindowLog implements RateLimitAlgorithm {
private final Rule rule;
private final ArrayDeque<Long> hits = new ArrayDeque<>();
public SlidingWindowLog(Rule rule) {
this.rule = rule;
}
@Override
public synchronized Decision tryAcquire(long nowMillis, int permits) {
RateLimitAlgorithm.checkPermits(permits, rule);
prune(nowMillis);
if (hits.size() + permits <= rule.permits()) {
for (int i = 0; i < permits; i++) {
hits.addLast(nowMillis);
}
return new Decision.Allowed(rule.permits() - hits.size());
}
// How many of the oldest hits have to age out before this request
// fits, and when the last of those ages out.
int mustExpire = hits.size() + permits - rule.permits();
return new Decision.Rejected(oldest(mustExpire - 1) + rule.windowMillis() - nowMillis);
}
// A hit at t leaves at exactly t plus the window. Rejected requests are
// never logged. Logging them would let a client already being refused push
// its own recovery further away every time it retried.
private void prune(long nowMillis) {
long cutoff = nowMillis - rule.windowMillis();
while (!hits.isEmpty() && hits.peekFirst() <= cutoff) {
hits.pollFirst();
}
}
private long oldest(int index) {
int i = 0;
for (long hit : hits) {
if (i++ == index) {
return hit;
}
}
throw new IllegalStateException("no hit at index " + index);
}
@Override
public synchronized boolean isIdle(long nowMillis) {
prune(nowMillis);
return hits.isEmpty();
}
}
com.androidinterview.ratelimiter.algorithm.TokenBucket.java
package com.androidinterview.ratelimiter.algorithm;
import java.util.concurrent.atomic.AtomicReference;
import com.androidinterview.ratelimiter.core.Decision;
import com.androidinterview.ratelimiter.core.Rule;
// The one to ship. A bucket holds up to a limit's worth of tokens, tokens
// arrive at a steady rate, a request costs one. A quiet client has a full
// bucket and may burst, a hammering client runs it dry and is metered at the
// refill rate. Neither window algorithm gives you that.
//
// The refill is lazy. No timer, no scheduled executor, no thread per bucket.
// A request looks at how long it has been since the last one and adds that
// much refill, capped at the bucket size, so an idle bucket runs no code.
//
// Tokens are a double. One token per ten seconds is a ten thousandth of a
// token per millisecond, and truncating that to a whole number on every call
// means a client polling once a second adds zero tokens forever while the
// timestamp keeps moving. The bucket never refills and nobody can work out why.
public final class TokenBucket implements RateLimitAlgorithm {
// The pair that has to change together. One immutable value means the
// update is a single reference swap, which is what makes it lock free.
private record State(double tokens, long atMillis) {}
private final Rule rule;
private final double capacity;
private final double perMillis;
private final AtomicReference<State> state;
public TokenBucket(Rule rule, long startMillis) {
this.rule = rule;
this.capacity = rule.permits();
this.perMillis = rule.permitsPerMillis();
this.state = new AtomicReference<>(new State(capacity, startMillis));
}
// Lock free, and the loop is the whole trick. Read the state, work out what
// it should be now, and swap it in only if nobody changed it first. If
// somebody did, the read is stale, so throw the answer away and go round
// again. A rejection writes nothing, so a refused client contends with
// nobody.
@Override
public Decision tryAcquire(long nowMillis, int permits) {
RateLimitAlgorithm.checkPermits(permits, rule);
while (true) {
State seen = state.get();
State filled = refill(seen, nowMillis);
if (filled.tokens() < permits) {
double missing = permits - filled.tokens();
long wait = (long) Math.ceil(missing / perMillis);
return new Decision.Rejected(Math.max(1L, wait));
}
State next = new State(filled.tokens() - permits, filled.atMillis());
if (state.compareAndSet(seen, next)) {
return new Decision.Allowed((int) Math.floor(next.tokens()));
}
}
}
private State refill(State seen, long nowMillis) {
long elapsed = nowMillis - seen.atMillis();
if (elapsed <= 0) {
return seen;
}
return new State(Math.min(capacity, seen.tokens() + elapsed * perMillis), nowMillis);
}
// A full bucket is indistinguishable from one never used, so it can be
// thrown away without forgiving anybody.
@Override
public boolean isIdle(long nowMillis) {
return refill(state.get(), nowMillis).tokens() >= capacity;
}
}
com.androidinterview.ratelimiter.core.Clock.java
package com.androidinterview.ratelimiter.core;
// Nothing in this package reads the system time directly. A limiter that calls
// the clock inside itself can only be tested by sleeping, so a test of a one
// minute window takes a minute and a boundary test is a coin toss.
@FunctionalInterface
public interface Clock {
long nowMillis();
// Monotonic on purpose. Wall clock time steps backwards whenever the
// device corrects itself against a time server, and a limiter that sees
// time run backwards either locks everyone out or hands out a free window.
Clock SYSTEM = () -> System.nanoTime() / 1_000_000L;
}
com.androidinterview.ratelimiter.core.Decision.java
package com.androidinterview.ratelimiter.core;
// The answer, and the reason it is a type rather than a boolean. A boolean
// makes the caller invent a retry delay, and every client inventing the same
// delay is how a backend gets a synchronised stampede. Carrying retryAfter
// turns a refusal into a schedule.
public sealed interface Decision {
boolean allowed();
// Zero when allowed. How long until this request could succeed otherwise.
long retryAfterMillis();
// What a server would put in an X-RateLimit-Remaining header.
record Allowed(int remaining) implements Decision {
@Override
public boolean allowed() {
return true;
}
@Override
public long retryAfterMillis() {
return 0L;
}
}
record Rejected(long retryAfterMillis) implements Decision {
@Override
public boolean allowed() {
return false;
}
}
}
com.androidinterview.ratelimiter.core.ManualClock.java
package com.androidinterview.ratelimiter.core;
// The clock the tests use. Time moves only when a test moves it, so an hour of
// traffic runs in a microsecond and a boundary is checked at the exact
// millisecond. This is what makes the fixed window burst demonstrable rather
// than something to take on faith.
public final class ManualClock implements Clock {
private long nowMillis;
public ManualClock() {
this(0L);
}
public ManualClock(long startMillis) {
this.nowMillis = startMillis;
}
@Override
public synchronized long nowMillis() {
return nowMillis;
}
public synchronized void advance(long millis) {
nowMillis += millis;
}
}
com.androidinterview.ratelimiter.core.Rule.java
package com.androidinterview.ratelimiter.core;
// The limit as one value. Every algorithm needs both numbers and several need
// the ratio, so a loose int and a loose long travelling separately is two
// chances to pair the wrong pair.
public record Rule(int permits, long windowMillis) {
public Rule {
if (permits <= 0) {
throw new IllegalArgumentException("permits must be positive, got " + permits);
}
if (windowMillis <= 0) {
throw new IllegalArgumentException("window must be positive, got " + windowMillis);
}
}
// The refill and leak rate. A double on purpose. One permit per ten
// seconds is 0.0001 per millisecond, and rounding that to a whole number
// is how a slow bucket never refills at all.
public double permitsPerMillis() {
return (double) permits / windowMillis;
}
public static Rule perSecond(int permits) {
return new Rule(permits, 1_000L);
}
public static Rule perMinute(int permits) {
return new Rule(permits, 60_000L);
}
}
Kotlin
com.androidinterview.ratelimiter.RateLimiter.kt
package com.androidinterview.ratelimiter
import com.androidinterview.ratelimiter.algorithm.RateLimitAlgorithm
import com.androidinterview.ratelimiter.core.Clock
import com.androidinterview.ratelimiter.core.Decision
import com.androidinterview.ratelimiter.core.Millis
import java.util.concurrent.ConcurrentHashMap
import java.util.concurrent.atomic.AtomicLong
// The whole public surface. A default argument covers the common call, so
// tryAcquire("user-42") is what almost every caller writes and the batch case
// is still there when a flush of forty events should cost forty.
interface RateLimiter {
fun tryAcquire(key: String, permits: Int = 1): Decision
}
// A limit is never global, it is per user, per API key, per device, per
// endpoint. So the limiter is a map from key to one bucket.
//
// newBucket is the seam, and in Kotlin it is a function type rather than a
// factory interface. Swapping the fleet from a fixed window to a token bucket
// is one lambda at the construction site.
class KeyedRateLimiter(
private val clock: Clock,
private val sweepEvery: Millis = Millis(60_000),
private val newBucket: () -> RateLimitAlgorithm,
) : RateLimiter {
private val buckets = ConcurrentHashMap<String, RateLimitAlgorithm>()
private val nextSweep = AtomicLong(clock.now().value + sweepEvery.value)
val size get() = buckets.size
// Notice what is not here. There is no lock in this method. The map is a
// ConcurrentHashMap, so two threads racing for the same new key get the
// same bucket back, and the bucket owns whatever locking it needs. One lock
// across every key would serialise the whole process behind the busiest
// client, which is the opposite of what a limiter is for. The clock is read
// once, so every decision in one request is made against one instant.
override fun tryAcquire(key: String, permits: Int): Decision {
val now = clock.now()
sweepIfDue(now)
return buckets.computeIfAbsent(key) { newBucket() }.tryAcquire(now, permits)
}
// Idle buckets carry no information, so removing them is free. Without this
// the map is a slow leak, one entry for every key ever seen, and the keys
// are user ids.
//
// There is a race and it is harmless. A thread can read a bucket out of the
// map, get descheduled, and use it after the sweep removed it. That request
// is counted against an object nobody else can see, but the bucket was
// idle, so a fresh one would have allowed the same request anyway.
fun evictIdle(now: Millis = clock.now()): Int {
val before = buckets.size
buckets.entries.removeIf { it.value.isIdle(now) }
return before - buckets.size
}
// One sweep per interval across all threads. The compare and set is what
// stops fifty threads sweeping at once the moment the interval passes.
private fun sweepIfDue(now: Millis) {
val due = nextSweep.get()
if (now.value < due || !nextSweep.compareAndSet(due, now.value + sweepEvery.value)) return
evictIdle(now)
}
}
com.androidinterview.ratelimiter.algorithm.RateLimitAlgorithm.kt
package com.androidinterview.ratelimiter.algorithm
import com.androidinterview.ratelimiter.core.Decision
import com.androidinterview.ratelimiter.core.Millis
import com.androidinterview.ratelimiter.core.Permits
import com.androidinterview.ratelimiter.core.Rule
import kotlin.math.ceil
import kotlin.math.floor
import kotlin.math.max
// The strategy, and the only extension point. One instance holds the state of
// one key. Time arrives as a parameter, so the caller reads the clock once per
// request and every implementation agrees on what now means, and each owns its
// own thread safety, because the lock that matters is per key.
interface RateLimitAlgorithm {
fun tryAcquire(now: Millis, permits: Int = 1): Decision
// True when this bucket holds no state that could change a future answer.
// Eviction that only removes idle buckets cannot forgive anybody.
fun isIdle(now: Millis): Boolean
}
// A request bigger than the whole limit can never be served however long the
// caller waits, so it is a bug and not a rate limit decision.
internal fun Rule.checkPermits(permits: Int) {
require(permits in 1..limit) { "$permits permits can never fit a limit of $limit" }
}
// Aligned to the epoch rather than to the first request, so every key rolls at
// the same instant. That makes the boundary burst reproducible instead of
// random, which is what you want from a bug you decided to live with.
internal fun Rule.windowStartAt(now: Millis) = now.value - Math.floorMod(now.value, windowMillis)
// Two numbers per key whatever the traffic, and a boundary burst. A hundred
// requests in the last millisecond of one window and a hundred in the first
// millisecond of the next is two hundred inside two milliseconds, and the
// counter sees nothing wrong because it saw a hundred and then a hundred.
class FixedWindowCounter(private val rule: Rule) : RateLimitAlgorithm {
private var windowStart = 0L
private var used = 0
@Synchronized
override fun tryAcquire(now: Millis, permits: Int): Decision {
rule.checkPermits(permits)
roll(now)
if (used + permits > rule.limit) {
// Nothing helps before the window turns over, so that is the wait.
return Decision.Rejected(Millis(windowStart + rule.windowMillis - now.value))
}
used += permits
return Decision.Allowed(Permits(rule.limit - used))
}
private fun roll(now: Millis) {
val start = rule.windowStartAt(now)
if (start != windowStart) {
windowStart = start
used = 0
}
}
@Synchronized
override fun isIdle(now: Millis) = now.value - windowStart >= rule.windowMillis
}
// Exactly right, and that is its only argument. No boundary burst, and retry
// after is exact. It also costs one timestamp per request per key held for a
// whole window, which is why nobody ships it at scale.
class SlidingWindowLog(private val rule: Rule) : RateLimitAlgorithm {
private val hits = ArrayDeque<Long>()
@Synchronized
override fun tryAcquire(now: Millis, permits: Int): Decision {
rule.checkPermits(permits)
prune(now)
if (hits.size + permits > rule.limit) {
// How many of the oldest hits must age out before this fits, and
// when the last of those goes.
val mustExpire = hits.size + permits - rule.limit
val leavesAt = hits[mustExpire - 1] + rule.windowMillis
return Decision.Rejected(Millis(leavesAt - now.value))
}
repeat(permits) { hits.addLast(now.value) }
return Decision.Allowed(Permits(rule.limit - hits.size))
}
// A hit at t leaves at exactly t plus the window. Rejected requests are
// never logged. Logging them would let a client already being refused push
// its own recovery further away every time it retried.
private fun prune(now: Millis) {
val cutoff = now.value - rule.windowMillis
while (hits.isNotEmpty() && hits.first() <= cutoff) hits.removeFirst()
}
@Synchronized
override fun isIdle(now: Millis): Boolean {
prune(now)
return hits.isEmpty()
}
}
// The compromise, and the one most large services run. Weight the previous
// window's count by how much of it is still inside the last window's worth of
// time. Thirty seconds into a minute, eighty last minute and twenty this
// minute reads as sixty. Three numbers per key, and no boundary burst. It
// assumes the previous window's traffic was spread evenly, which it was not,
// and the error is small and in the safe direction.
class SlidingWindowCounter(private val rule: Rule) : RateLimitAlgorithm {
private var windowStart = 0L
private var current = 0
private var previous = 0
@Synchronized
override fun tryAcquire(now: Millis, permits: Int): Decision {
rule.checkPermits(permits)
roll(now)
val estimate = estimate(now)
if (estimate + permits > rule.limit) {
return Decision.Rejected(retryAfter(now, permits))
}
current += permits
return Decision.Allowed(Permits(floor(rule.limit - estimate - permits).toInt()))
}
// Rolling one window forward carries current back into previous. Rolling
// further means the key went quiet for a whole window, so both go to zero.
private fun roll(now: Millis) {
val start = rule.windowStartAt(now)
if (start == windowStart) return
previous = if (start - windowStart == rule.windowMillis) current else 0
current = 0
windowStart = start
}
private fun estimate(now: Millis): Double {
val elapsed = now.value - windowStart
return previous * ((rule.windowMillis - elapsed) / rule.windowMillis.toDouble()) + current
}
// Waiting works by letting the previous window's weight fall, so solve for
// the weight at which this request fits and turn it back into a time. With
// the current window already over, or no previous window to shrink, only
// the next window helps.
private fun retryAfter(now: Millis, permits: Int): Millis {
val elapsed = now.value - windowStart
val headroom = rule.limit - current - permits
if (headroom <= 0 || previous == 0) return Millis(rule.windowMillis - elapsed)
val needed = ceil(rule.windowMillis * (1.0 - headroom.toDouble() / previous)).toLong()
return Millis(max(1L, needed - elapsed))
}
@Synchronized
override fun isIdle(now: Millis) = now.value - windowStart >= 2 * rule.windowMillis
}
// The token bucket read backwards, and the arithmetic mirrors it, which is why
// the two get confused. The difference is intent. A token bucket lets an idle
// client spend saved credit all at once, a leaky bucket used as a queue never
// lets a burst through at all, so whatever is downstream sees a flat line.
//
// This is the metering version. Parking requests instead of refusing them
// means owning a queue, a timer and a story about a full queue, and none of
// that belongs behind a method that answers yes or no.
class LeakyBucket(private val rule: Rule, start: Millis) : RateLimitAlgorithm {
private val capacity = rule.limit.toDouble()
private var level = 0.0
private var lastLeak = start.value
@Synchronized
override fun tryAcquire(now: Millis, permits: Int): Decision {
rule.checkPermits(permits)
leak(now)
val overflow = level + permits - capacity
if (overflow > 0) {
return Decision.Rejected(Millis(max(1L, ceil(overflow / rule.perMillis).toLong())))
}
level += permits
return Decision.Allowed(Permits(floor(capacity - level).toInt()))
}
private fun leak(now: Millis) {
val elapsed = now.value - lastLeak
if (elapsed <= 0) return
level = max(0.0, level - elapsed * rule.perMillis)
lastLeak = now.value
}
@Synchronized
override fun isIdle(now: Millis) = level - (now.value - lastLeak) * rule.perMillis <= 0.0
}
com.androidinterview.ratelimiter.algorithm.TokenBucket.kt
package com.androidinterview.ratelimiter.algorithm
import com.androidinterview.ratelimiter.core.Decision
import com.androidinterview.ratelimiter.core.Millis
import com.androidinterview.ratelimiter.core.Permits
import com.androidinterview.ratelimiter.core.Rule
import java.util.concurrent.atomic.AtomicReference
import kotlin.math.ceil
import kotlin.math.floor
import kotlin.math.max
import kotlin.math.min
// The one to ship. A bucket holds up to a limit's worth of tokens, tokens
// arrive at a steady rate, a request costs one. A quiet client has a full
// bucket and may burst, a hammering client runs it dry and is metered at the
// refill rate. Neither window algorithm gives you that.
//
// The refill is lazy. No timer, no scheduled executor, no thread per bucket.
// A request looks at how long it has been since the last one and adds that
// much refill, capped at the bucket size, so an idle bucket runs no code.
//
// Tokens are a Double. One token per ten seconds is a ten thousandth of a
// token per millisecond, and truncating that to a whole number on every call
// means a client polling once a second adds zero tokens forever while the
// timestamp keeps moving. The bucket never refills and nobody can work out why.
class TokenBucket(private val rule: Rule, start: Millis) : RateLimitAlgorithm {
// The pair that has to change together. One immutable value means the
// update is a single reference swap, which is what makes it lock free.
private data class State(val tokens: Double, val at: Long)
private val capacity = rule.limit.toDouble()
private val state = AtomicReference(State(capacity, start.value))
// Lock free, and the loop is the whole trick. Read the state, work out what
// it should be now, and swap it in only if nobody changed it first. If
// somebody did, the read is stale, so throw the answer away and go round
// again. A rejection writes nothing, so a refused client contends with
// nobody.
override fun tryAcquire(now: Millis, permits: Int): Decision {
rule.checkPermits(permits)
while (true) {
val seen = state.get()
val filled = seen.refilled(now)
if (filled.tokens < permits) {
val missing = permits - filled.tokens
return Decision.Rejected(Millis(max(1L, ceil(missing / rule.perMillis).toLong())))
}
val next = filled.copy(tokens = filled.tokens - permits)
if (state.compareAndSet(seen, next)) {
return Decision.Allowed(Permits(floor(next.tokens).toInt()))
}
}
}
private fun State.refilled(now: Millis): State {
val elapsed = now.value - at
if (elapsed <= 0) return this
return State(min(capacity, tokens + elapsed * rule.perMillis), now.value)
}
// A full bucket is indistinguishable from one never used, so it can be
// thrown away without forgiving anybody.
override fun isIdle(now: Millis) = state.get().refilled(now).tokens >= capacity
}
com.androidinterview.ratelimiter.core.Clock.kt
package com.androidinterview.ratelimiter.core
// Nothing in this package reads the system time directly. A limiter that calls
// the clock inside itself can only be tested by sleeping, so a test of a one
// minute window takes a minute and a boundary test is a coin toss.
//
// One method, so a fun interface, and a clock is a lambda outside tests.
fun interface Clock {
fun now(): Millis
}
// Monotonic on purpose. Wall clock time steps backwards whenever the device
// corrects itself against a time server, and a limiter that sees time run
// backwards either locks everyone out or hands out a free window.
object SystemClock : Clock {
override fun now() = Millis(System.nanoTime() / 1_000_000L)
}
// Time moves only when a test moves it, so an hour of traffic runs in a
// microsecond and a boundary is checked at the exact millisecond.
class ManualClock(start: Millis = Millis(0)) : Clock {
private var current = start
@Synchronized
override fun now() = current
@Synchronized
fun advance(millis: Long) {
current += Millis(millis)
}
}
com.androidinterview.ratelimiter.core.Decision.kt
package com.androidinterview.ratelimiter.core
// Two units, two types, and neither costs an object at runtime. A Long called
// now and a Long called retryAfter are the same thing to the compiler and
// different things to a reader.
@JvmInline
value class Millis(val value: Long) : Comparable<Millis> {
operator fun plus(other: Millis) = Millis(value + other.value)
operator fun minus(other: Millis) = Millis(value - other.value)
override fun compareTo(other: Millis) = value.compareTo(other.value)
override fun toString() = "${value}ms"
}
@JvmInline
value class Permits(val count: Int) {
override fun toString() = "$count permits"
companion object {
val ONE = Permits(1)
}
}
// The answer, and the reason it is a type rather than a Boolean. A Boolean
// makes the caller invent a retry delay, and every client inventing the same
// delay is how a backend gets a synchronised stampede.
//
// Sealed, so a when over a decision is exhaustive and a third outcome, say a
// shadow mode that would have refused but let the request through, is a
// compile error at every call site instead of a silent default branch.
sealed interface Decision {
val allowed: Boolean
val retryAfter: Millis
// What a server would put in an X-RateLimit-Remaining header.
data class Allowed(val remaining: Permits) : Decision {
override val allowed get() = true
override val retryAfter get() = Millis(0)
}
data class Rejected(override val retryAfter: Millis) : Decision {
override val allowed get() = false
}
}
// The limit as one value, because every algorithm needs both numbers and
// several need the ratio.
data class Rule(val permits: Permits, val window: Millis) {
init {
require(permits.count > 0) { "permits must be positive, got $permits" }
require(window.value > 0) { "window must be positive, got $window" }
}
val limit get() = permits.count
val windowMillis get() = window.value
// A Double on purpose. One permit per ten seconds is a ten thousandth of a
// permit per millisecond, and rounding that to a whole number is how a
// slow bucket never refills at all.
val perMillis get() = limit.toDouble() / windowMillis
companion object {
fun perSecond(permits: Int) = Rule(Permits(permits), Millis(1_000))
fun perMinute(permits: Int) = Rule(Permits(permits), Millis(60_000))
}
}
On Android, and when it goes distributed
This lands in Android rounds because the client side of it is real. An app that has been offline comes back with two hundred queued analytics events, and without a limiter the uploader turns that into two hundred requests in one second. Put a token bucket in front of the flush and the burst is metered at whatever the backend can take. The same bucket sits in front of retries, and it does a different job from exponential backoff. Backoff spaces out one failing request, the limiter caps the total across all of them, and an app that only has backoff will still hammer a server when fifty different calls fail at once.
The result type is what makes it usable there. A refusal carrying retry after is a number you can hand to whatever schedules deferred work, so nothing spins and nothing polls.
Going distributed changes one thing and it changes it completely. The state moves out of the process into something shared, usually Redis, keyed the same way. Read the bucket, decide, write it back is now a race between machines rather than between threads, and the compare and set loop does not help because the two ends of it are separate network calls. The whole check and consume has to be one atomic step on the server, a Lua script for the token bucket, an increment with an expiry for a fixed window, a sorted set for the log. The clock becomes the Redis server's clock rather than each app server's, which quietly fixes a problem you did not know you had. Then answer the question they will ask next, which is what happens when Redis is down, and the usual answer is fail open with a much stricter local limiter behind it.
Concurrency and edge cases
The lock is per bucket, never one lock. This is the whole concurrency answer. A single lock around the limiter serialises the entire process behind the busiest client, which is precisely backwards. A concurrent map plus a lock inside each bucket means two users never wait for each other. In the code the window algorithms synchronise on themselves, and the token bucket goes further and uses no lock at all.
Check then act on the counter. Reading the count, deciding, and then incrementing is two decisions with a gap in the middle, and two threads both see the last permit available. Every algorithm here does the check and the consume inside one critical section, and the token bucket does it by putting the token count and the timestamp in one immutable value so the update is a single compare and set.
Eviction racing a request. A thread can pull a bucket out of the map, get descheduled, and use it after the sweep removed it. That request is counted against an object nobody else can see. It is harmless precisely because only idle buckets are ever removed, so a fresh bucket would have allowed the same request. Say this out loud, because an interviewer who spots the race will assume you did not.
Other cases worth a sentence each.
- A key nobody has ever used. Created on demand with a full bucket, so a new user is not punished for being new.
- A request costing more than the whole limit. No amount of waiting fixes it, so it is a thrown exception and not a rejection.
- Unbounded keys. Idle eviction handles quiet users. It does not handle an attacker inventing a new key every request, so cap the map size too, or bound the key space upstream by limiting per IP as well.
- Retry after of zero. Round it up to one millisecond, otherwise a caller that trusts the number spins.
- Clock going backwards. Clamp elapsed time to zero rather than letting a negative interval drain or refill anything.
- A refused request is not counted. Logging rejections in the sliding window log would let a client push its own recovery further away every time it retried, which is the opposite of what you want.
Watch