Rate Limiting Algorithms Explained

Every rate limiter has to answer the same question on every request: has this client already used its allowance? The rate limiting algorithm is how it counts. That choice determines three things — how much state the limiter stores per client, how precisely it enforces the stated limit, and how it behaves at the edges of a time window, which is where most limiters leak.

Six algorithms cover essentially all production use. This page explains how each one works, what it costs, where it fails, and how to implement it on Valkey or Redis in Java.

Fixed window counter

Divide time into fixed windows aligned to the clock — each minute, each hour — and keep one counter per client per window. Increment on arrival, reject once the counter exceeds the limit, discard the counter when the window ends.

It is the cheapest algorithm by every measure: one integer per client, one increment per request, and expiry handled by the store rather than by your code.

Its weakness is the boundary. Consider a limit of 100 requests per minute. A client sends 100 requests at 12:00:59 and another 100 at 12:01:00. Both windows are individually within the limit, and both are accepted — but the downstream service just absorbed 200 requests in roughly one second. The limit you configured is not the limit the system experiences; the effective worst case is double.

On Valkey or Redis the counter is an atomic increment with an expiry:

long window = System.currentTimeMillis() / 60_000;
RAtomicLong counter = redisson.getAtomicLong("rl:fw:" + clientId + ":" + window);

long used = counter.incrementAndGet();
if (used == 1) {
    counter.expire(Duration.ofMinutes(1));
}
return used <= 100;

Note the gap between the increment and the expiry. If the process dies between the two calls, the key survives with no TTL and counts forever, locking that client out permanently. Closing that hole needs both operations in one atomic step — a Lua script, or an object that does it for you.

Sliding window log

Store a timestamp for every admitted request. On each new arrival, discard the timestamps that have fallen outside the trailing window and count what remains. If the count is below the limit, admit the request and append its timestamp.

This is exact. The window moves continuously with the clock, so there is no boundary to exploit — a client limited to 100 per minute can never get 101 through in any 60-second span, whichever 60 seconds you pick.

The cost is storage and work per request. One detail changes that cost materially: log only the requests you admit, never the ones you reject. Storage is then bounded by the limit itself rather than by incoming traffic, which matters precisely when you are under attack and the rejection rate is highest.

A sorted set scored by timestamp is the natural structure:

RScoredSortedSet<String> log = redisson.getScoredSortedSet("rl:log:" + clientId);
long now = System.currentTimeMillis();

// drop everything older than the trailing window
log.removeRangeByScore(0, true, now - 60_000, false);

if (log.size() < 100) {
    log.add(now, UUID.randomUUID().toString());
    return true;
}
return false;

Three round trips, and the trim, the count and the write are not atomic with respect to each other — two concurrent requests can both read a size of 99 and both be admitted. Correct enforcement requires collapsing them into a single scripted operation.

Sliding window counter

A compromise between the previous two. Keep fixed-window counters, but weight the previous window's count by how much of it still overlaps the trailing window.

The estimate is previous × (1 − elapsed) + current, where elapsed is the fraction of the current window that has passed. With a limit of 100 per minute, a previous minute of 90 requests, and 20 requests logged 25% of the way into the current minute:

estimate = 90 × 0.75 + 20 = 87.5   → under 100, admit

The result is an approximation. It assumes the previous window's requests were spread evenly, which is exactly what a bursting client does not do, so it can admit slightly over the limit or reject slightly under it. In exchange it costs two integers instead of one entry per request, and it removes nearly all of the boundary spike. That trade is why it is the default in most production API gateways.

Token bucket

Model the allowance as a bucket holding a fixed capacity of tokens, refilled at a steady rate. Each request removes one token. A request that finds the bucket empty is refused. While a client is idle, tokens accumulate — but only up to the capacity, so the allowance never grows without bound.

What makes token bucket the most widely deployed algorithm is that it separates two properties you usually want to control independently:

• The sustained rate is the refill rate. Over any long period, the client averages this.
• The burst size is the bucket capacity. It is how far a client may deviate from the average in the short term.

