!This gives away every stage. For a clean attempt, practise it first, then come back.

How this walkthrough is built

If the algorithms themselves are new to you, lesson 6.3 explains each one with pictures. Here we focus on turning them into classes.

Step 1Understand the problem

Picture the real thing first

You call a weather API from a script. It works for a while, then every request comes back 429 Too Many Requests with a header saying “try again in 12 seconds”. Somewhere inside that API, a small piece of code counted your requests, compared them with your plan’s limit, and said no. That piece of code runs on every single request, for every customer, so it has to be fast, correct, and tiny.

Ask before you design

Group the questions: what’s limited, the rules, what happens on “no”, how it’s called, and how long it runs.

Functional requirements

1. FR1. tryAcquire(key) answers allowed or denied for one request.
2. FR2. Each key has its own limit: N requests per period, looked up per key.
3. FR3. A denied answer says how long to wait; an allowed answer says how many are left.
4. FR4. The counting algorithm can be chosen: fixed window, sliding log, sliding counter, token bucket.
5. FR5. Several limits can apply to one key at once.

Non-functional requirements

1. NFR1: Correct under concurrency. Many threads, same key: never more allowed than the algorithm permits.
2. NFR2: Fast. Different keys never wait for each other.
3. NFR3: Bounded memory. Keys that go quiet are forgotten.
4. NFR4: Testable. Time is passed in, so tests can run minutes of traffic instantly and the same way every time.

Assumptions we’ll write down

Step 2Break it into entities

Pull out the nouns

Request, key, user, IP, limit, plan, tier, period, window, count, bucket, token, timestamp, decision, retry-after, remaining, algorithm, clock.

Three questions that decide if a noun is a class

The trap: one class that does everything

The common first answer:

class RateLimiter {
    Map counts = new HashMap<>();
    Map windowStart = new HashMap<>();
    int limit = 100;

    synchronized boolean allow(String key) {
        long now = System.currentTimeMillis();
        // reset the window if a minute has passed, then count
        ...
    }
}

It works for one algorithm, one limit, one thread at a time. Look at what’s tangled together:

• The algorithm (fixed window) is welded in. Switching to a token bucket means rewriting the class.
• The state lives in two parallel maps keyed by the same string. Every algorithm needs different state (a count, a list of times, a token level), so every algorithm would need different maps here.
• The rule (limit = 100) is a field, the same for every key.
• The clock is System.currentTimeMillis(), so a test of “after a minute” must wait a minute.
• One lock for everything: synchronized on the method means a request for key A waits for a request for key B.

The fix is to notice that an algorithm is really two things: a recipe (fixed window, token bucket) and the state that recipe keeps for each key. So:

• Algorithm is a factory: given a limit, it makes a fresh KeyState.
• KeyState holds one key’s numbers and answers tryAcquire(now). It locks only itself.
• RateLimiter just keeps a map from key to KeyState, creating one on first use.

Now each algorithm keeps exactly the state it needs, in its own small class, and two keys never share a lock.

Pull out the verbs

Look up the limit, find the key’s state, create it, count, decide, say how long to wait, forget idle keys.

Give each job to the class that knows the most

That last row matters. Only the state knows whether it has anything worth remembering, so the state answers idleSince(now), not the limiter.

Find what will change

Step 3Top-down or bottom-up?

Top-down: the gateway calls tryAcquire(key) and needs a Decision. The limiter needs the time, the key’s limit, and the key’s state. The state needs an algorithm to create it.

Bottom-up: first one KeyState for each algorithm, tested alone with a fake clock against exact expected numbers. Then the factory and the limiter.

Step 4Design each class

RateLimiter: the front door

It uses ConcurrentHashMap.computeIfAbsent to create a key’s state exactly once, even if two threads see a new key at the same moment.

Algorithm and KeyState: the recipe and the numbers

Algorithm.newState(limit, now) returns a fresh KeyState. KeyState has two methods: tryAcquire(now) and idleSince(now).

