Rate limit with a token bucket per key

Constraints

1. 1Each key has its own bucket, starting full at capacity tokens.
2. 2Between one request and the next for a key, the bucket refills by the elapsed seconds times refill_per_second, and never past capacity.
3. 3A request is allowed when the bucket holds at least one token, and spends one. Otherwise it is refused and spends nothing.
4. 4Process the requests in timestamp order regardless of the order they arrive in. Ties are broken by key then id so the replay is reproducible.
5. 5A request whose timestamp is not a number is refused with the reason unusable_timestamp, and does not touch any bucket.
6. 6Return one decision per request in processing order, each with the id, key, whether it was allowed, the tokens left rounded to four places, and a reason.
7. 7A capacity of zero or less, or a negative refill rate, describes no limiter: return an empty list.

Worked example

With a capacity of 3 and one token per second, tenant_a sends four requests in the first three tenths of a second. The first three are allowed and drain the bucket to nearly zero — the refill over 0.1 seconds is 0.1 tokens, which is not enough — so the fourth is refused. By 3.0 seconds the bucket has refilled and tenant_a is allowed again. tenant_b sends two requests in the same window and is never refused, because it has its own bucket. A single shared bucket would have throttled tenant_b for tenant_a's behaviour, which is the exact failure the limiter is meant to prevent — and it is what almost every first implementation does.

What this tests

Continuous state derived from elapsed time rather than from a counter that somebody has to reset, and per-key isolation. The cap on refill is what makes a bucket a burst allowance instead of an unbounded credit.