How would you implement a rate limiter?

The Answer

Say this in the room. 45 seconds.

• Token bucket when short bursts are fine: tokens refill at the sustained rate, and the bucket size is the burst you allow. This is what most APIs actually want.
• Sliding window when the limit must hold over every interval, not just aligned ones.
• Fixed window is one counter and one timestamp — the cheapest, and it permits twice the limit across a window boundary.
• Refuse with 429 and a Retry-After header. A limiter that queues instead of refusing has just moved the overload somewhere with less visibility.
• On one machine this is twenty lines. With more than one instance, the counter has to live somewhere shared, and that is the actual interview question.
• Dividing the limit by the instance count only works while routing is even. It is not.

Understand It

Every limiter below reads a clock you control rather than the wall clock. That is not a testing convenience — a rate limiter is a function of time, so any example that reads System.currentTimeMillis() is reporting whatever the machine happened to be doing that second.

Fixed window, and the burst at the boundary

Count requests per aligned window; reset the counter when the window rolls over. It is the implementation people reach for first, and the reset is the bug.

// "100 requests per minute." One clock, two limiters, the same traffic.
var clock = new Ticker(0);
var fixed = new FixedWindow(100, 60_000, clock);
var log = new SlidingLog(100, 60_000, clock);

// A quiet minute, then everything arrives in the last second of it.
clock.advance(59_000);
System.out.println("  t=59s  fixed=" + burst(fixed, 100) + " allowed, log=" + burst(log, 100) + " allowed");

// One second later. The wall clock has ticked over into a new minute.
clock.advance(1_000);
System.out.println("  t=60s  fixed=" + burst(fixed, 100) + " allowed, log=" + burst(log, 100) + " allowed");

System.out.println("  in that 1 second, fixed window let through 200 — twice the stated limit");

  t=59s  fixed=100 allowed, log=100 allowed
  t=60s  fixed=100 allowed, log=0 allowed
  in that 1 second, fixed window let through 200 — twice the stated limit

Both minutes are within budget by the fixed window's own accounting: 100 in minute zero, 100 in minute one. But those two hundred requests arrived inside a one-second span, and the service that was sized for 100/min just took 200.

This is not a rare edge. Anything clock-aligned — cron jobs, retry backoffs that round to the minute, dashboards refreshing on the minute — concentrates traffic exactly there. The limit reads as 100/min and the number you must actually survive is 200.

Token bucket, where the burst is a parameter instead of an accident

A bucket holds up to capacity tokens and refills at a steady rate. Each request takes one. Bursts are allowed up to the bucket size, which makes the burst something you chose rather than something the algorithm leaked.

// 5 requests per second sustained, but allow a burst of 10 that has built up
// during idle time. Capacity is the burst; the refill rate is the real limit.
var clock = new Ticker(0);
var bucket = new TokenBucket(10, 5, clock);

System.out.println("  idle start, 15 arrive at once -> " + burst(bucket, 15) + " allowed");
System.out.printf("  tokens left: %.1f%n", bucket.available());

clock.advance(1_000);
System.out.println("  +1s, 15 arrive at once       -> " + burst(bucket, 15) + " allowed");

clock.advance(2_000);
System.out.println("  +2s, 15 arrive at once       -> " + burst(bucket, 15) + " allowed");

// Idle long enough and the bucket refills to capacity, but no further.
clock.advance(60_000);
System.out.printf("  after 60s idle, tokens: %.1f (capacity 10, not 300)%n", bucket.available());
System.out.println("  so the burst is bounded    -> " + burst(bucket, 15) + " allowed");

  idle start, 15 arrive at once -> 10 allowed
  tokens left: 0.0
  +1s, 15 arrive at once       -> 5 allowed
  +2s, 15 arrive at once       -> 10 allowed
  after 60s idle, tokens: 10.0 (capacity 10, not 300)
  so the burst is bounded    -> 10 allowed

Three properties worth naming, because they are the reasons this is the default choice:

There is no timer. Nothing refills the bucket on a schedule. The refill is computed from elapsed time when a request arrives — so a million idle keys cost nothing, where a million scheduled tasks would cost a great deal.

Idle credit is capped. After sixty seconds of silence at 5/sec the bucket holds 10, not 300. A client cannot save up an hour of quota and spend it in one second.

