A token-bucket rate limiter class
Coding, Medium
Small real code that works when called late, twice, or with bad input.
Write a class TokenBucket in JavaScript (or the same idea in another language) that limits how often something may happen inside one process. The constructor takes capacity (most tokens the bucket holds), refillPerSec (tokens added each second, may be a fraction) and now (a function that returns the time in milliseconds; default: the system clock). The bucket starts full. tryTake(n = 1) takes n tokens and returns true if the bucket has at least n. If it has fewer, it takes nothing and returns false. Tokens are added as time passes, and the bucket never holds more than capacity. Do not use timers or loops that run in the background.
Examples
Input capacity 3, refill 1 per second. Four tryTake() calls at time 0, then one tryTake() at 1000 ms, then one more
Output true, true, true, false; then true; then false
Why Three tokens give a burst of 3. After 1 second one token has come back, and it is used at once.
Input capacity 2, refill 10 per second. Wait 60 seconds. Then three tryTake() calls
Output true, true, false
Why The bucket is capped at 2. It does not store 600 tokens.
Input capacity 2. tryTake(3)
Output false, and the bucket still holds 2 tokens
Why Edge case: a request bigger than the capacity can never succeed, and a refused call takes nothing.
Constraints
capacityis a whole number >= 1.refillPerSecis a number > 0.nis a whole number >= 1. Refuse bad values with a clear error.- Time must come only from the
nowfunction, so a test can move the clock by hand. tryTakemust run in constant time and must not use memory that grows with the number of calls.- If
nowever returns a smaller time than before (a clock change), the bucket must not gain or lose tokens because of it.
Your answer must contain
- The code
- What state the class keeps and how a refill is calculated (without a timer)
- How a refused call, a call bigger than the capacity, and a clock that goes back are handled
- How you would test it, using the injected clock