LOW LEVEL DESIGN · MACHINE CODING · MEDIUM · 6 OF 42

Design a Rate Limiter: Low-Level Design with Java Code

A rate limiter library designed and coded: per-key limits with rules per tier, the algorithm as a Strategy (token bucket, fixed window, sliding log, sliding window counter), the boundary burst that breaks fixed windows, a factory and computeIfAbsent for per-key state, a lock per key, retry-after answers, a hit counter with time buckets, and a full Java 17 solution.

Patterns usedFacadeFactory methodStrategyComposite

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
1 / 19

Press play to hear the narration, or step through at your own pace. The full Java code is below.

Full Java solution

One file, Java 17, 267 lines, with a small main() demo. Save it as RateLimiter.java, then run javac RateLimiter.java && java RateLimiter.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.function.LongSupplier;

/** A per-key rate limiter library: pluggable algorithms, one state object per key, an injectable clock. */
public class RateLimiter {

    // ---------- the model ----------
    /** What the caller gets back: allowed or not, how many are left, and when to retry. */
    record Decision(boolean allowed, long remaining, long retryAfterMs) {
        static Decision allow(long remaining) { return new Decision(true, remaining, 0); }

        static Decision deny(long retryAfterMs) { return new Decision(false, 0, retryAfterMs); }
    }

    /** At most limit requests per windowMs. The token bucket reads it as capacity and refill rate. */
    record Rule(int limit, long windowMs) {}

    /** Which rule applies to a key: per user tier, per API route, per IP. */
    interface RuleSource { Rule ruleFor(String key); }

    enum Algorithm { TOKEN_BUCKET, FIXED_WINDOW, SLIDING_LOG, SLIDING_COUNTER }

    /** One instance per key. Every implementation guards its own few fields with its own monitor. */
    interface Limiter { Decision tryAcquire(long now); }

    // ---------- the strategies ----------
    /** Tokens refill one every windowMs / limit; a burst up to the capacity is allowed. Integer math only. */
    static final class TokenBucket implements Limiter {
        private final long capacity;
        private final long refillEveryMs;
        private long tokens;
        private long lastRefill;

        TokenBucket(Rule r, long now) {
            capacity = r.limit();
            refillEveryMs = Math.max(1, r.windowMs() / r.limit());
            tokens = capacity;
            lastRefill = now;
        }

        public synchronized Decision tryAcquire(long now) {
            long earned = (now - lastRefill) / refillEveryMs;
            if (earned > 0) {
                tokens = Math.min(capacity, tokens + earned);
                lastRefill += earned * refillEveryMs; // keep the partial interval
            }
            if (tokens > 0) {
                tokens--;
                return Decision.allow(tokens);
            }
            return Decision.deny(lastRefill + refillEveryMs - now);
        }
    }

    /** Count per aligned window. Cheap, but allows up to 2x the limit across a window boundary. */
    static final class FixedWindow implements Limiter {
        private final Rule rule;
        private long windowStart = Long.MIN_VALUE;
        private int count;

        FixedWindow(Rule rule) { this.rule = rule; }

        public synchronized Decision tryAcquire(long now) {
            long start = now - now % rule.windowMs();
            if (start != windowStart) {
                windowStart = start;
                count = 0;
            }
            if (count < rule.limit()) {
                count++;
                return Decision.allow(rule.limit() - count);
            }
            return Decision.deny(windowStart + rule.windowMs() - now);
        }
    }

    /** Exact: keep a timestamp per accepted request. Memory grows with the limit. */
    static final class SlidingLog implements Limiter {
        private final Rule rule;
        private final Deque<Long> log = new ArrayDeque<>();

        SlidingLog(Rule rule) { this.rule = rule; }

        public synchronized Decision tryAcquire(long now) {
            while (!log.isEmpty() && log.peekFirst() <= now - rule.windowMs()) log.pollFirst();
            if (log.size() < rule.limit()) {
                log.addLast(now);
                return Decision.allow(rule.limit() - log.size());
            }
            return Decision.deny(log.peekFirst() + rule.windowMs() - now);
        }
    }

    /** Two counters: the previous window, weighted by how much of it still overlaps, plus the current one. */
    static final class SlidingCounter implements Limiter {
        private final Rule rule;
        private long currentStart = Long.MIN_VALUE;
        private long current;
        private long previous;

        SlidingCounter(Rule rule) { this.rule = rule; }