Capacity and rate are separate dials. Capacity is the burst you tolerate; the refill rate is the sustained limit. Set capacity equal to the rate and you have something close to a fixed window; set it to 1 and you have a strict spacing limiter that permits no burst at all.

Sliding window: exact, or nearly exact for two integers

The exact version keeps a timestamp per accepted request and drops the ones that have aged out. It is correct at every instant, and its memory grows with the limit — per key.

The approximation keeps two counters, the current window and the previous one, and fades the previous out as the current fills. The question is what that costs.

// The boundary that broke the fixed window, given to the sliding counter.
var clock = new Ticker(0);
var counter = new SlidingCounter(100, 60_000, clock);
clock.advance(59_000);
System.out.println("  t=59s  counter=" + burst(counter, 100) + " allowed");
clock.advance(1_000);
System.out.println("  t=60s  counter=" + burst(counter, 100) + " allowed   <- burst refused");
System.out.println();

// How much accuracy does the approximation actually cost? Replay identical
// traces through the exact log and the two-counter estimate, at rising load.
System.out.println("  limit 100/min, same trace through both, 10 minutes each:");
for (int max : new int[] { 2, 4, 6, 10 }) {
    var t = new Ticker(0);
    var exact = new SlidingLog(100, 60_000, t);
    var approx = new SlidingCounter(100, 60_000, t);
    var rng = new Random(4);
    int decisions = 0, differ = 0, exactOk = 0, approxOk = 0;
    for (int second = 0; second < 600; second++) {
        for (int i = 0, arriving = rng.nextInt(max); i < arriving; i++) {
            boolean e = exact.allow(), a = approx.allow();
            decisions++;
            if (e != a) differ++;
            if (e) exactOk++;
            if (a) approxOk++;
        }
        t.advance(1_000);
    }
    System.out.printf("    offered %3d/min -> log allowed %4d, counter allowed %4d, "
                    + "decisions differing %3d%%%n",
        (max - 1) * 30, exactOk, approxOk, differ * 100 / decisions);
}

var t = new Ticker(0);
var mem = new SlidingLog(100, 60_000, t);
for (int i = 0; i < 100; i++) mem.allow();
System.out.println();
System.out.println("  memory per tracked key: log " + mem.tracked()
                 + " timestamps, counter 2 ints");

  t=59s  counter=100 allowed
  t=60s  counter=0 allowed   <- burst refused

  limit 100/min, same trace through both, 10 minutes each:
    offered  30/min -> log allowed  308, counter allowed  308, decisions differing   0%
    offered  90/min -> log allowed  909, counter allowed  911, decisions differing   1%
    offered 150/min -> log allowed  993, counter allowed  987, decisions differing  30%
    offered 270/min -> log allowed 1000, counter allowed  990, decisions differing  34%

  memory per tracked key: log 100 timestamps, counter 2 ints

The last two columns are the answer to "is the approximation good enough", and they say something more precise than yes.

Below the limit the two never disagree. At 30/min and 90/min against a limit of 100, every client that would have been served by the exact algorithm is served by the approximation. Clients inside their quota cannot tell the difference, and that is almost all of them.

Above the limit they disagree about a third of the time — on which request is refused, not on how many. At 150/min offered, the exact log allowed 993 and the counter allowed 987 over ten minutes: a difference of 0.6%. At 270/min, 1000 against 990. The approximation is enforcing the same rate; it just picks different individual requests to reject once a client is already over budget.

That is exactly the trade you want. The guarantee a rate limiter sells is aggregate, and 2 integers per key against 100 timestamps per key is the difference between holding a million keys in memory and not.

The part the algorithm does not solve

Everything above is a single process. Put it behind a load balancer and the limit stops meaning what it says.

// One user, 100 requests in a minute, against a documented limit of 100/min.
// Three instances behind a load balancer, each running the limiter that passed
// code review — an in-memory one, holding the full limit.
var clock = new Ticker(0);
var perInstanceFullLimit = List.of(
    new FixedWindow(100, 60_000, clock),
    new FixedWindow(100, 60_000, clock),
    new FixedWindow(100, 60_000, clock));

int allowed = 0;
for (int i = 0; i < 300; i++) if (perInstanceFullLimit.get(i % 3).allow()) allowed++;
System.out.println("  limit 100 on each of 3 instances : " + allowed + " allowed, limit was 100");

