Low-Level Design of a Rate Limiter in Java

A rate limiter decides whether a request may proceed now or must wait. This article is the object-level design: the types, interfaces and state inside one process. The distributed service (Redis counters, gateways, headers, multi-region behavior) is covered in design a rate limiter, and the algorithms are compared in rate limiting algorithms. Here the questions are: what is the interface, how do the algorithms plug in, and how do we keep the code testable when the behavior depends on time?

The approach follows the LLD interview framework. Time is injected the same way as in design a key-value store with TTL.

Requirements

Functional

A limiter answers "may I proceed with this request of cost n?" with a decision: allowed (with the remaining budget) or denied (with a hint of when to retry).
At least two algorithms: token bucket (allows bursts, sustained rate bounded) and sliding window counter (smooth limit over a rolling window).
The algorithm and its parameters are chosen by configuration, not by code changes.
Limits apply per key (user, API key, IP address), and each key has independent state.
Invalid configuration (zero limit, zero rate) is rejected at construction.

Non-functional

Deterministic tests: no sleeping, no wall clock.
O(1) time and O(1) memory per key per decision.
Money-like exactness: no floating point drift in token accounting.

Entities and class diagram

classDiagram
    class Ticker {
        <<interface>>
        +nowMs() long
    }
    class RateLimiter {
        <<interface>>
        +acquire(cost) Decision
    }
    class TokenBucket {
        -capacity: int
        -refillPerSec: int
        -tokensMilli: long
        -lastMs: long
    }
    class SlidingWindow {
        -limit: int
        -windowMs: long
        -current: int
        -previous: int
    }
    class LimiterConfig {
        <<sealed interface>>
        TokenBucketConfig
        SlidingWindowConfig
        +build(ticker) RateLimiter
    }
    class PerKeyLimiter~K~ {
        -limiters: Map~K,RateLimiter~
        +acquire(key, cost) Decision
    }
    class Decision {
        <<sealed interface>>
        Allowed
        Denied
    }
    RateLimiter <|.. TokenBucket
    RateLimiter <|.. SlidingWindow
    TokenBucket --> Ticker : reads
    SlidingWindow --> Ticker : reads
    LimiterConfig ..> RateLimiter : builds
    PerKeyLimiter o-- LimiterConfig : has
    PerKeyLimiter *-- RateLimiter : one per key
    RateLimiter ..> Decision : returns

API

Java

sealed interface Decision {
    record Allowed(int remaining) implements Decision {}
    record Denied(long retryAfterMs) implements Decision {}
}

interface RateLimiter {
    Decision acquire(int cost); // throws IllegalArgumentException if cost < 1 or cost > limit
}

Two kinds of outcome are kept apart on purpose. A Decision.Denied is a normal answer that the caller must handle, so it is a return value. An IllegalArgumentException (a cost larger than the limit can never succeed) is a caller bug or misconfiguration, so it is thrown. The sealed Decision lets a caller write an exhaustive switch with no default. See errors in domain design.

Design decisions

Strategy pattern, because the algorithm varies. The requirement names two algorithms and implies more, so RateLimiter is an interface with one implementation per algorithm. Callers hold a RateLimiter because the algorithm is chosen at runtime from configuration.

Configuration as a sealed type. The set of supported algorithms is closed and known, so LimiterConfig is a sealed interface with one record per algorithm, and its build method is the single place that turns data into a behavior object. Adding an algorithm means one new class and one new record, which the compiler then forces every exhaustive switch to handle.

Injected clock. Both algorithms read time from a Ticker, a one-method interface that returns milliseconds. Tests share a ManualTicker and advance it explicitly. In production the ticker reads System.nanoTime(), which is monotonic. Wall-clock time can jump backwards, so the code ignores a backwards step instead of computing a negative elapsed time.

Integer token accounting. The token bucket stores tokens in thousandths (milli-tokens) in a long. With a refill rate of r tokens per second, one millisecond adds exactly r milli-tokens, so the refill is elapsedMs * r with no division and no floating point. Lazy refill on each call means no timer thread per key. The refill is capped before the multiplication, so a long idle period cannot overflow.

