Skip to main content

Low-Level Design: Rate Limiter in Java (Token Bucket, Sliding Window) + Spring Boot

A rate limiter built step by step in Java 25: fixed window, sliding window log and counter, token bucket (locked and lock-free), a Spring Boot 4.1 interceptor that returns 429, and a Redis Lua version that stays exact when 200 threads race. 17 passing tests, real output, plus a single-file whiteboard version to download.

A rate limiter is a bouncer for your API: it counts how many requests each client has made recently and turns away the ones over budget, so one noisy client cannot starve everyone else. It is also one of the most-asked low-level-design questions in Java interviews, because a correct answer needs data structures, time, and concurrency all at once. This post builds one from nothing. We start with the simplest possible limiter, watch it fail in a specific and measurable way, fix it twice, make the result thread-safe, wire it into Spring Boot so it answers 429 Too Many Requests, and finally move it into Redis so several servers can share one quota. Every number below comes from code that was compiled and run for this article.
Versions this article was tested against. JDK 25.0.5+8 (Temurin LTS), Spring Boot 4.1.2, Jedis 8.0.2, JUnit 6.1.3, Redis 7.0.15. Spring Boot, Jedis and JUnit versions were taken from maven-metadata.xml on Maven Central, skipping milestone, RC and beta releases. All 17 tests pass. Full source: the rate-limiter module of java-interview-lab.

What exactly are we building?

Picture an API that allows each client 100 requests per minute. Request number 101 should be refused immediately, with a clear message saying when to come back. That refusal is HTTP status 429, and the “come back at” part is the Retry-After header. Two things make this harder than it sounds. First, the limiter must remember something per client, and that memory must not grow forever. Second, many requests arrive at once, so the “check, then count” step has to be safe when threads race. Those two ideas run through the rest of the article.
client alice client bob client carol rate limiterone budget per key API → 200 OK 429 + Retry-After The limiter answers one question per request: is this key still within its budget? Yes → continue. No → reject at once.
The picture shows the whole job: a request comes in tagged with a key (here the client name), the limiter looks up that key’s budget, and the answer is either “go ahead” or “stop, try later”. Everything below is a different way of keeping that budget.
Interview tip: ask before you design. Per user, per IP or per API key? Reject with 429 or queue the request? One server or many? A hard limit or one that tolerates short bursts? These four questions decide which algorithm you should pick, and asking them is itself part of what the interviewer scores.
Deeper: what a good answer to “design a rate limiter” covers

Interviewers usually listen for five things: the requirements you clarified, the algorithm and why you picked it, the data you keep per key, how it behaves under concurrent calls, and what changes when it runs on more than one server. The sections below follow exactly that order, so you can use this article as a script.

A sixth point separates strong answers: what happens when the limiter itself fails. A limiter that fails open lets traffic through when its store is down (the API stays up, the budget is not enforced). One that fails closed rejects everything (the budget is safe, the API is down). Pick deliberately, and say which you picked.

Going deeper

One interface, so the algorithms are interchangeable

Before any algorithm, fix the shape of the answer. A limiter takes no arguments (one limiter instance guards one key) and returns a Decision: allowed, or denied with how long to wait. Returning the wait time is what lets the web layer fill in Retry-After honestly instead of guessing. Every limiter in this article also takes a clock as a constructor argument, a function returning nanoseconds. Production code passes System::nanoTime; tests pass a ManualClock they move by hand. That one decision lets us test “ten seconds later” without sleeping, which is why the whole suite runs in a few seconds. The files: RateLimiter.java, Decision.java and ManualClock.java.
public interface RateLimiter {

    /** Try to spend one request. Never blocks. */
    Decision tryAcquire();
}
public record Decision(boolean allowed, long retryAfterNanos) {

    private static final Decision ALLOWED = new Decision(true, 0);

    public static Decision permitted() {
        return ALLOWED;
    }

