Definition
- Fixed-window counter – counts requests per fixed clock window; simplest but allows up to 2x burst at the boundary.
- Sliding-window log – stores timestamps for exact trailing-window counts; accurate but memory-heavy.
- Sliding-window counter – blends current and previous window counts; smooth with minimal memory.
- Token bucket – refills tokens at a steady rate up to a capacity; permits controlled bursts while capping the average.
- Leaky bucket – drains at a constant rate; enforces smooth outflow with no burst allowance.
- Distributed enforcement – all instances must share the counter in Redis with atomic Lua scripts to avoid N-times overshoot.
Imagine the National Bank of India limits how many forms a customer can submit. The fixed-window counter resets the tally at the top of every hour: a clever customer submits a batch at 10:59 and another at 11:00, sneaking in almost double right at the boundary. The sliding window looks back over the last sixty minutes continuously, with no boundary trick. The token bucket gives the customer a jar of ten tokens that refills slowly: they can spend a quick burst of ten at once, then must wait. The leaky bucket is a funnel that drips forms through at a fixed steady rate no matter how fast they are poured in.
Understanding the Concepts
What is a fixed-window counter?
The fixed-window counter divides time into equal windows, say one minute, and keeps a per-client counter that resets at each boundary. Each request increments the counter, and once it reaches the limit, further requests are rejected. It is trivial to implement and cheap in memory. Its well-known flaw is the boundary burst: a client can send a full limit at the end of one window and another full limit at the start of the next, producing up to 2x the intended rate.
package com.bank.ratelimit;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
public class FixedWindowRateLimiter {
private final int maxRequests;
private final long windowSizeMs;
private final ConcurrentHashMap<String, WindowCounter> counters
= new ConcurrentHashMap<>();
public FixedWindowRateLimiter(int maxRequests, long windowSizeMs) {
this.maxRequests = maxRequests;
this.windowSizeMs = windowSizeMs;
}
public boolean allowRequest(String clientId) {
long currentWindow = System.currentTimeMillis() / windowSizeMs;
WindowCounter counter = counters.compute(clientId, (k, v) -> {
if (v == null || v.window != currentWindow) {
return new WindowCounter(currentWindow);
}
return v;
});
return counter.count.incrementAndGet() <= maxRequests;
}
private static class WindowCounter {
final long window;
final AtomicInteger count = new AtomicInteger(0);
WindowCounter(long window) { this.window = window; }
}
}
Boundary burst problem (limit = 100/min):
10:59:55 -> 100 requests (allowed, fills the window)
11:00:00 -> window resets
11:00:05 -> 100 requests (allowed, new window)
Result: 200 requests in 10 seconds!
What is a sliding-window log?
The sliding-window log stores a timestamp for every request and counts how many fall within the trailing window. This is perfectly accurate but memory-expensive, since you store one entry per request.
package com.bank.ratelimit;
import java.util.concurrent.ConcurrentLinkedDeque;
public class SlidingWindowLogLimiter {
private final int maxRequests;
private final long windowMs;
private final ConcurrentLinkedDeque<Long> timestamps
= new ConcurrentLinkedDeque<>();
public SlidingWindowLogLimiter(int maxRequests, long windowMs) {
this.maxRequests = maxRequests;
this.windowMs = windowMs;
}
public synchronized boolean allowRequest() {
long now = System.currentTimeMillis();
long cutoff = now - windowMs;
// Remove expired timestamps
while (!timestamps.isEmpty() && timestamps.peekFirst() < cutoff) {
timestamps.pollFirst();
}
if (timestamps.size() < maxRequests) {
timestamps.addLast(now);
return true;
}
return false;
}
}
Memory cost at 10,000 requests/sec with 60s window:
Entries stored: up to 600,000 timestamps
Memory: ~4.8 MB per client key (8 bytes per Long)
Accurate: yes, no boundary burst
What is a sliding-window counter?
The sliding-window counter keeps just two counters, the current window and the previous window, and estimates the rate by weighting the previous window's count by how much of it still overlaps the trailing window. This smooths the boundary burst to a small approximation error while using almost no memory.
package com.bank.ratelimit;
public class SlidingWindowCounterLimiter {
private final int maxRequests;
private final long windowMs;
private int previousCount;
private int currentCount;
private long currentWindowStart;
public SlidingWindowCounterLimiter(int maxRequests, long windowMs) {
this.maxRequests = maxRequests;
this.windowMs = windowMs;
this.currentWindowStart = System.currentTimeMillis();
}
public synchronized boolean allowRequest() {
long now = System.currentTimeMillis();
long elapsed = now - currentWindowStart;
if (elapsed >= windowMs) {
previousCount = currentCount;
currentCount = 0;
currentWindowStart = now;
elapsed = 0;
}
// Weight previous window by overlap
double overlapRatio = 1.0 - ((double) elapsed / windowMs);
double estimatedCount =
(previousCount * overlapRatio) + currentCount;
if (estimatedCount < maxRequests) {
currentCount++;
return true;
}
return false;
}
}
Memory: 2 integers per client key (trivial)
Accuracy: small approximation error (~1-2%)
Boundary burst: eliminated by weighted blending
What is a token bucket?
The token bucket refills tokens at a steady rate up to a capacity. Each request removes one token. Because the bucket can hold accumulated tokens, it permits a controlled burst up to that capacity when the client has been idle, then settles to the refill rate.
package com.bank.ratelimit;
public class TokenBucketLimiter {
private final int capacity;
private final double refillRate; // tokens per millisecond
private double tokens;
private long lastRefillTime;
public TokenBucketLimiter(int capacity, int refillPerSecond) {
this.capacity = capacity;
this.refillRate = refillPerSecond / 1000.0;
this.tokens = capacity;
this.lastRefillTime = System.currentTimeMillis();
}
public synchronized boolean allowRequest() {
long now = System.currentTimeMillis();
double elapsed = now - lastRefillTime;
tokens = Math.min(capacity, tokens + (elapsed * refillRate));
lastRefillTime = now;
if (tokens >= 1.0) {
tokens -= 1.0;
return true;
}
return false;
}
}
Token bucket (capacity=20, refill=10/sec):
Client idle for 2 seconds -> 20 tokens available
Burst of 20 requests -> all allowed (controlled burst)
Next request -> must wait 100ms for 1 token to refill
Steady state: 10 requests/sec average
What is a leaky bucket?
The leaky bucket drains requests at a constant rate, smoothing bursty input into steady output. It offers no burst allowance and may add queuing delay, but it is ideal when a downstream system can only handle a steady rate.
package com.bank.ratelimit;
import java.util.concurrent.LinkedBlockingQueue;
public class LeakyBucketLimiter {
private final LinkedBlockingQueue<Runnable> queue;
private final int drainRatePerSecond;
public LeakyBucketLimiter(int queueCapacity, int drainRatePerSecond) {
this.queue = new LinkedBlockingQueue<>(queueCapacity);
this.drainRatePerSecond = drainRatePerSecond;
startDraining();
}
public boolean submit(Runnable task) {
return queue.offer(task); // false if queue full
}
private void startDraining() {
Thread drainer = new Thread(() -> {
long intervalMs = 1000 / drainRatePerSecond;
while (!Thread.currentThread().isInterrupted()) {
try {
Runnable task = queue.take();
task.run();
Thread.sleep(intervalMs);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
});
drainer.setDaemon(true);
drainer.start();
}
}
Leaky bucket (queue=50, drain=10/sec):
Burst of 50 requests -> all queued
Processing: 1 every 100ms (strictly constant)
51st request -> rejected (queue full)
Total drain time for 50 requests: 5 seconds
How do the algorithms compare?
| Algorithm | Simplicity | Memory | Boundary Burst | Burst Tolerance | Best For |
|---|---|---|---|---|---|
| Fixed window | Trivial | Tiny | Yes (2x) | No | Simple internal limits |
| Sliding log | Medium | High | No | No | Exact precision needed |
| Sliding counter | Medium | Tiny | No (~1%) | No | Production rate limits |
| Token bucket | Medium | Tiny | No | Yes (controlled) | Public API limits |
| Leaky bucket | Medium | Queue size | No | No (queued) | Protecting downstream |
How do you enforce limits across multiple instances?
If each instance keeps its own counter, N instances each allow the full limit and the effective limit is N times too high. The state must live in Redis with atomic operations via Lua scripts.
-- Redis Lua script for distributed token bucket
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2]) -- tokens per second
local now = tonumber(ARGV[3]) -- current timestamp ms
local data = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(data[1]) or capacity
local last_refill = tonumber(data[2]) or now
-- Refill tokens
local elapsed = (now - last_refill) / 1000.0
tokens = math.min(capacity, tokens + (elapsed * refill_rate))
local allowed = 0
if tokens >= 1 then
tokens = tokens - 1
allowed = 1
end
redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
redis.call('EXPIRE', key, math.ceil(capacity / refill_rate) * 2)
return allowed
package com.bank.ratelimit;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.data.redis.core.script.DefaultRedisScript;
import org.springframework.stereotype.Component;
import java.util.Collections;
@Component
public class DistributedTokenBucket {
private final StringRedisTemplate redis;
private final DefaultRedisScript<Long> script;
public DistributedTokenBucket(StringRedisTemplate redis) {
this.redis = redis;
this.script = new DefaultRedisScript<>();
this.script.setScriptText("-- Lua script above");
this.script.setResultType(Long.class);
}
public boolean allowRequest(String clientId,
int capacity,
int refillPerSecond) {
Long result = redis.execute(script,
Collections.singletonList("ratelimit:" + clientId),
String.valueOf(capacity),
String.valueOf(refillPerSecond),
String.valueOf(System.currentTimeMillis()));
return result != null && result == 1;
}
}
Without shared counter (3 instances, limit 100/min):
Instance 1: allows 100
Instance 2: allows 100
Instance 3: allows 100
Effective limit: 300/min (3x too high!)
With Redis shared counter (3 instances, limit 100/min):
All instances check Redis atomically
Effective limit: exactly 100/min (correct)
What are common mistakes with rate limiting?
The most common mistake is keeping the counter in local memory, which makes the limit per-instance instead of global. Another is not returning a Retry-After header with a 429 response, leaving clients guessing when to retry.
package com.bank.ratelimit;
import org.springframework.http.HttpStatus;
import org.springframework.http.ResponseEntity;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;
@RestController
public class RateLimitedController {
private final DistributedTokenBucket limiter;
public RateLimitedController(DistributedTokenBucket limiter) {
this.limiter = limiter;
}
@GetMapping("/api/accounts/{id}/balance")
public ResponseEntity<?> getBalance(String clientId, String id) {
if (!limiter.allowRequest(clientId, 100, 10)) {
// CORRECT: return 429 with Retry-After
return ResponseEntity.status(HttpStatus.TOO_MANY_REQUESTS)
.header("Retry-After", "5")
.header("X-RateLimit-Remaining", "0")
.body("Rate limit exceeded. Try again in 5 seconds.");
}
return ResponseEntity.ok("Balance: 150000.00");
}
}
Visual Overview
Fixed Window: Sliding Window: Token Bucket: Leaky Bucket:
┌───┬───┐ ─────────────> ┌─────────┐ ┌─────────┐
│ 0 │ 0 │ reset [ 60 seconds ] │ tokens │ │ queue │
│...│...│ at continuous count │ ● ● ● ● │ │ ■ ■ ■ ■ │
│100│100│ boundary no boundary trick │ ● ● ● │ └────┬────┘
└───┴───┘ └────┬────┘ │
^boundary^ │ consume drain at
burst! refill at constant
steady rate rate
▼ ▼
Distributed Enforcement:
┌──────────┐ ┌──────────┐ ┌──────────┐
│Instance 1│ │Instance 2│ │Instance 3│
└─────┬────┘ └─────┬────┘ └─────┬────┘
│ │ │
└───────────────┼───────────────┘
│
▼
┌──────────────┐
│ Redis │
│ Lua script │
│ (atomic) │
└──────────────┘
Key Takeaway
There are four classic rate-limiting algorithms, and the choice comes down to burst behavior. The fixed-window counter is simplest, counting requests per clock window with almost no memory, but its boundary burst flaw allows up to twice the intended rate in a short span straddling the reset. The sliding-window counter is the practical fix: it blends the current and previous window counts to smooth the boundary burst with a tiny approximation error and trivial memory. The token bucket is the most common choice for public APIs because it permits controlled bursts up to the bucket capacity when a client has been idle, then settles to the refill rate, which matches how real user traffic actually behaves.
The leaky bucket is the mirror image: it drains at a constant rate regardless of arrival burstiness, so it is ideal for protecting a downstream system that can only handle a steady feed, at the cost of no burst allowance and possible queuing delay. At National Bank of India, a fixed window let a scripted client double-burst at the minute boundary, so we settled on a token bucket for the user-facing transfer API and a leaky bucket where we fed a legacy settlement system that needed a steady rate.
The distributed enforcement question is where most candidates slip. If each instance keeps its own counter, the effective limit is N times too high. The state must live in Redis, and the update must be atomic via a Lua script that reads, refills, checks, and updates in one indivisible step, so two instances can never both read a stale value and overshoot. Redis becomes the single clock source, sidestepping clock skew across instances.
Remember one sentence: fixed window is simplest but bursts at the boundary, sliding window smooths that, token bucket allows controlled bursts, leaky bucket forces constant outflow, and whichever you choose, back it with a shared atomic counter in Redis so the limit holds globally.
---