API Rate Limiter

A web service protects itself with two limits at once, and you are building the gatekeeper: a RateLimiter class.

Per client: a token bucket. Each client has a bucket that holds at most burst tokens and is full the first time the client appears. Every accepted request uses one token. While a bucket is below full, it gains one token every refill_every seconds, counted from the moment it last dropped below full, and no time is ever lost: with refill_every = 10, a bucket that dropped below full at second 0 gains tokens at seconds 10, 20, 30 and so on, whenever you happen to check. A full bucket gains nothing.

For the whole service: a sliding window. At most global_limit requests from all clients together may be accepted in any window seconds. A request accepted at second s still counts at second t when t - s < window.

• RateLimiter(burst, refill_every, global_limit, window) creates the limiter.
• allow(client, t) returns True and records the request if the client has a token and the window has room. Otherwise it returns False and changes nothing: a refused request uses no token and does not count toward the window.
• retry_after(client, t) returns how many seconds after t the client must wait before allow would succeed, if no other requests arrive in the meantime, or 0 if it would succeed right now. It changes nothing.

Times are whole seconds and never go down from one call to the next.

Examples

r = RateLimiter(2, 10, 100, 60)
r.allow('ana', 0)           # returns True     (1 token left)
r.allow('ana', 1)           # returns True     (0 left: they come back at 10 and 20)
r.allow('ana', 2)           # returns False
r.retry_after('ana', 2)     # returns 8
r.allow('ana', 15)          # returns True     (the token from second 10)
r.retry_after('ana', 15)    # returns 5        (the next token comes at 20)

r = RateLimiter(5, 1, 3, 10)
r.allow('a', 0)             # returns True
r.allow('b', 0)             # returns True
r.allow('c', 1)             # returns True
r.allow('d', 2)             # returns False    (3 requests in the last 10 seconds)
r.retry_after('d', 2)       # returns 8        (the two from second 0 stop counting at 10)

Constraints

• 1 <= burst, global_limit <= 1,000 and 1 <= refill_every, window <= 1,000,000
• 0 <= t <= 10^9, with up to 10,000 calls; client names are strings