Rate Limiter Algorithms

Algorithms for rate limiting

A rate-limiting algorithm defines which requests may proceed and how much state the limiter must keep. Compare these five options against the policy established in the previous lesson:

• Token bucket

• Leaking bucket

• Fixed window counter

• Sliding window log

• Sliding window counter

Token bucket algorithm

The token bucket algorithm uses a container with a predefined capacity. Tokens are added at a constant rate. When a request arrives, it attempts to consume a token. If the bucket is empty, the request is rejected.

The algorithm operates as follows:

Assume a refill rate of $\text{R}$ tokens per second and a bucket capacity of $\text{C}$ tokens. Each request costs one token in this example.

1. A new token is added to the bucket every 1/R seconds.

2. If the bucket reaches capacity $\text{C}$, incoming tokens are discarded.

3. Incoming requests consume tokens. If $(\text{N})$ requests arrive and at least $\text{N}$ tokens exist, the requests are processed.

4. If the bucket has fewer tokens than incoming requests, admit only as many requests as available tokens permit and reject the rest. Refill, check, and consumption must form one atomic decision for a shared bucket.

The following illustration demonstrates the token bucket workflow.