More interview problems · Chapter 30

Rate limiter class

Design an in-process rate limiter class: one interface, token bucket and sliding window strategies, per-key limiters, thread safety and an injected clock for tests.

IntermediateInterview priority: High55 min
On this page
  1. The problem: a limit that lets bursts through
  2. 1. Clarify the requirements
  3. 2. The class design
  4. 3. The algorithms
  5. 4. The code
  6. 5. Options and trade-offs
  7. 6. Concurrency
  8. 7. Extensions the interviewer will ask for
  9. When not to build this
  10. In the interview
  11. Quiz

The problem: a limit that lets bursts through

A rate limiter decides whether a caller may do something now, given how often they have done it recently: "100 requests per minute per API key", "5 login attempts per minute per account". Requests over the limit are rejected (for HTTP, with status 429 Too Many Requests). This page designs it as a class for a machine-coding round. For the system-design version, where many servers share one limit through Redis, see rate limiting.

A first attempt usually counts per calendar minute:

class RateLimiter {
    Map<String, Integer> counts = new HashMap<>();
    long currentMinute = 0;

    boolean allow(String key) {
        long minute = System.currentTimeMillis() / 60_000;
        if (minute != currentMinute) { counts.clear(); currentMinute = minute; }
        int c = counts.getOrDefault(key, 0);
        if (c >= 100) return false;
        counts.put(key, c + 1);
        return true;
    }
}

What is wrong:

  • Bursts at the boundary. 100 requests at 12:00:59 and 100 more at 12:01:00 are all allowed: 200 in one second, twice the intended rate.
  • Not thread-safe. Two threads read c = 99, both write 100, and both requests pass. HashMap itself can be corrupted by concurrent writes.
  • Untestable. It reads the system clock, so a test of "the limit resets after a minute" must sleep for a minute.
  • One algorithm, welded in. Switching to a smoother algorithm, or using different ones for logins and for API calls, means rewriting the class.

1. Clarify the requirements

Your turn: scope it

The interviewer says "Design a rate limiter." Write 5 questions and the requirements you would agree on.

Compare with our answer

Questions worth asking: Is it in one process (a class) or shared across servers? Limit per what: user, API key, IP, endpoint? Should short bursts be allowed? What happens to rejected requests: reject, or queue them? Do callers need to know when to retry? How many distinct keys (memory)? Must it be exact, or is approximately right acceptable?

A strong answer mentions: in-process versus distributed · the key · the limit as a rate plus a burst size · reject with a retry-after time · thread safety · a testable clock · memory per key.

The agreed list:

RequirementDetail
APItryAcquire(key) returns allowed or rejected, plus retry-after (how long until a request could succeed)
AlgorithmsToken bucket (allows controlled bursts) and sliding window (exact count in the last N ms), swappable
Per keyEach key (user id, API key, IP) has its own independent limit; limiters are created on first use
ThreadsSafe under many concurrent callers; never allows more than the limit
TimeRead from an injected clock, so tests control time exactly
ScopeOne process. The distributed version is a follow-up

Out of scope: queueing rejected requests (that is shaping rather than limiting), configuration from a file, and sharing limits across servers (discussed in "where this breaks").

2. The class design

One interface, several algorithms, one limiter per key

Class / typeKindResponsibility
RateLimiterinterfacetryAcquire() → Decision for one key
TokenBucket, SlidingWindowLog, FixedWindowstrategiesThe algorithms; each keeps its own state and lock
Decisionvalue objectallowed and retryAfterMs (for an HTTP Retry-After header)
KeyedRateLimiterclassA map from key to RateLimiter, created by a factory on first use
Clockinterfacemillis(): the system's monotonic clock in production, a FakeClock in tests

Why these choices:

  • Strategy for the algorithm. Logins might want a strict sliding window; an API might want a token bucket that tolerates bursts. The Strategy pattern lets each endpoint choose without the calling code changing.
  • Per-key limiters are separate objects. The algorithm is written once for one key, with no maps inside it. KeyedRateLimiter adds the "per key" dimension, and the factory decides which algorithm and which limits every new key gets.
  • An injected clock. Time is the input that every rate limiter depends on. With a fake clock a test says "advance 1,000 ms" and checks the result in microseconds, with no sleeping and no flakiness.
  • A Decision rather than a boolean: the caller can tell the client when to retry instead of letting it hammer the server.