The token bucket deserves a note. The usual description keeps “tokens” and “last refill time” and refills on each request. Ours keeps a single number, the moment at which the bucket would be full again, and moves it forward by one token’s worth of time per request. It’s the same bucket, written with one integer and no fractions. (This form is sometimes called GCRA, the generic cell rate algorithm, from old telephone networks.)

Limit, Decision, Ticker: the vocabulary

Limit is permits and a period, both positive. Decision is allowed, remaining, and how long to wait. Ticker returns nanoseconds; production passes System::nanoTime, tests pass a fake.

Why nanoTime and not the wall clock? The wall clock can jump: a server syncing its time can move backwards by a second, and a limiter reading it would think a window ended early. nanoTime only moves forwards.

Step 5How the classes relate

Step 6The class diagram, built up

Version 1: the limiter and its states

Version 2: algorithms as factories

Version 3: the whole picture

SlidingCounter, Decision and the per-algorithm state classes are left off. Each algorithm’s state class is a small inner class that only its algorithm can create.

Check it against the requirements

Step 7The patterns, and why each one is here

Why not a Singleton

“One rate limiter for the gateway” is true today. But you’ll want one limiter for logins (by IP, strict) and another for the API (by key, generous), and every test wants a fresh one with a fake clock. Create them and pass them in.

Patterns we deliberately didn’t use

• Decorator for combining limits. It’s tempting to wrap one limiter in another, and step 11 shows exactly why that wastes quota.
• Observer for “a key was limited”. Useful for metrics, but returning a Decision already lets the gateway log what it likes.

Step 8Walk the flows

A request

From a real run, seven requests at the same instant against 5 per second:

One token comes back every 200 ms (a second divided by 5), so “retry in 200 ms” is exactly right, and 200 ms later one request gets through.

The same attack against all four algorithms

How strict is each algorithm, really? We ran one test against all four: a limit of 100 per minute, and a client that tries every 10 ms for 5 minutes, starting halfway through a minute. Then we found the most requests allowed in any 60-second stretch:

What each line means:

• Fixed window resets at each minute boundary, so a client can use 100 in the last second of one minute and 100 in the first second of the next. We tested that exact pattern: 100 allowed at 0:59 and 100 more at 1:00.5, 200 in a second and a half.
• Sliding log is exact: never more than 100 in any 60 seconds. The cost is memory: it stores the time of every allowed request.
• Sliding counter guesses the last minute from two counters, assuming last minute’s requests were spread evenly. Against a client that bursts, the guess can be off: up to 149 here.
• Token bucket allows 199 in a minute, and that’s not a bug. A bucket promises “at most 100 at once, refilling at 100 per minute”. A client that empties a full bucket, then takes each token as it refills, gets 100 + 99 in one minute. If your contract says “never more than 100 in any minute”, a token bucket of capacity 100 doesn’t meet it.

That last point is the kind of thing that wins an interview: knowing what each algorithm actually promises, not just its name. If the interviewer says “short bursts are fine, keep the average”, token bucket. If they say “never more than 100 in any minute, no exceptions”, sliding log, or a token bucket with a smaller capacity.

What walking the flows taught us

The life of a key’s state

Step 9Write the code, bottom-up

Complete Java. Every output on this page comes from running it.

9.1 Time, limits and decisions

interface Ticker { long nanos(); }

record Limit(long permits, long periodNanos) {
    Limit {
        if (permits <= 0 || periodNanos <= 0)
            throw new IllegalArgumentException("bad limit");
    }
    static Limit perSecond(long n) { return new Limit(n, 1_000_000_000L); }
    static Limit perMinute(long n) { return new Limit(n, 60_000_000_000L); }
}

record Decision(boolean allowed, long remaining, long retryAfterNanos) {
    static Decision allow(long remaining) { return new Decision(true, remaining, 0); }
    static Decision deny(long retryAfterNanos) {
        return new Decision(false, 0, retryAfterNanos);
    }
}

interface KeyState {
    Decision tryAcquire(long now);
    boolean idleSince(long now);                              // (1)
}

interface Algorithm {
    KeyState newState(Limit limit, long now);
}

1. “Is this state the same as a brand-new one would be?” Step 10 explains why that’s the right question for eviction.

