Token bucket versus leaky bucket

01A rate and a burst are different limits

A customer organization shares an API allowance across all its users and servers. We want to allow occasional bursts without letting it consume unlimited sustained work.

A token represents permission to do some work. A token bucket:

1. Keeps up to B tokens as saved credit.
2. Adds r tokens per second, stopping at B.
3. Lets a request proceed only if it can spend the required tokens.

An ordinary read may cost one token and an expensive export five. Idle time earns credit up to the limit, so a short permitted burst can proceed immediately. A component making this immediate allow-or-reject decision is a policer.

“Leaky bucket” has two related meanings. A queued shaper holds requests and releases them at a controlled rate, adding waiting time. A meter instead estimates how much work an imaginary queue would still contain and immediately rejects work exceeding its limit. State which behavior you mean; the name alone does not tell callers whether they wait.

02Implement accounting as one decision

Give the organization 20-token capacity and refill at 5 tokens/s. All API servers must use the same allowance or reserved portions of it.

For each request, one indivisible operation does the following:

1. Read the balance and last-refill time stored under the organization's key.
2. Calculate earned credit: elapsed seconds × 5, then cap oldBalance + earnedCredit at 20.
3. Compare the request's cost with that available balance.
4. If enough credit exists, deduct the cost and allow the request. Otherwise reject it without deducting its cost. Save the newly refilled balance and time in that same indivisible operation, including on rejection.

“Atomic” means another caller cannot slip between the comparison and deduction. If two servers each read one token and later write separately, both can spend that last token. A shared transaction or script must protect the complete decision, not just each final write. Define clock source, precision and state expiry; recreating a full bucket too early can grant unearned credit.

03Worked example: a permitted burst

Start at time zero with 20 tokens and one token per read.

1. Twenty simultaneous reads spend all 20. An immediate twenty-first read is rejected; merely receiving a request does not earn a token.
2. Wait 0.4 seconds from empty. Five tokens/s × 0.4 seconds earns two tokens, enough for two reads. Two idle seconds earns ten.
3. Charge an export five tokens. It consumes the same allowance as five ordinary reads, making the limit better reflect expensive work.
4. Avoid independent full buckets on ten servers. They permit ten bursts and about 50/s aggregate refill. To enforce 5/s total, share the balance or reserve constrained portions from one total.

Now queue 20 requests in a shaper that releases one every 200 ms, equivalent to 5/s. If the first release is immediate, the twentieth leaves after 19 gaps: 3.8 seconds. That cannot fit a 200 ms interactive target unless most requests are rejected or the queue is much smaller. A different first-release convention changes the calculation, so state it.

Also protect unfinished work separately. At 10 admitted requests/s and 0.1 s mean duration, average in-flight work is one. At two seconds it becomes 20 under stable load. The arrival rate stayed allowed, but the requests now occupy many more worker slots or connections.

04Match the rule to the protected resource

Match the control to the resource:

• Use a token bucket when a short burst is useful and the backend can absorb it.
• Use queued shaping when smoother output matters and callers can tolerate the calculated wait. Set a finite queue limit.
• Limit concurrency as needed. An arrival limit does not stop slow requests from occupying every connection.
• Limit total work as well as each organization. Many customers respecting their own limits can still overwhelm one database.
• Choose behavior when the allowance store fails. Fail-open accepts work without exact shared accounting; fail-closed rejects because remaining credit cannot be established. A strict spending cap cannot safely become unlimited during an outage.
• Reserve limited local credit if useful. Subtract each server's allocation from the shared total in advance; during failure it can spend only that amount.
• Guide rejected clients. Estimate when refill would cover the missing tokens and tell the client when to try again. This is not reserved credit: other requests may spend it first. Encourage longer waits after repeated rejection, with varied retry times so clients do not all return together.

State the accounting key, capacity, refill rate, cost, atomic update, maximum wait and outage behavior. These details determine what the algorithm actually permits.