Part 4 of 6 · 4 min read
The code
Four classes, one interface.
The token bucket refills by the time that has passed, and not with a timer thread. Each call works out how many tokens have arrived since the last call.
class TokenBucket implements RateLimiter {
private final long capacity; private final double perMs; private final Clock clock;
private double tokens; private long last;
TokenBucket(long capacity, double tokensPerSecond, Clock clock) {
if (capacity < 1 || tokensPerSecond <= 0) throw new IllegalArgumentException("bad settings");
this.capacity = capacity; this.perMs = tokensPerSecond / 1000.0; this.clock = clock;
tokens = capacity; last = clock.nowMillis();
}
public synchronized boolean tryAcquire() {
long now = clock.nowMillis();
tokens = Math.min(capacity, tokens + (now - last) * perMs); // refill, never above capacity
last = now;
if (tokens >= 1) { tokens -= 1; return true; }
return false;
}
}
The fixed window keeps one counter and the start of its window. A request in a new window resets the counter.
public synchronized boolean tryAcquire() {
long now = clock.nowMillis(), w = Math.floorDiv(now, windowMs) * windowMs;
if (w != windowStart) { windowStart = w; count = 0; }
if (count < limit) { count++; return true; }
return false;
}
The sliding log drops timestamps older than the window, then compares the size to the limit. Only accepted requests are logged, which keeps memory bounded by the limit.
public synchronized boolean tryAcquire() {
long now = clock.nowMillis();
while (!log.isEmpty() && log.peekFirst() <= now - windowMs) log.pollFirst();
if (log.size() < limit) { log.addLast(now); return true; }
return false;
}
The sliding counter holds the counts of the current and the previous window and applies the book's formula. It is built the same way: a synchronized method, an injected clock, and a window start taken with floorDiv.
Runs, with a fake clock (Y is allowed, n is refused):
| Setup | Calls | Result |
|---|---|---|
| Token bucket, size 4, refill 2 per second | 6 calls at time 0 | YYYYnn |
| Same bucket, after 1 second | 3 calls | YYn (two tokens had arrived) |
| Same bucket, after 10 more seconds | 6 calls | YYYYnn (the bucket cannot hold more than 4) |
| Fixed window, 5 per minute | 7 calls at 30 s, then 7 calls at 61 s | YYYYYnn, then YYYYYnn |
| Sliding log, 5 per minute | 7 at 30 s, 7 at 61 s, 7 at 90.001 s | YYYYYnn, then nnnnnnn, then YYYYYnn |
| Sliding counter, 7 per minute | 5 calls in the first minute, then calls 18 s into the next | YYY, then Ynnn |
The fixed window row shows the flaw: ten requests within 31 seconds all pass. The sliding log refuses all seven at 61 seconds, since the five accepted ones from 30 seconds are still inside the minute. It allows again only after the first timestamp ages out, at 90.001 seconds. The sliding counter row matches the book's example: the fourth call after the window change is still allowed at an estimate of 6.5, and the fifth is refused at 7.5.
A registry holds one limiter for each key, created when first needed:
class Limiters {
private final ConcurrentMap<String, RateLimiter> byKey = new ConcurrentHashMap<>();
private final Supplier<RateLimiter> factory;
Limiters(Supplier<RateLimiter> f) { factory = f; }
boolean allow(String key) { return byKey.computeIfAbsent(key, k -> factory.get()).tryAcquire(); }
}
computeIfAbsent is atomic, so two threads that see a new key at the same time still end up sharing one limiter (the check-then-act race of Level 5, module 3). With a limit of 2 per second, key "u1" gets true, true and false, and key "u2" gets true. The keys do not affect each other.
A thread test: eight threads each try 100 times against a bucket of 100 tokens with a refill of 1 per second. In total, between 100 and 101 calls succeed, depending on whether one token was refilled while the test ran. Never more. The synchronized method makes the refill and the take one step.
Check yourself:
1. Why does the token bucket need no timer thread?
2. Why does the sliding log log only accepted requests?
3. What does computeIfAbsent prevent?