No wall clock and no sleeps: time is a virtual clock you advance by hand, so each limiter is one concrete spec with exact allow/deny sequences and internal state. Pin the fixed window allowing exactly the limit then denying until the boundary reset, the up-to-2x-limit burst across two adjacent windows, the sliding-window log denying a request the fixed window would wrongly allow, the weighted sliding-counter estimate at a partial offset, a token bucket refilling fractionally and capping at capacity, a drained bucket re-allowing the exact tick one token has accrued, a computed retry-after, and per-key isolation so one client cannot starve another.
Over 23 lessons you build a small rate-limiting library: several limiter algorithms that each answer one question - should this request be allowed right now? The whole thing is driven by an injected virtual clock you control with Now() and Advance(d), so there is no real time and no sleeping. Every allow/deny decision and every token or counter value is a number you assert exactly, and the same limiter behaves identically in any language.
You begin with the Allow contract and a plain quota, then build the classic algorithms one at a time: a fixed-window counter (and the boundary-burst flaw where two adjacent windows admit up to twice the limit in a short span), a sliding-window log that keeps request timestamps and is exact but O(requests) in memory, the sliding-window-counter approximation that weights the previous window by how much it still overlaps, and a token bucket that refills fractionally with elapsed time and caps bursts at its capacity, plus a leaky-bucket variant that smooths instead of bursting. You then add a keyed limiter so one client cannot starve another, a computed retry-after hint, and idle-key cleanup. The capstone runs one scripted, timestamped request stream through the fixed-window, sliding-window-counter, and token-bucket limiters at once and asserts each one's exact allow/deny timeline and final state.
This is a teaching-grade, single-process, in-memory library: it limits by virtual-clock ticks against an injected clock, it is not thread-safe, and it does no distributed or cross-process coordination (no shared store, no clock synchronization). That is the honest core that production limiters - the ones behind Cloudflare, Stripe, and Envoy - extend with a shared datastore, atomic operations, and real time.
Every rate limiter is about time - how many requests in how long - so the first thing we build is time we fully control. A virtual clock starts at zero and only moves when you advance it, which makes every later allow/deny decision exact and reproducible.
Build a clock that starts at 0 and moves forward only when you advance it.
A rate limiter’s whole job is measuring requests against time, so if time is the
real wall clock every test becomes a race with sleeps and slop. We dodge that
entirely with a virtual clock: time is a plain integer count of ticks that
starts at 0 and moves only when you call Advance. Nothing happens in the
background. A tick has no fixed real-world duration - it is whatever unit a given
limiter treats as its window or refill rate.
Because the clock is injected and hand-advanced, every decision the limiters make
later is pinned to an exact moment you chose, so an allow or a deny is never
“probably” - it is a value you assert. Advance(0) is a no-op by design: advancing
by nothing must not move time. Build this tiny clock now; every limiter in the
project reads the current tick from it.
// time is a plain int64 count of "ticks" - no real wall clocktype Clock struct {now int64}func NewClock() *Clock { return &Clock{} }func (c *Clock) Now() int64 { return c.now }func (c *Clock) Advance(d int64) { c.now += d }
A genuinely working single-process rate-limiting library driven by an injected virtual clock - fixed-window, sliding-window-log, sliding-window-counter, token-bucket, and leaky-bucket limiters with exact reproducible decisions, plus per-key isolation, retry-after hints, idle-key purging, and graceful denial on zero or negative configs - but it is not thread-safe, reads time from an int64 tick counter rather than a real clock, and does no distributed or cross-process coordination.
Cloudflare's writeup of the sliding-window-counter algorithm this project builds - approximating a rolling window by weighting the previous fixed window by its overlap. The clearest real-world motivation for why the approximation is close enough and far cheaper than a log.
Stripe's engineering account of running token-bucket limiters in production - request-rate versus concurrency limiting, load shedding, and why bucketed rates behave well under bursty traffic.
The reference definition of the token-bucket meter: a bucket of capacity C refilling at rate r, each conforming packet removing a token. The exact model the token-bucket chapter implements with fractional accrual.
The companion traffic-shaping algorithm: a queue that drains at a constant rate, smoothing bursts rather than admitting them. Read alongside the token bucket to see the two classic shapers side by side.
A systems-design survey of the whole family - fixed window, sliding log, sliding counter, token and leaky bucket - with the tradeoffs, where each is deployed, and how distributed rate limiting adds a shared store and race conditions on top of the single-node core built here.
The standard that defines 429 Too Many Requests and the Retry-After response header - the wire contract a real limiter's allow/deny plus retry-after hint feeds into.