Building blocks: a distributed rate limiter, end to end
Hands-on project: build a correct distributed token-bucket rate limiter — shared counter, atomic increment, 429 + Retry-After, fail-open — then prove the race is gone under concurrent load and reason about how the unit's other blocks would compose into the same service.
Reading that the distributed-counter race is the hard part of rate limiting is not the same as watching a naïve limiter leak under load and then watching the atomic version hold the line. Build a real token-bucket limiter backed by shared storage, demonstrate the lost-update race empirically with a non-atomic version, fix it, and add the production behaviours — 429 + Retry-After, fail-open — that separate a toy from something you’d ship.
This project makes the unit’s central lesson operational: the algorithm is trivial, but correctness under concurrency is the whole problem. You’ll build the limiter, measure the race, fix it atomically, and harden it — then reason about how the unit’s other building blocks would slot into the same gateway.
Build and harden a distributed token-bucket rate limiter backed by shared storage (Redis or equivalent), empirically demonstrate the read-modify-write race in a naïve version and prove it disappears in an atomic version, and implement the production rejection and resilience behaviours — closing the loop between the algorithm and a service you'd actually run.
- A working token-bucket limiter (capacity B, refill R) backed by a shared store, serving multiple instances against one counter per key.
- A reproducible experiment: a table or plot showing the naïve limiter's overshoot rising with concurrency, and the atomic version holding at or below the limit under the same load — with the numbers stated.
- A correct rejection path: 429 responses carry an accurate Retry-After, and the headers let a client self-throttle before hitting the wall.
- A fail-open path proven by a fault-injection test: when the store is made to error or time out, requests are allowed (verified), the fail-open metric increments, and the kill switch disables the limiter.
- A short write-up: one paragraph quantifying the race and why atomicity removes it, and one paragraph on the layering (per-IP edge vs per-key gateway) and what each protects.
- Add fencing for a singleton task: introduce a small piece of work that must run on exactly one instance (e.g. a periodic bucket-cleanup job), elect a leader via a lease, and protect a shared resource with a monotonically increasing fencing token — then simulate a stalled leader and show the stale-token operation is rejected.
- Add a bloom-filter guard: in front of the limiter, use a bloom filter of 'known abusive keys' (or, conversely, of valid API keys) to reject obvious traffic cheaply before touching the counter — size it for a target false-positive rate and explain why a false positive here is harmless.
- Compare algorithms empirically: implement a fixed-window limiter alongside the token bucket, and demonstrate the 2× boundary spike (100 just before a reset + 100 just after) that the token bucket / sliding window does not have.
- Add a time-ordered request ID (UUIDv7 or Snowflake) to each request log line, and show how the sortable IDs let you range-scan the log by time to reconstruct exactly which requests the limiter allowed during the spike.
- 01How do you empirically demonstrate and then fix the distributed-limiter race?
- 02What production behaviours separate a toy limiter from a shippable one?
- 03How would the unit's other building blocks compose into this same gateway?
This project turns the building-blocks unit into something you can run and measure. You build a token-bucket limiter (capacity B, refill R) on a shared store, then deliberately make the race visible: a naïve read-then-write version allows measurably more than the limit under concurrency (the lost update), and the overshoot grows with load. You then fix it with a single atomic operation — an atomic INCR or a Lua script doing refill-and-decrement in one round trip — and re-run the same load to show the overshoot vanish. That is the unit’s central truth made empirical: the algorithm is trivial, correctness under concurrency is the work. You then add the behaviours that make it shippable — 429 + Retry-After and header-based self-throttling, and fail-open resilience with a short timeout, a metric, and a kill switch — and layer coarse per-IP and precise per-key limits. Finally you reason about composition: a bloom filter to cheaply pre-reject, time-ordered IDs to keep the log range-scannable, and leader election + a fencing token to protect a singleton maintenance job from split-brain. An engineer who has built this once never again confuses “I wrote a rate limiter” with “I wrote a correct, distributed rate limiter.”
Something unclear?
Ask a question about this lesson. Questions are anonymous and go straight to the author to make the lesson better.