Sliding Window Rate Limiter (Log, Counter, Token Bucket)

Three per-key limiters with one result shape, so you can swap them and compare:

const r = limiter.consume('api-key:123', cost = 1);
// { allowed, limit, remaining, retryAfterMs, resetMs }
res.set(toHeaders(r)); // RateLimit-Limit / -Remaining / -Reset, Retry-After on 429

The problem and where it shows up

A rate limiter caps how much work one principal can cause per unit of time. It protects shared capacity, enforces pricing tiers, and slows abuse such as credential stuffing and scraping. You'll find it in API gateways (Kong, AWS API Gateway usage plans), edge proxies (Envoy local_ratelimit and the global ratelimit service, NGINX limit_req), CDNs (Cloudflare Rate Limiting), and public APIs (GitHub's x-ratelimit-* headers, Stripe's per-account limits).

The naive fixed window ("reset the counter every minute") admits up to 2x the limit in a short burst that straddles a boundary. demo.js section 1 shows 20 requests admitted in 2 s against a 10/min limit. All three algorithms here avoid that.

The three algorithms

1. Sliding log (SlidingLogLimiter): exact

Store one timestamp per admitted unit and count the ones in (now - W, now].

• Invariant: in every interval of length W, admitted ≤ limit. A randomized test checks all windows.
• Retry-After is exact. For a request of cost c with n entries logged, the k = n + c - limit oldest entries must leave, and the k-th oldest leaves at log[k-1] + W.
• Cost: O(limit) memory per key, which gets expensive for "10 000 / hour" limits across millions of keys.

2. Sliding-window counter (SlidingWindowCounter): O(1) approximation

Keep only the counts for the current and previous fixed windows:

estimate = prev * (1 - elapsed / W) + curr        admit if estimate + cost <= limit

This assumes the previous window's hits were spread uniformly. Retry-After is solved in closed form for two cases. (A) Room opens later in this window as prev decays: f >= 1 - (L - curr - cost) / prev. (B) curr alone is too full, so wait into the next window, where prev := curr: g >= 1 - (L - cost) / curr. The result is rounded up to whole ms and nudged forward if floating-point error left it a hair short. A randomized test checks that it is never early and never late.

• Error: when traffic in the previous window was not uniform (bunched at its end), the counter under-estimates and over-admits. In the demo's Poisson workload it admits about 0.6% more overall, and its worst true 60 s window reaches 113 against a limit of 100. Cloudflare has reported very low error on real traffic. The trade is exactness for 3 numbers per key.

3. Token bucket (TokenBucketLimiter): burst plus sustained rate

Tokens refill continuously at refillRate / refillIntervalMs, up to capacity. A request spends cost tokens.

• Invariant: over any interval T, admitted ≤ capacity + rate * T (randomized test).
• Tokens are stored as integer units (tokens * refillIntervalMs) and each ms adds refillRate units, so integer clocks give exact arithmetic. A test runs 30 000 ms at 0.3 tok/ms and expects exactly 9000.
• Retry-After = ceil(missingUnits / refillRate) ms. A clock that moves backwards adds nothing.
• Semantics differ from a window: a bucket allows an immediate burst of capacity, then smooths to the rate.

Shared behaviour

• Per-key state lives in a Map. sweep() drops keys whose state carries no information (empty log, both counters zero, full bucket), so memory is bounded by the active keys.
• Denied requests don't consume quota. Some systems do count them, to penalize clients that ignore 429s.
• cost > limit can never succeed and returns retryAfterMs: Infinity (no Retry-After header).
• Injectable clock (now): tests and the demo never sleep.
• Validation: non-positive or non-integer limits, costs and windows, and empty keys, all throw.

Complexity

Failure modes and trade-offs

• Distributed enforcement: these are single-process. With N gateway replicas, each enforcing L gives an effective limit of NL. Options: a central store (Redis + Lua script for atomic check-and-increment), sticky routing by key, or splitting the budget per node (L/N, which is unfair when load is uneven).
• Race conditions in a central store: a non-atomic GET-then-SET lets concurrent requests all pass. Use INCR + EXPIRE or a Lua script. For the log, use a sorted set with ZREMRANGEBYSCORE + ZCARD + ZADD in MULTI/Lua.
• Clock skew across nodes shifts windows. Use the store's clock (TIME in Redis Lua), not each client's.
• Key choice: per-IP punishes NAT and CGNAT users. Per-user needs authentication before limiting. Hot keys in a shared store become a hotspot.
• Fail open vs fail closed when the limiter store is down. Most APIs fail open, so an outage of the limiter doesn't become an outage of the API. Login endpoints often fail closed.
• Memory: an attacker rotating keys creates unbounded state. Sweep idle keys, cap the tracked-key count, or use a probabilistic structure (a Count-Min sketch) for coarse limits.

• NGINX limit_req uses a leaky bucket per key in a shared-memory zone (rate=10r/s, burst=, nodelay). Requests within burst are queued and delayed to the rate unless nodelay is set. Anything beyond the burst is rejected (503 by default, configurable via limit_req_status).
• Envoy does token-bucket local rate limiting per listener or route (local_ratelimit). Global limits go through an external gRPC Rate Limit Service (Lyft's ratelimit, backed by Redis) that uses fixed windows keyed by descriptors.
• Cloudflare described the sliding-window counter in its 2017 blog post on rate limiting, choosing it for O(1) memory per key at edge scale.
• Stripe runs several limiters in Redis, including a request rate limiter (token bucket) and a concurrent-requests limiter, and adds load shedders that prioritize critical traffic.
• Redis patterns: INCR+EXPIRE (fixed window), sorted sets (sliding log), and GCRA (redis-cell module's CL.THROTTLE), which is a token bucket stored as a single "theoretical arrival time".
• Headers: Retry-After is defined in RFC 9110 (delay-seconds or HTTP-date). RateLimit-* come from the IETF httpapi RateLimit header fields draft. GitHub uses its own x-ratelimit-* names.

1. GCRA: implement a token bucket as a single tat (theoretical arrival time) per key and prove it makes the same decisions as TokenBucketLimiter on random traffic.
2. Redis-backed log: port SlidingLogLimiter to a Lua script over a sorted set. Explain why the ZREMRANGEBYSCORE/ZCARD/ZADD sequence must be atomic.
3. Multi-tier limits: enforce 10/s and* 1000/h on the same key. When the second tier denies, the first must not have been charged, so check both before committing either.
4. Ring-buffer log: replace the array plus splice with a fixed ring of limit slots, making trim O(expired).
5. Adversarial counter: build the input pattern that maximizes the counter's over-admission (bunch the previous window's hits at its end) and derive the worst-case bound.