Ratelimiting Algorithms
We provide different algorithms to use out of the box. Each has pros and cons.
Fixed Window
This algorithm divides time into fixed durations/windows. For example each window is 10 seconds long. When a new request comes in, the current time is used to determine the window and a counter is increased. If the counter is larger than the set limit, the request is rejected.
Pros
- Very cheap in terms of data size and computation
- Newer requests are not starved due to a high burst in the past
Cons
- Can cause high bursts at the window boundaries to leak through
- Causes request stampedes if many users are trying to access your server, whenever a new window begins
Usage
Create a new ratelimiter, that allows 10 requests per 10 seconds.
Sliding Window
Builds on top of fixed window but instead of a fixed window, we use a rolling window. Take this example: We have a rate limit of 10 requests per 1 minute. We divide time into 1 minute slices, just like in the fixed window algorithm. Window 1 will be from 00:00:00 to 00:01:00 (HH:MM:SS). Let’s assume it is currently 00:01:15 and we have received 4 requests in the first window and 5 requests so far in the current window. The approximation to determine if the request should pass works like this:
Pros
- Solves the issue near boundary from fixed window.
Cons
- More expensive in terms of storage and computation
- Is only an approximation, because it assumes a uniform request flow in the previous window, but this is fine in most cases
Usage
Create a new ratelimiter, that allows 10 requests per 10 seconds.
Token Bucket
Consider a bucket filled with {maxTokens}
tokens that refills constantly at
{refillRate}
per {interval}
. Every request will remove one token from the
bucket and if there is no token to take, the request is rejected.
Pros
- Bursts of requests are smoothed out and you can process them at a constant rate.
- Allows to set a higher initial burst limit by setting
maxTokens
higher thanrefillRate
Cons
- Expensive in terms of computation
Usage
Create a new bucket, that refills 5 tokens every 10 seconds and has a maximum size of 10.
Was this page helpful?