3. The algorithms

Token bucket

Picture a bucket that holds up to capacity tokens and is refilled at rate tokens per second. Each request takes one token; with no token, the request is rejected. The capacity is the burst size (how many requests can arrive at once after a quiet period); the rate is the long-run average.

Tokens are spent per request and refilled lazily

The refill needs no background thread. Store the token count and the time of the last call; on each call add elapsed × rate, cap it at the capacity, then try to spend one. That is O(1) time and two numbers of memory per key.

Sliding window

A fixed window counter resets at each boundary, which lets twice the limit through across a boundary. A sliding window log keeps the timestamp of each allowed request and counts only those in the last window milliseconds ending now. It is exact, but stores up to limit timestamps per key.

Fixed windows let a double burst through; a sliding window does not

The sliding window counter: an approximation in O(1) memory

A third option keeps only two counters per key: the count in the current fixed window and the count in the previous one. The estimate for the last N ms is current + previous × (fraction of the previous window still inside the sliding window). At 1.1 s into a 1-second window, 90% of the previous window still overlaps, so estimate = current + 0.9 × previous. It assumes requests in the previous window were spread evenly, so it can be slightly off, but it is O(1) memory and is what many production limiters (including Cloudflare's) use.

4. The code

Three algorithms behind one interface, a keyed wrapper, a fake clock, and a demo that shows bursts, refill, the boundary problem and 8,000 concurrent calls.

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Supplier;

/** Time source in milliseconds. Production passes a monotonic clock; tests pass a fake. */
interface Clock { long millis(); }

final class FakeClock implements Clock {
    private long now;
    FakeClock(long start) { now = start; }
    public synchronized long millis() { return now; }
    synchronized void advance(long ms) { now += ms; }
}

/** allowed = may proceed; retryAfterMs = how long until a request could succeed (for HTTP Retry-After). */
record Decision(boolean allowed, long retryAfterMs) {}

/** One limiter guards one caller (one key). Implementations are strategies. */
interface RateLimiter { Decision tryAcquire(); }

/** Holds up to `capacity` tokens, refilled continuously at `perSecond`. Each request spends one. */
final class TokenBucket implements RateLimiter {
    private final double capacity, perMs;
    private final Clock clock;
    private double tokens;
    private long last;

    TokenBucket(int capacity, double perSecond, Clock clock) {
        if (capacity <= 0 || perSecond < 0) throw new IllegalArgumentException("bad limits");
        this.capacity = capacity; this.perMs = perSecond / 1000.0; this.clock = clock;
        this.tokens = capacity; this.last = clock.millis();                // start full
    }

    public synchronized Decision tryAcquire() {
        long now = clock.millis();
        tokens = Math.min(capacity, tokens + (now - last) * perMs);        // lazy refill: no timer thread
        last = now;
        if (tokens >= 1) { tokens -= 1; return new Decision(true, 0); }
        long wait = perMs == 0 ? Long.MAX_VALUE : (long) Math.ceil((1 - tokens) / perMs);
        return new Decision(false, wait);
    }
}

/** Remembers the time of each allowed request in the last window. Exact, but O(limit) memory per key. */
final class SlidingWindowLog implements RateLimiter {
    private final int limit; private final long windowMs; private final Clock clock;
    private final Deque<Long> log = new ArrayDeque<>();

    SlidingWindowLog(int limit, long windowMs, Clock clock) {
        if (limit <= 0 || windowMs <= 0) throw new IllegalArgumentException("bad limits");
        this.limit = limit; this.windowMs = windowMs; this.clock = clock;
    }

    public synchronized Decision tryAcquire() {
        long now = clock.millis();
        while (!log.isEmpty() && log.peekFirst() <= now - windowMs) log.pollFirst();   // drop expired
        if (log.size() < limit) { log.addLast(now); return new Decision(true, 0); }
        return new Decision(false, log.peekFirst() + windowMs - now);                  // when the oldest expires
    }
}

/** Fixed window, shown for comparison: simple, but allows 2x the limit across a boundary. */
final class FixedWindow implements RateLimiter {
    private final int limit; private final long windowMs; private final Clock clock;
    private long windowStart = -1; private int count;
    FixedWindow(int limit, long windowMs, Clock clock) { this.limit = limit; this.windowMs = windowMs; this.clock = clock; }
    public synchronized Decision tryAcquire() {
        long now = clock.millis(), start = now - now % windowMs;
        if (start != windowStart) { windowStart = start; count = 0; }
        if (count < limit) { count++; return new Decision(true, 0); }
        return new Decision(false, start + windowMs - now);
    }
}

/** One limiter per key (user id, API key, IP), created on first use. */
final class KeyedRateLimiter {
    private final ConcurrentHashMap<String, RateLimiter> limiters = new ConcurrentHashMap<>();
    private final Supplier<RateLimiter> factory;
    KeyedRateLimiter(Supplier<RateLimiter> factory) { this.factory = factory; }

    Decision tryAcquire(String key) {
        return limiters.computeIfAbsent(key, k -> factory.get()).tryAcquire();   // atomic: one limiter per key
    }
    int keys() { return limiters.size(); }
}

public class RateLimiterDemo {
    static String run(RateLimiter rl, int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            Decision d = rl.tryAcquire();
            sb.append(d.allowed() ? "ok " : "429(" + d.retryAfterMs() + "ms) ");
        }
        return sb.toString().trim();
    }

    public static void main(String[] args) throws Exception {
        FakeClock clock = new FakeClock(0);

        TokenBucket bucket = new TokenBucket(3, 1.0, clock);                // burst 3, then 1 per second
        System.out.println("bucket t=0     : " + run(bucket, 5));
        clock.advance(1_000);
        System.out.println("bucket t=1s    : " + run(bucket, 2));
        clock.advance(10_000);
        System.out.println("bucket t=11s   : " + run(bucket, 4) + "   (refill capped at 3)");

        FakeClock c2 = new FakeClock(0);
        RateLimiter fixed = new FixedWindow(3, 1_000, c2), sliding = new SlidingWindowLog(3, 1_000, c2);
        c2.advance(900);
        String f1 = run(fixed, 3), s1 = run(sliding, 3);
        c2.advance(200);                                                    // t = 1100: a new fixed window
        System.out.println("fixed   t=0.9s : " + f1 + " | t=1.1s: " + run(fixed, 3));
        System.out.println("sliding t=0.9s : " + s1 + " | t=1.1s: " + run(sliding, 3));

        FakeClock c3 = new FakeClock(0);
        KeyedRateLimiter perUser = new KeyedRateLimiter(() -> new TokenBucket(2, 0.5, c3));
        System.out.println("alice: " + run(() -> perUser.tryAcquire("alice"), 3)
            + " | bob: " + run(() -> perUser.tryAcquire("bob"), 2) + " | keys=" + perUser.keys());

        // Concurrency: 8 threads x 1,000 calls against a bucket of 100 that never refills
        TokenBucket shared = new TokenBucket(100, 0, () -> System.nanoTime() / 1_000_000);
        AtomicInteger allowed = new AtomicInteger();
        ExecutorService pool = Executors.newFixedThreadPool(8);
        List<Future<?>> fs = new ArrayList<>();
        for (int t = 0; t < 8; t++) fs.add(pool.submit(() -> {
            for (int i = 0; i < 1_000; i++) if (shared.tryAcquire().allowed()) allowed.incrementAndGet();
        }));
        for (Future<?> f : fs) f.get();
        pool.shutdown();
        System.out.println("8,000 concurrent calls, capacity 100: allowed " + allowed.get());
    }
}