A client allowed 10 requests per second with a capacity of 50 can go quiet for five seconds, fire 50 requests at once, and then continue at 10 per second while the bucket refills. Real clients batch, retry and poll on timers; token bucket accommodates that without letting the long-run average drift, which is exactly what a fixed window fails to do.

Redisson's RRateLimiter provides this behaviour as a distributed object, with the state held in Valkey or Redis so one allowance is shared across every JVM:

RRateLimiter limiter = redisson.getRateLimiter("rl:tb:" + clientId);
limiter.trySetRate(RateType.OVERALL, 10, 1, RateIntervalUnit.SECONDS);

if (limiter.tryAcquire()) {
    // handle the request
} else {
    // over the limit — reject with 429
}

RRateLimiter enforces an average rate, so after an idle stretch it may briefly admit above the nominal rate while it catches up — the accumulate-while-idle behaviour described above. Where that tolerance is unacceptable, GCRA gives tighter control.

Leaky bucket

Picture requests entering a bucket that drains at a constant rate. If the bucket overflows, requests are dropped. Implemented as a queue, this shapes traffic: however erratic the arrival pattern, departures leave at a fixed pace.

Leaky bucket produces the smoothest downstream load of any algorithm here, which is what recommends it for protecting a dependency that degrades badly under bursts — a legacy service, a connection-limited database, a third-party API with a hard ceiling. The costs are latency, since requests wait rather than fail fast, and memory for the queue itself.

The same effect comes from acquiring permits with a blocking call rather than a conditional one:

RRateLimiter shaper = redisson.getRateLimiter("rl:downstream");
shaper.trySetRate(RateType.OVERALL, 50, 1, RateIntervalUnit.SECONDS);

shaper.acquire(1);   // blocks until a permit frees up
callFragileDownstream();

The distinction between rejecting and delaying is the distinction between rate limiting and throttling. A conditional acquire rate limits; a blocking acquire throttles.

Token bucket vs leaky bucket

The two are frequently presented as rivals, which obscures the fact that they are the same algorithm viewed from different ends. Used as a meter — a yes/no decision on each request — leaky bucket is mathematically equivalent to token bucket. The genuine difference appears when leaky bucket is used as a queue.

The practical rule: if a human is waiting on the response, reject fast with token bucket and let the client retry. If the work is asynchronous and the downstream is what needs protecting, queue with leaky bucket.

GCRA

The Generic Cell Rate Algorithm comes from ATM network traffic scheduling and takes an approach unlike the others: instead of counting requests, it tracks a single point in time — the theoretical arrival time (TAT) of the next request that would conform to the rate.

Given an emission interval T (the reciprocal of the rate) and a burst tolerance τ, a request arriving at time t is evaluated as:

if t < TAT − τ        → reject
else                   → admit, and set TAT = max(t, TAT) + T

That is the whole algorithm. It yields the same sustained-rate-plus-burst behaviour as token bucket while storing one timestamp rather than a count and a refill clock, and it has no windows, so there is no boundary to spike at.

Its distinguishing benefit is what falls out of the rejection case. TAT − τ − t is exactly how long the caller must wait before a request would succeed — a precise value for the Retry-After header, where counting algorithms can only offer the end of the current window as an estimate.

Redisson exposes GCRA through RGcra, built on the native Redis command. Burst, rate and interval are passed directly to the acquisition call:

RGcra gcra = redisson.getGcra("rl:gcra:" + clientId);

// 4 tokens/sec sustained, plus a burst of 2
GcraResult result = gcra.tryAcquire(2, 4, Duration.ofSeconds(1));

if (result.isLimited()) {
    long retryAfter = result.getRetryAfterSeconds();     // when to retry
    long fullBurst  = result.getFullBurstAfterSeconds(); // when burst fully refills
    // reject with 429 + Retry-After: retryAfter
} else {
    // proceed
}

The GCRA command requires Redis 8.8 or later and is not available on Valkey. On Valkey, use RRateLimiter.

