Token Bucket Rate Limiting

Worked Example

Consider an API token bucket starting with a full bucket of 5 tokens. The refill rate is 2 tokens/sec, and each request costs 2 tokens. We can trace the token balance through a series of events:

1. Time t=0: We send three requests. The first request costs 2 tokens (5 - 2 = 3). The second request costs 2 tokens (3 - 2 = 1). The third request costs 2 tokens, but only 1 token remains, so it is strictly rejected. Final state: 1 token remaining.
2. Time t=1: Time advances by 1 second. The bucket refills by 2 tokens. The new balance is min(5, 1 + 2) = 3 tokens.
3. Time t=1 (again): We send one request. It costs 2 tokens (3 - 2 = 1). Final state: 1 token remaining.
4. Time t=2: Time advances by 1 second. The bucket refills by 2 tokens. The new balance is min(5, 1 + 2) = 3 tokens.
5. Time t=3: Time advances by another 1 second. The bucket refills by 2 tokens. The new balance is min(5, 3 + 2) = 5 tokens. The capacity limit is reached.

Experiment

You can try this out in the Token Bucket Rate Limiting module:

1. Set the Capacity to 5, the Refill Rate to 2, and the Request Cost to 2.
2. Click Reset Simulation to start with a full bucket of 5 tokens.
3. Click Send Request three times. Notice that the first two are accepted, and the third is rejected.
4. Click Advance 1s to refill the bucket by 2 tokens.
5. Click Send Request once more. Notice that it is accepted.
6. Click Advance 1s multiple times and observe the tokens capping strictly at 5 without exceeding the limit.

Limitations

This is a single deterministic bucket: time advances only through Advance 1s, and changing any parameter restarts it. The graph joins refill events with a linear rise capped at capacity; same-time requests create vertical drops. The log retains the latest 200 events and the graph the latest 400 balance updates; counters remain cumulative until reset. While simple and efficient, the token bucket strictly refuses requests once empty, offering no built-in queue for burst absorption beyond the immediate capacity. In distributed systems, maintaining a perfectly synchronized global token count is challenging, often requiring trade-offs between strict consistency (e.g., Redis centralized counters) and high availability (e.g., eventual consistency or localized node limits).

Primary References

For formal algorithm specifications, refer to RFC standards.

• RFC 3290 Appendix A.4: Token Bucket - Formal definition of the algorithm in network traffic shaping.