These are the notes for Low-Level Design (LLD) episode 68: designing a rate limiter, the code that says "slow down, you've asked too many times". It's a favourite interview question because there are five classic algorithms, each with a trade-off. We make the design testable with clock injection, then build the fixed window counter, sliding window log, sliding window counter, token bucket and leaky bucket, put them behind a RateLimiter interface (a Strategy per algorithm) with per-user and per-API limits, and make the counters thread-safe.
How the code was run: every program was saved as Main.java in a fresh folder and run with javac Main.java && java -cp . Main on OpenJDK 21. Every output below is the real output, pasted exactly. The users (Asha, Ravi), APIs and limits are made up for teaching.
1. The problem: the sweet shop on Diwali morning
| At the sweet shop | In software |
|---|---|
| 500 people arrive at the door at once | A flood of requests to an API |
| Everyone pushes in; the counter jams | The server is overloaded; everyone's requests fail or crawl |
| A guard lets in only 5 people a minute | Rate limiting: a limit on requests per unit of time |
| One big family can't take all 5 places | Per-user limits: everyone gets a fair share |
2. What rate limiting is
- Request: one call from a client (an app, a browser, a bot) to a server.
- API (application programming interface): a door into a server that programs call, e.g.
/login,/search,/otp. - Rate: how many requests arrive in some time, e.g. 5 a minute.
- Rate limiting: refusing requests above an allowed rate.
- Why: protect the server from floods, stop someone guessing a 6-digit OTP by trying a million codes, and give every user a fair share.
- On the web, a refused request gets HTTP 429 Too Many Requests (defined in RFC 6585, section 4), and the server may add a
Retry-Afterheader saying how long to wait before trying again (MDN: 429 Too Many Requests). - Our core method:
boolean tryAcquire():true= go ahead,false= refused.
3. Clock injection: testing time without waiting
If the limiter calls System.currentTimeMillis() inside, a test of "5 a minute" must wait a real minute, and can't choose the moment.
- Clock: an interface with one method,
long millis(), the current time in milliseconds. - Clock injection: the limiter receives a
Clockin its constructor instead of asking the system. This is dependency injection (episode 16) applied to time. - Production passes a real clock (
System.currentTimeMillis()); tests pass a FakeClock whose time is set by hand.
4. Fixed window counter
Divide time into fixed windows (10:00, 10:01, ...). Count requests in the current window; reset the count when a new window starts.
interface Clock { long millis(); } // where "now" comes from
class FakeClock implements Clock { // a clock a test can move by hand
private long now = 0;
public long millis() { return now; }
void set(long hh, long mm, long ss) { now = ((hh * 60 + mm) * 60 + ss) * 1000; }
}
class FixedWindowLimiter { // at most `limit` requests per window
private final int limit; private final long windowMs; private final Clock clock;
private long window = -1; private int count = 0;
FixedWindowLimiter(int limit, long windowMs, Clock clock) {
this.limit = limit; this.windowMs = windowMs; this.clock = clock; }
boolean tryAcquire() {
long w = clock.millis() / windowMs; // which window are we in? 10:00, 10:01, ...
if (w != window) { window = w; count = 0; } // a new window: the counter starts again
if (count < limit) { count++; return true; }
return false; }
}
public class Main {
public static void main(String[] args) {
FakeClock clock = new FakeClock();
FixedWindowLimiter otp = new FixedWindowLimiter(5, 60_000, clock); // OTP: 5 per minute
int allowed = 0;
clock.set(10, 0, 59); for (int i = 0; i < 5; i++) if (otp.tryAcquire()) allowed++;
clock.set(10, 1, 0); for (int i = 0; i < 5; i++) if (otp.tryAcquire()) allowed++;
System.out.println("10:00:59 and 10:01:00: " + allowed + " allowed in 1 second (limit 5 a minute)");
clock.set(10, 1, 30); System.out.println("10:01:30, one more: " + otp.tryAcquire());
}
}
Real output:
10:00:59 and 10:01:00: 10 allowed in 1 second (limit 5 a minute)
10:01:30, one more: false
10 allowed in 1 second with a limit of 5 a minute: the last 5 of one window and the first 5 of the next sit side by side. This is the boundary burst: fixed windows all reset at the same moment, so up to 2 × limit fit around an edge.
5. Sliding windows: the log and the counter
A sliding window always looks at the last 60 seconds counted back from now, so there is no edge to squeeze through.
- Sliding window log: keep the time of every allowed request in a queue (a
Deque). On each request, drop times older than the window; allow if fewer thanlimitremain. Exact, but memory grows with the limit. - Sliding window counter: keep only this window's count (
curr) and the last window's (prev). If we are a quarter of the way into this window, three quarters of the last window still overlap the last 60 seconds, so estimateprev × 0.75 + curr. Two numbers, an estimate that assumes the last window's requests were spread evenly.
import java.util.*;
interface Clock { long millis(); }
class FakeClock implements Clock { long now; public long millis() { return now; } }
class SlidingLog { // remembers the time of every allowed request
final int limit; final long win; final Clock clock; final Deque<Long> times = new ArrayDeque<>();
SlidingLog(int limit, long win, Clock c) { this.limit = limit; this.win = win; clock = c; }
boolean tryAcquire() { long now = clock.millis();
while (!times.isEmpty() && times.peekFirst() <= now - win) times.pollFirst(); // older: forget
if (times.size() < limit) { times.addLast(now); return true; }
return false; } }
class SlidingCounter { // only two counters: this window and the last one
final int limit; final long win; final Clock clock; long window = 0; int curr = 0, prev = 0;
SlidingCounter(int limit, long win, Clock c) { this.limit = limit; this.win = win; clock = c; }
boolean tryAcquire() { long now = clock.millis(), w = now / win;
if (w != window) { prev = (w == window + 1) ? curr : 0; curr = 0; window = w; }
double overlap = 1.0 - (double) (now % win) / win; // how much of the last window still counts
if (prev * overlap + curr < limit) { curr++; return true; }
return false; } }
public class Main { public static void main(String[] args) {
FakeClock clock = new FakeClock();
SlidingLog log = new SlidingLog(5, 60_000, clock);
SlidingCounter counter = new SlidingCounter(5, 60_000, clock);
for (long t : new long[]{59_000, 60_000, 90_000, 119_000, 125_000}) { // seconds 59, 60, 90, ...
clock.now = t; int a = 0, b = 0;
for (int i = 0; i < 5; i++) { if (log.tryAcquire()) a++; if (counter.tryAcquire()) b++; }
System.out.printf("t=%3d s: 5 tries -> log %d allowed, counter %d allowed%n", t / 1000, a, b); }
System.out.println("the log keeps " + log.times.size() + " timestamps; the counter keeps 2 numbers"); } }
Real output:
t= 59 s: 5 tries -> log 5 allowed, counter 5 allowed
t= 60 s: 5 tries -> log 0 allowed, counter 0 allowed
t= 90 s: 5 tries -> log 0 allowed, counter 3 allowed
t=119 s: 5 tries -> log 5 allowed, counter 2 allowed
t=125 s: 5 tries -> log 0 allowed, counter 1 allowed
the log keeps 5 timestamps; the counter keeps 2 numbers
| Time | Log (exact) | Counter (estimate) | Why |
|---|---|---|---|
| 59 s | 5 | 5 | Fresh |
| 60 s | 0 | 0 | The burst at 59 s is still inside the last 60 s: no boundary burst |
| 90 s | 0 | 3 | Counter: 5 × 0.5 + curr < 5 allows 3 |
| 119 s | 5 | 2 | Log: the 59 s requests are now 60 s old; counter: window 2 already has 3 |
| 125 s | 0 | 1 | Log: 5 from 119 s; counter: 5 × 0.92 + 0 < 5 allows 1 |
The memory bill: with 1,000 a minute and 1,000,000 users, the log could hold 1,000,000,000 timestamps; the counter holds 2 numbers per user.
6. Token bucket and leaky bucket
| Real life | Algorithm |
|---|---|
| A bowl at the door holds 5 entry tokens; you take one to enter | Token bucket: capacity = 5 tokens, each request spends one |
| One new token every second, never more than 5 | Refill rate |
| A clay matka with a small tap: pour fast, it drips out at one speed | Leaky bucket: requests wait in a queue and are served at a fixed rate |
| The matka is full: extra water spills | A full queue: the request is refused |
- Token bucket: allows short bursts (up to the capacity) and an average rate (the refill rate). "Lazy refill": no timer thread; when a request arrives, add
elapsed ÷ refill intervaltokens, capped at the capacity. - Leaky bucket (as a queue): output is smooth, exactly one per interval, however bursty the input.
import java.util.*;
interface Clock { long millis(); }
class FakeClock implements Clock { long now; public long millis() { return now; } }
class TokenBucket { // a bowl of tokens; one more drops in every `everyMs`
final long capacity, everyMs; final Clock clock; double tokens; long last;
TokenBucket(long cap, long everyMs, Clock c) {
capacity = cap; this.everyMs = everyMs; clock = c; tokens = capacity; last = c.millis(); }
boolean tryAcquire() { long now = clock.millis();
tokens = Math.min(capacity, tokens + (double) (now - last) / everyMs); last = now; // refill
if (tokens >= 1) { tokens--; return true; } // a token = permission for 1 request
return false; } }
class LeakyBucket { // a queue with a hole: requests drip out at a fixed rate
final int capacity; final long everyMs; final Clock clock; final Deque<String> q = new ArrayDeque<>();
long last;
LeakyBucket(int cap, long everyMs, Clock c) { capacity = cap; this.everyMs = everyMs; clock = c; }
boolean offer(String r) { leak(); if (q.size() < capacity) { q.addLast(r); return true; } return false; }
void leak() { long now = clock.millis();
while (!q.isEmpty() && now - last >= everyMs) {
last += everyMs; System.out.println(" at " + last / 1000 + " s leaky serves " + q.pollFirst()); }
if (q.isEmpty()) last = now; } }
public class Main { public static void main(String[] args) {
FakeClock clock = new FakeClock();
TokenBucket token = new TokenBucket(5, 1000, clock); LeakyBucket leaky = new LeakyBucket(5, 1000, clock);
int t = 0, q = 0;
for (int i = 1; i <= 8; i++) { if (token.tryAcquire()) t++; if (leaky.offer("req" + i)) q++; }
System.out.println("0 s, burst of 8: token serves " + t + " now; leaky queues " + q + ", rejects " + (8 - q));
clock.now = 3_000; t = 0; for (int i = 0; i < 5; i++) if (token.tryAcquire()) t++;
System.out.println("3 s, 5 more tries: token serves " + t + " (3 tokens dripped back in)");
clock.now = 6_000; leaky.leak(); } }
Real output:
0 s, burst of 8: token serves 5 now; leaky queues 5, rejects 3
3 s, 5 more tries: token serves 3 (3 tokens dripped back in)
at 1 s leaky serves req1
at 2 s leaky serves req2
at 3 s leaky serves req3
at 4 s leaky serves req4
at 5 s leaky serves req5
7. One interface, many algorithms, per-user and per-API
The obvious way is one big RateLimiter with an if/else on an algorithm name and one counter for the whole app: a single bot uses up Asha's limit too, and /login gets the same limit as /search.
The fix:
- RateLimiter interface with tryAcquire(); one class per algorithm. This is the Strategy pattern (episode 34): the algorithm is an object you can swap.
- A registry: rules maps an API to a Supplier<RateLimiter> (a function that makes a new limiter); limiters maps "user API" to that user's own limiter, created on first use with computeIfAbsent.
import java.util.*; import java.util.function.Supplier;
interface Clock { long millis(); }
class FakeClock implements Clock { long now; public long millis() { return now; } }
interface RateLimiter { boolean tryAcquire(); } // Strategy: one method, many algorithms
class FixedWindow implements RateLimiter {
final int limit; final long win; final Clock clock; long w = -1; int n;
FixedWindow(int limit, long win, Clock c) { this.limit = limit; this.win = win; clock = c; }
public boolean tryAcquire() { long cur = clock.millis() / win;
if (cur != w) { w = cur; n = 0; }
if (n < limit) { n++; return true; } return false; } }
class TokenBucket implements RateLimiter {
final double cap, perMs; final Clock clock; double tokens; long last;
TokenBucket(double cap, double perSec, Clock c) { this.cap = tokens = cap; perMs = perSec / 1000; clock = c; }
public boolean tryAcquire() { long now = clock.millis();
tokens = Math.min(cap, tokens + (now - last) * perMs); last = now;
if (tokens >= 1) { tokens--; return true; } return false; } }
class RateLimiterRegistry { // one limiter per user, per API
private final Map<String, Supplier<RateLimiter>> rules = new HashMap<>(); // API -> how to make one
private final Map<String, RateLimiter> limiters = new HashMap<>(); // "asha /login" -> its own
void rule(String api, Supplier<RateLimiter> make) { rules.put(api, make); }
boolean allow(String user, String api) {
return limiters.computeIfAbsent(user + " " + api, k -> rules.get(api).get()).tryAcquire(); } }
public class Main { public static void main(String[] args) {
FakeClock clock = new FakeClock(); RateLimiterRegistry r = new RateLimiterRegistry();
r.rule("/login", () -> new FixedWindow(3, 60_000, clock)); // 3 tries a minute
r.rule("/search", () -> new TokenBucket(10, 10, clock)); // bursts of 10, 10 a second
for (String[] call : new String[][]{{"asha", "/login"}, {"ravi", "/login"}, {"asha", "/search"}}) {
int ok = 0; for (int i = 0; i < 5; i++) if (r.allow(call[0], call[1])) ok++;
System.out.println(call[0] + " " + call[1] + ", 5 tries: " + ok + " allowed"); } } }
Real output:
asha /login, 5 tries: 3 allowed
ravi /login, 5 tries: 3 allowed
asha /search, 5 tries: 5 allowed
8. Thread-safe counters
A server handles many requests at once on many threads. if (tokens > 0) tokens--; is check-then-act: two threads can both see a token and both take it, and tokens-- itself is read-modify-write. That's a race condition (episode 46).
- Fix 1:
synchronized: only one thread at a time runstryAcquire. - Fix 2:
AtomicLong+compareAndSet(lock-free): "set it tot - 1only if it is stillt"; if another thread changed it first, read again and retry. This is compare-and-swap (CAS).
import java.util.*; import java.util.concurrent.atomic.*;
interface RateLimiter { boolean tryAcquire(); }
class UnsafeBucket implements RateLimiter { // 10,000,000 tokens, no refill: at most that many
private long tokens = 10_000_000;
public boolean tryAcquire() { if (tokens > 0) { tokens--; return true; } return false; } // check, then act
}
class SafeBucket implements RateLimiter {
private long tokens = 10_000_000;
public synchronized boolean tryAcquire() { if (tokens > 0) { tokens--; return true; } return false; }
}
class AtomicBucket implements RateLimiter { // lock-free: compare-and-swap in a loop
private final AtomicLong tokens = new AtomicLong(10_000_000);
public boolean tryAcquire() {
for (long t = tokens.get(); t > 0; t = tokens.get())
if (tokens.compareAndSet(t, t - 1)) return true; // only wins if nobody changed it meanwhile
return false; }
}
public class Main {
static void hammer(String name, RateLimiter limiter) throws InterruptedException {
AtomicInteger allowed = new AtomicInteger(); List<Thread> threads = new ArrayList<>();
for (int t = 0; t < 4; t++) threads.add(Thread.ofPlatform().start(() -> { // 4 threads at once
for (int i = 0; i < 5_000_000; i++) if (limiter.tryAcquire()) allowed.incrementAndGet(); }));
for (Thread t : threads) t.join();
System.out.printf("%-13s 20,000,000 tries: %,d allowed (limit 10,000,000)%n", name, allowed.get());
}
public static void main(String[] args) throws InterruptedException {
hammer("no lock:", new UnsafeBucket()); hammer("synchronized:", new SafeBucket());
hammer("atomic CAS:", new AtomicBucket()); } }
Real output (the "no lock" number changes every run; we saw from 10,060,175 to 16,831,201):
no lock: 20,000,000 tries: 10,060,175 allowed (limit 10,000,000)
synchronized: 20,000,000 tries: 10,000,000 allowed (limit 10,000,000)
atomic CAS: 20,000,000 tries: 10,000,000 allowed (limit 10,000,000)
9. The class diagram
RateLimiter (interface: boolean tryAcquire()) Strategy
├─ FixedWindow one counter per window cheap, boundary burst
├─ SlidingLog a deque of timestamps exact, O(limit) memory
├─ SlidingCounter curr + prev × overlap 2 numbers, an estimate
├─ TokenBucket tokens refill at a rate allows short bursts
└─ LeakyBucket a queue drained at a rate smooth output
RateLimiterRegistry: rules API → Supplier<RateLimiter>; limiters "user API" → its own
Clock (interface): SystemClock in production, FakeClock in tests
Thread-safe: synchronized tryAcquire, or AtomicLong + compareAndSet
10. Choosing an algorithm
| Algorithm | Memory per key | Accuracy | Bursts | Good for |
|---|---|---|---|---|
| Fixed window counter | 2 numbers | Up to 2× at edges | Yes, at edges | Simple daily quotas |
| Sliding window log | One timestamp per request | Exact | No | Low limits that must be exact (OTP: 3 a minute) |
| Sliding window counter | 3 numbers | Close estimate | Smoothed | High-volume APIs |
| Token bucket | 2 numbers | Exact average | Yes, up to capacity | Most APIs: allow short bursts |
| Leaky bucket (queue) | Up to capacity requests | Exact output rate | No: smooth | Protecting a slow downstream service |
11. Interview follow-ups
| Follow-up | Answer |
|---|---|
| Many servers, one limit | Each server only sees its own requests; keep counters in one shared store all servers use, and update them atomically |
| What does the client see? | 429 Too Many Requests and a Retry-After header (mini project computes it) |
| Millions of idle users | Their limiters stay in memory: evict idle ones, e.g. with an LRU cache (episode 65) or a TTL |
| Bursts allowed or not? | Bursts OK → token bucket; smooth flow → leaky bucket |
| Change limits without a deploy | Read rules from configuration and rebuild limiters |
| 10 a second AND 1,000 a day | Several limiters per key; the request passes only if all allow (AllOf in the mini project) |
| Fail open or fail closed? | If the limiter's store is down: allow everything (fail open, keeps the service up) or refuse everything (fail closed, protects it); choose per API |
12. Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
System.currentTimeMillis() inside |
Tests must wait a real minute | Time can't be controlled | Inject a Clock |
| Fixed window only | 10 allowed in 1 second (limit 5 a minute) |
Windows reset together | A sliding window or token bucket |
| Sliding log for huge limits | a billion timestamps | One entry per request | Sliding counter |
long tokens with a fractional refill |
error: incompatible types: possible lossy conversion from double to long |
Tokens need fractions | double tokens |
| Integer division in the refill | tokens after 3 seconds: 0 (a request every 500 ms; 500 / 1000 = 0) |
Each small gap rounds to 0 | Use double, or keep the remainder |
long millis() without public in the class |
error: millis() in FakeClock cannot implement millis() in Clock ... attempting to assign weaker access privileges; was public |
Interface methods are public | public long millis() |
| One counter for all users | A bot uses up Asha's limit | No per-user key | Registry: user + API |
if (tokens > 0) tokens-- with no lock |
more than 10,000,000 allowed | Check-then-act race | synchronized or CAS |
The integer-division bug, run for real:
public class Main { public static void main(String[] a) {
long tokens = 0, last = 0; // integer refill: 1 token per 1000 ms
for (long now = 500; now <= 3000; now += 500) { // a request every 500 ms
tokens += (now - last) / 1000; last = now; // 500 / 1000 = 0 in integer maths
}
System.out.println("tokens after 3 seconds: " + tokens);
} }
tokens after 3 seconds: 0
Mini project: a small rate-limiting library
Thread-safe limiters that return a Decision with the Retry-After time, a registry with per-user, per-API rules, two limits combined with AllOf, a SystemClock for production and a FakeClock for tests.
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Supplier;
// Mini project: a small rate-limiting library. Every limiter is thread-safe, testable with a FakeClock,
// and answers with a Decision that says how long to wait (the Retry-After value) when it refuses.
interface Clock { long millis(); }
class SystemClock implements Clock { public long millis() { return System.currentTimeMillis(); } }
class FakeClock implements Clock {
private long now;
public synchronized long millis() { return now; }
synchronized void advance(long ms) { now += ms; }
}
record Decision(boolean allowed, long retryAfterMs) {
static Decision allow() { return new Decision(true, 0); }
static Decision deny(long waitMs) { return new Decision(false, Math.max(1, waitMs)); }
}
interface RateLimiter { Decision tryAcquire(); }
class FixedWindow implements RateLimiter {
private final int limit; private final long win; private final Clock clock;
private long window = -1; private int count;
FixedWindow(int limit, long win, Clock clock) { this.limit = limit; this.win = win; this.clock = clock; }
public synchronized Decision tryAcquire() {
long now = clock.millis(), w = now / win;
if (w != window) { window = w; count = 0; }
if (count < limit) { count++; return Decision.allow(); }
return Decision.deny((w + 1) * win - now); // wait until the next window starts
}
}
class SlidingLog implements RateLimiter {
private final int limit; private final long win; private final Clock clock;
private final Deque<Long> times = new ArrayDeque<>();
SlidingLog(int limit, long win, Clock clock) { this.limit = limit; this.win = win; this.clock = clock; }
public synchronized Decision tryAcquire() {
long now = clock.millis();
while (!times.isEmpty() && times.peekFirst() <= now - win) times.pollFirst();
if (times.size() < limit) { times.addLast(now); return Decision.allow(); }
return Decision.deny(times.peekFirst() + win - now); // wait until the oldest one leaves
}
}
class SlidingCounter implements RateLimiter {
private final int limit; private final long win; private final Clock clock;
private long window = 0; private int curr, prev;
SlidingCounter(int limit, long win, Clock clock) { this.limit = limit; this.win = win; this.clock = clock; }
public synchronized Decision tryAcquire() {
long now = clock.millis(), w = now / win;
if (w != window) { prev = (w == window + 1) ? curr : 0; curr = 0; window = w; }
double overlap = 1.0 - (double) (now % win) / win;
if (prev * overlap + curr < limit) { curr++; return Decision.allow(); }
return Decision.deny(win / 10); // an estimate: try again a bit later
}
}
class TokenBucket implements RateLimiter {
private final double capacity, perMs; private final Clock clock;
private double tokens; private long last;
TokenBucket(double capacity, double perSecond, Clock clock) {
this.capacity = tokens = capacity; this.perMs = perSecond / 1000.0; this.clock = clock; last = clock.millis(); }
public synchronized Decision tryAcquire() {
long now = clock.millis();
tokens = Math.min(capacity, tokens + (now - last) * perMs); last = now;
if (tokens >= 1) { tokens -= 1; return Decision.allow(); }
return Decision.deny((long) Math.ceil((1 - tokens) / perMs)); // until one whole token is back
}
}
class AllOf implements RateLimiter { // several limits at once: all must pass
private final List<RateLimiter> parts;
AllOf(RateLimiter... parts) { this.parts = List.of(parts); }
public synchronized Decision tryAcquire() {
// simple version: a refusal by a later limiter still used up the earlier ones' quota
long wait = 0;
for (RateLimiter p : parts) { Decision d = p.tryAcquire(); if (!d.allowed()) wait = Math.max(wait, d.retryAfterMs()); }
return wait == 0 ? Decision.allow() : Decision.deny(wait);
}
}
class RateLimiterRegistry {
private final Map<String, Supplier<RateLimiter>> rules = new ConcurrentHashMap<>();
private final Map<String, RateLimiter> limiters = new ConcurrentHashMap<>();
void rule(String api, Supplier<RateLimiter> make) { rules.put(api, make); }
Decision check(String user, String api) {
Supplier<RateLimiter> make = rules.get(api);
if (make == null) return Decision.allow(); // no rule: not limited
return limiters.computeIfAbsent(user + " " + api, k -> make.get()).tryAcquire();
}
int size() { return limiters.size(); }
}
public class Main {
static String http(Decision d) { // what an HTTP API would answer
return d.allowed() ? "200 OK" : "429 Too Many Requests, Retry-After: " + (long) Math.ceil(d.retryAfterMs() / 1000.0) + " s";
}
public static void main(String[] args) {
FakeClock clock = new FakeClock();
RateLimiterRegistry api = new RateLimiterRegistry();
api.rule("/otp", () -> new SlidingLog(3, 60_000, clock));
api.rule("/search", () -> new AllOf(new TokenBucket(5, 1, clock), new FixedWindow(100, 86_400_000, clock)));
for (int i = 1; i <= 4; i++) System.out.println("asha /otp try " + i + ": " + http(api.check("asha", "/otp")));
clock.advance(20_000);
System.out.println("20 s later, asha /otp: " + http(api.check("asha", "/otp")));
System.out.println("ravi /otp: " + http(api.check("ravi", "/otp")));
int ok = 0; Decision last = null;
for (int i = 0; i < 7; i++) { last = api.check("asha", "/search"); if (last.allowed()) ok++; }
System.out.println("asha /search burst of 7: " + ok + " allowed, then " + http(last));
clock.advance(2_000);
System.out.println("2 s later, asha /search: " + http(api.check("asha", "/search")));
System.out.println("limiters in memory: " + api.size());
System.out.println("with the real clock: " + http(new TokenBucket(1, 1, new SystemClock()).tryAcquire()));
}
}
Real output:
asha /otp try 1: 200 OK
asha /otp try 2: 200 OK
asha /otp try 3: 200 OK
asha /otp try 4: 429 Too Many Requests, Retry-After: 60 s
20 s later, asha /otp: 429 Too Many Requests, Retry-After: 40 s
ravi /otp: 200 OK
asha /search burst of 7: 5 allowed, then 429 Too Many Requests, Retry-After: 1 s
2 s later, asha /search: 200 OK
limiters in memory: 3
with the real clock: 200 OK
Asha's 4th OTP try is refused with Retry-After: 60 s; 20 s later she must wait 40 s more; Ravi is not affected. The /search burst of 7: 5 allowed by the token bucket, and 2 s later a token is back.
Practice
1. Add a SystemClock that uses the real time.
Answer
class SystemClock implements Clock { public long millis() { return System.currentTimeMillis(); } }. See the mini project: with the real clock: 200 OK.
2. Return the wait time (Retry-After) when a request is refused.
Answer
Return a Decision(allowed, retryAfterMs). Fixed window: until the next window starts, (w + 1) * win - now. Sliding log: until the oldest time leaves, oldest + win - now. Token bucket: until one whole token is back, (1 - tokens) / perMs. See the mini project.
3. Make SlidingCounter thread-safe.
Answer
Mark tryAcquire synchronized: it reads and writes window, curr and prev together, so they must change as one step. See the mini project.
4. Combine two limits: 10 a second and 100 a day.
Answer
new AllOf(new TokenBucket(10, 10, clock), new FixedWindow(100, 86_400_000, clock)): ask every part; refuse if any refuses, with the longest wait. Note the simple version still uses up the earlier parts' quota when a later one refuses; a stricter version checks all first, then commits.
5. Why is the leaky bucket called "smooth" and the token bucket "bursty"? Use the run in section 6.
Answer
The burst of 8 at 0 s: the token bucket served 5 immediately; the leaky bucket queued 5 and served them one per second at 1, 2, 3, 4 and 5 s.
Quick quiz
Token bucket: capacity 5, 1 new token per second, starts full. 7 requests at 0 s, 3 at 2 s. How many are allowed in total? (a) 5 (b) 7 (c) 8 (d) 10
Answer
(b) 7. 5 at 0 s (2 refused); by 2 s, 2 tokens have dripped back, so 2 of the 3 pass. Checked by running our TokenBucket:
7
Interview questions
- Name the classic rate-limiting algorithms and one trade-off of each. Fixed window (cheap, boundary burst), sliding log (exact, memory), sliding counter (cheap, estimate), token bucket (bursts allowed), leaky bucket (smooth, queues).
- What is the boundary burst? Up to 2 × limit requests around a fixed-window edge: 10 in 1 second with "5 a minute".
- Token bucket vs leaky bucket? Token bucket limits the average and allows bursts up to the capacity; leaky bucket forces a constant output rate.
- How do you test a limiter that depends on time? Inject a
Clock; tests use a fake clock and move time by hand. - How do you support different limits per user and per API? A key of
user + API, a rule per API, and one limiter object per key, created on first use. - How do you add a new algorithm? A new class implementing
RateLimiter; nothing else changes (Strategy, Open-Closed). - Is
if (tokens > 0) tokens--thread-safe? No: check-then-act and read-modify-write. Usesynchronizedor anAtomicLongwithcompareAndSet. - What HTTP response does a refused request get?
429 Too Many Requests, optionally withRetry-After. - How do you rate-limit across many servers? Shared counters in one store with atomic updates; or give each server a share of the limit.
- How much memory does each algorithm need per user? Fixed/counter/token: a few numbers; sliding log: one timestamp per request in the window; leaky bucket: up to its queue capacity.
Glossary
| Term | Meaning, with an example |
|---|---|
| Request | One call from a client to a server: Asha asking for an OTP |
| API | A door into a server that programs call: /login, /search |
| Rate | Requests per unit of time: 5 a minute |
| Rate limiting | Refusing requests above an allowed rate |
| Rate limiter | The object that decides: tryAcquire() → true/false |
| tryAcquire | Ask for permission for one request; false means refused |
| HTTP 429 Too Many Requests | The web status code for a rate-limited request |
| Retry-After | Optional header saying how long to wait: Retry-After: 60 |
| OTP | One-time password: a short code sent by SMS; limited to stop guessing |
| Clock | An interface giving the current time: long millis() |
| Clock injection for tests | Passing the clock in, so tests can use a fake one |
| FakeClock | A test clock set by hand: clock.set(10, 0, 59) |
| Dependency injection | Giving an object what it needs from outside, through its constructor |
| Window | A block of time: the minute 10:00 to 10:01 |
| Fixed window counter | Count per fixed window, reset at each boundary |
| Boundary burst | Up to 2 × limit around a window edge: 10 in 1 second |
| Sliding window | Always the last N seconds counted back from now |
| Sliding window log | Keep every allowed request's time; exact |
| Deque | A double-ended queue: add at the back, remove from the front |
| Sliding window counter | prev × overlap + curr; two numbers, an estimate |
| Overlap | The part of the last window still inside the sliding window: 0.75 |
| Token bucket | A bucket of tokens refilled at a rate; each request spends one |
| Token | Permission for one request |
| Capacity | The most tokens (or queued requests) a bucket holds: 5 |
| Refill rate | How fast tokens come back: 1 a second |
| Lazy refill | Compute the refill when a request arrives, no timer thread |
| Leaky bucket | A queue served at a fixed rate; full means refuse |
| Burst | Many requests in a very short time |
| Per-user and per-API limits | A separate limiter for each user and API pair: "asha /login" |
| RateLimiter interface | interface RateLimiter { boolean tryAcquire(); } |
| Strategy per algorithm | Each algorithm is a class behind the same interface, swappable |
| Registry | A map that creates and keeps one limiter per key |
| Supplier | A function with no input that makes a value: () -> new FixedWindow(...) |
| computeIfAbsent | Get the value for a key, creating it once if missing |
| Thread | One path of work; servers run many at once |
| Race condition | Threads interleave and the result is wrong: over 10,000,000 allowed |
| Check-then-act | Check a condition, then act on it; unsafe if another thread acts in between |
| Thread-safe counters | Counters that stay correct with many threads: synchronized or atomics |
| synchronized | Only one thread at a time runs the method |
| AtomicLong | A long with atomic operations like compareAndSet |
| Compare-and-swap (CAS) | "Set to new only if still old"; retry if it changed |
| Lock-free | Correct under threads without locks, using CAS |
| Fail open / fail closed | When the limiter is broken: allow everything / refuse everything |
Summary
- Rate limiting refuses requests above a rate; on the web the answer is 429 with an optional Retry-After.
- Clock injection made every algorithm testable in milliseconds with a FakeClock.
- The fixed window counter is cheap but let 10 through in 1 second at the boundary.
- The sliding window log is exact but stores every timestamp; the sliding window counter keeps 2 numbers and estimates.
- The token bucket allows bursts up to its capacity; the leaky bucket gives a smooth, constant output.
- A RateLimiter interface (Strategy) and a registry gave every user and API its own limiter.
synchronizedor an AtomicLong compare-and-swap loop kept the limit exact under many threads.