Sliding window counter, not a log. A log of timestamps is exact but O(limit) memory. The counter keeps two numbers, the count in the current fixed window and in the previous one, and estimates the rolling count as previous * (window - elapsed) / window + current. The estimate assumes requests were spread evenly across the previous window. It is cheap and never allows more than about the limit, at the cost of a small error.

Why not a plain fixed window. A fixed window resets its count at each boundary, so a client can send limit requests right before the boundary and limit right after: twice the limit in a short span.

Java

public class Main {
    /** Fixed-window counter: count resets when the window index changes. */
    static final class FixedWindow {
        private final int limit;
        private final long windowMs;
        private long index;
        private int count;

        FixedWindow(int limit, long windowMs) {
            this.limit = limit;
            this.windowMs = windowMs;
        }

        boolean allow(long nowMs) {
            long current = nowMs / windowMs;
            if (current != index) {
                index = current;
                count = 0;
            }
            if (count < limit) {
                count++;
                return true;
            }
            return false;
        }
    }

    public static void main(String[] args) {
        var w = new FixedWindow(10, 1000);
        int before = 0;
        int after = 0;
        for (int i = 0; i < 10; i++) {
            if (w.allow(999)) before++;
        }
        for (int i = 0; i < 10; i++) {
            if (w.allow(1000)) after++;
        }
        System.out.println("allowed at t=999: " + before + ", at t=1000: " + after + ", within 1 ms: " + (before + after));
    }
}

Output

allowed at t=999: 10, at t=1000: 10, within 1 ms: 20

Twenty requests pass within one millisecond against a limit of ten per second. The sliding window counter below closes this gap.

Per-key state in a map, created lazily. PerKeyLimiter owns a Map<K, RateLimiter> and builds a limiter the first time a key appears, with computeIfAbsent. Keys never share state. The map grows with the number of distinct keys, which is addressed under extensions.

Full implementation

The lesson uses no test library: the checks are printed outputs that can be read against the design. The limiters are not thread-safe by themselves. SynchronizedLimiter at the end of the program adds that, and the last part of main uses it from several threads.

Java

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.ArrayList;
import java.util.List;

@FunctionalInterface
interface Ticker {
    long nowMs();

    /** Production ticker: monotonic, so it never runs backwards. */
    static Ticker monotonic() {
        return () -> System.nanoTime() / 1_000_000;
    }
}

/** Test ticker: holds a time and advances only when told to. */
final class ManualTicker implements Ticker {
    private long now;

    void advance(long ms) {
        now += ms;
    }

    @Override
    public long nowMs() {
        return now;
    }
}

sealed interface Decision {
    record Allowed(int remaining) implements Decision {}

    record Denied(long retryAfterMs) implements Decision {}
}

interface RateLimiter {
    /** Returns a decision. Throws IllegalArgumentException if cost is below 1 or above the limit. */
    Decision acquire(int cost);
}

/** Token bucket with tokens counted in thousandths. */
final class TokenBucket implements RateLimiter {
    private final Ticker ticker;
    private final int capacity;
    private final int refillPerSec;
    private long tokensMilli;
    private long lastMs;

    TokenBucket(Ticker ticker, int capacity, int refillPerSec) {
        this.ticker = Objects.requireNonNull(ticker);
        if (capacity <= 0) {
            throw new IllegalArgumentException("capacity must be positive");
        }
        if (refillPerSec <= 0) {
            throw new IllegalArgumentException("refill rate must be positive");
        }
        this.capacity = capacity;
        this.refillPerSec = refillPerSec;
        this.tokensMilli = capacity * 1000L;
        this.lastMs = ticker.nowMs();
    }

    private void refill() {
        long now = ticker.nowMs();
        long elapsed = Math.max(0, now - lastMs); // a backwards step adds nothing
        long cap = capacity * 1000L;
        // r tokens per second is exactly r milli-tokens per millisecond.
        long added = elapsed > cap / refillPerSec ? cap : elapsed * refillPerSec;
        tokensMilli = Math.min(cap, tokensMilli + added);
        lastMs = Math.max(lastMs, now);
    }

