rate-proof

Measures what six rate-limiting algorithms actually let through once they are deployed: several nodes behind a load balancer, each with its own clock, sharing state in a store a round trip away, sometimes restarting. Then it checks its own simulator against a real Redis.

A limiter is usually tested on one machine: send 150 requests, see that 100 get through. In production its clock is whichever node took the request, its state is a network call away, and the store can come back empty. None of that shows up in a unit test, and each one changes how many requests reach the service behind it.

View on GitHub The Redis check

Plays the six stages below in order, about 55 seconds. Scroll or press Esc to stop.

Language: Go 1.22 or newer, standard library only
Tests: 33 passing with go test ./... and a Redis; 2 of them skip without one
Algorithms: Token bucket, leaky bucket, GCRA, fixed window, sliding log, sliding counter
Simulator: Discrete events in integer microseconds; the same flags print the same numbers
Store: Redis 7, through six Lua scripts and its own small RESP client
License: MIT

rateproof table 100 requests/s per key, 20s per run, seeds 1-10. Deployments: 4 nodes, 1 ms round trip to the store.

Real runs of rate-proof at 38d4084, output verbatim; rateproof is the binary from go build ./cmd/rateproof. The first three are simulations and print the same numbers every time. The last ran against Redis 7.4 in Docker on this machine, and its live half changes a little from run to run.

1Six algorithms, written for a store

Each limiter is a function of one key's stored state, the time it is told, and the limit, which is how it runs inside Redis. Every one is configured as 100 requests per second.

Times are integer microseconds, and the buckets keep their tokens scaled so a refill is never fractional. The Lua scripts can then do the same arithmetic exactly.
Each algorithm states its own promise, and every admit is checked against it at the true time it was decided.
"100 per second" means different things. Fixed window allows 200 in one second around a window edge, and the three buckets allow a full burst on top of the refill. Only the sliding log holds 100 in every second.

Most admitted in any one second, on one node with a true clock

The limit, 100 in a secondPeak, as a multiple of the limit

Peaks are the "ideal" column of rateproof table: the worst of ten seeds and all four attack patterns. The promises are from rateproof algos, and the stored state is the README's table, checked against limiter/limiter.go.

2Give every node its own clock

Requests land on one of four nodes at random. Each node tells the store the time by its own clock, and the clocks are spread evenly across the skew. The store is a round trip away, each leg jittering by 25%, and a script runs when it arrives, one at a time.

The token bucket stores last = now on every call. A node whose clock is behind moves last back, and the next node that is ahead is refilled for the same 50 ms again.
The leaky bucket does the same arithmetic mirrored, but keeps last = max(last, now). GCRA stores one timestamp that only moves forward.
At 50 ms of skew the token bucket refuses nothing: the whole flood, five times the limit, gets through. On the flood the other two admit 0.2% more than one node with a true clock would.

The same flood, three buckets, clocks 50 ms apart

The code lines are from limiter/limiter.go. The rows are the flood key of three real runs, rateproof run --algo NAME --skew 50ms, seed 1; "ideal" is the same algorithm on one node with a true clock and no latency, fed the same requests. The terminal is the end of the token bucket's run.

3Attack every deployment the same way

Every run sends the same four clients, each on its own key, and the arrivals depend only on the seed. So every algorithm and every deployment sees exactly the same requests.

A flood at five times the limit; boundary bursts of 100 just before a window edge and 100 just after; the flood switched on for 2 s and off for 3 s; and an honest client sending evenly at 90% of its limit.
Deployments: node clocks 50 ms apart, the store's own clock (Redis TIME), a store wiped once, and no store at all, each node enforcing a quarter of the limit and restarting now and then.
Over compares a deployment with the same algorithm on one node, so it separates what the deployment did from what the algorithm does by design.

Reading the store's clock instead brings every peak back to its one-node value. Splitting the limit across nodes fails both ways: 5 to 11% too much gets through, and an honest client is turned away up to 6.6% of the time.

Peak in any one second, and attack traffic over the ideal

Up to 1.25xUp to 2.05xAbove 2.05x

Every cell is from one real run of rateproof table: 100 requests a second per key, 20 s per run, seeds 1 to 10, 4 nodes, 1 ms round trip. Each cell is the worst seed and the worst attack pattern. The honest column is the share of the honest client turned away under local split; in every other column it was never turned away.

4Check the checker with planted bugs

A checker that never finds anything proves nothing. rateproof mutants runs where every promise must hold exactly: 4 nodes, a 1 ms round trip, clocks in agreement, nothing restarting.

All six correct algorithms, in store-backed and local deployments, must stay clean on every seed.
Six planted bugs must each break their promise. Four are one line away from a correct algorithm; two are deployment mistakes: a GET, a decision in the app and a SET, and local limiters each given the full limit.
CI runs it on 200 seeds of 12 s each, with all four traffic patterns.

12 correct deployments and 6 bugs, 200 seeds each

The verdicts, first seeds, counts and reasons are rateproof mutants at its default of 200 seeds, verbatim. It took about 8 s on this machine.

ProvenAbove this line everything is a model, deterministic by seed. Below it, the same algorithms run as Lua in a real Redis, and the model has to reproduce what Redis did, admit for admit.

5The same arithmetic, in Lua, in Redis