        public synchronized Decision tryAcquire(long now) {
            long w = rule.windowMs();
            long start = now - now % w;
            if (start != currentStart) {
                previous = (start - currentStart == w) ? current : 0;
                current = 0;
                currentStart = start;
            }
            double overlap = 1.0 - (double) (now - start) / w;
            double estimate = previous * overlap + current;
            if (estimate + 1 <= rule.limit()) {
                current++;
                return Decision.allow((long) (rule.limit() - estimate - 1));
            }
            return Decision.deny(start + w - now);
        }
    }

    /** Factory: callers name an algorithm, each key gets its own fresh state. */
    static Limiter create(Algorithm a, Rule r, long now) {
        return switch (a) {
            case TOKEN_BUCKET -> new TokenBucket(r, now);
            case FIXED_WINDOW -> new FixedWindow(r);
            case SLIDING_LOG -> new SlidingLog(r);
            case SLIDING_COUNTER -> new SlidingCounter(r);
        };
    }

    // ---------- the facade ----------
    private final Algorithm algorithm;
    private final RuleSource rules;
    private final LongSupplier clock;
    private final Map<String, Limiter> limiters = new ConcurrentHashMap<>();

    RateLimiter(Algorithm algorithm, RuleSource rules, LongSupplier clock) {
        this.algorithm = algorithm;
        this.rules = rules;
        this.clock = clock;
    }

    /** computeIfAbsent creates the state for a new key exactly once, even when threads race. */
    Decision tryAcquire(String key) {
        long now = clock.getAsLong();
        return limiters.computeIfAbsent(key, k -> create(algorithm, rules.ruleFor(k), now)).tryAcquire(now);
    }

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

    // ---------- follow-up: hit counter with time buckets ----------
    /** Hits in the last N seconds using N buckets, so memory stays fixed however many hits arrive. */
    static final class HitCounter {
        private final int seconds;
        private final long[] stamp;
        private final long[] count;

        HitCounter(int seconds) {
            this.seconds = seconds;
            stamp = new long[seconds];
            count = new long[seconds];
        }

        synchronized void hit(long second) {
            int i = (int) (second % seconds);
            if (stamp[i] != second) { // this bucket holds an old second: reuse it
                stamp[i] = second;
                count[i] = 0;
            }
            count[i]++;
        }

        synchronized long hits(long second) {
            long total = 0;
            for (int i = 0; i < seconds; i++) if (second - stamp[i] < seconds) total += count[i];
            return total;
        }
    }