    @Override
    public Decision acquire(int cost) {
        if (cost < 1 || cost > capacity) {
            throw new IllegalArgumentException("cost " + cost + " is outside 1.." + capacity);
        }
        refill();
        long need = cost * 1000L;
        if (tokensMilli >= need) {
            tokensMilli -= need;
            return new Decision.Allowed((int) (tokensMilli / 1000));
        }
        long deficit = need - tokensMilli;
        return new Decision.Denied(Math.ceilDiv(deficit, (long) refillPerSec));
    }
}

/** Sliding window counter: two adjacent fixed windows, weighted. */
final class SlidingWindow implements RateLimiter {
    private final Ticker ticker;
    private final int limit;
    private final long windowMs;
    private long index;
    private int current;
    private int previous;

    SlidingWindow(Ticker ticker, int limit, long windowMs) {
        this.ticker = Objects.requireNonNull(ticker);
        if (limit <= 0) {
            throw new IllegalArgumentException("limit must be positive");
        }
        if (windowMs <= 0) {
            throw new IllegalArgumentException("window must be positive");
        }
        this.limit = limit;
        this.windowMs = windowMs;
        this.index = ticker.nowMs() / windowMs;
    }

    /** Moves to the window containing now and returns the estimated usage. */
    private long usage(long now) {
        long target = now / windowMs;
        long gap = Math.max(0, target - index);
        if (gap == 1) {
            previous = current;
            current = 0;
        } else if (gap > 1) {
            previous = 0;
            current = 0;
        }
        index = Math.max(index, target);
        long elapsed = now % windowMs;
        long carried = previous * (windowMs - elapsed) / windowMs;
        return carried + current;
    }

    @Override
    public Decision acquire(int cost) {
        if (cost < 1 || cost > limit) {
            throw new IllegalArgumentException("cost " + cost + " is outside 1.." + limit);
        }
        long now = ticker.nowMs();
        long used = usage(now);
        if (used + cost <= limit) {
            current += cost;
            return new Decision.Allowed((int) (limit - used - cost));
        }
        // A hint: the next window boundary, when the old count starts to fade.
        return new Decision.Denied(windowMs - now % windowMs);
    }
}

/** The closed set of supported algorithms, as data. */
sealed interface LimiterConfig {
    record TokenBucketConfig(int capacity, int refillPerSec) implements LimiterConfig {}

    record SlidingWindowConfig(int limit, long windowMs) implements LimiterConfig {}

    default RateLimiter build(Ticker ticker) {
        return switch (this) {
            case TokenBucketConfig(var capacity, var refillPerSec) -> new TokenBucket(ticker, capacity, refillPerSec);
            case SlidingWindowConfig(var limit, var windowMs) -> new SlidingWindow(ticker, limit, windowMs);
        };
    }
}

/** One independent limiter per key, created on first use. Not thread-safe. */
final class PerKeyLimiter<K> {
    private final LimiterConfig config;
    private final Ticker ticker;
    private final Map<K, RateLimiter> limiters = new HashMap<>();

    PerKeyLimiter(LimiterConfig config, Ticker ticker) {
        this.config = Objects.requireNonNull(config);
        this.ticker = Objects.requireNonNull(ticker);
        config.build(ticker); // validate once, up front
    }

    Decision acquire(K key, int cost) {
        return limiters.computeIfAbsent(key, k -> config.build(ticker)).acquire(cost);
    }

    int trackedKeys() {
        return limiters.size();
    }
}

/** Decorator: one lock around the whole limiter makes each acquire atomic. */
final class SynchronizedLimiter implements RateLimiter {
    private final RateLimiter delegate;

    SynchronizedLimiter(RateLimiter delegate) {
        this.delegate = Objects.requireNonNull(delegate);
    }

    @Override
    public synchronized Decision acquire(int cost) {
        return delegate.acquire(cost);
    }
}

public class Main {
    static void tryBadConfig(Runnable action) {
        try {
            action.run();
        } catch (IllegalArgumentException e) {
            System.out.println("rejected: " + e.getMessage());
        }
    }

