Design a Rate Limiter

1Clarify the requirements#

Before I draw a single box, I want to know what I'm actually building. "Rate limiter" can mean five different things, and picking the wrong one quietly wastes ten minutes. So I ask.

Questions I'd put to the interviewer:

• What are we limiting on? User ID, API key, IP, or tenant. This becomes my key, and it decides how many distinct buckets I keep in memory.
• What's the limit shape? "100 per minute" is a different machine from "10 per second with bursts allowed." One number plus one window is not enough.
• Do we allow bursts? Token bucket does by design; a strict fixed window does not. This single answer drives the algorithm choice, so I pin it down early.
• Single JVM or distributed? For an LLD round I build it clean for one process but keep storage swappable, so "now make it distributed" is a one-line change at the wiring, not a rewrite.
• What happens on reject? Boolean, throw, or tell the caller how long to wait? I return a decision object with a retry-after hint, because the caller almost always needs it for the 429.

Functional scope:

• Decide allow or deny for a given key.
• Different limits per key or per tier (free gets 10/min, paid gets 1000).
• More than one algorithm, because interviewers love "what if we wanted a sliding window instead?" and I want the design to shrug at that, not buckle.

Non-functional scope:

• Thread safe. Many requests hit the same key at the same instant, and two of them must not both spend the last token.
• Fast. This runs on the hot path of every request, so the decision is cheap: ideally zero I/O and a handful of arithmetic ops.
• Memory bounded. I can't keep state for keys that went quiet an hour ago and never came back.

I'll scope it to an in-process limiter with pluggable algorithms and pluggable storage. That hits the full design signal without drowning the 45 minutes in infra.

2Identify the core entities#

Here's how I carve it up, and why each piece exists:

• RateLimiter: the thing the caller talks to. Takes a key, returns a decision. Owns no algorithm logic itself, it delegates. Keeping it thin is deliberate.
• RateLimitStrategy: the algorithm. Token bucket, fixed window, sliding window log. This is the piece that actually decides allow or deny.
• RateLimitDecision: the answer. Allowed or not, remaining quota, and when to retry. A value object beats a bare boolean because the caller needs the retry hint for the 429, and I don't want to bolt that on later.
• RateLimitConfig: the rules. Limit count, window duration, burst size. Separated from the algorithm so one strategy class serves many tiers with different numbers.
• StateStore: where per-key counters live. In-memory map today, Redis tomorrow. Behind an interface, which is exactly what lets the design survive "now make it distributed."
• RateLimiterFactory: builds the right limiter from config, so callers never new up strategies by hand.

3Class design#

The caller holds a RateLimiter. The limiter holds a RateLimitStrategy and hands it the current per-key state fetched from a StateStore. The strategy mutates that state and returns a RateLimitDecision.

• Strategy pattern carries the weight: swap algorithms without touching callers.
• Factory keeps construction in one place so the wiring doesn't leak across the codebase.
• Config lives beside the strategy, so one strategy class works for many limits.

4Key implementation#

Start with the value types and the contracts. These are boring on purpose, and boring is good: nothing surprising happens in a record, which is where I want zero surprises.

public record RateLimitDecision(boolean allowed, long remaining, long retryAfterMillis) {
    static RateLimitDecision ok(long remaining) {
        return new RateLimitDecision(true, remaining, 0);
    }
    static RateLimitDecision denied(long retryAfterMillis) {
        return new RateLimitDecision(false, 0, retryAfterMillis);
    }
}

public record RateLimitConfig(long limit, long windowMillis, long burst) {}

public interface RateLimitStrategy {
    RateLimitDecision tryAcquire(KeyState state, RateLimitConfig config, long nowMillis);
}

Why pass now in rather than calling the clock inside the strategy:

• It makes the strategy a pure function of its inputs.
• I can fake time in a unit test and assert exact token counts, never touching Thread.sleep.
• The strategy gets everything it needs handed to it: the mutable per-key state, the rules, and the current time.

Now the per-key state and the store:

public final class KeyState {
    double tokens;      // used by token bucket
    long lastRefill;    // millis, used by token bucket
    long windowStart;   // used by fixed window
    long count;         // used by fixed window
    final Object lock = new Object();
}

public interface StateStore {
    KeyState getOrCreate(String key);
}

