Design a Rate Limiter (LLD)
A rate limiter answers one question, over and over, very quickly: may this caller do this thing right now? The system-design version of the problem is about where the limiter lives (gateway, sidecar, Redis cluster) and how many servers agree on a count. That's covered in Design a Rate Limiter and in Rate Limiting. This page is the low-level design version: the classes inside one process.
At class level the interesting problems are different. You need the algorithms right, down to the boundary arithmetic. You need to swap one algorithm for another without touching the code that calls it. You need to manage one limiter per user without leaking memory. You have to be correct when 16 threads hit the same key at once. And you need to test all of it without ever calling sleep. The last point is the one that separates candidates. A limiter is entirely about time, and a design that reads the system clock directly is a design you can't test.
1. Clarifying questions and requirements
| Question | Why it matters | Answer we'll assume |
|---|---|---|
| What's being limited: requests, bytes, operations with different costs? | Unit of a "permit" | One request = one permit (weighted is an extension) |
| Limit per what? User, API key, IP, endpoint? | Need a per-key registry | Per key, any key type |
| Are bursts allowed? | Token bucket allows them, sliding log doesn't | Configurable by choosing the algorithm |
| Can different users have different limits? | Factory per key | Yes, tiers (free vs premium) |
| On rejection, does the caller need to know when to retry? | Retry-After header | Yes, return a retry hint |
| Reject, or wait until allowed? | Server-side vs client-side throttling | Reject. Waiting is an extension |
| One process or many servers? | Distributed state is HLD | One process |
| How precise must it be? | Fixed window vs sliding, memory per key | Pick per use case and explain |
| How many distinct keys? | Memory bound on the registry | Possibly millions, so it has to be bounded (extension) |
Functional requirements
tryAcquire()on a limiter returns a decision: allowed or not, permits remaining, and a retry-after hint when denied.- Four interchangeable algorithms: token bucket, fixed window, sliding window log, sliding window counter.
- A keyed limiter creates one limiter per key on first use, with the limit chosen by a rule (so premium users can get more).
- Time comes from an injected clock.
Non-functional requirements
- O(1) per decision for token bucket, fixed window and sliding counter. O(limit) memory per key for sliding log, and say so.
- Thread-safe. With a frozen clock and limit N, exactly N concurrent requests succeed, never N+1.
- Deterministic tests. No sleeps, no flaky timing.
- Never throws on the hot path for a valid key.
2. Entities
| Entity | Responsibility |
|---|---|
Clock | Monotonic milliseconds. System implementation in production, ManualClock in tests |
Decision | Immutable result: allowed, remaining, retryAfterMillis |
RateLimiter | Strategy interface: tryAcquire() returns a Decision |
TokenBucket | Refills one token every interval, holds at most capacity |
FixedWindow | Counts requests in aligned windows. Resets at each boundary |
SlidingWindowLog | Keeps the timestamp of every accepted request in the last window |
SlidingWindowCounter | Weighted blend of the previous and current window counts |
KeyedRateLimiter | Maps key → limiter, creating limiters with a factory on first use |
The design has two layers on purpose. A RateLimiter limits one stream of requests and knows nothing about users. KeyedRateLimiter knows about keys and nothing about algorithms. Each layer can be tested alone, and a new algorithm never touches the registry.
3. Class diagram
classDiagram
class Clock {
<<interface>>
+nowMillis() long
}
class ManualClock {
+advance(millis)
}
class Decision {
+allowed: boolean
+remaining: int
+retryAfterMillis: long
}
class RateLimiter {
<<interface>>
+tryAcquire() Decision
}
class TokenBucket {
-capacity: int
-millisPerToken: long
-tokens: int
-lastRefill: long
+refund(permits)
}
class FixedWindow {
-limit: int
-windowMillis: long
-windowStart: long
-count: int
}
class SlidingWindowLog {
-limit: int
-windowMillis: long
-log: Deque of long
}
class SlidingWindowCounter {
-limit: int
-windowMillis: long
-windowIndex: long
-previous: int
-current: int
}
class KeyedRateLimiter {
-limiters: ConcurrentMap of K to RateLimiter
-factory: Function of K to RateLimiter
+tryAcquire(key) Decision
+trackedKeys() int
}
Clock <|.. ManualClock
RateLimiter <|.. TokenBucket
RateLimiter <|.. FixedWindow
RateLimiter <|.. SlidingWindowLog
RateLimiter <|.. SlidingWindowCounter
RateLimiter ..> Decision : returns
TokenBucket --> Clock
FixedWindow --> Clock
SlidingWindowLog --> Clock
SlidingWindowCounter --> Clock
KeyedRateLimiter o-- "*" RateLimiter
4. Key flows
A request through an API handler
sequenceDiagram
participant C as Client
participant H as API handler
participant K as KeyedRateLimiter
participant F as factory
participant L as TokenBucket for user
C->>H: GET /search, api key free-alice
H->>K: tryAcquire("free-alice")
alt first request from this key
K->>F: create limiter for "free-alice"
F-->>K: TokenBucket capacity 10
end
K->>L: tryAcquire()
L->>L: refill from elapsed time, take one token
L-->>K: Decision allowed, remaining 9
K-->>H: allowed
H-->>C: 200 OK, X-RateLimit-Remaining 9
A rejected request
sequenceDiagram
participant C as Client
participant H as API handler
participant L as TokenBucket for user
participant T as Clock
C->>H: GET /search
H->>L: tryAcquire()
L->>T: nowMillis()
T-->>L: 5030
L->>L: refill, 0 tokens, next token due at 5100
L-->>H: Decision denied, retryAfter 70 ms
H-->>C: 429 Too Many Requests, Retry-After 1
Retry-After is in whole seconds in HTTP, so the handler rounds the hint up. Sending a retry hint is a courtesy that pays for itself: well-behaved clients stop hammering, and the limiter does less work.
Lifecycle of a key in the registry
stateDiagram-v2
[*] --> Active: first request creates a limiter
Active --> Active: requests within the limit or denied
Active --> Idle: no requests for a while
Idle --> Active: new request
Idle --> [*]: evicted by idle sweep or size bound
The core listing never leaves Active. Without eviction, every key ever seen stays in memory. Extension C adds the Idle → evicted transition.
5. The algorithms, as Strategies
Each algorithm implements the same one-method interface. That's the Strategy pattern, and here it's justified by the requirements. Different endpoints genuinely want different trade-offs, and the choice is a configuration decision, not a code change.
Token bucket
A bucket holds up to capacity tokens and gains one token every millisPerToken. Each request takes a token. An empty bucket means denial.
- Bursts: a quiet user accumulates up to
capacitytokens and can spend them at once. That's usually what you want for humans and SDKs that batch. - Long-run rate: exactly one request per
millisPerToken. - State: two numbers. O(1) time and memory.
- No background thread. Refill is computed lazily from elapsed time on each call. Never use a timer that adds tokens. With a million keys that's a million timers, and the timer thread becomes the bottleneck.
The listings keep tokens as an integer and advance lastRefill by whole intervals only (lastRefill += added * millisPerToken). The remainder of a partial interval is carried forward, never lost. A floating-point bucket (tokens += elapsed * ratePerMilli) is the common alternative and is fine in production, but it makes exact tests awkward: after enough small refills, 0.1 + 0.1 + ... lands on 0.9999999 and a request that should pass is denied. Integer state makes every test assertion exact. The cost is that the rate must be expressed as a whole number of milliseconds per token, which caps one key at 1,000 per second. Switch the clock to nanoseconds if you need more.
Fixed window
Count requests in aligned windows ([0, 1000), [1000, 2000), ...) and reset the count at each boundary. It's the simplest algorithm and the cheapest one. It has one famous flaw: a client can send limit requests at 999 ms and another limit at 1000 ms, so 2 × limit requests land within two milliseconds. The test suite demonstrates exactly that.
Sliding window log
Keep the timestamp of every accepted request in a deque. On each call, drop timestamps older than the window. Allow if fewer than limit remain.
- Exact: never more than
limitin any window of length W, at any alignment. - Memory: O(limit) per key. A limit of 10,000 per hour means storing up to 10,000 longs per user. That's the price of exactness.
- Retry hint is exact: the oldest timestamp plus W.
Sliding window counter
A compromise between the two windows. Keep counts for the current and previous fixed windows, and estimate the sliding count as:
where elapsed is the time since the current window started. The assumption is that requests in the previous window were evenly spread. It's O(1) memory like fixed window and smooths the boundary burst like the log. Cloudflare wrote publicly about using this approach and finding it very accurate on their real traffic.
The listings compare in integer arithmetic by multiplying both sides by W: allow if previous × (W − elapsed) + (current + 1) × W ≤ limit × W. There's no floating point, so there are no surprises at the boundary.
Choosing
| Algorithm | Burst behaviour | Accuracy | Memory per key | Good for |
|---|---|---|---|---|
| Token bucket | Allows up to capacity | Exact long-run rate | O(1) | Public APIs, user-facing traffic |
| Fixed window | Up to 2× at boundaries | Coarse | O(1) | Quotas where coarse is fine ("1,000 per day") |
| Sliding log | None | Exact | O(limit) | Low limits that must be strict (login attempts, OTP sends) |
| Sliding counter | Smoothed | Approximate | O(1) | High-volume per-key limits |
Leaky bucket is the fifth classic. It's a queue drained at a fixed rate, which shapes traffic (smooths output) rather than just policing it. In "reject or allow" form it behaves like a token bucket with capacity 1 plus a queue. Mention it, but there's no need to build it.
Other patterns, and what was rejected
Factory function for per-key limiters. KeyedRateLimiter takes a Function<K, RateLimiter>. That one parameter handles tiers (key -> isPremium(key) ? bucket(100) : bucket(10)), per-endpoint limits and per-test fakes. It's the lightweight form of the Factory Method idea: the registry decides when to create, and the caller decides what. A full RateLimiterFactory class hierarchy would add nothing.
Injected clock. Every limiter takes a Clock. Production uses a monotonic source (System.nanoTime, time.monotonic_ns, performance.now), not wall-clock time, because wall-clock time can jump backwards under NTP correction and either freeze a window or hand out a free burst. Tests use ManualClock, which only moves when told to. This is the seam that makes the whole design testable.
Rejected: enum Algorithm plus a switch in one RateLimiter class. Each algorithm needs different state (a deque, two counters, a token count). One class would carry all of it, mostly unused, and grow a branch in every method.
Rejected: a Singleton global limiter. It's tempting ("there's one limiter for the app") until two endpoints need different limits, or a test needs a fresh one. Construct it at startup and inject it.
Rejected: boolean tryAcquire(). It works, but it throws away information callers need: how many requests remain (for X-RateLimit-Remaining) and when to retry (for Retry-After). Returning a small immutable Decision costs one allocation and makes the API honest.
6. Complete implementation
Each listing contains the four strategies, the keyed limiter and a main that checks: token bucket burst, refill and cap; the fixed-window boundary burst; the sliding log's exact retry hint; the sliding counter's weighted estimate; tiered keys; and concurrent access with a frozen clock, where exactly limit requests must win.
// file: RateLimiterDemo.java
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.function.Function;
import java.util.function.Supplier;
/** Monotonic milliseconds. Never wall-clock time: it can jump backwards. */
interface Clock {
long nowMillis();
Clock SYSTEM = () -> System.nanoTime() / 1_000_000;
}
final class ManualClock implements Clock {
private final AtomicLong now = new AtomicLong();
public long nowMillis() { return now.get(); }
void advance(long millis) { now.addAndGet(millis); }
}
record Decision(boolean allowed, int remaining, long retryAfterMillis) {
static Decision allow(int remaining) { return new Decision(true, remaining, 0); }
static Decision deny(long retryAfterMillis) { return new Decision(false, 0, Math.max(1, retryAfterMillis)); }
}
/** Strategy: one stream of requests, one algorithm. */
interface RateLimiter {
Decision tryAcquire();
}
final class TokenBucket implements RateLimiter {
private final int capacity;
private final long millisPerToken;
private final Clock clock;
private int tokens;
private long lastRefill;
TokenBucket(int capacity, long millisPerToken, Clock clock) {
if (capacity < 1 || millisPerToken < 1) throw new IllegalArgumentException("capacity and interval must be >= 1");
this.capacity = capacity;
this.millisPerToken = millisPerToken;
this.clock = clock;
this.tokens = capacity; // start full: a new user may burst
this.lastRefill = clock.nowMillis();
}
public synchronized Decision tryAcquire() {
long now = refill();
if (tokens > 0) {
tokens--;
return Decision.allow(tokens);
}
return Decision.deny(lastRefill + millisPerToken - now);
}
/** Give permits back, e.g. when a later check in a chain rejected the request. */
synchronized void refund(int permits) {
refill();
tokens = Math.min(capacity, tokens + permits);
}
synchronized int available() { refill(); return tokens; }
private long refill() {
long now = clock.nowMillis();
long added = (now - lastRefill) / millisPerToken;
if (added > 0) {
tokens = (int) Math.min(capacity, tokens + added);
lastRefill += added * millisPerToken; // keep the partial interval
if (tokens == capacity) lastRefill = now; // a full bucket doesn't bank time
}
return now;
}
}
final class FixedWindow implements RateLimiter {
private final int limit;
private final long windowMillis;
private final Clock clock;
private long windowStart = Long.MIN_VALUE;
private int count;
FixedWindow(int limit, long windowMillis, Clock clock) {
if (limit < 1 || windowMillis < 1) throw new IllegalArgumentException("limit and window must be >= 1");
this.limit = limit;
this.windowMillis = windowMillis;
this.clock = clock;
}
public synchronized Decision tryAcquire() {
long now = clock.nowMillis();
long start = now - Math.floorMod(now, windowMillis);
if (start != windowStart) {
windowStart = start;
count = 0;
}
if (count < limit) {
count++;
return Decision.allow(limit - count);
}
return Decision.deny(windowStart + windowMillis - now);
}
}
final class SlidingWindowLog implements RateLimiter {
private final int limit;
private final long windowMillis;
private final Clock clock;
private final ArrayDeque<Long> log = new ArrayDeque<>();
SlidingWindowLog(int limit, long windowMillis, Clock clock) {
if (limit < 1 || windowMillis < 1) throw new IllegalArgumentException("limit and window must be >= 1");
this.limit = limit;
this.windowMillis = windowMillis;
this.clock = clock;
}
public synchronized Decision tryAcquire() {
long now = clock.nowMillis();
while (!log.isEmpty() && log.peekFirst() + windowMillis <= now) log.pollFirst();
if (log.size() < limit) {
log.addLast(now);
return Decision.allow(limit - log.size());
}
return Decision.deny(log.peekFirst() + windowMillis - now);
}
}
final class SlidingWindowCounter implements RateLimiter {
private final int limit;
private final long windowMillis;
private final Clock clock;
private long windowIndex = Long.MIN_VALUE;
private long previous, current;
SlidingWindowCounter(int limit, long windowMillis, Clock clock) {
if (limit < 1 || windowMillis < 1) throw new IllegalArgumentException("limit and window must be >= 1");
this.limit = limit;
this.windowMillis = windowMillis;
this.clock = clock;
}
public synchronized Decision tryAcquire() {
long now = clock.nowMillis();
long index = Math.floorDiv(now, windowMillis);
if (index != windowIndex) {
previous = index == windowIndex + 1 ? current : 0;
current = 0;
windowIndex = index;
}
long w = windowMillis;
long elapsed = now - index * w;
long weightedPrevious = previous * (w - elapsed); // scaled by w, so no floating point
if (weightedPrevious + (current + 1) * w <= limit * w) {
current++;
return Decision.allow((int) ((limit * w - weightedPrevious - current * w) / w));
}
if (current + 1 <= limit && previous > 0) {
// Wait until the previous window's weight has decayed enough.
long t = w - elapsed - ((limit - current - 1) * w) / previous;
return Decision.deny(t);
}
return Decision.deny(w - elapsed); // a lower bound: try again next window
}
}
/** One limiter per key, created on first use by a caller-supplied rule. */
final class KeyedRateLimiter<K> {
private final ConcurrentHashMap<K, RateLimiter> limiters = new ConcurrentHashMap<>();
private final Function<K, RateLimiter> factory;
KeyedRateLimiter(Function<K, RateLimiter> factory) { this.factory = factory; }
Decision tryAcquire(K key) {
// computeIfAbsent runs the factory at most once per key, even under contention.
return limiters.computeIfAbsent(key, factory).tryAcquire();
}
int trackedKeys() { return limiters.size(); }
}
class RateLimiterDemo {
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
public static void main(String[] args) throws Exception {
ManualClock clock = new ManualClock();
// Token bucket: burst of 3, then one token per 100 ms, capped at capacity.
TokenBucket bucket = new TokenBucket(3, 100, clock);
for (int i = 0; i < 3; i++) check(bucket.tryAcquire().allowed(), "burst " + i);
Decision denied = bucket.tryAcquire();
check(!denied.allowed() && denied.retryAfterMillis() == 100, "retry hint " + denied);
clock.advance(60);
check(bucket.tryAcquire().retryAfterMillis() == 40, "partial interval is remembered");
clock.advance(40);
check(bucket.tryAcquire().allowed(), "one token after 100 ms");
clock.advance(10_000);
check(bucket.available() == 3, "refill is capped at capacity");
// Fixed window lets 2x the limit through around a boundary. The log does not.
ManualClock c2 = new ManualClock();
FixedWindow fixed = new FixedWindow(5, 1000, c2);
SlidingWindowLog slog = new SlidingWindowLog(5, 1000, c2);
c2.advance(999);
for (int i = 0; i < 5; i++) {
check(fixed.tryAcquire().allowed(), "fixed first half");
check(slog.tryAcquire().allowed(), "log first half");
}
c2.advance(1);
int fixedExtra = 0;
for (int i = 0; i < 5; i++) if (fixed.tryAcquire().allowed()) fixedExtra++;
check(fixedExtra == 5, "fixed window boundary burst");
Decision logDenied = slog.tryAcquire();
check(!logDenied.allowed() && logDenied.retryAfterMillis() == 999, "log exact retry " + logDenied);
// Sliding counter: 10 in window 0, then halfway through window 1 the estimate is 5.
ManualClock c3 = new ManualClock();
SlidingWindowCounter counter = new SlidingWindowCounter(10, 1000, c3);
c3.advance(500);
for (int i = 0; i < 10; i++) check(counter.tryAcquire().allowed(), "window 0");
c3.advance(1000); // t = 1500, elapsed 500 into window 1
int allowed = 0;
Decision last = null;
for (int i = 0; i < 10; i++) {
last = counter.tryAcquire();
if (last.allowed()) allowed++;
}
check(allowed == 5, "10 x 0.5 + current must stay <= 10, got " + allowed);
check(last.retryAfterMillis() == 100, "counter retry hint " + last);
c3.advance(100);
check(counter.tryAcquire().allowed(), "previous window weight decayed");
// Keyed limiter with tiers.
ManualClock c4 = new ManualClock();
KeyedRateLimiter<String> keyed = new KeyedRateLimiter<>(key ->
key.startsWith("premium:") ? new TokenBucket(5, 1000, c4) : new TokenBucket(2, 1000, c4));
int free = 0, premium = 0;
for (int i = 0; i < 10; i++) {
if (keyed.tryAcquire("free:alice").allowed()) free++;
if (keyed.tryAcquire("premium:bob").allowed()) premium++;
}
check(free == 2 && premium == 5, "tiers " + free + "/" + premium);
check(keyed.trackedKeys() == 2, "two keys tracked");
ManualClock frozen = new ManualClock();
exactlyLimitWins(() -> new TokenBucket(100, 1000, frozen));
exactlyLimitWins(() -> new FixedWindow(100, 1000, frozen));
exactlyLimitWins(() -> new SlidingWindowLog(100, 1000, frozen));
exactlyLimitWins(() -> new SlidingWindowCounter(100, 1000, frozen));
keyedUnderContention(frozen);
System.out.println("RateLimiterDemo: all checks passed");
}
/** 16 threads, 800 attempts, frozen clock: exactly 100 may succeed. */
static void exactlyLimitWins(Supplier<RateLimiter> make) throws Exception {
RateLimiter limiter = make.get();
AtomicInteger wins = new AtomicInteger();
ExecutorService pool = Executors.newFixedThreadPool(16);
CountDownLatch start = new CountDownLatch(1);
List<Future<Object>> fs = new ArrayList<>();
for (int t = 0; t < 16; t++) {
fs.add(pool.submit(() -> {
start.await();
for (int i = 0; i < 50; i++) if (limiter.tryAcquire().allowed()) wins.incrementAndGet();
return null;
}));
}
start.countDown();
for (Future<Object> f : fs) f.get();
pool.shutdown();
check(wins.get() == 100, limiter.getClass().getSimpleName() + " allowed " + wins.get());
}
static void keyedUnderContention(Clock frozen) throws Exception {
AtomicInteger created = new AtomicInteger();
KeyedRateLimiter<Integer> keyed = new KeyedRateLimiter<>(k -> {
created.incrementAndGet();
return new SlidingWindowLog(20, 1000, frozen);
});
ConcurrentHashMap<Integer, AtomicInteger> wins = new ConcurrentHashMap<>();
ExecutorService pool = Executors.newFixedThreadPool(8);
List<Future<Object>> fs = new ArrayList<>();
for (int t = 0; t < 8; t++) {
fs.add(pool.submit(() -> {
for (int round = 0; round < 10; round++) {
for (int key = 0; key < 50; key++) {
if (keyed.tryAcquire(key).allowed()) {
wins.computeIfAbsent(key, k -> new AtomicInteger()).incrementAndGet();
}
}
}
return null;
}));
}
for (Future<Object> f : fs) f.get();
pool.shutdown();
check(created.get() == 50, "factory ran " + created.get() + " times for 50 keys");
for (int key = 0; key < 50; key++) check(wins.get(key).get() == 20, "key " + key);
}
}
# file: ratelimit.py
"""Rate limiting strategies with an injectable clock and per-key registry."""
from __future__ import annotations
import threading
import time
from abc import ABC, abstractmethod
from collections import deque
from dataclasses import dataclass
from typing import Callable, Deque, Dict, Generic, Hashable, List, TypeVar
Clock = Callable[[], int] # monotonic milliseconds
K = TypeVar("K", bound=Hashable)
def system_clock() -> int:
return time.monotonic_ns() // 1_000_000
class ManualClock:
def __init__(self) -> None:
self._now = 0
def __call__(self) -> int:
return self._now
def advance(self, millis: int) -> None:
self._now += millis
@dataclass(frozen=True)
class Decision:
allowed: bool
remaining: int
retry_after_ms: int
@staticmethod
def allow(remaining: int) -> "Decision":
return Decision(True, remaining, 0)
@staticmethod
def deny(retry_after_ms: int) -> "Decision":
return Decision(False, 0, max(1, retry_after_ms))
class RateLimiter(ABC):
@abstractmethod
def try_acquire(self) -> Decision: ...
def _validate(a: int, b: int) -> None:
if a < 1 or b < 1:
raise ValueError("limits and intervals must be >= 1")
class TokenBucket(RateLimiter):
def __init__(self, capacity: int, ms_per_token: int, clock: Clock = system_clock) -> None:
_validate(capacity, ms_per_token)
self._capacity, self._interval, self._clock = capacity, ms_per_token, clock
self._tokens = capacity
self._last = clock()
self._lock = threading.Lock()
def _refill(self) -> int:
now = self._clock()
added = (now - self._last) // self._interval
if added > 0:
self._tokens = min(self._capacity, self._tokens + added)
self._last += added * self._interval # keep the partial interval
if self._tokens == self._capacity:
self._last = now # a full bucket doesn't bank time
return now
def try_acquire(self) -> Decision:
with self._lock:
now = self._refill()
if self._tokens > 0:
self._tokens -= 1
return Decision.allow(self._tokens)
return Decision.deny(self._last + self._interval - now)
def refund(self, permits: int = 1) -> None:
with self._lock:
self._refill()
self._tokens = min(self._capacity, self._tokens + permits)
def available(self) -> int:
with self._lock:
self._refill()
return self._tokens
class FixedWindow(RateLimiter):
def __init__(self, limit: int, window_ms: int, clock: Clock = system_clock) -> None:
_validate(limit, window_ms)
self._limit, self._window, self._clock = limit, window_ms, clock
self._start = None
self._count = 0
self._lock = threading.Lock()
def try_acquire(self) -> Decision:
with self._lock:
now = self._clock()
start = now - now % self._window
if start != self._start:
self._start, self._count = start, 0
if self._count < self._limit:
self._count += 1
return Decision.allow(self._limit - self._count)
return Decision.deny(start + self._window - now)
class SlidingWindowLog(RateLimiter):
def __init__(self, limit: int, window_ms: int, clock: Clock = system_clock) -> None:
_validate(limit, window_ms)
self._limit, self._window, self._clock = limit, window_ms, clock
self._log: Deque[int] = deque()
self._lock = threading.Lock()
def try_acquire(self) -> Decision:
with self._lock:
now = self._clock()
while self._log and self._log[0] + self._window <= now:
self._log.popleft()
if len(self._log) < self._limit:
self._log.append(now)
return Decision.allow(self._limit - len(self._log))
return Decision.deny(self._log[0] + self._window - now)
class SlidingWindowCounter(RateLimiter):
def __init__(self, limit: int, window_ms: int, clock: Clock = system_clock) -> None:
_validate(limit, window_ms)
self._limit, self._window, self._clock = limit, window_ms, clock
self._index = None
self._previous = self._current = 0
self._lock = threading.Lock()
def try_acquire(self) -> Decision:
with self._lock:
now, w, limit = self._clock(), self._window, self._limit
index = now // w
if index != self._index:
adjacent = self._index is not None and index == self._index + 1
self._previous = self._current if adjacent else 0
self._current = 0
self._index = index
elapsed = now - index * w
weighted_prev = self._previous * (w - elapsed) # scaled by w, integers only
if weighted_prev + (self._current + 1) * w <= limit * w:
self._current += 1
return Decision.allow((limit * w - weighted_prev - self._current * w) // w)
if self._current + 1 <= limit and self._previous > 0:
return Decision.deny(w - elapsed - ((limit - self._current - 1) * w) // self._previous)
return Decision.deny(w - elapsed)
class KeyedRateLimiter(Generic[K]):
def __init__(self, factory: Callable[[K], RateLimiter]) -> None:
self._factory = factory
self._limiters: Dict[K, RateLimiter] = {}
self._lock = threading.Lock()
def _limiter_for(self, key: K) -> RateLimiter:
limiter = self._limiters.get(key) # fast path, no lock
if limiter is None:
with self._lock:
limiter = self._limiters.get(key) # re-check: another thread may have won
if limiter is None:
limiter = self._factory(key)
self._limiters[key] = limiter
return limiter
def try_acquire(self, key: K) -> Decision:
return self._limiter_for(key).try_acquire()
def tracked_keys(self) -> int:
return len(self._limiters)
def _exactly_limit_wins(limiter: RateLimiter) -> None:
wins: List[int] = []
barrier = threading.Barrier(16)
def worker() -> None:
barrier.wait()
mine = sum(1 for _ in range(50) if limiter.try_acquire().allowed)
wins.append(mine) # list.append is atomic in CPython
threads = [threading.Thread(target=worker) for _ in range(16)]
for t in threads:
t.start()
for t in threads:
t.join()
assert sum(wins) == 100, f"{type(limiter).__name__} allowed {sum(wins)}"
def _keyed_under_contention(clock: Clock) -> None:
created: List[int] = []
keyed: KeyedRateLimiter[int] = KeyedRateLimiter(
lambda k: created.append(k) or SlidingWindowLog(20, 1000, clock))
wins: Dict[int, int] = {}
wins_lock = threading.Lock()
def worker() -> None:
for _ in range(10):
for key in range(50):
if keyed.try_acquire(key).allowed:
with wins_lock:
wins[key] = wins.get(key, 0) + 1
threads = [threading.Thread(target=worker) for _ in range(8)]
for t in threads:
t.start()
for t in threads:
t.join()
assert len(created) == 50, f"factory ran {len(created)} times"
assert all(wins[k] == 20 for k in range(50)), wins
def main() -> None:
clock = ManualClock()
bucket = TokenBucket(3, 100, clock)
assert all(bucket.try_acquire().allowed for _ in range(3))
d = bucket.try_acquire()
assert not d.allowed and d.retry_after_ms == 100, d
clock.advance(60)
assert bucket.try_acquire().retry_after_ms == 40
clock.advance(40)
assert bucket.try_acquire().allowed
clock.advance(10_000)
assert bucket.available() == 3
c2 = ManualClock()
fixed, slog = FixedWindow(5, 1000, c2), SlidingWindowLog(5, 1000, c2)
c2.advance(999)
for _ in range(5):
assert fixed.try_acquire().allowed and slog.try_acquire().allowed
c2.advance(1)
assert sum(fixed.try_acquire().allowed for _ in range(5)) == 5, "fixed window boundary burst"
d = slog.try_acquire()
assert not d.allowed and d.retry_after_ms == 999, d
c3 = ManualClock()
counter = SlidingWindowCounter(10, 1000, c3)
c3.advance(500)
assert all(counter.try_acquire().allowed for _ in range(10))
c3.advance(1000)
results = [counter.try_acquire() for _ in range(10)]
assert sum(r.allowed for r in results) == 5
assert results[-1].retry_after_ms == 100, results[-1]
c3.advance(100)
assert counter.try_acquire().allowed
c4 = ManualClock()
keyed: KeyedRateLimiter[str] = KeyedRateLimiter(
lambda k: TokenBucket(5 if k.startswith("premium:") else 2, 1000, c4))
free = sum(keyed.try_acquire("free:alice").allowed for _ in range(10))
premium = sum(keyed.try_acquire("premium:bob").allowed for _ in range(10))
assert (free, premium) == (2, 5) and keyed.tracked_keys() == 2
frozen = ManualClock()
for make in (lambda: TokenBucket(100, 1000, frozen), lambda: FixedWindow(100, 1000, frozen),
lambda: SlidingWindowLog(100, 1000, frozen), lambda: SlidingWindowCounter(100, 1000, frozen)):
_exactly_limit_wins(make())
_keyed_under_contention(frozen)
print("ratelimit.py: all checks passed")
if __name__ == "__main__":
main()
// file: ratelimit.ts
// Rate limiting strategies with an injectable clock and a per-key registry.
// Run directly: npx tsx ratelimit.ts
import { performance } from "node:perf_hooks";
export type Clock = () => number; // monotonic milliseconds
export const systemClock: Clock = () => Math.floor(performance.now());
export class ManualClock {
private now = 0;
readonly read: Clock = () => this.now;
advance(ms: number): void { this.now += ms; }
}
export interface Decision { readonly allowed: boolean; readonly remaining: number; readonly retryAfterMs: number; }
const allow = (remaining: number): Decision => ({ allowed: true, remaining, retryAfterMs: 0 });
const deny = (retryAfterMs: number): Decision => ({ allowed: false, remaining: 0, retryAfterMs: Math.max(1, retryAfterMs) });
export interface RateLimiter { tryAcquire(): Decision; }
function validate(a: number, b: number): void {
if (!Number.isInteger(a) || !Number.isInteger(b) || a < 1 || b < 1) throw new RangeError("limits and intervals must be integers >= 1");
}
export class TokenBucket implements RateLimiter {
private tokens: number;
private last: number;
constructor(private readonly capacity: number, private readonly msPerToken: number, private readonly clock: Clock = systemClock) {
validate(capacity, msPerToken);
this.tokens = capacity;
this.last = clock();
}
private refill(): number {
const now = this.clock();
const added = Math.floor((now - this.last) / this.msPerToken);
if (added > 0) {
this.tokens = Math.min(this.capacity, this.tokens + added);
this.last += added * this.msPerToken; // keep the partial interval
if (this.tokens === this.capacity) this.last = now; // a full bucket doesn't bank time
}
return now;
}
tryAcquire(): Decision {
const now = this.refill();
if (this.tokens > 0) { this.tokens--; return allow(this.tokens); }
return deny(this.last + this.msPerToken - now);
}
refund(permits = 1): void { this.refill(); this.tokens = Math.min(this.capacity, this.tokens + permits); }
available(): number { this.refill(); return this.tokens; }
}
export class FixedWindow implements RateLimiter {
private start = Number.NEGATIVE_INFINITY;
private count = 0;
constructor(private readonly limit: number, private readonly windowMs: number, private readonly clock: Clock = systemClock) {
validate(limit, windowMs);
}
tryAcquire(): Decision {
const now = this.clock();
const start = now - (now % this.windowMs);
if (start !== this.start) { this.start = start; this.count = 0; }
if (this.count < this.limit) { this.count++; return allow(this.limit - this.count); }
return deny(start + this.windowMs - now);
}
}
export class SlidingWindowLog implements RateLimiter {
// A plain array with a moving head index: O(1) amortized "popleft" without a deque library.
private log: number[] = [];
private head = 0;
constructor(private readonly limit: number, private readonly windowMs: number, private readonly clock: Clock = systemClock) {
validate(limit, windowMs);
}
tryAcquire(): Decision {
const now = this.clock();
while (this.head < this.log.length && this.log[this.head] + this.windowMs <= now) this.head++;
if (this.head > 1024 && this.head * 2 > this.log.length) { this.log = this.log.slice(this.head); this.head = 0; }
const size = this.log.length - this.head;
if (size < this.limit) { this.log.push(now); return allow(this.limit - size - 1); }
return deny(this.log[this.head] + this.windowMs - now);
}
}
export class SlidingWindowCounter implements RateLimiter {
private index = Number.NaN;
private previous = 0;
private current = 0;
constructor(private readonly limit: number, private readonly windowMs: number, private readonly clock: Clock = systemClock) {
validate(limit, windowMs);
}
tryAcquire(): Decision {
const now = this.clock();
const w = this.windowMs;
const index = Math.floor(now / w);
if (index !== this.index) {
this.previous = index === this.index + 1 ? this.current : 0;
this.current = 0;
this.index = index;
}
const elapsed = now - index * w;
const weightedPrev = this.previous * (w - elapsed); // scaled by w, integers only
if (weightedPrev + (this.current + 1) * w <= this.limit * w) {
this.current++;
return allow(Math.floor((this.limit * w - weightedPrev - this.current * w) / w));
}
if (this.current + 1 <= this.limit && this.previous > 0) {
return deny(w - elapsed - Math.floor(((this.limit - this.current - 1) * w) / this.previous));
}
return deny(w - elapsed);
}
}
export class KeyedRateLimiter<K> {
protected readonly limiters = new Map<K, RateLimiter>();
constructor(protected readonly factory: (key: K) => RateLimiter) {}
tryAcquire(key: K): Decision {
let limiter = this.limiters.get(key);
if (!limiter) { limiter = this.factory(key); this.limiters.set(key, limiter); }
return limiter.tryAcquire();
}
get trackedKeys(): number { return this.limiters.size; }
}
function assert(cond: unknown, msg: string): asserts cond { if (!cond) throw new Error(msg); }
const count = (n: number, f: () => boolean): number => Array.from({ length: n }, f).filter(Boolean).length;
async function main(): Promise<void> {
const clock = new ManualClock();
const bucket = new TokenBucket(3, 100, clock.read);
assert(count(3, () => bucket.tryAcquire().allowed) === 3, "burst");
let d = bucket.tryAcquire();
assert(!d.allowed && d.retryAfterMs === 100, `retry hint ${JSON.stringify(d)}`);
clock.advance(60);
assert(bucket.tryAcquire().retryAfterMs === 40, "partial interval");
clock.advance(40);
assert(bucket.tryAcquire().allowed, "refilled");
clock.advance(10_000);
assert(bucket.available() === 3, "capped");
const c2 = new ManualClock();
const fixed = new FixedWindow(5, 1000, c2.read);
const slog = new SlidingWindowLog(5, 1000, c2.read);
c2.advance(999);
for (let i = 0; i < 5; i++) assert(fixed.tryAcquire().allowed && slog.tryAcquire().allowed, "first half");
c2.advance(1);
assert(count(5, () => fixed.tryAcquire().allowed) === 5, "fixed window boundary burst");
d = slog.tryAcquire();
assert(!d.allowed && d.retryAfterMs === 999, `log retry ${JSON.stringify(d)}`);
const c3 = new ManualClock();
const counter = new SlidingWindowCounter(10, 1000, c3.read);
c3.advance(500);
assert(count(10, () => counter.tryAcquire().allowed) === 10, "window 0");
c3.advance(1000);
const results = Array.from({ length: 10 }, () => counter.tryAcquire());
assert(results.filter((r) => r.allowed).length === 5, "weighted estimate");
assert(results[9].retryAfterMs === 100, "counter retry");
c3.advance(100);
assert(counter.tryAcquire().allowed, "decayed");
const c4 = new ManualClock();
const keyed = new KeyedRateLimiter<string>((k) => new TokenBucket(k.startsWith("premium:") ? 5 : 2, 1000, c4.read));
assert(count(10, () => keyed.tryAcquire("free:alice").allowed) === 2, "free tier");
assert(count(10, () => keyed.tryAcquire("premium:bob").allowed) === 5, "premium tier");
// Node runs each tryAcquire to completion, so interleaved async callers can't overshoot.
const frozen = new ManualClock();
for (const limiter of [new TokenBucket(100, 1000, frozen.read), new FixedWindow(100, 1000, frozen.read),
new SlidingWindowLog(100, 1000, frozen.read), new SlidingWindowCounter(100, 1000, frozen.read)]) {
let wins = 0;
await Promise.all(Array.from({ length: 16 }, async () => {
for (let i = 0; i < 50; i++) {
await Promise.resolve();
if (limiter.tryAcquire().allowed) wins++;
}
}));
assert(wins === 100, `${limiter.constructor.name} allowed ${wins}`);
}
console.log("ratelimit.ts: all checks passed");
}
if (require.main === module) {
main().catch((e) => { console.error(e); process.exit(1); });
}
Walking through the code
The token bucket starts full. A new user gets their burst immediately. Starting empty is also defensible (it stops a burst right after a restart, when every bucket is recreated) but it surprises users on their first request. Pick one and say why.
A full bucket doesn't bank time. When the bucket refills to capacity, lastRefill jumps to now. Without that line, a user idle for an hour would have lastRefill an hour in the past, and the arithmetic stays correct only because of the min. The line keeps the retry hint accurate: the next token is one full interval after the bucket last became non-full.
refill is lazy. It only runs inside tryAcquire. A million idle keys cost nothing per second.
Sliding log eviction uses <=. A request at time t stops counting at exactly t + W. The 999 retry hint in the demo checks this: the five requests at 999 expire at 1999, and the clock is at 1000.
The sliding counter's retry hint is solved, not guessed. It rearranges the inequality to find the earliest time the weighted previous count has decayed enough. When the current window alone is full, the only safe statement is "not before the next window", which is a lower bound. The hint says so in a comment.
KeyedRateLimiter.computeIfAbsent matters. A naive get, then if null put lets two threads both create a limiter for a new key. Each thread then spends from its own fresh bucket, and that key gets double its limit on the first burst. The Java version relies on computeIfAbsent's per-key atomicity. The Python version uses double-checked locking (a lock-free fast path for existing keys, and a re-check under the lock for new ones). The keyed contention test counts factory calls to prove it runs exactly once per key.
7. Concurrency
What's shared
| State | Shared by | Protection |
|---|---|---|
| One limiter's counters, deque or tokens | All threads using that key | The limiter's own monitor (synchronized) / threading.Lock |
| The key → limiter map | All threads | ConcurrentHashMap / lock-guarded creation |
| The clock | Everyone | Read-only (AtomicLong in the manual clock) |
The race this prevents
Every algorithm is a read-modify-write. "Read the count, compare to the limit, increment" is three steps. Without a lock, two threads read count = 99 with a limit of 100, both see room, both increment, and the limit is exceeded. Remove the synchronized keyword and the 16-thread test can let more than 100 through. How many varies from run to run, which is exactly what makes these bugs hard to catch in production. The exactlyLimitWins test uses a frozen clock, so no refill or window change can explain extra wins. Any count other than exactly 100 is a race.
Lock granularity comes for free
Each key has its own limiter, and each limiter has its own lock. Threads serving different users never contend. That's lock striping without any striping code, and it's why there's no global lock anywhere in the design. The only shared structure is the map, and ConcurrentHashMap reads don't lock.
Lock-free token bucket
For a single, very hot key (a global limiter in front of a database, for example) the monitor can become a bottleneck. A token bucket's state fits in one 64-bit word (tokens in the high bits, last-refill time in the low bits), so it can be updated with a compare-and-set loop on an AtomicLong: read, compute the new state, compareAndSet, retry on failure. It's a good thing to describe. Build it only if the interviewer asks, and mention that CAS loops under heavy contention can spin and do worse than a lock. Measure before choosing.
Python and TypeScript
The GIL doesn't make self._count += 1 atomic across the check before it, so each Python limiter carries a lock and the threaded test proves exactly 100 wins. In Node, each synchronous tryAcquire runs to completion before any other callback, so no lock is needed. The TS test interleaves 16 async workers with await between calls and still sees exactly 100. The Node risk appears only if a check and the update are separated by an await, for example when a limiter reads state from Redis. Then you need the atomicity on the server side (a Lua script or INCR with expiry), and that's where the distributed design takes over.
8. Extensions: "the interviewer adds X"
Extension A: "Our service calls a partner API limited to 50 requests per second. Wait instead of failing."
This is client-side throttling. Instead of rejecting, the caller blocks until a permit is available or a deadline passes. The Decision.retryAfterMillis hint makes this efficient: the waiter sleeps exactly as long as needed instead of polling. The sleep is injected too, so the test drives a manual clock and finishes instantly.
// file: BlockingLimiterDemo.java
/** Waits for a permit up to a deadline, sleeping by the limiter's own retry hint. */
final class BlockingRateLimiter {
interface Sleeper { void sleep(long millis) throws InterruptedException; }
private final RateLimiter limiter;
private final Clock clock;
private final Sleeper sleeper;
BlockingRateLimiter(RateLimiter limiter, Clock clock, Sleeper sleeper) {
this.limiter = limiter;
this.clock = clock;
this.sleeper = sleeper;
}
boolean acquire(long timeoutMillis) throws InterruptedException {
long deadline = clock.nowMillis() + timeoutMillis;
while (true) {
Decision d = limiter.tryAcquire();
if (d.allowed()) return true;
long left = deadline - clock.nowMillis();
if (left <= 0 || d.retryAfterMillis() > left) return false; // fail fast: we'd miss the deadline anyway
sleeper.sleep(d.retryAfterMillis());
}
}
}
class BlockingLimiterDemo {
public static void main(String[] args) throws Exception {
ManualClock clock = new ManualClock();
java.util.List<Long> sleeps = new java.util.ArrayList<>();
BlockingRateLimiter.Sleeper fakeSleep = ms -> { sleeps.add(ms); clock.advance(ms); };
BlockingRateLimiter limiter = new BlockingRateLimiter(new TokenBucket(2, 20, clock), clock, fakeSleep);
for (int i = 0; i < 5; i++) {
if (!limiter.acquire(1_000)) throw new AssertionError("should wait, not fail");
}
// 2 from the burst, then three waits of one interval each.
if (!sleeps.equals(java.util.List.of(20L, 20L, 20L))) throw new AssertionError("sleeps " + sleeps);
if (clock.nowMillis() != 60) throw new AssertionError("clock " + clock.nowMillis());
if (limiter.acquire(5)) throw new AssertionError("a 5 ms deadline can't cover a 20 ms wait");
// And with real threads and the real clock: 5 callers, 1 token per 30 ms, all must get through.
BlockingRateLimiter real = new BlockingRateLimiter(new TokenBucket(1, 30, Clock.SYSTEM), Clock.SYSTEM, Thread::sleep);
java.util.concurrent.ExecutorService pool = java.util.concurrent.Executors.newFixedThreadPool(5);
java.util.List<java.util.concurrent.Future<Boolean>> fs = new java.util.ArrayList<>();
long start = System.nanoTime();
for (int i = 0; i < 5; i++) fs.add(pool.submit(() -> real.acquire(2_000)));
for (var f : fs) if (!f.get()) throw new AssertionError("real acquire timed out");
pool.shutdown();
long tookMs = (System.nanoTime() - start) / 1_000_000;
if (tookMs < 110) throw new AssertionError("5 permits at 30 ms each can't finish in " + tookMs + " ms");
System.out.println("BlockingLimiterDemo ok, sleeps=" + sleeps + ", real run took " + tookMs + " ms");
}
}
Two waiting threads can both wake at the same moment, and one of them loses the race for the token and loops again. That's correct, just not fair. If fairness matters, put waiters in a FIFO queue and reserve future permits for them, which is roughly what Guava's RateLimiter does: it hands each caller a time slot, then sleeps until that slot.
Extension B: "Each user gets 3 per second, but the whole backend can only take 4 per second"
Now one request must pass two limiters, a per-user one and a shared global one. The trap is ordering. If you take the user's token and then the global limiter rejects, the user has paid for a request that never ran. The fix is to refund on partial failure, which is easy for a token bucket (put the token back) and is one more reason token bucket is the default choice.
# file: ext_composite.py
"""All-or-nothing across several limiters: refund what was taken if a later one says no."""
from typing import List
from ratelimit import Decision, KeyedRateLimiter, ManualClock, TokenBucket
class CompositeLimiter:
def __init__(self, buckets: List[TokenBucket]) -> None:
self._buckets = buckets # cheapest and most specific first: user, then global
def try_acquire(self) -> Decision:
taken: List[TokenBucket] = []
for bucket in self._buckets:
d = bucket.try_acquire()
if not d.allowed:
for t in taken:
t.refund(1)
return d
taken.append(bucket)
return Decision.allow(min(b.available() for b in self._buckets))
if __name__ == "__main__":
clock = ManualClock()
global_bucket = TokenBucket(4, 250, clock)
users = KeyedRateLimiter(lambda user: TokenBucket(3, 333, clock))
def request(user: str) -> bool:
user_bucket = users._limiter_for(user)
assert isinstance(user_bucket, TokenBucket)
return CompositeLimiter([user_bucket, global_bucket]).try_acquire().allowed
assert [request("alice") for _ in range(4)] == [True, True, True, False] # alice's own limit
assert request("bob") is True # global now has 0 left
assert request("bob") is False # rejected by the global limit...
bob = users._limiter_for("bob")
assert isinstance(bob, TokenBucket) and bob.available() == 2 # ...and bob's token was refunded
clock.advance(250)
assert request("bob") is True # global refilled one token
print("ext_composite.py ok")
Between "take the user token" and "refund it", another request from the same user could see one fewer token than it should and be wrongly rejected. That's a brief false negative and never an overshoot, which is the safe direction for a limiter. If that window matters, lock the user's bucket across both checks. Never hold a lock on the global bucket across the user check, because that serializes every user through one lock.
Extension C: "A scraper rotates through a million IPs and the limiter map ate 2 GB"
The registry grows forever. Bound it. The simplest robust bound combines a maximum size with least-recently-used eviction and an idle timeout. Evicting a key resets its limit, so a key that gets evicted and comes back starts with a full bucket. That's fail-open for that key, and it's acceptable only if evicted keys are cold. That's exactly what LRU gives you. The LRU itself is the same trick as in Design an LRU / LFU Cache, using JavaScript's insertion-ordered Map.
// file: bounded-keyed.ts
import { Clock, KeyedRateLimiter, ManualClock, RateLimiter, TokenBucket } from "./ratelimit";
/** Keeps at most maxKeys limiters, dropping the least recently used, plus any idle past idleMs. */
export class BoundedKeyedRateLimiter<K> extends KeyedRateLimiter<K> {
private readonly lastSeen = new Map<K, number>();
constructor(factory: (key: K) => RateLimiter, private readonly maxKeys: number,
private readonly idleMs: number, private readonly clock: Clock) { super(factory); }
override tryAcquire(key: K) {
const limiter = this.limiters.get(key);
if (limiter) { this.limiters.delete(key); this.limiters.set(key, limiter); } // move to the young end
else if (this.limiters.size >= this.maxKeys) {
const oldest = this.limiters.keys().next().value as K;
this.limiters.delete(oldest);
this.lastSeen.delete(oldest);
}
this.lastSeen.set(key, this.clock());
return super.tryAcquire(key);
}
/** Call from a timer. Map order is LRU order, so stop at the first young key. */
sweepIdle(): number {
const cutoff = this.clock() - this.idleMs;
let removed = 0;
for (const key of this.limiters.keys()) {
if ((this.lastSeen.get(key) ?? 0) > cutoff) break;
this.limiters.delete(key);
this.lastSeen.delete(key);
removed++;
}
return removed;
}
}
const clock = new ManualClock();
const limiter = new BoundedKeyedRateLimiter<string>((k) => new TokenBucket(1, 60_000, clock.read), 3, 10_000, clock.read);
const tracked = (): number => limiter.trackedKeys; // a call, so TS doesn't narrow it
for (const ip of ["a", "b", "c"]) limiter.tryAcquire(ip);
if (limiter.tryAcquire("a").allowed) throw new Error("a is limited and still tracked");
limiter.tryAcquire("d"); // evicts b, the least recently used
if (tracked() !== 3) throw new Error("bounded");
if (!limiter.tryAcquire("b").allowed) throw new Error("b was evicted, so it starts fresh");
clock.advance(10_000);
limiter.tryAcquire("a");
if (limiter.sweepIdle() !== 2 || tracked() !== 1) throw new Error("idle sweep");
console.log("bounded-keyed.ts ok: tracked keys stay bounded");
At very large scale you'd stop keeping a limiter object per key. A count-min sketch can estimate per-key counts in fixed memory, at the cost of occasionally over-counting (rejecting a light user who collides with a heavy one). Say it as the next step and stop there.
9. Testing
The whole design is shaped by one testing need: time must be controllable. With a ManualClock, every test is exact, instant and deterministic. Tests that call sleep(1000) are slow, and they're flaky on a loaded CI machine where the sleep overshoots.
What to cover, per algorithm:
- Within the limit: the first
limitrequests pass andremainingcounts down. - At the limit: the next request is denied, with the correct retry hint.
- Recovery: after exactly the retry hint, a request passes. One millisecond before, it doesn't.
- Boundaries: behaviour at
t = W - 1,t = Wandt = W + 1. This is where off-by-one errors live. - Algorithm-specific properties: the fixed-window boundary burst (to document it), the sliding log's strictness, the counter's weighted estimate, and the bucket's cap.
- Keyed behaviour: keys are independent, tiers are applied, the factory runs once per key.
- Concurrency: frozen clock, many threads, exactly
limitwins. - Validation: zero or negative limits are rejected at construction.
A useful extra is a property-style test: for random request times, the sliding log never admits more than limit in any window of length W. Check it by brute force over the accepted timestamps.
// file: RateLimiterTests.java
import java.util.*;
class RateLimiterTests {
static int passed;
static void test(String name, Runnable body) { body.run(); passed++; System.out.println(" ok " + name); }
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
public static void main(String[] args) {
test("token bucket recovers exactly at the retry hint", () -> {
ManualClock clock = new ManualClock();
TokenBucket b = new TokenBucket(1, 50, clock);
b.tryAcquire();
long hint = b.tryAcquire().retryAfterMillis();
clock.advance(hint - 1);
check(!b.tryAcquire().allowed(), "one ms early");
clock.advance(1);
check(b.tryAcquire().allowed(), "on time");
});
test("remaining counts down", () -> {
SlidingWindowLog log = new SlidingWindowLog(3, 1000, new ManualClock());
check(log.tryAcquire().remaining() == 2 && log.tryAcquire().remaining() == 1
&& log.tryAcquire().remaining() == 0, "remaining");
});
test("sliding log never exceeds the limit in any window (random property)", () -> {
ManualClock clock = new ManualClock();
SlidingWindowLog log = new SlidingWindowLog(7, 1000, clock);
Random r = new Random(42);
List<Long> accepted = new ArrayList<>();
for (int i = 0; i < 5_000; i++) {
clock.advance(r.nextInt(60));
if (log.tryAcquire().allowed()) accepted.add(clock.nowMillis());
}
for (int i = 0; i + 7 < accepted.size(); i++) {
check(accepted.get(i + 7) - accepted.get(i) >= 1000, "8 requests inside one window at " + i);
}
});
test("keys are independent", () -> {
KeyedRateLimiter<String> k = new KeyedRateLimiter<>(x -> new FixedWindow(1, 1000, new ManualClock()));
check(k.tryAcquire("a").allowed() && k.tryAcquire("b").allowed(), "both first requests pass");
check(!k.tryAcquire("a").allowed(), "a is limited");
});
test("invalid configuration is rejected", () -> {
for (Runnable bad : List.<Runnable>of(
() -> new TokenBucket(0, 10, Clock.SYSTEM),
() -> new SlidingWindowCounter(5, 0, Clock.SYSTEM))) {
try { bad.run(); throw new AssertionError("accepted bad config"); }
catch (IllegalArgumentException expected) { }
}
});
System.out.println("RateLimiterTests: " + passed + " passed");
}
}
# file: test_ratelimit.py
import random
import unittest
from ratelimit import (FixedWindow, KeyedRateLimiter, ManualClock, SlidingWindowCounter,
SlidingWindowLog, TokenBucket)
class RateLimitTest(unittest.TestCase):
def test_fixed_window_boundaries(self):
clock = ManualClock()
fw = FixedWindow(2, 1000, clock)
clock.advance(998)
self.assertTrue(fw.try_acquire().allowed and fw.try_acquire().allowed)
clock.advance(1) # t = 999, same window
self.assertFalse(fw.try_acquire().allowed)
clock.advance(1) # t = 1000, new window
self.assertTrue(fw.try_acquire().allowed)
def test_counter_forgets_a_distant_window(self):
clock = ManualClock()
c = SlidingWindowCounter(5, 1000, clock)
for _ in range(5):
c.try_acquire()
clock.advance(2500) # skipped a whole window: previous must count as 0
self.assertEqual(sum(c.try_acquire().allowed for _ in range(10)), 5)
def test_sliding_log_property(self):
clock, rng = ManualClock(), random.Random(7)
log = SlidingWindowLog(7, 1000, clock)
accepted = []
for _ in range(5_000):
clock.advance(rng.randrange(60))
if log.try_acquire().allowed:
accepted.append(clock())
for i in range(len(accepted) - 7):
self.assertGreaterEqual(accepted[i + 7] - accepted[i], 1000)
def test_refund_is_capped(self):
b = TokenBucket(2, 1000, ManualClock())
b.refund(10)
self.assertEqual(b.available(), 2)
def test_factory_sees_the_key(self):
seen = []
k = KeyedRateLimiter(lambda key: seen.append(key) or TokenBucket(1, 1000, ManualClock()))
k.try_acquire("x")
k.try_acquire("x")
self.assertEqual(seen, ["x"])
def test_invalid_config(self):
with self.assertRaises(ValueError):
FixedWindow(0, 1000)
if __name__ == "__main__":
unittest.main(verbosity=2)
// file: ratelimit.test.ts
import { test } from "node:test";
import assert from "node:assert/strict";
import { FixedWindow, ManualClock, SlidingWindowCounter, SlidingWindowLog, TokenBucket } from "./ratelimit";
test("token bucket long-run rate equals one per interval", () => {
const clock = new ManualClock();
const b = new TokenBucket(5, 100, clock.read);
let allowed = 0;
for (let t = 0; t < 10_000; t += 10) { if (b.tryAcquire().allowed) allowed++; clock.advance(10); }
assert.equal(allowed, 5 + 10_000 / 100 - 1); // initial burst + one per 100 ms (last refill lands after the loop)
});
test("sliding log admits again exactly when the oldest expires", () => {
const clock = new ManualClock();
const log = new SlidingWindowLog(2, 1000, clock.read);
log.tryAcquire();
clock.advance(300);
log.tryAcquire();
const d = log.tryAcquire();
assert.equal(d.retryAfterMs, 700);
clock.advance(699);
assert.equal(log.tryAcquire().allowed, false);
clock.advance(1);
assert.equal(log.tryAcquire().allowed, true);
});
test("counter at the start of a window counts the whole previous window", () => {
const clock = new ManualClock();
const c = new SlidingWindowCounter(4, 1000, clock.read);
for (let i = 0; i < 4; i++) c.tryAcquire();
clock.advance(1000); // elapsed 0: previous weight is 1
assert.equal(c.tryAcquire().allowed, false);
});
test("invalid config throws", () => {
assert.throws(() => new FixedWindow(1.5, 1000), RangeError);
});
10. Common mistakes
- Reading the system clock directly. The design becomes untestable, and tests end up sleeping. Inject a clock from the start and say why.
- Using wall-clock time.
System.currentTimeMillis()andDate.now()can jump backwards. A backwards jump freezes a fixed window or a log, and a forwards jump hands out a burst. Use a monotonic source. - A timer thread that refills buckets. It's O(keys) work per tick and a thread to manage. Compute refill lazily from elapsed time.
- Check-then-act without a lock.
if (count < limit) count++from two threads letslimit + 1through. Test with a frozen clock to prove it. getthenputfor new keys. Two limiters for the same key on its first burst gives double the limit. UsecomputeIfAbsentor double-checked creation.- An unbounded key map. Every IP ever seen stays in memory. Bound it with LRU, an idle sweep, or both.
- Floating-point drift in the bucket. Tests that compare
tokens == 1.0fail intermittently. Use integer state, or compare with a tolerance and say so. - Fixed window presented as "sliding". Know and state the boundary-burst flaw. The interviewer will ask.
- Sliding log with a big limit. 100,000 per hour means 100,000 timestamps per key. Switch to the counter for large limits.
- Returning only a boolean. Callers then can't send
Retry-AfterorX-RateLimit-Remaining, and clients retry blindly. - One global lock for every key. Users then contend with each other for no reason. Per-limiter locks are free striping.
- Charging a request before every check passes. In layered limits (user plus global), refund on partial failure or the user pays for rejected work.
11. Interview follow-ups
"Which algorithm would you pick for a public REST API, and why?" Token bucket. It allows the short bursts real clients produce (a page load fires six requests at once), it enforces an exact long-run rate, and it's O(1) in time and memory. It's also trivially refundable, which matters for layered limits. Stripe has written publicly about using token buckets for its API rate limiting.
"And for login attempts?" A sliding window log with a small limit, say 5 per 15 minutes per account, plus a separate limiter per IP. Exactness matters more than memory at that size, and you don't want a boundary burst to give an attacker 10 guesses.
"How do you support requests that cost more than one permit?"
Add tryAcquire(int permits). The token bucket checks tokens >= permits. The sliding log stores (timestamp, permits) pairs and sums them, or appends permits copies for small costs. The counter adds permits instead of 1. Reject single requests whose cost exceeds the capacity outright, or they'd wait forever.
"What happens when the clock goes backwards?"
With a monotonic clock, it can't. If it did (a bad clock source), the token bucket computes a negative elapsed time. The added > 0 guard ignores it, so no tokens appear, which is safe. A fixed window would compute an earlier window and reset its count, which hands out a free burst. That's another reason to use a monotonic source.
"How would you make this work across ten API servers?"
Locally limiting at limit / 10 per server is the cheap approximation, and it's wrong when traffic is uneven across servers. The real answer moves state to a shared store: a Redis key per user with INCR and EXPIRE for fixed windows, a sorted set for the log, or a Lua script that performs the whole token-bucket update atomically. Then you deal with Redis latency on every request, failure modes (fail open or closed?), and hot keys. That's the system-design version.
"Should a rate limiter fail open or closed if it breaks?" For an in-process limiter, it doesn't really break, short of a bug. For a remote one, most APIs fail open. Letting traffic through during a Redis outage is usually better than an outage of your own. Limiters that protect something fragile, or that are a security control (OTP sends, password attempts), should fail closed. It's a per-limiter decision, so make it configurable.
"Where in the code would you put the limiter: controller, middleware, service?" Middleware or a filter in front of the handlers, so every route is covered by default and the business code doesn't know about it. The key extraction (API key, user ID, IP) belongs there too. Per-operation limits ("5 password resets per hour") belong in the service, because they're business rules.
"Isn't KeyedRateLimiter just a cache?"
Yes, structurally, a cache of limiter objects keyed by user, with the same need for bounded size and eviction. The difference is what eviction means. Evicting a cache entry costs a reload, while evicting a limiter forgets a user's usage. So only evict keys that are idle long enough that their limiter would have fully reset anyway. With a token bucket, that's after capacity × millisPerToken of idleness. Evicting then is perfectly safe.
Related
- Design a Rate Limiter and Rate Limiting: the distributed, high-level version.
- Strategy and Factory Method: interchangeable algorithms and per-key creation.
- Designing for Testability: the injected clock.
- Thread-Safe Class Design: check-then-act races and lock granularity.
- Design an LRU / LFU Cache: the bounded map in Extension C.
- Design a Logging Framework: the same fixed-window idea used to stop log floods.