Design a Rate Limiter (Low Level Design)

Problem Statement

A rate limiter is a doorman for your code. It says "you may come in" or "not now, try again in a bit". Think of a tea shop that serves each customer at most 5 cups every 10 minutes. The 6th request gets a polite no, and a hint about when to come back.

This note is about the low level version. You are inside one application, and you have to design the classes: what the interface looks like, how the different counting methods plug in, where the rules live, and how to keep it safe when many threads call it at once. The version that spans many servers (Redis, shared counters, API gateways) is a system design question and is a different note. I will say where that line is as we go.

Questions to Ask First

In an interview, do not start drawing boxes. Ask these first. They take one minute and they decide the shape of the design.

Requirements

What the code has to do:

• Answer "is this request allowed?" for a given user and API.
• Offer three algorithms: token bucket, fixed window and sliding window log.
• Pick the algorithm and numbers from config. The most specific rule wins: user rule, then API rule, then default.
• Give each user and API pair its own counter, so Alice cannot use up Bob's limit.
• Return a small result object with the answer and a retry hint.
• Be safe when many threads call at the same time.
• Never read the real time directly, so a test can control it.

What it does not do (say this out loud): no sharing between servers, no cleaning of idle users, no config reload while running, no HTTP headers.

Core Classes

There are 12 small files in the code folder. The three limiters are the heart of it. Everything else is there to pick the right one, feed it time, and hold one per user and API.

How the Design Works

The interface and the answer

Every algorithm has one job, so the interface has one method.

public interface RateLimiter {

    Decision tryAcquire();
}

A limiter object guards one key. It does not know about users or APIs. That keeps each algorithm tiny, and it also means locks are per key, not one big lock for the whole app.

The answer is a record (a short way in Java to write a class that only holds values):

public record Decision(boolean allowed, int remaining, long retryAfterMillis) {

    public static Decision allow(int remaining) {
        return new Decision(true, remaining, 0);
    }

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

Returning a Decision instead of a plain boolean is a small choice that pays off. The caller can turn retryAfterMillis into a Retry-After header, or sleep and try again. A bare true or false throws that information away.

The clock

The limiters never call System.currentTimeMillis() themselves. They ask a Clock.

@FunctionalInterface
public interface Clock {

    long nowMillis();

    static Clock system() {
        return System::currentTimeMillis;
    }
}

In production you pass Clock.system(). In tests you pass a FakeClock, which only moves when you call advance. Without this, testing "wait 10 seconds and try again" means a test that really sleeps for 10 seconds, or one that fails now and then. This one idea is worth the whole interface.

Token bucket

Picture a bucket that holds 5 tokens. Every request takes one. The bucket refills slowly. If it is empty, you wait.

The refill is worked out lazily. Nobody runs a timer. When a request arrives, the code looks at how much time has passed since last time and adds the tokens that would have dropped in.

@Override
public synchronized Decision tryAcquire() {
    refill();
    if (tokens >= 1) {
        tokens -= 1;
        return Decision.allow((int) tokens);
    }
    long missing = (long) Math.ceil((1 - tokens) / tokensPerMillis);
    return Decision.deny(missing);
}

private void refill() {
    long now = clock.nowMillis();
    double earned = (now - lastRefillMillis) * tokensPerMillis;
    tokens = Math.min(capacity, tokens + earned);
    lastRefillMillis = now;
}

With "5 per 10 seconds" the bucket holds 5 tokens and earns 0.0005 tokens per millisecond, so one new token every 2 seconds. This method allows a burst (all 5 at once) and then settles into a steady speed. Most real APIs want exactly that.

Fixed window

Cut time into boxes: 0 to 10 seconds, 10 to 20 seconds, and so on. Count requests in the current box. When a new box starts, reset the count.

long windowStart = now - (now % windowMillis);
if (windowStart != currentWindowStart) {
    currentWindowStart = windowStart;
    count = 0;
}
if (count < limit) {
    count++;
    return Decision.allow(limit - count);
}
return Decision.deny(windowStart + windowMillis - now);

It is the simplest one: one number and one timestamp per key. The weakness is at the edge of a box, which I show in the example below.

Sliding window log

Keep the time of every recent request in a queue. For each new request, throw away the times older than one window, then count what is left.

long now = clock.nowMillis();
dropExpired(now);
if (timestamps.size() < limit) {
    timestamps.addLast(now);
    return Decision.allow(limit - timestamps.size());
}
return Decision.deny(timestamps.peekFirst() + windowMillis - now);

This is the most exact one. At any moment, "the last 10 seconds" really contains at most limit requests. The price is memory: up to limit timestamps for every key. For a limit of 10 that is nothing. For a limit of a million per hour, it hurts.

Rules and the factory

A rule is three numbers and an algorithm name. It can be read from a short text, so it can live in a config file.

public record Rule(Algorithm algorithm, int limit, long windowMillis) {