// The obvious fix: divide the limit by the instance count.
var divided = List.of(
    new FixedWindow(33, 60_000, clock),
    new FixedWindow(33, 60_000, clock),
    new FixedWindow(33, 60_000, clock));
allowed = 0;
for (int i = 0; i < 100; i++) if (divided.get(i % 3).allow()) allowed++;
System.out.println("  limit 33 each, even routing      : " + allowed + " of 100 allowed");

// It works only while routing is even. Sticky sessions, a hash on user id, or
// one instance restarting all break that assumption.
var skewed = List.of(
    new FixedWindow(33, 60_000, clock),
    new FixedWindow(33, 60_000, clock),
    new FixedWindow(33, 60_000, clock));
int[] routing = { 70, 20, 10 };            // percent of this user's traffic per instance
allowed = 0;
for (int inst = 0; inst < 3; inst++)
    allowed += burst(skewed.get(inst), routing[inst]);
System.out.println("  limit 33 each, 70/20/10 routing  : " + allowed + " of 100 allowed");
System.out.println("  the user bought 100/min and got " + allowed + " — no error, no alert");

  limit 100 on each of 3 instances : 300 allowed, limit was 100
  limit 33 each, even routing      : 99 of 100 allowed
  limit 33 each, 70/20/10 routing  : 63 of 100 allowed
  the user bought 100/min and got 63 — no error, no alert

Three failure modes in six lines of output.

The default is silently 3× wrong, and it scales with your deployment. Autoscale to twelve instances and the documented 100/min becomes 1,200/min — the limit loosens exactly when load is highest, which is the opposite of what a limiter is for.

Dividing by the instance count is correct only under even routing. It also has to be updated on every scale event, which means a limit that changes when the deployment changes.

Skew turns it into a wrong answer in the other direction. With 70/20/10 routing the customer paid for 100/min and received 63, and nothing anywhere reports an error — the requests were refused correctly by a limiter doing exactly what it was configured to do. This is the version that reaches support as "your API is flaky" and cannot be reproduced, because it depends on which instance the load balancer picked.

The fix is a shared counter — Redis with an atomic increment, or a dedicated limiter in the gateway — and the cost is a network hop on every request plus a decision about what happens when that store is unreachable. That decision is the interview question: fail open and the limiter stops protecting you during exactly the incident where you need it, or fail closed and a Redis blip takes down an API that was otherwise healthy.

Reference

The correct implementation, the configuration, and the migration path. Copy from here.

Choosing one

Token bucket unless something forces otherwise. It is the only one where the burst is a number you chose.

A thread-safe token bucket

The version on this page is single-threaded so the algorithm is visible. Under concurrency, read-modify-write on the token count has to be atomic:

public final class TokenBucket {
    private final long capacity;
    private final double refillPerNano;
    private final Clock clock;                       // inject it; never read the wall clock directly
    private final AtomicReference<State> state;

    private record State(double tokens, long nanos) {}

    public TokenBucket(long capacity, double perSecond, Clock clock) {
        this.capacity = capacity;
        this.refillPerNano = perSecond / 1_000_000_000.0;
        this.clock = clock;
        this.state = new AtomicReference<>(new State(capacity, System.nanoTime()));
    }

    public boolean tryAcquire() {
        // CAS loop rather than synchronized: the critical section is a few
        // arithmetic ops, so contention is better spent spinning than parking.
        while (true) {
            State now = state.get();
            long t = System.nanoTime();
            double refilled = Math.min(capacity, now.tokens() + (t - now.nanos()) * refillPerNano);
            if (refilled < 1.0) return false;
            if (state.compareAndSet(now, new State(refilled - 1.0, t))) return true;
        }
    }
}

Use System.nanoTime() for elapsed time, never currentTimeMillis() — the latter jumps when NTP corrects the clock, and a backwards jump makes a limiter refuse everything until real time catches up.

Don't write it — the libraries

// Bucket4j — the standard choice for token bucket in Java.
Bucket bucket = Bucket.builder()
    .addLimit(limit -> limit.capacity(100).refillGreedy(100, Duration.ofMinutes(1)))
    .build();
if (!bucket.tryConsume(1)) return ResponseEntity.status(429).build();

// Resilience4j — when you also want circuit breaking and bulkheads together.
RateLimiterConfig config = RateLimiterConfig.custom()
    .limitForPeriod(100)
    .limitRefreshPeriod(Duration.ofMinutes(1))
    .timeoutDuration(Duration.ZERO)              // ZERO = reject; non-zero = wait
    .build();