    // ---------- demo ----------
    static String run(RateLimiter rl, String key, int times) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < times; i++) {
            Decision d = rl.tryAcquire(key);
            sb.append(d.allowed() ? "Y" : "n");
        }
        return sb.toString();
    }

    static void check(boolean ok, String what) {
        if (!ok) throw new AssertionError(what);
    }

    public static void main(String[] args) throws InterruptedException {
        AtomicLong now = new AtomicLong(0);
        RuleSource tiers = key -> key.startsWith("pro:") ? new Rule(20, 1000) : new Rule(5, 1000);

        // 1. Token bucket: a burst of 5, then one token every 200 ms.
        RateLimiter tb = new RateLimiter(Algorithm.TOKEN_BUCKET, tiers, now::get);
        String burst = run(tb, "free:reader", 7);
        Decision denied = tb.tryAcquire("free:reader");
        System.out.println("token bucket t=0     " + burst + "  retry after "
                + denied.retryAfterMs() + " ms");
        now.set(400);
        String later = run(tb, "free:reader", 3);
        System.out.println("token bucket t=400   " + later);
        check(burst.equals("YYYYYnn") && later.equals("YYn"), "token bucket");
        System.out.println("pro key, same time   " + run(tb, "pro:editor", 7) + "  (own bucket, limit 20)");

        // 2. The boundary burst: 5 just before a window ends, 5 just after.
        for (Algorithm a : new Algorithm[] {Algorithm.FIXED_WINDOW, Algorithm.SLIDING_LOG,
                Algorithm.SLIDING_COUNTER}) {
            AtomicLong t = new AtomicLong(999);
            RateLimiter rl = new RateLimiter(a, tiers, t::get);
            String before = run(rl, "free:writer", 5);
            t.set(1000);
            String after = run(rl, "free:writer", 5);
            long allowed = (before + after).chars().filter(c -> c == 'Y').count();
            System.out.printf("%-16s t=999 %s t=1000 %s -> %d in 2 ms%n", a, before, after, allowed);
            check(allowed == (a == Algorithm.FIXED_WINDOW ? 10 : 5), "boundary " + a);
        }

        // 3. Sixteen threads, one key, a frozen clock: exactly the limit gets through.
        now.set(5000);
        RateLimiter shared = new RateLimiter(Algorithm.TOKEN_BUCKET, k -> new Rule(50, 1000), now::get);
        AtomicInteger ok = new AtomicInteger();
        CountDownLatch go = new CountDownLatch(1);
        ExecutorService pool = Executors.newFixedThreadPool(16);
        for (int i = 0; i < 16; i++) {
            pool.submit(() -> {
                try {
                    go.await();
                    for (int j = 0; j < 100; j++) {
                        if (shared.tryAcquire("api:search").allowed()) ok.incrementAndGet();
                    }
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
        }
        go.countDown();
        pool.shutdown();
        check(pool.awaitTermination(5, TimeUnit.SECONDS), "pool finished");
        System.out.println("race: 1600 attempts, " + ok.get() + " allowed, keys tracked "
                + shared.trackedKeys());
        check(ok.get() == 50 && shared.trackedKeys() == 1, "race");

        // 4. Hit counter over the last 300 seconds.
        HitCounter hc = new HitCounter(300);
        hc.hit(1);
        hc.hit(1);
        hc.hit(2);
        hc.hit(300);
        System.out.println("hits in last 300 s: at 300 -> " + hc.hits(300) + ", at 301 -> " + hc.hits(301));
        check(hc.hits(300) == 4 && hc.hits(301) == 2, "hit counter");
        System.out.println("all checks passed");
    }
}

Notes

Requirements

Fix the scope first. The library has one main call, try acquire, with a key such as a user id, an API key or an IP address. Each key gets a rule like five requests per second, and paid tiers get bigger rules. The algorithm is chosen when the limiter is built. A denial says how long to wait. Calls must be fast and safe from many threads. Limiting across many servers is a follow-up, so say it is out of scope for now.

Ask the questions that pick the algorithm. Are short bursts fine? Then a token bucket fits. Must the limit hold over every rolling window, with no exceptions? Then a sliding log or a sliding counter. Should a caller block until allowed, or be rejected? Reject, with a retry-after hint. And how many keys? If it is millions, the state per key must be a few numbers, not a list of timestamps.

Requirements
  • tryAcquire(key): allow or deny
  • key: user id, API key, IP
  • rule: N requests per window
  • different rules per tier
  • algorithm chosen at build
  • deny says when to retry
  • O(1) or close per call
  • safe from many threads
  • out of scope: many servers
  • sharing one limit (later)
Clarify first
  • bursts allowed?
  • yes, up to the limit at once
  • strict over any window?
  • sometimes: offer sliding
  • blocking or reject?
  • reject now, say retry after
  • one rule per key or several?
  • one now, stacking later
  • memory per key?
  • small: millions of keys

Entities

The entities. The rate limiter is a facade the callers see. Inside, a concurrent map holds one small limiter object per key, created on first use. A rule source says which rule applies to a key, so free and paid users can differ. A clock is injected so tests can move time. And every call returns a decision: allowed or not, how many are left, and how long to wait before retrying.

Class diagram

Turn them into types. A rule is a record: a limit and a window in milliseconds. A decision is a record too, so it is safe to hand to any thread. The rule source is a one-method interface, so a lambda can map paid keys to a bigger rule. And the limiter interface has one method that takes the current time. Passing time in, rather than reading the clock inside, keeps every algorithm a pure, testable piece of state.

Types
record Rule(int limit, long windowMs)
record Decision(boolean allowed,
    long remaining, long retryAfterMs)
interface RuleSource {
  Rule ruleFor(String key); }
interface Limiter {
  Decision tryAcquire(long now); }
enum Algorithm { TOKEN_BUCKET,
  FIXED_WINDOW, SLIDING_LOG,
  SLIDING_COUNTER }

Strategy: algorithm

The algorithm is a Strategy. Four classes implement the same limiter interface, and the facade only ever calls try acquire. Token bucket allows bursts and stores two numbers. Fixed window is the simplest but leaks at window edges. Sliding log is exact but stores a timestamp per request. Sliding counter is nearly exact with three numbers. Naming the trade-off for each one is what interviewers listen for.

Pick by trade-off
  • token bucket: bursts OK,
  • 2 numbers per key
  • fixed window: simplest,
  • 2x burst at the boundary
  • sliding log: exact,
  • one timestamp per request
  • sliding counter: near exact,
  • 3 numbers per key

Token bucket

The token bucket. A bucket holds up to five tokens and earns one every two hundred milliseconds. There is no timer thread: on each call we work out how many tokens were earned since the last refill, add them up to the capacity, and move the refill time forward by whole intervals, so partial progress is kept. Spend a token to allow. With none left, the retry time is when the next token lands. Integer math only, so nothing drifts.

TokenBucket.tryAcquire
earned = (now - lastRefill) / every
if (earned > 0) {
  tokens = min(capacity, tokens + earned)
  lastRefill += earned * every
}
if (tokens > 0) { tokens--; allow }
else deny(lastRefill + every - now)

5 per second: every = 200 ms
t=0: 5 allowed, then retry in 200

Fixed window

The fixed window keeps one counter per aligned window, say each whole second, and resets it when a new window starts. It is tiny and fast, but it has a famous flaw. Send five requests at nine hundred ninety-nine milliseconds and five more at one thousand: they land in different windows, so all ten pass within two milliseconds. That is double the limit. Always point this out yourself before the interviewer does.

FixedWindow
start = now - now % windowMs
if (start != windowStart) {
  windowStart = start; count = 0;
}
if (count < limit) { count++; allow }
else deny(windowStart + window - now)

limit 5 per second:
  t=999  YYYYY
  t=1000 YYYYY  (new window)

Sliding log

The sliding log fixes the edge. Keep a queue of the times of accepted requests. On each call, drop timestamps older than one window, then allow only if fewer than the limit remain, and record the new time. At one thousand milliseconds the five requests from nine hundred ninety-nine are still in the log, so all five new ones are denied. It is exact, but a limit of ten thousand per hour means up to ten thousand timestamps per key.

SlidingLog
Deque<Long> log  // accepted times

while (head <= now - windowMs)
  log.pollFirst()      // too old
if (log.size() < limit) {
  log.addLast(now); allow
}
else deny(head + windowMs - now)

memory: up to limit stamps per key

Sliding counter

The sliding window counter is the practical middle ground. Keep only two counts: the previous window and the current one. Estimate the rolling count as the previous count, weighted by how much of that window still overlaps the last second, plus the current count. Right at the boundary the overlap is one, so the five earlier requests still count and new ones are denied. Three numbers per key, and the error is small because it assumes the old requests were spread evenly.

SlidingCounter
overlap = 1 - (now - start) / window
estimate = previous * overlap
         + current
if (estimate + 1 <= limit) {
  current++; allow
}

limit 5, previous window had 5,
  250 ms into the new one:
  5 x 0.75 + 0 = 3.75, allow 1

Factory: per-key state

Per-key state comes from a small factory: a switch over the algorithm enum returns a fresh limiter built with that key's rule. The facade looks the key up with compute if absent on a concurrent map, which runs the factory at most once per key even when two threads see a new key at the same moment. If we used get and then put instead, two threads could each create a bucket, and each would let five requests through.

Facade + factory
Decision tryAcquire(String key) {
  long now = clock.getAsLong();
  return limiters.computeIfAbsent(key,
      k -> create(algorithm,
          rules.ruleFor(k), now))
    .tryAcquire(now);
}
create(): switch over Algorithm,
  a fresh object per key

Flow: tryAcquire

Walk one call. The facade reads the clock once, finds or creates the state for the key, and asks it. The eighth request in the same instant gets a denial with retry after two hundred milliseconds. The limiter only returns a decision; the caller decides what to do with it. A web filter turns a denial into status four twenty-nine with a retry-after header, and a background job might simply wait that long.

At the HTTP edge
  • allowed: handle the request
  • header: remaining = 3
  • denied: status 429
  • header: Retry-After
  • the limiter returns data;
  • the caller picks the reply

Concurrency

Concurrency. Refill, check and spend must happen as one step, or two threads can both see one token left and both take it. So each limiter's method is synchronized on that limiter only. Different keys have different locks, so user A never waits for user B, and the lock is held for a few nanoseconds. In the demo, sixteen threads make sixteen hundred calls on one key with a limit of fifty, and exactly fifty get through, every run.

Thread safety
  • map: ConcurrentHashMap
  • new key: computeIfAbsent
  • each Limiter: synchronized
  • methods, a few fields
  • refill + check + spend is
  • one atomic step
  • test: 16 threads x 100 calls
  • on one key, limit 50
  • allowed: exactly 50

Extensibility

Now the extensions. Several rules on one key, like ten per second and a thousand per hour, is a composite that allows only if every rule allows. Idle keys must be evicted after a quiet period, or the map grows forever. Across many servers, the state moves to a shared store, with refill, check and spend in one atomic script, or each server takes a share of the global limit locally. A new algorithm is just one new class.

Extension points
  • several rules on one key:
  • 10/s AND 1000/hour, all pass
  • idle keys: evict after an hour
  • of silence (sweep or a cache)
  • many servers: state in Redis,
  • check-and-spend in one Lua
  • script, or local buckets with
  • a share of the global limit
  • new algorithm: one new class

Follow-up: hit counter

A common follow-up is a hit counter: how many hits in the last five minutes? Storing every hit is the sliding log again, and it grows without bound. Instead keep three hundred buckets, one per second, each with the second it belongs to and a count. A hit finds its bucket by the second modulo three hundred, resets it if it holds an old second, and adds one. Reading sums the buckets that are still inside the window. Memory is fixed.

HitCounter, 300 buckets
long[] stamp, count  // one per second
hit(sec):
  i = sec % 300
  if (stamp[i] != sec)
    { stamp[i] = sec; count[i] = 0; }
  count[i]++
hits(sec): sum count[i] where
  sec - stamp[i] < 300
memory fixed, however many hits

Testing

The full code is below the player. The demo uses a fake clock, so a burst of seven at time zero gives five yeses and two nos with a retry of two hundred milliseconds, and four hundred milliseconds later two more pass. It replays the boundary burst against three algorithms: the fixed window lets ten through, the sliding ones only five. Then the sixteen-thread race, and the hit counter. Every result is asserted.

Run it
token bucket t=0     YYYYYnn
  retry after 200 ms
token bucket t=400   YYn
FIXED_WINDOW    -> 10 in 2 ms
SLIDING_LOG     -> 5 in 2 ms
SLIDING_COUNTER -> 5 in 2 ms
race: 1600 attempts, 50 allowed
hits: at 300 -> 4, at 301 -> 2
all checks passed

Follow-ups

Expect follow-ups. Why not one global lock? Every user would queue behind every other. What if the wall clock jumps back? Use a monotonic clock, like nano time. Expensive calls should cost more? Spend several tokens at once. A client that prefers waiting can sleep for the retry-after time. And across servers, either keep the state in a shared store and update it atomically, or split the limit between nodes and accept a little slack.

Follow-ups to expect
  • why not one global lock?
  • all users would queue
  • clock goes backwards?
  • use a monotonic clock
  • limit by cost, not count?
  • spend N tokens per call
  • wait instead of reject?
  • sleep for retryAfter
  • distributed: atomic script
  • or split the limit per node

Say it like this

The short version to say out loud. A facade keeps one small limiter per key in a concurrent map, created once by a factory from that key's rule. The algorithm is a strategy: token bucket when bursts are fine, sliding window counter when the limit must hold over any second, and I know why a fixed window leaks double at the edge. Each limiter synchronizes on itself, so keys never contend, and time is injected for tests.

In the interview
  • "A facade keeps one small
  • limiter per key in a concurrent
  • map, built by a factory from
  • the key's rule. The algorithm
  • is a strategy: token bucket for
  • bursts, sliding counter for
  • strict limits. Each limiter is
  • synchronized on itself."

Interview questions

How does a token bucket work, and why does it need no timer thread?

Each key has a bucket with a capacity and a refill rate. On every call you compute the tokens earned since the last refill from the elapsed time, cap at the capacity, and spend one if available. Refilling lazily on each call gives the same result as a timer, with no thread per key.

What is wrong with a fixed window counter?

Counts reset at aligned window edges, so a client can send the full limit just before the edge and again just after it, getting twice the limit in a moment. Sliding log or sliding window counter algorithms remove that burst.

Sliding log versus sliding window counter: when do you choose each?

The sliding log keeps a timestamp per accepted request and is exact, but memory grows with the limit. The sliding window counter keeps two counts and weights the previous one by its overlap, which is approximate but constant memory, so it suits millions of keys.

How do you make the limiter thread-safe without slowing everyone down?

Keep state per key and synchronize each key's limiter on itself, so refill, check and spend are atomic for that key while different keys never contend. Create per-key state with ConcurrentHashMap.computeIfAbsent so two threads cannot create two buckets for one new key.

Why make the algorithm a Strategy?

The facade logic, finding per-key state and returning a decision, is identical for every algorithm. With a Limiter interface and a factory switch over an Algorithm enum, adding a new algorithm is one class and the callers never change.

What should a denied request return?

A decision with allowed false and the time until a request would succeed: when the next token lands, or when the oldest logged request leaves the window. An HTTP layer maps it to status 429 with a Retry-After header.

How would you rate limit across many servers?

Move the per-key state to a shared store and run refill, check and spend as one atomic operation there, such as a server-side script. Or give each server a share of the limit and keep buckets local, trading a little accuracy for no network hop.

How do you count hits in the last five minutes with fixed memory?

Use 300 buckets, one per second, each storing the second it represents and a count. A hit goes to bucket second mod 300, resetting it if it holds an old second; the total sums buckets whose second is still inside the window.