Rate limiters are everywhere — API gateways, login endpoints, the scraper you're trying to slow down. They're also a favourite systems-design interview question, for a sneaky reason: a correct single-threaded version is easy, and a correct concurrent one quietly is not.
In this post we'll build two classic algorithms — sliding window and token bucket — put them behind one clean interface with the Strategy pattern, then make them thread-safe: first with per-user locks, and finally a lock-free token bucket built on compare-and-swap.
What a rate limiter does
A rate limiter answers one question: is this user allowed to make this request right now, or have they exceeded their quota?
The interface is small:
boolean allow(int userId);
It returns true if the request may proceed and false if the user is over their limit — say, five requests per second. Each user has their own quota, users appear dynamically, and in any real system many threads call allow concurrently. That last constraint is what makes the problem interesting: the naive versions are easy to get right on a single thread and easy to get wrong on many.
We'll build the two algorithms, wire them behind a clean interface, then make them correct under concurrency — ending with a lock-free implementation.
The sliding window algorithm
The idea is direct: keep a record of when each request happened, and count how many fall inside the last second. If that count is already at the limit, reject.
Concretely, each user gets a queue of timestamps. On each request, drop the timestamps older than the window from the front, then check how many remain.
public boolean allow(int userId, int N) {
long now = System.currentTimeMillis();
ArrayDeque<Long> q = requestsByUser.computeIfAbsent(userId, k -> new ArrayDeque<>());
while (q.peekFirst() != null && now - q.peekFirst() > WINDOW_MS) {
q.removeFirst(); // evict timestamps older than the window
}
if (q.size() >= N) return false; // already at the limit
q.addLast(now); // record this request
return true;
}
Two details here are worth understanding.
Why a deque. We evict from the front and append at the back, so we need efficient access at both ends. ArrayDeque is the array-backed, allocation-light choice for exactly that.
Why front-eviction is enough. Timestamps only ever increase, so the queue is always sorted oldest-to-newest. Expired entries are therefore always clustered at the front — we can stop evicting the moment we hit one still inside the window, and whatever remains is the exact count for the current second.
The token bucket algorithm
Token bucket takes a different approach. Instead of storing a history of every request, it stores a small amount of state: how many tokens a user currently has, and when that count was last updated.
Picture a bucket holding up to N tokens. Every request spends one token. Tokens refill over time at a fixed rate — but the bucket has a cap, so they never exceed N. A request is allowed if there's a token to spend, rejected if the bucket is empty.
The elegant part is that you don't run a background timer dripping tokens. You compute the refill on demand: when a request arrives, you look at how much time has passed since the last update and add that many tokens (capped at N), then try to spend one.
class Bucket {
double tokens;
long lastRefillMs;
Bucket(double tokens, long lastRefillMs) {
this.tokens = tokens;
this.lastRefillMs = lastRefillMs;
}
}
public boolean allow(int userId, int N) {
long now = System.currentTimeMillis();
Bucket b = bucketByUser.computeIfAbsent(userId, k -> new Bucket(N, now)); // starts full
double elapsedSec = (now - b.lastRefillMs) / 1000.0;
b.tokens = Math.min(N, b.tokens + elapsedSec * N); // refill, capped at N
b.lastRefillMs = now;
if (b.tokens >= 1) { b.tokens -= 1; return true; } // spend one
return false;
}
Key detail — tokens are fractional
The token count is a double, not an int, because tokens accumulate continuously. At 5 tokens/second, 0.3 seconds earns 1.5 tokens — and that half-token is real, representing time already earned toward the next whole one. Truncate to an integer and you'd discard that fraction on every call, quietly throttling users below their configured rate.
The resolution: the count is fractional, but the decision is whole. A request is allowed only when there's at least one full token (tokens >= 1), and exactly one is spent. Store continuous, decide discrete.
Two arithmetic points matter for correctness: divide elapsed milliseconds by 1000.0 (a floating-point divisor) so sub-second refills aren't lost to integer division, and cap the total after refilling — min(N, current + refill) — so the bucket never holds more than N.
How the two compare
Sliding window is more precise — it enforces a true rolling count — but stores a timestamp per request, so its memory is O(N) per user. Token bucket stores just a count and a timestamp (O(1) per user) and permits controlled bursts: an idle user can spend a full bucket at once, then settle to the refill rate. That memory difference is the main reason token bucket is often preferred at scale.
Designing for both: the Strategy pattern
With two algorithms that answer the same question differently, we want to swap between them without rewriting anything around them. This is exactly what the Strategy pattern is for: the part that varies (the allow/deny decision) goes behind an interface, and the part that stays fixed (registration, quota lookup, and later the locking) lives in a context class that holds the interface.
interface RateLimiterAlgorithm {
boolean allow(int userId, int limit); // the limit is supplied by the context
}
class RateLimiter {
private final Map<Integer, Integer> quotaByUser = new ConcurrentHashMap<>();
private final RateLimiterAlgorithm algo;
RateLimiter(RateLimiterAlgorithm algo) { this.algo = algo; } // strategy injected here
void registerUser(int userId, int quota) { quotaByUser.put(userId, quota); }
boolean allow(int userId) {
Integer limit = quotaByUser.get(userId);
if (limit == null) throw new RuntimeException("User rule not present");
return algo.allow(userId, limit); // delegate the decision
}
}
Why this boundary
The context owns the quota map and the "is this user registered" check — written once, in one place. Each algorithm holds only its own per-user state (the queue map or the bucket map) and receives the limit as a parameter. Swapping token bucket for sliding window becomes a single constructor argument, with no changes to the RateLimiter class at all. The general principle: decide which class owns each piece of state before wiring anything, and keep shared concerns in the context, not duplicated across strategies.
Using it is then straightforward:
RateLimiter limiter = new RateLimiter(new TokenBucketAlgorithm());
limiter.registerUser(1, 5);
limiter.allow(1); // swap in SlidingWindowAlgorithm with no other changes
Making it thread-safe
Everything so far is correct on a single thread. In production, many threads call allow at once, and both algorithms need protection in two places.
The map. A plain HashMap is unsafe under concurrent access — it can corrupt its internal structure, and two threads creating an entry for a new user can race. The fix is ConcurrentHashMap, whose computeIfAbsent creates a user's state atomically, resolving the creation race.
The per-user state. This is the subtler part. Once two threads are working with the same user, they share the same queue (or bucket), and the read-modify-write on that shared state must happen as one indivisible unit.
A common misconception
Switching to ConcurrentHashMap is not sufficient on its own. A concurrent map protects the map's own operations — a single get, put, or computeIfAbsent. But once it hands you the queue, you're operating on the queue, which the map knows nothing about. Two threads for the same user both receive the same queue and both run evict → check → append on it at once, corrupting the (non-thread-safe) ArrayDeque and both slipping past the size check. Making a container thread-safe does not make a compound operation on its contents atomic.
The critical section
The sequence that must be atomic — evict expired entries, check the count, append — is the critical section. The instinct to wrap the whole method in a single lock works, but it's coarse: one lock shared by all users means a request for user B waits on user A, even though they touch entirely different data. Throughput collapses.
The better approach is per-user locking: lock on each user's own state object. Different users hold different locks and never block each other; requests for the same user serialize correctly. For sliding window, that object is the queue itself.
public boolean allow(int userId, int N) {
ArrayDeque<Long> q = requestsByUser.computeIfAbsent(userId, k -> new ArrayDeque<>());
synchronized (q) { // lock this user's queue only
long now = System.currentTimeMillis(); // read the clock inside the lock
while (q.peekFirst() != null && now - q.peekFirst() > WINDOW_MS) {
q.removeFirst();
}
if (q.size() >= N) return false;
q.addLast(now);
return true;
}
}
The map is a
ConcurrentHashMap;computeIfAbsentruns outside the lock (the map handles its own safety); the evict–check–append runs inside. Areturnfrom inside asynchronizedblock still releases the lock automatically.
Why read the clock inside the lock
Reading now inside the synchronized block preserves ordering. Because only one thread holds the lock at a time, the clock read and the append happen together — so the thread that reads an earlier timestamp always appends before one that reads a later timestamp, and the queue stays sorted. Front-eviction depends on that ordering (it stops at the first entry still inside the window), so reading the clock inside the lock keeps eviction correct.
The token bucket takes the same treatment, locking on the per-user Bucket. Its critical section is the entire computation apart from the map lookup, because every step — the refill and the spend — reads and writes the same tokens field, and they must be atomic together so no thread ever observes a half-updated count.
What a lock actually guarantees
A lock is about ownership, not execution. When a thread enters a synchronized block it acquires ownership of that object's monitor, and it keeps that ownership even if the operating system pauses it mid-section to run another thread. A second thread can run, but the moment it reaches the same synchronized block it cannot acquire the lock the first thread holds, so it waits there. However the OS interleaves threads, only one is ever inside the block. The right way to reason about concurrency is: any thread can be paused at any point, so ensure the result is correct no matter how they interleave — and a lock is the tool that makes a group of lines behave as one indivisible step.
Going lock-free with CAS
Locks are correct, but they block: a waiting thread is put to sleep until the lock frees. For the token bucket there's a lock-free alternative built on compare-and-swap (CAS), a hardware instruction that updates a value only if it hasn't changed since you read it.
CAS does three things as one atomic step: if the value at a location still equals what you expect, set it to a new value and report success; otherwise change nothing and report failure. In effect: "set this to X, but only if it's still Y." Rather than preventing other threads from interfering (a lock), you detect whether they did and retry if so.
AtomicInteger counter = new AtomicInteger(0);
// lock-free increment
while (true) {
int old = counter.get(); // read
int next = old + 1; // compute from what was read
if (counter.compareAndSet(old, next)) break; // swap only if still == old
// otherwise another thread changed it — loop and retry
}
If two threads both read 5 and compute 6, the first swap succeeds and the second fails (the value is now 6, not the 5 it expected), so the second retries with the fresh value and produces 7. No update is lost, and no thread ever blocks — which is what "lock-free" means.
CAS works on a single variable
A CAS instruction operates on exactly one memory location, so you can't atomically swap two fields at once. The token bucket has two — tokens and lastRefillMs — so to go lock-free you make the whole Bucket immutable and swap the single reference to it. You're not swapping two fields; you're swapping one pointer that points to an immutable snapshot of both. That's how you get multi-field atomicity from a single-variable primitive.
class Bucket { // immutable
final double tokens;
final long lastRefillMs;
Bucket(double t, long ms) { tokens = t; lastRefillMs = ms; }
}
public boolean allow(int userId, int N) {
long now = System.currentTimeMillis();
AtomicReference<Bucket> ref = bucketByUser.computeIfAbsent(
userId, k -> new AtomicReference<>(new Bucket(N, now)));
while (true) {
Bucket current = ref.get(); // read
double elapsedSec = (now - current.lastRefillMs) / 1000.0;
double refilled = Math.min(N, current.tokens + elapsedSec * N);
if (refilled < 1) return false; // no token — reject
Bucket next = new Bucket(refilled - 1, now); // new snapshot, one spent
if (ref.compareAndSet(current, next)) return true; // swap if unchanged
// otherwise retry with the updated state
}
}
CAS is not automatically faster
Lock-free is a real tradeoff, not a free win. CAS shines under low-to-moderate contention: no blocking, no context switches, and a paused thread doesn't stall the others. But under high contention on a single value, many threads keep failing and retrying — spending cycles on work they discard — and a lock that sleeps its waiters can actually perform better. For a per-user bucket, contention on any one bucket is naturally low, so CAS fits well; the cost is an object allocation per attempt, since the bucket must be immutable. Choose based on the contention profile, not a blanket rule.
Summary
A rate limiter is small, but it touches a surprising number of ideas worth carrying to other problems:
- Two algorithms, two tradeoffs. Sliding window is precise but stores a timestamp per request; token bucket stores O(1) state and allows bursts. Pick based on accuracy versus memory.
- Design boundaries first. With the Strategy pattern, the context owns shared concerns and the strategy is pure decision logic, so algorithms swap with a one-line change.
- Thread safety needs two things: a concurrent map for the structure, and a per-user lock for the compound operation on each user's state. A thread-safe container alone doesn't make your read-modify-write atomic.
- Per-user locking keeps different users from blocking each other while serializing same-user access. Read time-sensitive values inside the lock to preserve ordering.
- CAS is a single-variable "swap only if unchanged, else retry." Multi-field state goes lock-free by making it immutable and swapping the reference — a good fit under low contention.
The complete program
Everything above, assembled into one file you can drop into RateLimiterDemo.java and run. It wires the lock-free token bucket behind the RateLimiter context; swapping in new SlidingWindowAlgorithm() is the only change needed to try the other algorithm. A main method demonstrates a burst, a refill after one second, and a 100-thread race that a correct limiter caps at five.
import java.util.ArrayDeque;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
// The strategy: the only thing that varies is the allow/deny decision.
interface RateLimiterAlgorithm {
boolean allow(int userId, int limit);
}
// The context: owns registration and quota lookup, and delegates the decision.
class RateLimiter {
private final Map<Integer, Integer> quotaByUser = new ConcurrentHashMap<>();
private final RateLimiterAlgorithm algo;
RateLimiter(RateLimiterAlgorithm algo) { this.algo = algo; }
void registerUser(int userId, int quota) { quotaByUser.put(userId, quota); }
boolean allow(int userId) {
Integer limit = quotaByUser.get(userId);
if (limit == null) throw new RuntimeException("User rule not present");
return algo.allow(userId, limit);
}
}
// Sliding window: a per-user queue of timestamps, guarded by a per-user lock.
class SlidingWindowAlgorithm implements RateLimiterAlgorithm {
private static final long WINDOW_MS = 1000;
private final Map<Integer, ArrayDeque<Long>> requestsByUser = new ConcurrentHashMap<>();
public boolean allow(int userId, int limit) {
ArrayDeque<Long> q = requestsByUser.computeIfAbsent(userId, k -> new ArrayDeque<>());
synchronized (q) { // lock this user's queue only
long now = System.currentTimeMillis(); // read the clock inside the lock
while (q.peekFirst() != null && now - q.peekFirst() > WINDOW_MS) {
q.removeFirst();
}
if (q.size() >= limit) return false;
q.addLast(now);
return true;
}
}
}
// Token bucket, lock-free: an immutable Bucket swapped atomically with CAS.
class TokenBucketAlgorithm implements RateLimiterAlgorithm {
private final Map<Integer, AtomicReference<Bucket>> bucketByUser = new ConcurrentHashMap<>();
private static final class Bucket {
final double tokens;
final long lastRefillMs;
Bucket(double tokens, long lastRefillMs) {
this.tokens = tokens;
this.lastRefillMs = lastRefillMs;
}
}
public boolean allow(int userId, int limit) {
long now = System.currentTimeMillis();
AtomicReference<Bucket> ref = bucketByUser.computeIfAbsent(
userId, k -> new AtomicReference<>(new Bucket(limit, now))); // starts full
while (true) {
Bucket current = ref.get(); // read
double elapsedSec = (now - current.lastRefillMs) / 1000.0;
double refilled = Math.min(limit, current.tokens + elapsedSec * limit);
if (refilled < 1) return false; // no token, reject
Bucket next = new Bucket(refilled - 1, now); // new snapshot, one spent
if (ref.compareAndSet(current, next)) return true; // swap only if unchanged
// otherwise another thread won the race, loop and retry
}
}
}
public class RateLimiterDemo {
public static void main(String[] args) throws InterruptedException {
// Swap the strategy here: new SlidingWindowAlgorithm() works with no other change.
RateLimiter limiter = new RateLimiter(new TokenBucketAlgorithm());
limiter.registerUser(1, 5); // user 1: 5 requests per second
System.out.println("Burst of 7 back-to-back requests (limit 5):");
for (int i = 1; i <= 7; i++) {
System.out.println(" request " + i + " -> " + (limiter.allow(1) ? "ALLOW" : "DENY"));
}
Thread.sleep(1000); // let the bucket refill
System.out.println("After 1s: " + (limiter.allow(1) ? "ALLOW" : "DENY"));
// Concurrency check: 100 threads hit a fresh user (limit 5) simultaneously.
// A correct limiter admits at most 5; a broken one over-admits.
RateLimiter concurrent = new RateLimiter(new TokenBucketAlgorithm());
concurrent.registerUser(2, 5);
int threads = 100;
AtomicInteger allowed = new AtomicInteger();
CountDownLatch start = new CountDownLatch(1);
CountDownLatch done = new CountDownLatch(threads);
for (int i = 0; i < threads; i++) {
new Thread(() -> {
try { start.await(); } catch (InterruptedException ignored) {}
if (concurrent.allow(2)) allowed.incrementAndGet();
done.countDown();
}).start();
}
start.countDown(); // release all threads at once
done.await();
System.out.println(threads + " threads race, limit 5 -> allowed " + allowed.get());
}
}
Compile and run it with any modern JDK:
javac RateLimiterDemo.java && java RateLimiterDemo
You should see the first five requests allowed and the rest denied, one request succeeding again after the refill, and — the part that matters — exactly five admits when a hundred threads race for the same five-request quota:
Burst of 7 back-to-back requests (limit 5):
request 1 -> ALLOW
request 2 -> ALLOW
request 3 -> ALLOW
request 4 -> ALLOW
request 5 -> ALLOW
request 6 -> DENY
request 7 -> DENY
After 1s: ALLOW
100 threads race, limit 5 -> allowed 5
Thanks for reading. If you found an issue or have a sharper way to frame any of this, I'd love to hear it — reach me on LinkedIn.