// Spring Cloud Gateway — Redis-backed, distributed, no application code.
// spring.cloud.gateway.routes[0].filters[0]=RequestRateLimiter=
//   redis-rate-limiter.replenishRate=100,
//   redis-rate-limiter.burstCapacity=200,
//   redis-rate-limiter.requestedTokens=1

Bucket4j also has distributed backends (Redis, Hazelcast, Infinispan) so the same API works across instances — which is usually a better answer than writing the Lua below.

The distributed counter, when you do write it

The whole check must be one atomic operation, or two instances read the same count and both allow. Redis runs a Lua script atomically:

-- KEYS[1] = bucket key   ARGV = capacity, refillPerSec, nowMillis, requested
local state    = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local now      = tonumber(ARGV[3])
local want     = tonumber(ARGV[4])

local tokens = tonumber(state[1]) or capacity
local ts     = tonumber(state[2]) or now
tokens = math.min(capacity, tokens + (now - ts) / 1000 * rate)

local allowed = tokens >= want
if allowed then tokens = tokens - want end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000) * 2)   -- self-cleaning
return { allowed and 1 or 0, math.floor(tokens) }

Two details that are easy to miss and expensive to omit. The PEXPIRE is what stops the key space growing without bound as users come and go. And now is passed in from the caller rather than read inside the script, because a script that reads the clock is not deterministic and cannot be replicated safely.

What to return

return ResponseEntity.status(HttpStatus.TOO_MANY_REQUESTS)   // 429, not 503
    .header("Retry-After", "30")                             // seconds, or an HTTP date
    .header("RateLimit-Limit", "100")
    .header("RateLimit-Remaining", "0")
    .header("RateLimit-Reset", "30")
    .body(problem("rate_limit_exceeded", "100 requests per minute per API key"));

429 means "you, slow down" and is safe to retry after the stated delay. 503 means "the service is unwell" and invites clients to retry against a service that is fine. Sending the wrong one turns a working limiter into an outage report.

Publishing the remaining quota in headers is what lets a well-behaved client pace itself instead of discovering the limit by hitting it.

Where to put it

These are layers, not alternatives. Volumetric filtering belongs at the edge and per-tenant fairness belongs in the application, because only the application knows that one endpoint costs 200ms of database time and another costs nothing.

Scenarios

Real situations, with the decision and the argument.

1. The limit is documented as 100/min and a customer is measurably getting 300.

Almost certainly an in-memory limiter on three instances. Confirm by checking whether the number tracks the replica count — if scaling to six makes it 600, that is the whole diagnosis.

The fix is a shared counter, but there is a decision to make first: what happens when the shared store is unreachable. Fail open keeps the API up and removes the protection during an incident; fail closed keeps the guarantee and lets a Redis blip take down a healthy API. For a paid API protecting a fragile backend, fail closed with a short timeout and a local fallback limiter set generously. For a public read endpoint, fail open and alert. State which you chose and why — an interviewer is asking this to see whether you know it is a choice.

2. A customer reports intermittent 429s but their own metrics show they are well inside the quota.

Both are probably right. Look for uneven routing — sticky sessions, a hash on user id, or an instance that just restarted with a cold counter — against a limiter whose per-instance limit is the global limit divided by replica count. The customer's traffic concentrates on one instance and gets refused at a third of their real quota.

This is the failure mode that never reproduces, because it depends on load balancer state. It is also the argument against dividing the limit, and worth making before someone spends a week on it: the division is only correct under an assumption about routing that nothing in the system enforces.

3. Someone proposes queueing rate-limited requests instead of rejecting them.

Ask how long the queue is allowed to get. If the answer is "unbounded", this converts a rate limit into a memory leak, and the failure moves from a clean 429 to an out-of-memory kill that takes healthy traffic with it.

A bounded queue with a short timeout is defensible and is what a token bucket with a non-zero acquire timeout gives you. But it is worth being clear about what queueing buys: it smooths a burst that is briefly over the limit, and it does nothing for a client that is sustainably over. For sustained overload the queue fills, and you are rejecting again — just later, having spent memory and added latency to the requests you did serve.