9.2 Fixed window

final class FixedWindow implements Algorithm {
    public KeyState newState(Limit limit, long now) {
        return new KeyState() {
            private long windowStart = now - Math.floorMod(now, limit.periodNanos());
            private long count;

            public synchronized Decision tryAcquire(long t) {
                if (t - windowStart >= limit.periodNanos()) {
                    windowStart = t - Math.floorMod(t, limit.periodNanos());   // (2)
                    count = 0;
                }
                if (count < limit.permits())
                    return Decision.allow(limit.permits() - ++count);
                return Decision.deny(windowStart + limit.periodNanos() - t);
            }

            public synchronized boolean idleSince(long t) {
                return t - windowStart >= limit.periodNanos();
            }
        };
    }
}

1. Windows line up with the clock (every whole minute), not with the key’s first request.

Each state is an anonymous class: a class with no name, written inline, which can only be created here. Nothing outside FixedWindow can make or poke at a fixed-window state.

9.3 Sliding log

final class SlidingLog implements Algorithm {
    public KeyState newState(Limit limit, long now) {
        return new KeyState() {
            private final ArrayDeque times = new ArrayDeque<>();

            public synchronized Decision tryAcquire(long t) {
                while (!times.isEmpty() && t - times.peekFirst() >= limit.periodNanos())
                    times.pollFirst();                                   // (3)
                if (times.size() < limit.permits()) {
                    times.addLast(t);
                    return Decision.allow(limit.permits() - times.size());
                }
                return Decision.deny(times.peekFirst() + limit.periodNanos() - t);
            }

            public synchronized boolean idleSince(long t) {
                return times.isEmpty() || t - times.peekLast() >= limit.periodNanos();
            }
        };
    }
}

1. Drop every request older than one period. What’s left is exactly the last period’s requests.

Exact, and expensive: we measured about 28.8 KB per busy key at 1,000 per minute, because it keeps a thousand boxed timestamps. Ten thousand busy keys would be 288 MB.

9.4 Sliding counter

final class SlidingCounter implements Algorithm {
    public KeyState newState(Limit limit, long now) {
        return new KeyState() {
            private final long p = limit.periodNanos();
            private long windowStart = now - Math.floorMod(now, p);
            private long current, previous;

            public synchronized Decision tryAcquire(long t) {
                long start = t - Math.floorMod(t, p);
                if (start != windowStart) {
                    previous = start - windowStart == p ? current : 0;   // (4)
                    current = 0;
                    windowStart = start;
                }
                double weight = 1.0 - (double) (t - windowStart) / p;   // (5)
                double estimate = previous * weight + current;
                if (estimate + 1 <= limit.permits()) {
                    current++;
                    return Decision.allow((long) (limit.permits() - estimate - 1));
                }
                return Decision.deny(Math.max(1, p / limit.permits()));
            }

            public synchronized boolean idleSince(long t) {
                return t - windowStart >= 2 * p;
            }
        };
    }
}

1. If a whole window passed with no requests, the previous count is zero, not whatever was last seen.
2. Twenty seconds into a minute, the last 60 seconds include 40 seconds of the previous minute: weight 2/3.

9.5 Token bucket

final class TokenBucket implements Algorithm {
    public KeyState newState(Limit limit, long now) {
        return new KeyState() {
            private final long cost = limit.periodNanos() / limit.permits();  // (6)
            private final long capacity = limit.periodNanos();
            private long full = now;                                       // (7)

            public synchronized Decision tryAcquire(long t) {
                long earliest = Math.max(full, t);
                long next = earliest + cost;
                if (next - t > capacity) return Decision.deny(next - t - capacity);
                full = next;
                return Decision.allow((capacity - (next - t)) / cost);
            }

            public synchronized boolean idleSince(long t) { return t >= full; }
        };
    }
}

1. Each request “costs” one token’s worth of time: a minute ÷ 100 = 600 ms.
2. full is when the bucket would be completely refilled. If it’s in the past, the bucket is full now. Each request pushes it forward by cost. If that would push it more than one whole period past now, the bucket is empty: deny, and the wait is exactly how far over we’d be.