Running either version prints:

bucket t=0     : ok ok ok 429(1000ms) 429(1000ms)
bucket t=1s    : ok 429(1000ms)
bucket t=11s   : ok ok ok 429(1000ms)   (refill capped at 3)
fixed   t=0.9s : ok ok ok | t=1.1s: ok ok ok
sliding t=0.9s : ok ok ok | t=1.1s: 429(800ms) 429(800ms) 429(800ms)
alice: ok ok 429(2000ms) | bob: ok ok | keys=2
8,000 concurrent calls, capacity 100: allowed 100

Read the lines against the algorithms. The bucket allows a burst of 3, then one per second; ten idle seconds refill it to 3, not 10. The fixed window lets 6 requests through in 200 ms; the sliding window rejects the second burst and says to retry in 800 ms, when the requests from 0.9 s leave the window. Alice and bob have separate buckets. Under 8,000 concurrent calls exactly 100 succeed.

5. Options and trade-offs

AlgorithmGood atWeak atUse when
Token bucketAllows bursts up to a set size, smooth average; O(1) memoryTwo parameters to explain; a full bucket allows a burst right awayAPIs where short bursts are normal (Stripe, AWS and many gateways use it)
Leaky bucket (a queue drained at a fixed rate)Perfectly smooth outputAdds delay; requests wait in a queueProtecting a downstream system that cannot take bursts
Fixed window counterSimplest; one counter per keyUp to 2× the limit across a boundaryRough quotas ("10,000 calls per day")
Sliding window logExactMemory grows with the limit (a timestamp per request)Small limits that must be strict: logins, password resets
Sliding window counterNearly exact, O(1) memoryAn approximationLarge limits, many keys

