Step 3 of 4
Survive a rate below one per second
Here is the bug that ships.
Plenty of real limits are slower than one request per second — one upload every
four seconds, thirty API calls a minute. Run your bucket at
refillPerSecond = 0.5 and watch what happens if the refill rounds down: each
call adds floor(1 × 0.5) = 0 tokens and advances the bookmark, so the
remaining half-token is thrown away every single time. The bucket refills
never, and the client is throttled forever.
capacity 2, 0.5 tokens/second
t=0 allow -> true allow -> true // empty
t=1 allow -> false // half a token is not a token
t=2 allow -> true // the halves added upThe fix is to stop throwing the remainder away: hold the balance as a fraction
and only insist on a whole token at the moment one is spent. tokens() already
floors for display, which is the right place for rounding — at the boundary,
not in the accounting.
Your build
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| runOps(2, 0.5, [["allow",0],["allow",0],["allow",1],["allow",2]]) | a rate below one per second still refills | [true,true,false,true] | — |
| runOps(1, 0.25, [["allow",0],["allow",1],["allow",2],["allow",3],["allow",4]]) | fractions accumulate across repeated polls | [true,false,false,false,true] | — |
| runOps(4, 0.5, [["allow",0],["allow",0],["allow",0],["allow",0],["tokens",3]]) | a partial token is reported as none | [true,true,true,true,1] | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left