Rate Limiter Algorithms

Algorithms for rate limiting

Rate limiters rely on efficient algorithms to control traffic flow. While requirements vary, we will focus on the most popular options:

• 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 rate limit of $\text{R}$ and a total bucket capacity of $\text{C}$.

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, the system processes only the available number and discards the rest.

The following illustration demonstrates the token bucket workflow.

In this example, the bucket capacity is three, and it refills at a rate of three tokens per minute.

Essential parameters

Key parameters for the token bucket algorithm include:

• Bucket capacity $(\text{C})$: The maximum number of tokens the bucket can hold.

• Rate limit $(\text{R})$: The number of requests allowed per unit of time.

• Refill rate $(\frac{1}{\text{R}})$ ...