    public enum Algorithm {
        TOKEN_BUCKET,
        FIXED_WINDOW,
        SLIDING_WINDOW
    }

    /** Reads text like "token-bucket,5,10" (algorithm, limit, window in seconds). */
    public static Rule parse(String text) { ... }
}

The factory is the one place that knows which class goes with which algorithm:

public RateLimiter create(Rule rule) {
    switch (rule.algorithm()) {
        case TOKEN_BUCKET:
            return new TokenBucketLimiter(rule.limit(), rule.windowMillis(), clock);
        case FIXED_WINDOW:
            return new FixedWindowLimiter(rule.limit(), rule.windowMillis(), clock);
        case SLIDING_WINDOW:
            return new SlidingWindowLogLimiter(rule.limit(), rule.windowMillis(), clock);
        default:
            throw new IllegalArgumentException("Unknown algorithm: " + rule.algorithm());
    }
}

RuleBook reads the config (a java.util.Properties object here, but it could come from a file or a database) and answers "which rule applies to this user and API?":

public Rule ruleFor(String userId, String api) {
    Rule userRule = userRules.get(userId);
    if (userRule != null) {
        return userRule;
    }
    return apiRules.getOrDefault(api, defaultRule);
}

The demo config looks like this:

default    = token-bucket,5,10
api./login = fixed-window,2,10
user.vip-1 = token-bucket,8,10

The service the app calls

public Decision check(String userId, String api) {
    String key = userId + "|" + api;
    RateLimiter limiter = limiters.computeIfAbsent(key, k -> factory.create(rules.ruleFor(userId, api)));
    return limiter.tryAcquire();
}

The first call for a pair creates its limiter. Later calls reuse it. limiters is a ConcurrentHashMap, and computeIfAbsent is atomic, so two threads arriving at the same time for a new key still get the same limiter. Without that, each thread could make its own, and both would think they have a fresh limit.

Thread safety in one paragraph

There are two places where threads meet. The map of limiters (handled by ConcurrentHashMap) and the state inside each limiter (handled by synchronized on tryAcquire). The second one matters because "read the count, compare, add one" is three steps. If two threads do the first step at the same time, both see 99 out of 100, and both get in. Making the whole method one locked block fixes it. The lock is on the single limiter, so Alice's requests never wait for Bob's.

Patterns Used and Why

I did not use the Singleton pattern, even though there is "one service per app". You create the service once at start-up and pass it around. That is simpler to test.

Walk Through One Full Example

All of this is real output from Main.java. The clock is fake, so it prints the same thing every run.

Part one: Alice calls /orders, which uses the default rule (token bucket, 5 per 10 seconds).

t=    0ms  alice /orders #1         ALLOWED  remaining=4
t=    0ms  alice /orders #2         ALLOWED  remaining=3
t=    0ms  alice /orders #3         ALLOWED  remaining=2
t=    0ms  alice /orders #4         ALLOWED  remaining=1
t=    0ms  alice /orders #5         ALLOWED  remaining=0
t=    0ms  alice /orders #6         REJECTED retryAfter=2000ms
t= 2000ms  alice /orders after 2s   ALLOWED  remaining=0

Five go through at once, the sixth is told to come back in 2000 ms. That matches the refill speed of one token per 2 seconds. We advance the fake clock by exactly 2000 ms and the next call is allowed.

Part two: same user, different API. /login has its own rule (fixed window, 2 per 10 seconds), and its own counter.

t= 2000ms  alice /login #1          ALLOWED  remaining=1
t= 2000ms  alice /login #2          ALLOWED  remaining=0
t= 2000ms  alice /login #3          REJECTED retryAfter=8000ms

The window started at 0 and ends at 10000, and the time now is 2000, so the retry hint is 8000.

Part three: other users. Bob has his own counter, and vip-1 has a user rule (8 per 10 seconds), so he is on a different bucket size.

t= 2000ms  bob /orders              ALLOWED  remaining=4
t= 2000ms  vip-1 /orders #1         ALLOWED  remaining=7
...
t= 2000ms  vip-1 /orders #6         ALLOWED  remaining=2

Part four is the one interviewers love. Same limit (3 per 10 seconds) for all three algorithms. Send 3 requests at 9.0 seconds, then 3 more at 10.0 seconds.

TOKEN_BUCKET    allowed 3 at 9.0s, 0 at 10.0s
FIXED_WINDOW    allowed 3 at 9.0s, 3 at 10.0s
SLIDING_WINDOW  allowed 3 at 9.0s, 0 at 10.0s

The fixed window let 6 requests through in one second, because 9.0s is the end of one box and 10.0s is the start of the next. That is the famous "boundary burst". For a limit of 3 it is harmless. For a payment API it could be a problem, and you can say that in the interview.

Part five checks thread safety. Eight threads each make 50 calls against a limit of 100, with the clock frozen:

400 calls made, allowed = 100

Exactly 100. If you remove the synchronized keyword and run it a few times, most runs still print 100 but now and then you get 101. That is the nasty part of thread bugs: they hide. The lock is what makes the answer right every time, not just most times.

Edge Cases

• A new key starts with a full bucket (or an empty window). The first request is never rejected.
• Time going backwards. Someone can adjust the system clock. The token bucket would then compute a negative refill. A real clock should be based on System.nanoTime(), which only moves forward. I kept currentTimeMillis to keep the code short.
• Limit of 0 or a negative window is rejected when the rule is parsed.
• Unknown algorithm name in config fails at start-up with a clear message, not at the first request.
• Many different users. The map of limiters grows forever, one entry per user and API ever seen. This design does not remove idle entries. A real one would clear limiters that have not been used for a while.
• Rule changes while running. The limiters already created keep the old numbers. Reloading config needs a way to replace them.
• Token bucket uses double. For huge limits, rounding errors could add up. For normal limits it is fine.

Follow Up Questions an Interviewer May Ask

"How would you make this work across many servers?"

The state (counts, tokens) has to move to a shared store such as Redis, and the check and update must be one atomic step, usually a small Lua script. The class design stays almost the same: the RateLimiter interface and Decision do not change, only the implementation behind them. That is the benefit of the interface.

"Which algorithm would you pick?"

Token bucket for most public APIs, because bursts are allowed and the memory is two numbers per key. Sliding window log when exactness matters and the limit is small. Fixed window when you want the cheapest thing and a boundary burst is acceptable.

"Is there something in between fixed window and the log?"

Yes, the sliding window counter. It keeps the count of the current and the previous window and mixes them by how far into the current window you are. It is not exact, but it uses two numbers per key and removes most of the boundary burst. I did not build it here, but it would be one more class and one more enum value.

"How do you stop the map from growing forever?"

Remove limiters that have been idle for longer than their window, using a scheduled cleanup or a cache with expiry (Caffeine does this).

"What if the caller wants to wait instead of being rejected?"

Add a second method such as acquire() that sleeps for retryAfterMillis and tries again. Keep tryAcquire() as it is. The Decision already has the number you need.

"How do you unit test it?"

Create a FakeClock, build a limiter, call tryAcquire a few times, call clock.advance(2000) and check again. No sleeping. Part four of the demo is basically a test of this kind.

"Why is the lock inside each limiter and not on the service?"

A lock on the service would make every user wait for every other user. A lock per limiter only blocks two calls for the same user and API.

Common Mistakes

• Reading the system time inside the limiter. Then it cannot be tested without sleeping.
• Returning only true or false. The caller then has no idea when to retry, so clients hammer the API.
• Splitting "check the count" and "increase the count" into two separate steps without a lock. Two threads both pass the check.
• Using one global lock for everything.
• Putting if (algorithm == ...) branches inside the service. The strategy pattern is there to avoid exactly that.
• Starting a background thread to refill buckets every second. Refill lazily when a request comes instead.
• Forgetting the boundary burst in fixed windows, then being surprised when someone points it out.

How to Run

From the repository root. The class files go to /tmp, so nothing is left in the repo.

javac --release 17 -d /tmp/ratelimiter-out $(find src/LLD/RateLimiter/src -name '*.java')
java -cp /tmp/ratelimiter-out com.blueprint.lld.ratelimiter.Main

The code uses Java 17 only and no libraries.