    public static void main(String[] args) throws Exception {
        // Token bucket: capacity 3, one token per second.
        var ticker = new ManualTicker();
        var bucket = new TokenBucket(ticker, 3, 1);
        for (int i = 0; i < 4; i++) {
            System.out.println("t=0     " + bucket.acquire(1));
        }
        ticker.advance(500);
        System.out.println("t=500   " + bucket.acquire(1));
        ticker.advance(500);
        System.out.println("t=1000  " + bucket.acquire(1));
        ticker.advance(60_000);
        System.out.println("t=61000 " + bucket.acquire(3) + " (refill is capped at capacity)");
        tryBadConfig(() -> bucket.acquire(5));
        tryBadConfig(() -> new TokenBucket(ticker, 0, 1));

        // Sliding window: the previous window's usage fades out gradually.
        var windowTicker = new ManualTicker();
        windowTicker.advance(900);
        var window = new SlidingWindow(windowTicker, 10, 1000);
        System.out.println("t=900   " + window.acquire(10));
        windowTicker.advance(100);
        System.out.println("t=1000  " + window.acquire(1));
        windowTicker.advance(500);
        System.out.println("t=1500  " + window.acquire(5));
        System.out.println("t=1500  " + window.acquire(1));

        // Per key: state is independent, and the algorithm comes from configuration.
        var config = new LimiterConfig.TokenBucketConfig(2, 1);
        var limiter = new PerKeyLimiter<String>(config, new ManualTicker());
        for (String key : List.of("alice", "alice", "alice", "bob")) {
            System.out.println(key + ": " + limiter.acquire(key, 1));
        }
        System.out.println("tracked keys: " + limiter.trackedKeys());

        // A caller handles both outcomes with an exhaustive switch.
        String message = switch (limiter.acquire("alice", 1)) {
            case Decision.Allowed(var remaining) -> "go, " + remaining + " left";
            case Decision.Denied(var retryAfterMs) -> "wait " + retryAfterMs + " ms";
        };
        System.out.println(message);

        // Eight threads share one limiter. No time passes, so exactly 100 of 400 attempts win.
        RateLimiter shared = new SynchronizedLimiter(new TokenBucket(new ManualTicker(), 100, 1));
        int allowed = 0;
        try (ExecutorService pool = Executors.newFixedThreadPool(8)) {
            List<Future<Integer>> results = new ArrayList<>();
            for (int t = 0; t < 8; t++) {
                results.add(pool.submit(() -> {
                    int won = 0;
                    for (int i = 0; i < 50; i++) {
                        if (shared.acquire(1) instanceof Decision.Allowed) won++;
                    }
                    return won;
                }));
            }
            for (Future<Integer> result : results) {
                allowed += result.get();
            }
        }
        System.out.println("attempts: 400, allowed: " + allowed);
    }
}

Output

t=0     Allowed[remaining=2]
t=0     Allowed[remaining=1]
t=0     Allowed[remaining=0]
t=0     Denied[retryAfterMs=1000]
t=500   Denied[retryAfterMs=500]
t=1000  Allowed[remaining=0]
t=61000 Allowed[remaining=0] (refill is capped at capacity)
rejected: cost 5 is outside 1..3
rejected: capacity must be positive
t=900   Allowed[remaining=0]
t=1000  Denied[retryAfterMs=1000]
t=1500  Allowed[remaining=0]
t=1500  Denied[retryAfterMs=500]
alice: Allowed[remaining=1]
alice: Allowed[remaining=0]
alice: Denied[retryAfterMs=1000]
bob: Allowed[remaining=1]
tracked keys: 2
wait 1000 ms
attempts: 400, allowed: 100

Read the output against the design. The bucket allows a burst of three, denies the fourth with a retry hint of 1000 ms (one whole token missing at one token per second), and after 500 ms reports 500 ms remaining because half a token has accumulated. After a long idle period the bucket is capped at capacity, so an hour of silence buys only a burst of three. In the window demo, ten requests at t=900 leave the client denied at t=1000 (the whole previous window still counts), while at t=1500 half of it has faded and five more are allowed.

The design splits outcomes into a returned Decision for expected results and an unchecked IllegalArgumentException for misuse. An unchecked exception keeps the RateLimiter signature small, and the misuse cases (a bad cost, a bad configuration) are programming errors, not conditions a caller recovers from.

