Rate Limiting Algorithms

Deciding whether a request is over the limit sounds like it needs nothing more than a counter. It gets interesting because of one question: what should happen when a client saves up its allowance and spends it all at once?

That single question separates the five standard algorithms. Each one takes a different position on bursts, and pays a different price in memory and accuracy.

Token bucket

Picture a bucket that holds a fixed number of tokens. Tokens are added at a steady rate, and the bucket cannot hold more than its capacity. Every request takes one token out