One long of state per key, no fractions, no refill loop.

9.6 The limiter

final class RateLimiter {
    private final Algorithm algorithm;
    private final Function limits;
    private final Ticker ticker;
    private final ConcurrentHashMap states = new ConcurrentHashMap<>();

    RateLimiter(Algorithm algorithm, Function limits, Ticker ticker) {
        this.algorithm = algorithm;
        this.limits = limits;
        this.ticker = ticker;
    }

    Decision tryAcquire(String key) {
        long now = ticker.nanos();
        KeyState s = states.computeIfAbsent(key,
            k -> algorithm.newState(limits.apply(k), now));            // (1)
        return s.tryAcquire(now);
    }

    int evictIdle() {
        long now = ticker.nanos();
        int before = states.size();
        states.entrySet().removeIf(e -> e.getValue().idleSince(now)); // (2)
        return before - states.size();
    }

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

1. The limit is looked up once, when the key’s state is created. Changing a key’s plan takes effect when its state is next recreated: worth saying, and step 11 has the alternative.
2. Forget every state that’s indistinguishable from a new one.

Usage: new RateLimiter(new TokenBucket(), key -> key.startsWith("paid") ? Limit.perMinute(1000) : Limit.perMinute(100), System::nanoTime).

Step 10Make it safe

The race inside a key

The token bucket’s update is read full, work out next, write full. Two threads can both read the same full, both decide there’s room, and both write. We ran 8 threads sending 40,000 requests at one key with a limit of 1,000 and no time passing:

Up to 5% too many, different every run. Not dramatic, which is exactly why it survives code review.

One lock per key, not one for everything

Each KeyState method is synchronized on that state. Two requests for the same key take turns; requests for different keys never meet. We compared it with one lock around the whole limiter, 8 threads making 8 million checks across 1,000 keys:

one lock for everything: 8M checks in 600 ms
lock per key: 8M checks in 373 ms

Per-key locking was about 1.6 times faster here, and the gap grows with more threads, because a single lock means only one thread is ever inside the limiter.

A million keys that never come back

1M addresses, one request each: tracked keys = 1000000
evict after 0.5 s: removed 0, tracked 1000000
evict after 1.5 s: removed 1000000, tracked 0

Without eviction, a gateway limiting by IP keeps a state for every address that ever called it, and memory only grows. A timer that calls evictIdle() every few seconds fixes that. Half a second after the burst, every bucket still had a token being refilled (one costs 600 ms at 100 per minute), so nothing was removed. A second later, every bucket was full again, and all million were forgotten.

Why eviction is safe without a lock

There’s a real race here. Thread A looks up key K and gets its state. The evictor removes K’s state. Thread A then counts a request on the state it’s holding, which is no longer in the map. Thread B creates a fresh state for K.

What did that cost? The evictor only removes states that are indistinguishable from brand-new ones. So the fresh state B created is exactly what K’s state would have been anyway. The only loss is A’s single request, counted on the orphaned state: at worst one extra request let through, once, for a key that had been idle long enough to be forgotten. That’s why idleSince asks “would a new state look the same?”, not “has it been quiet for a while?”. Choosing the question carefully is what makes the cheap, lock-free eviction correct.

Step 11Follow-ups, extended without editing

Two limits at once

Bad solutionTwo limiters, one after the other

boolean allowed = perMinute.tryAcquire(key).allowed()
               && perSecond.tryAcquire(key).allowed();

If the per-minute limiter says yes and the per-second limiter says no, the per-minute token has already been spent on a request that was refused. Swap the order and the problem flips. We sent 10 requests a second for 2 minutes:

two limiters chained: allowed 53 in 2 minutes; first 6 s: [9, 5, 0, 1, 0, 0]
AllOf: allowed 59 in 2 minutes; first 6 s: [9, 5, 5, 2, 0, 0]

The chained version wasted per-minute quota on requests that the per-second limit refused, so the client ran dry early, in the third second, and got 53 of the 59 it was entitled to.

Good solutionCheck both, then spend both

Ask each limit “would you allow this?” without spending, and spend only if all say yes. But with two separate limiters, another thread can spend between your check and your spend.

Great solutionOne state that holds both limits

A new algorithm whose per-key state holds a bucket for every limit, checks all of them, and spends from all of them, inside one lock:

final class AllOf implements Algorithm {
    private final List limits;

