The harness in code · Code exercises

A token-bucket rate limiter

Implement the limiter each call asks first, answering now, later or not in time, so two automations on one key stay under the vendor's limit.

codemediumExercise · 4 min · 44 of 75

On this page

A vendor's rate limit is a bucket on their side, and the cheapest place to honour it is a copy of that bucket on yours, asked before every call, where why we write these five by hand puts it on the path. The answer it gives is a time, not a yes or no. Rate limits, retries and backoff counts what an unpaced connector costs, and rate limiting compares the token bucket with the other counting algorithms from the server's side.

The situation

The 40-person wholesaler this module uses in place of the agency supplies 900 cafés, and its accounting API gives each key a bucket of 10 requests, refilled at one every 2 seconds, 30 a minute, and answers 429 when the bucket is empty. Two automations share the key: the invoice sender, about 240 calls across a working day, and the Friday statement run, which sends 80 account statements at 16:00.

Last Friday the statement run fired all 80 calls in the same second. Ten succeeded and 70 got 429s. Those retried three times at a fixed 1-second interval into a bucket that refills half a token a second, so one more got through and 69 failed for good; two invoice sends in the same seconds failed with them. The bookkeeper resent the 69 statements by hand on Monday at 2 minutes each: 2.3 hours at an assumed $30 an hour, $69.

Both automations run on a platform that stops any execution after 5 minutes, so a call that waits past that point never goes.

The question

Implement the limiter so the examples below hold. A caller that would wait longer than max_wait is refused at once, so it can be rescheduled instead of dying mid-wait.

def solve(requests, capacity, every, max_wait):
    """requests: the times callers ask to send, in seconds, non-decreasing, one call each.
    capacity: tokens the bucket holds when full; it starts full. every: seconds to refill
    one token. max_wait: the longest a caller will wait, in seconds.
    Each granted call reserves its token, so a later caller sees the bucket after every
    earlier reservation. Returns one entry per request: the time it may send, or None when
    the wait would exceed max_wait; a refused request reserves nothing."""

solve([0, 0, 0, 0], 2, 2, 60)    -> [0, 0, 2, 4]
solve([0, 0, 0, 10], 2, 2, 60)   -> [0, 0, 2, 10]
solve([0, 0, 0, 1], 2, 2, 1)     -> [0, 0, None, 2]
solve([0] * 80, 10, 2, 300)      -> ten 0s, then 2, 4, 6, ..., 140

A strong answer · Rubric · Where answers go wrong · Solution

Write your answer first, then open

A strong answer

Store the bucket as seconds of refill rather than tokens: full is capacity × every, 20 seconds here, a call costs every, and every number stays an integer. On each ask, add the seconds since the last ask, capped at full, so a quiet ten-hour night banks 10 calls, not 18,000. If the credit covers a call, the answer is now; otherwise now plus the shortfall. Either way the cost is subtracted at once, so credit can go negative. That is a reservation: the next caller in the same second is told a later time rather than "now" for the same token (example 1). A caller whose wait would exceed max_wait gets None and reserves nothing (example 3), so it cannot delay the callers behind it.

The Friday run: 10 calls at 16:00:00, then one every 2 seconds, the 80th at 140 seconds, with no 429s and inside the 5-minute limit. Set max_wait from that limit less the call itself, about 280 seconds. At 200 statements the 151st would wait 282 seconds, so the last 50 are refused when they ask and go into a second run at 16:10, rather than dying inside the platform holding reserved tokens.

Put one limiter on the key, shared by both automations through one process or one store. Two copies, each believing it owns 10 tokens, send 20 at once and the 429s return. Evidence that would change the numbers: 429s that persist with the limiter in place, meaning the vendor counts differently. Then run the local bucket slower than theirs, one every 3 seconds, and let the retry policy honour Retry-After.

Rubric

lets a burst up to capacity go at once and caps the refill at capacity
reserves the token on every grant, so two callers in the same second get different times
refuses a caller whose wait exceeds max_wait without reserving anything for it
works the Friday run: 10 at once, then one every 2 seconds, the 80th at 140 seconds
sets max_wait from the platform's 5-minute execution limit
puts one limiter on the key, shared by every automation that uses it

Where answers go wrong

"Sleep 2 seconds between calls." Fixed pacing throws away the burst, so the 80th statement leaves at 158 seconds instead of 140. It is also per automation: the invoice sender pacing itself at 30 a minute and the statement run doing the same make 60 a minute against a limit of 30.

"Answer yes or no from the token count." Two callers in the same second with one token left are both told yes, and one gets a 429. A caller told no has no time to wait for, so it polls in a loop.

"Refill from the elapsed time, uncapped." After a quiet night the bucket believes it holds thousands of tokens, the 08:00 burst goes out at once, and the vendor's bucket, which holds 10, answers the rest with 429s.

Solution

Python 3 · standard library24 lines · 9 of 9 tests passing

"""A token-bucket rate limiter — "send now, send at t, or not in time" for every call on one API key."""


def solve(requests, capacity, every, max_wait):
    """requests: the times callers ask to send, in seconds, non-decreasing, one call each.
    capacity: tokens the bucket holds when full; it starts full. every: seconds to refill
    one token. max_wait: the longest a caller will wait, in seconds.
    Each granted call reserves its token, so a later caller sees the bucket after every
    earlier reservation. Returns one entry per request: the time it may send, or None when
    the wait would exceed max_wait; a refused request reserves nothing."""
    full = capacity * every            # the bucket stored as seconds of refill, so every number stays an integer
    credit = full                      # >= every: a token is free now; < 0: tokens are reserved ahead of time
    last = requests[0] if requests else 0
    out = []
    for t in requests:
        credit = min(full, credit + (t - last))   # refill since the last ask, never past capacity
        last = t
        wait = max(0, every - credit)             # seconds until one whole token is free
        if wait > max_wait:
            out.append(None)                      # refuse at ask time: no ghost reservation
            continue
        credit -= every                           # reserve the token, now or in the future
        out.append(t + wait)
    return out

The cases that ran

TESTS = [
    # the examples on the page
    (([0, 0, 0, 0], 2, 2, 60), [0, 0, 2, 4]),
    (([0, 0, 0, 10], 2, 2, 60), [0, 0, 2, 10]),
    (([0, 0, 0, 1], 2, 2, 1), [0, 0, None, 2]),
    (([0] * 80, 10, 2, 300), [0] * 10 + [2 * k for k in range(1, 71)]),
    # the Friday run with a 60-second limit: 40 calls go, 40 are refused at ask time
    (([0] * 80, 10, 2, 60), [0] * 10 + [2 * k for k in range(1, 31)] + [None] * 40),
    # a quiet spell refills to capacity and no further
    (([0] * 10 + [100] * 12, 10, 2, 60), [0] * 10 + [100] * 10 + [102, 104]),
    # the token that arrives exactly when it is asked for is free
    (([0, 0, 2], 2, 2, 0), [0, 0, 2]),
    # spread-out calls never wait
    (([0, 2, 4, 6, 8], 1, 2, 0), [0, 2, 4, 6, 8]),
    (([], 10, 2, 60), []),
]