Each algorithm is also a Lua script in redisx/lua, sharing a prelude that reads Redis TIME. rateproof redis sends the same calls to the script and to the Go code the simulator runs, and compares every decision and every stored value.

The calls step across window edges, sit idle for seconds, and 15% come from a clock up to 60 ms behind.
Lua numbers are doubles, so stored values are written with %.0f to stay exact integers past 14 digits.
Six algorithms, 20,000 calls each: 120,000 decisions, none different.

Leaky bucket, in Go and in Lua, then every algorithm

limiter/limiter.go

redisx/lua/leaky-bucket.lua

Both sources are verbatim, without their comments. The counts are part 1 of the Redis run in the hero, against Redis 7.4.11 in Docker. The test suite runs the same comparison with 5,000 calls per algorithm.

6Live traffic, replayed through the simulator

Four goroutines, one connection each, play the simulator's own arrival schedule against Redis in real time, 6 s per case. For every request it records when the node sent it and when Redis ran it, by Redis's clock.

The simulator is then handed those timings and recomputes every decision with its own model of the store. --check fails unless the count matches within 0.5% and the peak within 0.02.
The last column gives the simulator only each step's mean delay. For atomic scripts that is close; for the non-atomic GET and SET it misses most of the race, because timers wake goroutines in clumps, and clumps race.
So the tables above, which model a 1 ms round trip, are a lower bound for the non-atomic race.

Nine live cases: Redis, the replay, and the mean-delay model

Same as RedisDifferent from Redis

Part 2 of the Redis run in the hero, verbatim. "Replay" is the simulator given every request's measured timing, "mean delay" the simulator given only each step's average. Peak is the most admitted in any one second over the limit; over is admits beyond one node with a true clock. Live timing varies: the README's run had the non-atomic case at +23.5% and admitted counts that matched exactly; this one was 747 against 748, inside the check's tolerance.

Measured, not assumed

What skew does as it grows, how the real-Redis check holds up across runs, and what all of it costs to run. One Linux machine, an i5-12400F that other jobs were also using.

Skew, swept from 0 to 200 ms

Most admitted in any one second, as a multiple of the limit, worst of 10 seeds, against the skew between node clocks in ms. 4 nodes, 1 ms round trip.

The token bucket passes 2.8x at 10 ms and reaches 5.79x at 50 ms, where it refuses nothing. The leaky bucket and GCRA draw the same line and never pass 2.08x. rateproof sweep --svg regenerates the README's chart byte for byte.

Redis, run after run

The live half uses real timing, so its numbers move. What must not move is that the simulator matches each run.

The README's run and three here. All passed --check, and the replay matched Redis exactly except once: ^*run 1's non-atomic case, where it said +24.7% and 748 admits against Redis's 747. The differential half was identical every time: 0 mismatches in 120,000 calls.

What it costs

Wall time on this machine, with a load average around 9 to 14 from other work.

The table is 300 simulated runs of 20 s; the mutants are 3,600 runs of 12 s. The Redis run is mostly its nine 6 s live cases. With the machine far busier, a load of 44, the table took 14.9 s.

33 tests, two of them against Redis

Counted with RATEPROOF_REDIS=localhost:6379 go test -count=1 -json ./...: 33 tests, all passing, no subtests, in 13 to 16 s. Without RATEPROOF_REDIS, 31 pass in a few seconds and the two Redis tests skip. CI runs them on Go 1.22 and stable, and the Redis ones against a redis:7-alpine service.

Tests that would fail if the claims were wrong

Algorithms: a full burst and no more, the refill rate, fixed window's 2x across a boundary, the sliding log holding its window, the token bucket refilling twice when the clock steps back, and each planted bug breaking its promise on some input.
Simulator: the same seed gives the same run, every deployment sees the same traffic, one node with no latency equals the ideal, correct deployments keep their promises, every planted bug is caught.
The README's findings: the token bucket collapses under skew while the leaky bucket holds, local split turns away an honest client, a wiped store hands out a fresh burst, boundary bursts peak at 2x for fixed window.
Redis: every algorithm has a Lua script, the RESP client's replies and errors, the Lua and Go decisions call for call, and live runs the simulator must reproduce.

CI has four jobs: tests on Go 1.22 and stable with -race, the mutants on 200 seeds, the Redis check, and a check that docs/skew.svg is what the current code draws. The run on 38d4084 passed all five job runs.

Deliberately missing

Production traffic: All four clients are synthetic. Real traffic has other shapes, and the numbers are for these.
Drift: Each node's clock offset is fixed. Clocks that drift or jump, such as an NTP step, are not modelled.
Clusters: One store and one key per client: no Redis Cluster, no replication lag, no failover beyond the store losing everything once.
Real machines: The Redis check ran clients and Redis on one host, with skew injected into the time sent.
Your library: These are the algorithms written plainly, not any library's code. To measure a library, port its script into redisx/lua and limiter/.

Run it

git clone https://github.com/ahmed-hashim-pro/rate-proof
cd rate-proof
go build -o rateproof ./cmd/rateproof

./rateproof table
./rateproof run --algo token-bucket --skew 50ms
./rateproof mutants
go test ./...        # 31 pass, 2 skip without Redis

# The real-Redis check, in Docker:
make redis

Go 1.22 or newer and nothing else. make redis starts a throwaway Redis and runs the check in a Go container. With your own Redis: ./rateproof redis --addr localhost:6379.