    AllOf(List limits) { this.limits = List.copyOf(limits); }

    public KeyState newState(Limit ignored, long now) {
        return new KeyState() {
            private final long[] full = new long[limits.size()];
            { Arrays.fill(full, now); }

            public synchronized Decision tryAcquire(long t) {
                long wait = 0, left = Long.MAX_VALUE;
                long[] next = new long[full.length];
                for (int i = 0; i < full.length; i++) {               // (1)
                    Limit l = limits.get(i);
                    long cost = l.periodNanos() / l.permits();
                    next[i] = Math.max(full[i], t) + cost;
                    long over = next[i] - t - l.periodNanos();
                    if (over > 0) wait = Math.max(wait, over);
                    else left = Math.min(left, (l.periodNanos() - (next[i] - t)) / cost);
                }
                if (wait > 0) return Decision.deny(wait);                 // (2)
                System.arraycopy(next, 0, full, 0, full.length);          // (3)
                return Decision.allow(left);
            }

            public synchronized boolean idleSince(long t) {
                for (long f : full) if (t < f) return false;
                return true;
            }
        };
    }
}

1. Work out every bucket’s new value without changing anything.
2. If any limit says no, return with nothing spent. The wait is the longest of the limits’ waits.
3. Only now, spend from every bucket.

It’s a new Algorithm; RateLimiter doesn’t change. That’s the payoff of making the algorithm a factory for per-key state: a combined limit is just a different kind of state.

Limits that change while a key is active

Today the limit is read when a key’s state is created. If a user upgrades their plan, they keep the old limit until their state is evicted. If that’s not acceptable, give KeyState.tryAcquire the current Limit on every call instead of fixing it at creation. That’s a real interface change, so it’s worth deciding in the first ten minutes rather than discovering later. Say which you chose and why.

Expensive requests cost more

A search costs 10, a simple read costs 1. Add a permits argument to tryAcquire(key, permits): the token bucket moves full forward by cost × permits. Fixed windows add permits to the count. A new method with a default of 1 keeps every existing caller working.

Many gateway servers

Each server’s in-memory limiter only sees its own traffic, so a client spread over 10 servers gets 10 times the limit. Move the state: a KeyState whose tryAcquire runs a short script in Redis that does the same token bucket arithmetic atomically. The algorithm and the limiter are unchanged; only where the numbers live moves. The rate limiter system design walkthrough covers that version in depth: one Redis round trip per request, what to do when Redis is slow, and local pre-checks.

Mistakes people make on this one

• One class with the algorithm, state, rules and clock all welded together.
• *One synchronized method for every key,* so unrelated users wait for each other.
• No lock at all inside a key, and a few percent too many requests let through.
• *System.currentTimeMillis(),* which can jump backwards and can’t be faked in tests.
• A map of keys that only grows.
• Saying the token bucket enforces “at most N per minute”. It enforces a burst size and an average rate.
• Chaining two limiters, and wasting one limit’s quota on requests the other refuses.
• *Returning a bare boolean,* so callers can’t say when to retry.

How this answer gets scored

The whole design on one page

1. Separate four things: the limit (Limit), the recipe (Algorithm), the per-key numbers (KeyState) and the front door (RateLimiter).
2. Request: read the ticker, find or create the key’s state with computeIfAbsent, let the state decide under its own lock, return a Decision with remaining and retry-after.
3. Algorithms: fixed window (cheap, 2× at boundaries), sliding log (exact, memory per request), sliding counter (cheap estimate), token bucket (burst plus average rate, one long).
4. Concurrency: lock per key; nothing shared between keys.
5. Memory: forget states that look brand-new; that’s what makes lock-free eviction safe.
6. Extend: combined limits as one state (AllOf); weighted costs; Redis-backed state for many servers.