public final class InMemoryStateStore implements StateStore {
    private final ConcurrentHashMap<String, KeyState> map = new ConcurrentHashMap<>();

    @Override
    public KeyState getOrCreate(String key) {
        return map.computeIfAbsent(key, k -> new KeyState());
    }
}

Token bucket is my default answer. It allows bursts up to the bucket size and refills at a steady rate, which matches how real traffic behaves: quiet for a while, then a clump of requests. A client that's been idle should get to spend its saved-up headroom.

public final class TokenBucketStrategy implements RateLimitStrategy {

    @Override
    public RateLimitDecision tryAcquire(KeyState state, RateLimitConfig config, long nowMillis) {
        double refillPerMilli = (double) config.limit() / config.windowMillis();
        double capacity = config.burst() > 0 ? config.burst() : config.limit();

        synchronized (state.lock) {
            if (state.lastRefill == 0) {
                state.lastRefill = nowMillis;
                state.tokens = capacity;
            }
            long elapsed = nowMillis - state.lastRefill;
            if (elapsed > 0) {
                state.tokens = Math.min(capacity, state.tokens + elapsed * refillPerMilli);
                state.lastRefill = nowMillis;
            }
            if (state.tokens >= 1.0) {
                state.tokens -= 1.0;
                return RateLimitDecision.ok((long) state.tokens);
            }
            double needed = 1.0 - state.tokens;
            long waitMillis = (long) Math.ceil(needed / refillPerMilli);
            return RateLimitDecision.denied(waitMillis);
        }
    }
}

The refill is lazy, and that is the whole trick:

• No background thread adding tokens every tick.
• I compute how many tokens should have arrived since the last check and top up on the spot.
• With 100 per 60000 millis, refillPerMilli is about 0.00167 tokens/ms, multiplied by the elapsed gap.
• Cost on the hot path: one subtraction and one multiply. No timer per key, no scheduler.

Fixed window is simpler and sometimes exactly what the interviewer wants to hear next. It carries a known flaw I'll call out in the edge cases, which is itself a signal worth giving.

public final class FixedWindowStrategy implements RateLimitStrategy {

    @Override
    public RateLimitDecision tryAcquire(KeyState state, RateLimitConfig config, long nowMillis) {
        synchronized (state.lock) {
            long window = nowMillis / config.windowMillis();
            if (window != state.windowStart) {
                state.windowStart = window;
                state.count = 0;
            }
            if (state.count < config.limit()) {
                state.count++;
                return RateLimitDecision.ok(config.limit() - state.count);
            }
            long nextWindow = (state.windowStart + 1) * config.windowMillis();
            return RateLimitDecision.denied(nextWindow - nowMillis);
        }
    }
}

Finally the limiter and factory that tie it together:

public final class RateLimiter {
    private final RateLimitStrategy strategy;
    private final StateStore store;
    private final RateLimitConfig config;

    public RateLimiter(RateLimitStrategy strategy, StateStore store, RateLimitConfig config) {
        this.strategy = strategy;
        this.store = store;
        this.config = config;
    }

    public RateLimitDecision allow(String key) {
        KeyState state = store.getOrCreate(key);
        return strategy.tryAcquire(state, config, System.currentTimeMillis());
    }
}

public final class RateLimiterFactory {
    public enum Type { TOKEN_BUCKET, FIXED_WINDOW, SLIDING_WINDOW_LOG }

    public static RateLimiter build(RateLimitConfig config, Type type) {
        RateLimitStrategy strategy = switch (type) {
            case TOKEN_BUCKET -> new TokenBucketStrategy();
            case FIXED_WINDOW -> new FixedWindowStrategy();
            case SLIDING_WINDOW_LOG -> new SlidingWindowLogStrategy();
        };
        return new RateLimiter(strategy, new InMemoryStateStore(), config);
    }
}

Here's the runtime flow for a single allow call:

5Design decisions and patterns used#