How to choose

Work from the constraint rather than from the algorithm:

• A public API with ordinary clients. Token bucket. Bursts are normal traffic, not abuse, and rejecting them produces support tickets.
• A strict quota you must not exceed — a billing tier, a contractual ceiling, an upstream that cuts you off. GCRA, for the exactness and the accurate retry timing.
• A fragile downstream. Leaky bucket as a queue. Smooth output matters more than fast failure.
• Something reasonable, quickly. Sliding window counter. Two integers, no boundary spike, good enough for the large majority of endpoints.
• Low request volume, zero tolerance for overshoot — password attempts, OTP sends, expensive operations. Sliding window log. The per-request storage is affordable when the limit is small.
• A coarse internal quota where a 2× overshoot is harmless. Fixed window. Do not use it on anything user-facing.

One consideration outranks the algorithm choice: correctness under concurrency. A perfect sliding window log implemented with three non-atomic round trips enforces its limit less reliably than a fixed window done atomically.

Implementing rate limiting algorithms on Valkey or Redis

All six algorithms need shared, atomically-updated state once an application runs on more than one node — a counter held in one JVM's memory is enforced separately by every instance behind the load balancer. Valkey and Redis suit the job: command execution is effectively serialized, the data is in memory, and keys expire natively.

Each algorithm maps to a different structure:

The split in that table is the practical one. The first three rows are algorithms you assemble from primitives and then have to make atomic yourself, which in every case means writing and testing Lua. The next three arrive as objects with the atomicity already handled.

For working implementations — including where hand-rolled limiters break, how to scope a limit per user or across a fleet, and a reusable Spring Boot @RateLimit annotation — see distributed rate limiting in Java with Valkey or Redis and Spring Boot.

Frequently asked questions

What are the main rate limiting algorithms?

Six cover nearly all production use: fixed window counter, sliding window log, sliding window counter, token bucket, leaky bucket and GCRA. They differ in how much state they keep per client, whether they permit bursts, and how they behave at window boundaries. Fixed window is the cheapest and the least accurate; token bucket and GCRA give a sustained rate plus a configurable burst and are the usual choice for public APIs.

What is the difference between token bucket and leaky bucket?

Used as a meter, they are mathematically equivalent. The difference appears when leaky bucket is implemented as a queue: token bucket rejects excess requests immediately and permits bursts up to the bucket capacity, while a queueing leaky bucket holds them and releases at a constant rate, smoothing output at the cost of latency. Reject fast with token bucket when a user is waiting; queue with leaky bucket when a fragile downstream needs protecting.

Which rate limiting algorithm is best?

There is no single best one, but token bucket is the strongest default for user-facing APIs because it tolerates the bursty traffic real clients produce without letting the long-run average drift. Choose GCRA when a quota must be enforced exactly and callers need an accurate Retry-After, sliding window counter when you want something sound with minimal state, and leaky bucket when smoothing downstream load matters more than failing fast.

Why does the fixed window algorithm allow double the limit?

Because its windows are aligned to the clock and counted independently. A client can exhaust its allowance at the very end of one window and the full allowance again at the start of the next, putting twice the configured limit through in a span approaching zero. Both windows are individually compliant, which is why the effective worst case is 2× and why fixed window is a poor fit for anything user-facing.

What is GCRA rate limiting?

GCRA, the Generic Cell Rate Algorithm, tracks the theoretical arrival time of the next conforming request instead of counting requests in a window. A request arriving earlier than that time, beyond the configured burst tolerance, is rejected. It gives the same sustained-rate-plus-burst behaviour as token bucket from a single stored timestamp, has no window boundaries, and yields the exact wait before a retry would succeed.

Similar terms

• Rate limiting
• Redis Sorted Set
• Redis TTL
• Redis Lua scripting
• Java Semaphore
• Race condition
• Idempotency

Redisson implements token bucket and GCRA rate limiting as distributed objects across Valkey and Redis, with the atomic logic written and tested. Start a free trial.