Build challenges · 4 steps · javascript · python
Rate Limiter (Token Bucket)
Bound a client to a sustained rate while still tolerating a burst.
A rate limiter has to do two things that pull against each other: stop a client hammering you, and not punish a client for being briefly busy. A fixed counter per minute fails the second — reset the window at 12:00:00 and a client can spend its whole minute's budget at 11:59:59 and again a second later, which is twice the rate you promised.
The token bucket solves both with one idea. A bucket holds up to capacity
tokens and gains refillPerSecond of them as time passes. Every request spends
one. A client that has been quiet has a full bucket and may burst; a client that
has been busy waits for the drip.
You will build it across four steps:
- spend a token per request, refuse when empty
- refill as time passes, never above capacity
- survive a rate slower than one token per second — the bug that quietly makes a limiter refill never
- give every client its own bucket
Time is passed in, never read. Every method takes now in seconds rather
than calling a clock. That is not a testing convenience bolted on — it is how
the real thing is written, because a limiter that reads a clock internally can
only be tested by sleeping.
The workspace
These files carry across every step. What you write in one step is what you start the next with.
- limiter.js
- bucket.js
- harness.jsread-only
Steps · 0 of 4 done
Start anywhere. Open step 3 first and you are handed the reference build of steps 1 and 2, so every step stands on its own. Nothing here is locked behind anything else.
This build applies Rate Limiting and Hash Maps. Read the lesson first if it is unfamiliar — a recommendation, not a prerequisite.