Token Bucket Rate Limiter

The Gatekeeper guards the server gate. Its orders: let through about refill_per_second requests per second on average, but don't punish a short burst. Counting requests in fixed one-second boxes won't do: five requests at the end of one box and five at the start of the next all get in, ten in a blink. So the Gatekeeper keeps a bucket of tokens instead.

Build TokenBucket(capacity, refill_per_second) with one method:

• The bucket holds at most capacity tokens and starts full.
• Tokens drip back in at a steady refill_per_second tokens per second: exactly refill_per_second / 1000 of a token every millisecond, so part-tokens build up between whole ones. A full bucket stays full (the extra drip is lost).
• allow(t: int) -> bool: a request reaches the gate at time t milliseconds. If the bucket holds at least one whole token, take one and return True. Otherwise return False and take nothing.

Across all calls t never decreases, and several requests can share the same t. A rejected request costs nothing, and the drip never stops.

b = TokenBucket(5, 5)   # 5 tokens, refilled at 5 per second: one every 200 ms
b.allow(0)      # True   (4 left)
b.allow(0)      # True   (3 left)
b.allow(0)      # True
b.allow(0)      # True
b.allow(0)      # True   (a burst of 5: the bucket is empty)
b.allow(0)      # False
b.allow(100)    # False  (half a token has dripped in)
b.allow(200)    # True   (a whole token now; it's used up)
b.allow(200)    # False
b.allow(9000)   # True   (refilled, but never above 5: 4 left)

g = TokenBucket(1, 3)   # one token every 333.33... ms
g.allow(0)      # True
g.allow(333)    # False  (333 ms bring 0.999 of a token)
g.allow(334)    # True   (1.002 tokens)

1 <= capacity <= 10^6, 1 <= refill_per_second <= 10^6, 0 <= t <= 10^9. Up to 300,000 calls; each should take O(1) time, however far apart they are.