6. Concurrency

RaceWhat goes wrongFix in the code
Two calls read the same token countBoth see 1 token, both spend it: the limit is exceededEach limiter's tryAcquire is synchronized / holds its own lock; refill, check and spend are one step
Two first requests for a new keyEach creates its own limiter; one is lost, so the key gets double the limitJava: ConcurrentHashMap.computeIfAbsent is atomic per key. Python: get-or-create under a lock
One global lock for all keysEvery request in the process queues on one lockThe lock is per key; different users never wait for each other
Long work inside the lockThroughput collapsesThe critical section is a few arithmetic operations; the actual request runs after tryAcquire returns

The demo proves the first row: 8 threads make 8,000 calls against a bucket of 100 that never refills, and exactly 100 are allowed. Remove synchronized and the count is usually higher.

7. Extensions the interviewer will ask for

  • Different limits per plan (free 60/min, paid 1,000/min): the factory takes the key and looks up its plan: Function<String, RateLimiter> instead of Supplier.
  • Cost per request: tryAcquire(n) spends n tokens, so an expensive search costs 10 and a cheap read costs 1.
  • Several limits at once ("10 per second and 1,000 per hour"): a CompositeLimiter that asks each child and allows only if all allow. Check first without spending, or spend and refund, so a rejection by the second limit does not burn a token in the first.
  • Blocking instead of rejecting: acquire() sleeps for retryAfterMs and tries again (Guava's RateLimiter.acquire() works like this).
  • Metrics: count allowed and rejected per key, so you can see who hits limits.

When not to build this

  • The framework already has it: API gateways (Envoy, NGINX limit_req, cloud API gateways) and libraries (Guava RateLimiter, Resilience4j, Bucket4j) are tested and configurable.
  • Many servers sharing one limit: an in-process class is the wrong tool; use a shared store or the gateway.
  • One caller, generous limits: if nothing is at risk, a limiter only adds failure modes.

In the interview

Your turn: spot the bug

This token bucket allows far more requests than it should after a quiet period, and is not thread-safe. Find the bugs and fix them.

public boolean tryAcquire() {
    long now = System.currentTimeMillis();
    tokens += (now - last) / 1000 * ratePerSecond;
    last = now;
    if (tokens > 0) { tokens--; return true; }
    return false;
}
Compare with our answer

The bugs: (1) no cap: after an hour idle a bucket with rate 10 holds 36,000 tokens, so the "burst" is unlimited. (2) Integer division: (now - last) / 1000 is 0 for calls less than a second apart, so with frequent calls the bucket never refills (and last is still updated, so the time is lost). (3) No lock: two threads can both see one token. (4) tokens > 0 with fractional tokens lets a request through with 0.3 of a token. (5) The wall clock can jump backwards; read an injected monotonic clock.

public synchronized Decision tryAcquire() {
    long now = clock.millis();                               // injected, monotonic
    long elapsed = Math.max(0, now - last);
    tokens = Math.min(capacity, tokens + elapsed * ratePerSecond / 1000.0);   // capped, no integer division
    last = now;
    if (tokens >= 1) { tokens -= 1; return new Decision(true, 0); }
    return new Decision(false, (long) Math.ceil((1 - tokens) * 1000 / ratePerSecond));
}

A strong answer mentions: capping tokens at the capacity · floating-point (or millisecond) refill instead of integer seconds · a lock around refill, check and spend · requiring a whole token (>= 1) · a monotonic, injected clock · returning a retry-after time.

Your turn: the requirement changes

Product wants two limits on the search API at once: 10 per second and 500 per hour per user. A request is allowed only if both allow it, and a request rejected by one limit must not use up the other. Design it.

Compare with our answer

A CompositeLimiter that implements RateLimiter and holds the two child limiters, so callers and KeyedRateLimiter do not change. The difficulty is atomicity: if the per-second bucket spends a token and the hourly one then rejects, the first token is wasted. Give the strategies a peek() (would it allow?) and a commit(), or let tryAcquire spend and add a refund(). Hold both children's locks in a fixed order (or one lock for the composite) so two threads can't interleave. The retry-after is the largest of the children's.

final class CompositeLimiter implements RateLimiter {
    private final List<RefundableLimiter> parts;            // e.g. 10/s bucket, 500/h bucket
    CompositeLimiter(List<RefundableLimiter> parts) { this.parts = parts; }

    public synchronized Decision tryAcquire() {             // one lock: the parts change together
        List<RefundableLimiter> spent = new ArrayList<>();
        for (RefundableLimiter p : parts) {
            Decision d = p.tryAcquire();
            if (!d.allowed()) {
                spent.forEach(RefundableLimiter::refund);   // give back tokens already taken
                return d;
            }
            spent.add(p);
        }
        return new Decision(true, 0);
    }
}
interface RefundableLimiter extends RateLimiter { void refund(); }

A strong answer mentions: a composite behind the same interface · all-or-nothing (refund or peek-then-commit) · one lock or a fixed lock order across the parts · returning the rejecting limit's retry-after · KeyedRateLimiter's factory building one composite per user.

Rate limiter class on one page
  • Interface: RateLimiter.tryAcquire() → Decision(allowed, retryAfterMs); strategies behind it; KeyedRateLimiter = map key → limiter + factory.
  • Token bucket: capacity = burst, rate = average; lazy refill min(cap, tokens + elapsed × rate); spend one; O(1).
  • Fixed window: one counter, resets at boundaries; up to 2× the limit across a boundary.
  • Sliding log: timestamps in the last window; exact; memory O(limit) per key. Sliding counter: current + overlap × previous, O(1), approximate.
  • Threads: per-key lock (synchronized); computeIfAbsent for atomic creation; tiny critical sections; CAS as the lock-free option.
  • Clock: injected and monotonic (nanoTime, time.monotonic); FakeClock in tests; clamp negative elapsed.
  • Memory: evict idle keys (expire-after-access).
  • Distributed: counters in Redis with an atomic Lua script or INCR + EXPIRE; one network hop per request.
Check what stuck

1. A fixed-window limiter allows 100 requests per minute. What is the most a client can send in any 2-second period without being rejected?

2. A token bucket has capacity 10 and refills at 2 tokens per second. It is empty, then idle for 30 seconds. How many requests can arrive at once and be allowed?

3. Two threads call tryAcquire on the same bucket holding 1 token, and both requests are allowed. What is the cause and the fix?

4. How should a unit test check that a 1-request-per-second limiter allows a second request after 1,000 ms?

5. A login endpoint must allow at most 5 attempts per account in any 15 minutes, strictly. Which algorithm fits best?

6. The service runs on 8 servers behind a round-robin load balancer, each with an in-process limit of 100 requests per minute per key. What is a client's effective limit?

7. The keyed limiter stores one bucket per client IP and the service's memory grows steadily for days. What is the best fix?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.