Thread safety

The limiters above keep plain mutable fields, so two threads calling acquire at once can lose updates. The simple fix is the decorator from the program: SynchronizedLimiter holds one lock, so each call to acquire runs alone. The lock also gives visibility: everything one thread wrote before releasing the lock is seen by the next thread that takes it (a happens-before edge), so the fields need no volatile. For a PerKeyLimiter, use a ConcurrentHashMap with computeIfAbsent and wrap each limiter in a SynchronizedLimiter, so only calls for the same key contend. See thread-safe components.

The second way is a lock-free design when the state is a single number. A pure quota (at most N operations in total) is one atomic counter decremented with a compare-and-set loop:

Java

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.atomic.AtomicInteger;

public class Main {
    static final class Quota {
        private final AtomicInteger remaining;

        Quota(int total) {
            remaining = new AtomicInteger(total);
        }

        boolean tryTake() {
            // Retries until it wins the race or finds the quota empty; never goes below zero.
            while (true) {
                int current = remaining.get();
                if (current == 0) {
                    return false;
                }
                if (remaining.compareAndSet(current, current - 1)) {
                    return true;
                }
            }
        }

        int left() {
            return remaining.get();
        }
    }

    public static void main(String[] args) throws Exception {
        var quota = new Quota(100);
        int allowed = 0;
        try (ExecutorService pool = Executors.newFixedThreadPool(8)) {
            List<Future<Integer>> results = new ArrayList<>();
            for (int t = 0; t < 8; t++) {
                results.add(pool.submit(() -> {
                    int won = 0;
                    for (int i = 0; i < 50; i++) {
                        if (quota.tryTake()) won++;
                    }
                    return won;
                }));
            }
            for (Future<Integer> result : results) {
                allowed += result.get();
            }
        }
        System.out.println("attempts: 400, allowed: " + allowed + ", left: " + quota.left());
    }
}

Output

attempts: 400, allowed: 100, left: 0

Which thread wins each slot varies from run to run, but the total does not: exactly 100 requests are allowed. A token bucket needs two fields (tokens and last refill time), which do not fit one atomic integer, so it uses a lock, or it packs both into one AtomicLong.

Extensions

Follow-up question	Answer
Idle keys grow the map forever	Record the last-seen time per key and remove keys that have been idle longer than the window, or store limiters in a TTL store; see design a key-value store with TTL.
Several limits at once (10 per second and 1000 per hour)	A `CompositeLimiter` implementing `RateLimiter` that holds a `List<RateLimiter>`. It must not consume from any limiter unless all would allow.
Different limits per tier	Look up the `LimiterConfig` by tier in a map, then build the per-key limiter from it.
Return HTTP headers	`Decision.Allowed.remaining` maps to a remaining header and `retryAfterMs` to `Retry-After`; see design a rate limiter.
Leaky bucket or fixed window	One more `RateLimiter` implementation and one more `LimiterConfig` record. The compiler flags every `switch` that must handle it.
Limits shared across servers	The state moves to a shared store with atomic updates; see design a rate limiter and rate limiting algorithms.
Blocking until allowed	A wrapper that loops on `Denied` and waits for `retryAfterMs`. Keep it out of the core interface so the core stays testable.

Summary

The interface is one method, RateLimiter.acquire, which returns a sealed Decision for expected outcomes and throws IllegalArgumentException for misuse.
Token bucket and sliding window counter are two implementations of that interface. Configuration is a sealed interface of records whose build method returns a strategy.
Inject the clock as a Ticker so tests advance time by hand. Ignore a backwards clock step so elapsed time never goes negative.
Count tokens as long thousandths so refill is exact, and cap the refill before multiplying. Refill lazily on each call instead of running timers.
A sliding window counter fixes the fixed window boundary burst with two counters and a weighted estimate, at O(1) memory.
Per-key limiting is a map from key to an independent limiter, created lazily. Plan for cleaning up idle keys.
Thread safety is a separate concern: wrap a limiter in a lock-holding decorator, or use an atomic compare-and-set loop when the state is a single number.