    public static Decision denied(long retryAfterNanos) {

Excerpt from Decision.java. Note that it is a record whose component is named allowed; the factory for the “yes” answer therefore has to be called permitted(), because a static method allowed() collides with the record’s own accessor. That was a compile error while writing the companion code.

Going deeper

  • Passing a clock instead of calling System.nanoTime() inside: ManualClock.java
  • Why monotonic time: nanoTime never jumps backwards when the wall clock is adjusted, which is what a limiter wants

The simplest limiter: count requests in fixed windows

Cut time into aligned windows of, say, ten seconds (0–10, 10–20 and so on). Keep a counter for the current window; when the window changes, reset it to zero. If the counter is below the limit, accept and increment. That is the whole algorithm, and it needs just two numbers of state per key. The code is in FixedWindowRateLimiter.java. The method is synchronized because “read counter, compare, increment” must not be interleaved between threads.
    public synchronized Decision tryAcquire() {
        long now = clock.getAsLong();
        long currentWindow = Math.floorDiv(now, windowNanos) * windowNanos;
        if (currentWindow != windowStart) {
            windowStart = currentWindow;
            count = 0;
        }
        if (count < limit) {
            count++;
            return Decision.permitted();
        }
        return Decision.denied(windowStart + windowNanos - now);

(The closing braces are omitted; the full method is in the file linked above.)

Its flaw is the boundary. A client can spend its whole budget in the last second of one window and its whole budget again in the first second of the next.
window 1 (0–10 s): limit 5window 2 (10–20 s): limit 5 0s10s20s 5 @ 9s 5 @ 11s Each window sees only 5, so a fixed window accepts all ten. But ten requests landed inside two seconds: twice the limit you meant to allow. Sliding windows look back from “now”, so the boundary does not exist for them.
Window one sees five requests, window two sees five requests, and each is within the limit. Yet ten requests arrived within two seconds: double the rate you promised. This is not theoretical; any client that retries on a schedule can hit it by accident.
Deeper: when a fixed window is still the right choice

Two numbers of state and a trivial implementation make it the cheapest option, and for coarse limits (“1000 per day”) a 2x burst at midnight rarely matters. It also maps directly onto a single Redis INCR with an expiry, which is why it is the common first version in production. Choose it when the limit protects your cost or quota rather than your server’s instantaneous load.

Going deeper

Fixing the boundary: look back from now, not from the window start

A sliding window asks “how many requests in the last ten seconds?” measured backwards from this request. There is no boundary to straddle. There are two common implementations, with a classic trade of accuracy against memory. The sliding window log stores the timestamp of every accepted request, discards those older than the window, and accepts if fewer than limit remain. It is exact. The cost is memory: up to limit timestamps per key. Source: SlidingWindowLogRateLimiter.java.
    public synchronized Decision tryAcquire() {
        long now = clock.getAsLong();
        while (!accepted.isEmpty() && accepted.peekFirst() <= now - windowNanos) {
            accepted.pollFirst();
        }
        if (accepted.size() < limit) {
            accepted.addLast(now);
            return Decision.permitted();
        }
        return Decision.denied(accepted.peekFirst() + windowNanos - now);
The sliding window counter keeps just two counts, the previous window and the current one, and weights the previous by how much of it still overlaps the sliding window. At 30% of the way into the current window, 70% of the previous window still counts. It is an estimate (it assumes the previous window’s requests were evenly spread) but it needs constant memory. Source: SlidingWindowCounterRateLimiter.java.
        double overlap = 1.0 - (double) (now - currentStart) / windowNanos;
        double estimate = previousCount * overlap + currentCount;
        if (estimate + 1 <= limit) {
            currentCount++;
            return Decision.permitted();
The same abuse scenario from the previous section, run against all four algorithms by BoundaryBurstDemo.java (script: run-demo.sh). Output from a real run on JDK 25:
Limit 5 per 10s. Client sends 5 requests at t=9s, then 5 at t=11s.

algorithm                  t=9s       t=11s      total in 2s
fixed window               5/5        5/5        10
sliding window log         5/5        0/5        5
sliding window counter     5/5        0/5        5
token bucket (5, 0.5/s)    5/5        1/5        6
The fixed window lets all ten through. Both sliding windows let five through and reject the second burst. The token bucket (next section) lets one through, because two seconds is long enough to earn one token back.
The sliding counter’s Retry-After is approximate. It reports the time until the current window ends, which is a safe upper bound, not the exact moment a request would first be accepted. The log version, which knows the oldest timestamp, can report the exact wait.
Deeper: choosing between log and counter

Memory per key is the deciding number. A log for a limit of 100 per minute stores up to 100 longs per active key; with a million active keys that is a real allocation, plus garbage as entries expire. The counter stores two ints and a long. If the limit is small (say 5 login attempts per 15 minutes) the log is perfectly affordable and exact is worth having. If the limit is large and keys are many, the counter’s small error is the right trade.

The estimate can be off in either direction when the previous window was bursty rather than even. In practice the error is small enough that large public APIs accept it, but if you need a hard guarantee (“never more than N in any window”), use the log.

Going deeper

The one most APIs use: the token bucket

Windows count requests. A token bucket does something more natural: it models permission. The bucket holds up to capacity tokens and is topped up at a steady rate; each request must take one token to proceed. A quiet client accumulates a full bucket and can then burst; a busy client is held to the refill rate.
capacity = 5 tokens refill: 1 token / 2 s each request spends 1 token Full bucket = a burst of 5 is fine. Empty bucket = reject, and the wait is (1 – tokens) / refill rate.
The two numbers you choose, capacity and refill rate, are independent: capacity is how big a burst you tolerate, refill rate is the sustained speed. A bucket of 5 refilling at 0.5 per second allows 5 requests at once, then one every two seconds. There is no timer thread: instead of adding tokens on a schedule, the code works out how many tokens would have arrived since the last request, at the moment of each request. Source: TokenBucketRateLimiter.java.
    public synchronized Decision tryAcquire() {
        long now = clock.getAsLong();
        tokens = Math.min(capacity, tokens + (now - lastRefill) * refillPerNano);
        lastRefill = now;
        if (tokens >= 1.0) {
            tokens -= 1.0;
            return Decision.permitted();
        }
        return Decision.denied((long) Math.ceil((1.0 - tokens) / refillPerNano));
No background refill thread. Computing the refill lazily on each call means an idle key costs nothing and there is nothing to schedule, stop, or leak. The price is a floating-point balance; if you need exact integer arithmetic, store tokens in a scaled long instead.
Deeper: token bucket vs leaky bucket

A leaky bucket is the mirror image: requests pour into a bucket that drains at a constant rate, and requests that would overflow are rejected (or, as a queue, delayed). Used as a queue it smooths traffic to a perfectly even output rate; the token bucket instead permits bursts and then settles. If the downstream system cannot tolerate even a short burst, the leaky bucket is the better model. If bursts are fine and you just want a cap on the average, use the token bucket.

Going deeper

When many threads call at once

A web server handles requests on many threads, so two threads can call tryAcquire() on the same limiter simultaneously. Without protection both may read “one token left” and both spend it. The simple fix, used so far, is synchronized on the method; it is correct, and at the speed of a single key’s traffic it is usually plenty fast. The alternative is a lock-free version. The entire state (token balance and last-refill time) is held in one immutable object. A request computes the next state and publishes it with compareAndSet; if another thread changed the state in between, the compare fails and the request simply recomputes and tries again. Source: LockFreeTokenBucketRateLimiter.java.
    public Decision tryAcquire() {
        while (true) {
            State current = state.get();
            long now = clock.getAsLong();
            double refilled = Math.min(capacity, current.tokens() + Math.max(0, now - current.lastRefill()) * refillPerNano);
            if (refilled < 1.0) {
                // Deny without writing: nothing to spend, and a stale read only makes us wait slightly longer.
                return Decision.denied((long) Math.ceil((1.0 - refilled) / refillPerNano));
            }
Why one object, not two atomics. The balance and the timestamp must change together. Two separate AtomicLongs can be observed half-updated by another thread, which is a bug no single-threaded test finds. Putting both in one record behind one AtomicReference makes “both or neither” true by construction.
To prove all five limiters are safe, ConcurrencyTest (source) hammers each with 64 threads making 100 attempts apiece against a frozen clock, five rounds each, and asserts that exactly 50 attempts succeed — not 49, not 51. Test summary from mvn test:
[INFO] Tests run: 3, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.449 s -- in com.ankurm.interviewlab.ratelimiter.redis.RedisLimiterTest
[INFO] Tests run: 2, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 2.084 s -- in com.ankurm.interviewlab.ratelimiter.web.RateLimitedAppTest
[INFO] Tests run: 5, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.664 s -- in com.ankurm.interviewlab.ratelimiter.ConcurrencyTest
[INFO] Tests run: 7, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.019 s -- in com.ankurm.interviewlab.ratelimiter.AlgorithmBehaviourTest
[INFO] Tests run: 17, Failures: 0, Errors: 0, Skipped: 0
[INFO] BUILD SUCCESS
Deeper: when to choose which

Use synchronized first. It is simpler to read, and the lock is held for a handful of arithmetic operations. Reach for compare-and-set when profiling shows contention on a very hot single key; it removes blocking, but under heavy contention threads may retry several times, so it is not automatically faster. The article’s tests prove both are correct; they do not claim either is faster, because that was not measured here.

A subtle point in the lock-free code: when the bucket has no token to give, it returns the denial without writing the refilled state. That is safe, because the refill is recomputed from the stored timestamp on the next call, and it avoids a pointless write on every rejected request.

Going deeper

One limiter per client

So far one limiter guards one key. A real service has many, so we keep a map from key to limiter. The detail that matters is how a new key gets its limiter: if two threads both see “no limiter for bob” and each creates one, bob briefly has two budgets. ConcurrentHashMap.computeIfAbsent prevents that by running the factory at most once per key. Source: KeyedRateLimiter.java.
    public Decision tryAcquire(String key) {
        return limiters.computeIfAbsent(key, k -> factory.get()).tryAcquire();
    }
This map only grows. Every distinct key stays in memory forever, which an attacker can exploit by sending requests with a million random client ids. Production code needs expiry: a cache with time-based eviction (for example Caffeine’s expireAfterAccess), or Redis key expiry as in the distributed version below. This is left out of the module on purpose, to keep the code readable, and called out here so it is not copied blindly.

Going deeper

  • Keyed behaviour tested: keyedLimiterGivesEachKeyItsOwnQuota
  • Choosing the key matters as much as the algorithm: an IP is shared by everyone behind one office or mobile carrier, so API-key or user-id keys are fairer where you have them

Plugging it into Spring Boot

In Spring MVC the natural hook is a HandlerInterceptor: its preHandle method runs before the controller, and returning false stops the request there. The interceptor picks a key (the X-Client-Id header, falling back to the caller’s address), asks the limiter, and on denial writes the 429 and the Retry-After header itself. Source: RateLimitInterceptor.java.
        Decision decision = limiter.tryAcquire(key);
        if (decision.allowed()) {
            return true;
        }
        response.setStatus(429);
        response.setHeader("Retry-After", Long.toString(decision.retryAfterSeconds()));
        response.setContentType("text/plain");
        response.getWriter().write("Too Many Requests - retry after " + decision.retryAfterSeconds() + "s\n");
        return false;
The application class registers it for /api/** only, so health checks are never limited, with a bucket of 5 refilling one token every two seconds. Source: RateLimitedApp.java.
    KeyedRateLimiter keyedRateLimiter() {
        return new KeyedRateLimiter(() -> new LockFreeTokenBucketRateLimiter(5, 0.5, System::nanoTime));
    }

    @Override
    public void addInterceptors(InterceptorRegistry registry) {
        registry.addInterceptor(new RateLimitInterceptor(keyedRateLimiter())).addPathPatterns("/api/**");
Real responses from the running application, seven calls from client alice and then one from bob, made with curl (test: RateLimitedAppTest.java):
request 1:
HTTP/1.1 200 
hello
request 2:
HTTP/1.1 200 
hello
request 3:
HTTP/1.1 200 
hello
request 4:
HTTP/1.1 200 
hello
request 5:
HTTP/1.1 200 
hello
request 6:
HTTP/1.1 429 
Retry-After: 2
Too Many Requests - retry after 2s
request 7:
HTTP/1.1 429 
Retry-After: 2
Too Many Requests - retry after 2s
--- different client:
HTTP/1.1 200 
hello
Five requests pass, the sixth and seventh get 429 with Retry-After: 2 (one token takes two seconds to refill), and bob is unaffected because he has his own bucket.
Deeper: interceptor, servlet filter, or gateway?

An interceptor runs inside Spring MVC, so it only sees requests that reach a controller mapping and it has access to the handler. A servlet Filter runs earlier and covers everything, including static resources and errors, which is better if you want to shed load as cheaply as possible. A gateway or reverse proxy in front of the application rejects before your JVM spends anything at all, and is usually the right place for coarse, per-IP limits. Many systems use two layers: a coarse limit at the edge, and this finer per-user limit inside.

One practical detail: in Spring Boot 4 the web starter used here is spring-boot-starter-webmvc. The pom is in the repository.

Going deeper

Several servers: the quota has to live somewhere shared

Everything above keeps its state in one JVM’s memory. Run three instances behind a load balancer and each keeps its own count, so a client effectively gets three times the limit. The fix is to move the state to a store all instances share, and Redis is the usual choice.
app server 1 app server 2 app server 3 Redis: key “user:alice” EVAL token_bucket.lua read → refill → spend → write one uninterrupted step Every server asks the same script about the same key, so the quota is shared however many servers you run.
Moving the state is easy; keeping it correct is not. The tempting implementation reads the counter with GET, compares in Java, then calls INCR. Each command is atomic by itself, but the sequence is not: many callers read “9” at the same time, all decide 9 is under the limit of 10, and all increment. Source of that deliberately wrong version: NaiveRedisRateLimiter.java.
        String current = jedis.get(key);
        long count = current == null ? 0 : Long.parseLong(current);
        if (count < limit) {
            jedis.incr(key);
            return Decision.permitted();
        }
        return Decision.denied(1_000_000_000L);
The demo RedisRaceDemo.java releases 200 threads at the same instant against a limit of 10 (script: run-redis-demo.sh), five runs, real Redis 7.0.15:
Limit 10. 200 threads, one request each, released at the same instant.

run 1: naive GET+INCR allowed 10 | Lua token bucket allowed 10
run 2: naive GET+INCR allowed 10 | Lua token bucket allowed 10
run 3: naive GET+INCR allowed 12 | Lua token bucket allowed 10
run 4: naive GET+INCR allowed 11 | Lua token bucket allowed 10
run 5: naive GET+INCR allowed 12 | Lua token bucket allowed 10
The naive limiter let 10, 10, 12, 11 and 12 requests through. The Lua version admitted exactly 10 every time. The naive overshoot is small and varies from run to run, because the race window is tiny, but it is real, and on a busy production system the window is hit constantly. The fix is to do read, refill, spend and write as one step. Redis runs a Lua script without interleaving any other command, so the whole token-bucket update becomes atomic. The script (token_bucket.lua) also asks Redis for the time with TIME, so servers with slightly different clocks cannot disagree about how many tokens have refilled:
local t = redis.call('TIME')
local now_ms = t[1] * 1000 + math.floor(t[2] / 1000)

local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])

local data = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(data[1])
local ts = tonumber(data[2])
if tokens == nil then
  tokens = capacity
  ts = now_ms
end

tokens = math.min(capacity, tokens + math.max(0, now_ms - ts) * rate / 1000)

local allowed = 0
local retry_ms = 0
if tokens >= 1 then
  tokens = tokens - 1
  allowed = 1
else
  retry_ms = math.ceil((1 - tokens) / rate * 1000)
end

redis.call('HSET', KEYS[1], 'tokens', tostring(tokens), 'ts', now_ms)
-- an idle bucket is a full bucket, so it can be forgotten after one full refill (+ margin)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000) + 1000)
return {allowed, retry_ms}
It is called from Java by RedisTokenBucketRateLimiter.java:
    public Decision tryAcquire() {
        Object raw = jedis.eval(script, List.of(key), List.of(Integer.toString(capacity), Double.toString(refillPerSecond)));
        List<?> reply = (List<?>) raw;
        boolean allowed = ((Long) reply.get(0)) == 1L;
        long retryMs = (Long) reply.get(1);
        return allowed ? Decision.permitted() : Decision.denied(TimeUnit.MILLISECONDS.toNanos(retryMs));
    }
Jedis 8 renamed the pooled client. Code written for Jedis 7 uses JedisPooled; against Jedis 8.0.2 that class no longer exists and compilation fails with “cannot find symbol”. The replacement used here is RedisClient.create(host, port), which this module’s tests exercise. Found while writing the companion code.
RedisLimiterTest (source) covers three facts: 50 simultaneous callers get exactly 10 permits, five rounds in a row; two separate clients (standing in for two app servers) share one bucket; and an idle bucket gets a Redis expiry, so unused keys clean themselves up.
Deeper: what changes in production

Fail open or closed. If Redis is unreachable, tryAcquire() throws. Decide what your interceptor does: let the request through (the API stays available, limits are not enforced for a while) or reject it. This module lets the exception propagate, which is neither; real code should catch it and choose.

Round trips. Each check is one network call to Redis. That is fine at thousands of requests per second but is the first cost to measure. Sending the script by its SHA with EVALSHA avoids resending the script text on every call; this module sends the full script with EVAL for simplicity and has not been measured against EVALSHA.

Redis Cluster. A script that touches one key is fine, because all of a key’s data lives on one node. Scripts touching several keys must declare them all in KEYS and have them in the same hash slot.

Expiry. The script sets PEXPIRE to one full refill time plus a second after every call. An idle bucket would be full anyway, so forgetting it changes nothing; the test asserts the expiry exists.

Going deeper

The version for the whiteboard

In an interview you will not write seven classes. You need something you can sketch in ten minutes that is still correct. Below is a single file with no dependencies containing a token bucket and a sliding window log, keyed per client, using a per-key lock rather than one global lock so different clients do not block each other. It is not part of the repository; download it here and run it with java InterviewRateLimiter.java:

Download InterviewRateLimiter.java

Output from running it on JDK 25, with a hand-moved clock. The token bucket spends its burst of three, rejects, and earns two tokens back after two seconds; the sliding log accepts at 0s and 4s, rejects at 8s, then accepts again at 11s and 14s as old entries age out:
TokenBucket(capacity=3, 1 token/s)
  t=0s   request 1 -> true
  t=0s   request 2 -> true
  t=0s   request 3 -> true
  t=0s   request 4 -> false
  t=0s   request 5 -> false
  t=2s   request 1 -> true
  t=2s   request 2 -> true
  t=2s   request 3 -> false
  t=2s   other key  -> true
SlidingWindowLog(limit=2, window=10s)
  t=0s  -> true
  t=4s  -> true
  t=8s  -> false
  t=11s  -> true
  t=14s  -> true
Deeper: a script for explaining it out loud
  1. Clarify the four questions from the first section.
  2. Pick the token bucket: it allows bursts and needs two numbers per key. Mention the sliding window log if exactness matters.
  3. State the data: a map from key to (tokens, last-refill-time), refilled lazily on each call.
  4. Handle concurrency: a lock per key, or compare-and-set on an immutable state object.
  5. Scale out: move the state to Redis and make the update one Lua script so it is atomic.
  6. Failure and cleanup: expire idle keys, and say whether you fail open or closed.

The follow-up an interviewer most often asks is “what if there are several servers?” — which the Redis section above answers, including the race you must avoid.

Going deeper

Should you build this yourself?

Usually not. For a production system, prefer a limiter at your gateway or reverse proxy, or a maintained library, over hand-rolled code; they have already met the edge cases (clock changes, key expiry, Redis failures, metrics) that this article only names. Build your own when the limit depends on your business logic (per plan, per endpoint cost), when you are learning the algorithms, or when an interviewer asks you to. Everything here is correct and tested, but it deliberately omits eviction of idle in-memory keys, fail-open or fail-closed handling, and metrics.

Further reading

No Comments yet!

This site uses Akismet to reduce spam. Learn how your comment data is processed.