• Strategy pattern is the backbone. RateLimitStrategy lets me drop in token bucket, fixed window, or sliding log without the caller knowing or caring. When the interviewer says "change the algorithm," I change one enum value in the factory and nothing else moves.
• Factory pattern in RateLimiterFactory centralizes construction. Callers pass config plus a type and get a fully wired limiter. No new TokenBucketStrategy() scattered through twenty call sites.
• Constructor injection: RateLimiter takes its strategy and store as arguments. That's what makes it unit-testable with a fake store, and what makes the swap to Redis a one-line change at the wiring rather than surgery inside the limiter.
• Interface-segregated storage: StateStore is the seam between in-process and distributed. One JVM uses ConcurrentHashMap. A fleet backs it with Redis and moves the acquire logic into a Lua script, so the whole read-modify-write decision is atomic on the Redis server, not racing across app nodes.

6Handling edge cases and concurrency#

Concurrency on a single key.

• Two threads hitting the same user at the same instant must not both read "1 token left" and both spend it.
• I lock per KeyState, not globally. Different keys never contend, so throughput scales with the number of distinct keys instead of serializing on one mutex.
• ConcurrentHashMap.computeIfAbsent guarantees exactly one shared state object per key, which is the whole premise the per-key lock rests on.

Fixed window's boundary burst.

• With a 100-per-minute window, a client sends 100 at 11:59:59 and 100 more at 12:00:01: 200 in two seconds, double the rate, right at the seam.
• I call this out before being asked and offer sliding window log or sliding window counter as the fix.
• Naming the flaw unprompted shows I understand the algorithm's failure mode, not just its happy path.

Clock behavior.

• I use elapsed-time math, so a monotonic-ish millis clock is fine.
• If the system clock jumps backward (NTP correction, VM migration), elapsed could go negative and the naive math would hand out free tokens or overwrite lastRefill with a stale value.
• The guard elapsed > 0 means a backward jump simply skips that round's refill instead of corrupting the bucket.

Memory growth.

• Every new key creates a KeyState that lives forever in the map.
• For millions of one-shot keys (per-IP limiting under a scan) that's an unbounded leak.
• I swap the raw map for a size-bounded cache with idle eviction: Caffeine with a max size and expire-after-access.
• A cold key starts full anyway, so dropping an idle key costs the client nothing it was owed.

Fairness and the thundering herd.

• When a fixed window resets, every blocked client retries at the same millisecond and slams the service in a spike.
• An accurate retryAfterMillis, plus a little client-side jitter, spreads those retries out instead of synchronizing them.

7Extensions and follow-ups#

• Make it distributed. Replace InMemoryStateStore with a Redis-backed store and push the token-bucket math into a Lua script, so the read-modify-write is atomic across all app servers and no two nodes double-spend a token. The class design doesn't change, only the store implementation and where the arithmetic runs. That's the payoff of the Store seam.
• Tiered limits. Free gets 10/min, paid gets 1000. I resolve a RateLimitConfig per tier before calling the strategy. The strategy code stays identical, only the three numbers differ, which is why config and algorithm are separate types.
• Multiple limits at once. "100 per minute AND 5 per second" is a real requirement. A CompositeRateLimiter holds several sub-limiters, runs the request through all of them, and short-circuits on the first denial. It reuses everything above.
• Observability. An Observer-style hook fires on every allow and deny so we emit metrics and spot abuse early. Listeners run outside the decision path, so a slow metrics sink never adds latency to the hot call.
• Sliding window counter. The practical middle ground. It weights the previous window's count into the current one, smoothing the boundary burst without storing a timestamp per request the way the log does. This is the answer I give when they push on accuracy versus memory, because it's what most production systems actually ship.

Get the two seams right and the follow-ups stop being rewrites. They become one-line edits.

8What the interviewer is really checking#

I'm not counting whether you memorized token bucket. The algorithm is the easy part. I'm watching for a few things.

• Do you clarify before coding? "Distributed or single process?" tells me you think about scope before syntax.
• Do you separate algorithm from storage, or jam everything into one class? That split is the entire design.
• Do you handle concurrency on purpose, with a clear reason for where the lock lives and why it's per key, or do you sprinkle synchronized around and hope?
• Does your design bend at a clean seam when I say "now make it a sliding window" or "now make it distributed," or does it break and need a rewrite?

Get the Strategy seam and the Store seam right, name the fixed-window boundary flaw before I ask, and lock per key with a reason you can defend. Do that and you've shown staff-level instincts on what looks like a Medium problem.

If this clicked, try Design an LRU Cache next, it pairs the same concurrency and eviction thinking, or revisit the Strategy and Factory patterns on their own.