Rate Limiter Algorithms

Algorithms for rate limiting

The task of rate limiter is directed by highly efficient algorithms each of which has distinct advantages and disadvantages. However, there is always a choice to choose an algorithm or combination of algorithms depending on the nature of use cases. There are different algorithms used, however, we will explain the following popular algorithms.

• Token bucket
• Leaking bucket
• Fixed window counter
• Sliding window log
• Sliding window counter

Token bucket algorithm

The token bucket is a simple, well-understood, and widely used algorithm for rate limiting.

The working of the token bucket algorithm is explained below.

• This algorithm is based on the analogy of a bucket with a pre-defined tokens capacity. The bucket is periodically filled with tokens at a constant rate. Each time a request is received, it checks for a token in the bucket. There should be at least one token to process the request further. The following figure shows that the bucket can contain four tokens, and the refiller puts two tokens into the bucket every second. Similarly, the token is wasted if the client does not consume it.

• When a client’s request arrives, a token is consumed from the bucket. The total number of tokens is reduced by one, and the request is processed further; otherwise, the request is dropped. The following illustration shows this process.

The following illustration demonstrates how token consumption and rate-limiting logic work. In this example, the size of the bucket is four, and it is refilled with a rate of 4 tokens per 1 minute.

As evident from the above discussion, the token bucket algorithm takes two parameters:

• Bucket size: the maximum number of tokens that can reside in the bucket.

• Refill rate: the number of tokens put into the bucket per unit time.

Moreover, the number of buckets needed in a particular case can differ depending on the rate-limiting rules.

Let’s discuss some examples given below.

• A good practice is using different buckets for different API endpoints. Assume that a client wants to use five different services of a system. In this case, it is recommended to use five different buckets for each service.

• Each IP address would require a bucket if throttling is based on the IP addresses.

• Another case would be, if a system allows a specific number of requests, say 6 million per minute, there should be a global bucket shared by all requests.

Advantages

• Due to its simplicity, the implementation is easier.

• Space-efficient: The memory need for the algorithm is nominal due to limited states i.e. refill rate, maximum bucket size, etc.

• A burst of traffic can be possible as long as there are enough tokens in the bucket.

Disadvantages

• The two parameters, bucket size and refill rate might be challenging to tune according to the use case.

Leaking bucket algorithm

The leaking bucket algorithm is a variant of the bucket algorithm with slight modifications. In this algorithm, requests are processed at a fixed rate with a first-in-first-out (FIFO) queue.

• Requests are added to the queue and served one by one.

• If the queue is full incoming requests are discarded.

The following figure illustrates the working of the leaking bucket algorithm.

The leaking bucket algorithm also takes the following two parameters.

• Bucket size: It determines the queue size.

• Outflow rate: The number of requests that can be processed per second.

Advantages

• This algorithm is also space-efficient as it requires a few states, i.e. outflow rate, queue size.

• As requests are processed at a fixed rate; therefore, it is suitable for applications ...