On Java 21 this is a different calculation than it used to be. Parking a virtual thread while waiting for a token holds no OS thread, so waiting is genuinely cheap in a way it was not when every waiter pinned a platform thread.

4. Traffic spikes exactly on the minute and the service falls over, but the limiter reports no violations.

The limiter is fixed-window and the traffic is clock-aligned — cron jobs, retries that round to the minute, dashboards refreshing. Two full windows land in the same second and the limiter is correct in its own terms while the service takes twice what it was sized for.

Switching to a token bucket or sliding window fixes it. Jittering the clients' schedules also fixes it and is often faster to deploy if you control them. Do both: the jitter helps immediately, and the limiter change means the next badly-behaved client cannot do the same thing.

5. A big customer complains they get throttled while smaller ones do not.

Probably a single global limit with no per-tenant fairness, where one heavy tenant's traffic consumes the shared budget. The complaint is real even though the limiter is working.

Per-tenant buckets are the fix, and they raise a question worth surfacing rather than answering silently: what should the limit be for a customer paying ten times more? If the answer is "ten times higher", the limit is a product decision and belongs in configuration keyed by plan, not in code. Weighting by request cost matters too — one expensive endpoint can consume more capacity than a thousand cheap ones, so a limiter counting requests is measuring the wrong thing.

Interviewer's Next Move

The question after the question. This is what the round is actually testing.

1. "How would you implement a rate limiter?" Token bucket for the common case: tokens refill at the sustained rate, bucket size is the burst you allow, and there is no timer because the refill is computed from elapsed time when a request arrives. Sliding window if the limit must hold over every interval.

2. "Why not just a counter that resets every minute?" That is a fixed window, and it permits twice the limit across a boundary — 100 in the last second of one minute and 100 in the first second of the next. Clock-aligned traffic lands exactly there, so it is not a rare case.

3. "What is the difference between token bucket and leaky bucket?" Token bucket allows a burst up to the bucket size and limits the average rate. Leaky bucket drains at a fixed rate and smooths output completely, allowing no burst. Use leaky when a downstream system needs an even rate; use token when clients are allowed to be bursty.

4. "How much memory does each approach need?" Fixed window and token bucket are constant per key. A sliding log stores one timestamp per request in the window — with a limit of 10,000 and a million users, that is ten billion timestamps. A sliding counter is 2 integers per key, and matches the exact algorithm's rate to within about a percent.

5. "Now run it on ten instances." The in-memory version becomes a limit ten times higher, and it loosens further every time you scale out. Dividing by the replica count works only while routing is even and has to change on every scale event. The real answer is a shared counter — Redis with an atomic script, or the gateway.

6. "Redis is down. What happens?" That is a decision, not a detail. Fail open keeps the API up and drops the protection during an incident; fail closed keeps the guarantee and turns a Redis blip into an outage. Pick per endpoint: fail closed with a generous local fallback for anything protecting a fragile backend, fail open with an alert for public reads.

7. "Why does the check have to be atomic?" Read-then-write lets two instances read the same count and both allow. A Lua script, INCR with an expiry, or a CAS loop on one node all make the read-modify-write indivisible. Without that the limiter is approximately right, which for a paid quota is wrong.

8. "What do you return?" 429 with Retry-After, plus RateLimit-Limit / -Remaining / -Reset so a client can pace itself rather than probing. Not 503 — that says the service is unwell and invites retries against something that is fine.

9. "Where should the limiter live?" Layers, not alternatives. Volumetric abuse at the edge, per-key limits at the gateway, per-tenant and per-cost rules in the application — because only the application knows one endpoint costs 200ms of database time and another costs nothing.

Code traps

Trap A — predict before you run:

if (requestCount.incrementAndGet() > LIMIT) {
    return reject();
}

Trap B:

long now = System.currentTimeMillis();
double refilled = tokens + (now - lastRefill) * ratePerMs;

Trap C:

Map<String, Bucket> buckets = new ConcurrentHashMap<>();

Bucket forUser(String userId) {
    return buckets.computeIfAbsent(userId, id -> newBucket());
}

Common wrong answers

Check Yourself

Q1. Why does a fixed-window limiter allow twice its limit, and why is that not a rare edge case?

Q2. A sliding counter disagrees with an exact sliding log on about a third of decisions under overload. Why is it still the right default?

Q3. Your limiter works perfectly in staging on one instance. What breaks in production on twelve?

Practice