A rate limiter is a common component in system design that helps control the rate at which certain operations or requests are allowed to occur. It acts as a mechanism to prevent overloading a system by limiting the number of requests or actions processed within a specified time period.
A rate limiter is employed to regulate the flow of traffic originating from a client or service. Within the realm of HTTP, this mechanism restricts the number of client requests permitted within a designated timeframe. If the count of API requests surpasses the threshold set by the rate limiter, any surplus calls are obstructed.
Algorithms For Rate Limiting
Rate limiting is a crucial technique used in system design to control the rate at which certain operations or requests are allowed to be processed. It helps protect systems from abuse, prevents resource exhaustion, and ensures fair usage among users.
Sliding Window Log Algorithm
The issue with the fixed window counter algorithm: The main issue which is faced by the fixed window counter algorithm is that it allows more requests to go through at the edges of a window.
Whereas the sliding window log algorithm fixes the issue faced by the fixed window counter algorithm.
Here is the flow of working of the sliding window log algorithm:
This algorithm keeps track of the request timestamps, whereas timestamp data is stored in the cache such as sorted sets of Redis.
When a new request comes in, this algorithm removes all the outdated timestamps. Outdated timestamps are those older than the start of the current time window.
Then the timestamp of the new request is added to the log.
Then there is a check happens that if the log size is the same or lower than the allowed count, then the request is accepted otherwise, the request is rejected.
Here's a simplified example to illustrate the algorithm:
Condition: The rate limiter allows 2 requests per minute.
Here is the flow of working of the sliding window log algorithm:
A new request arrives at 1:00:01, as the log is currently empty, the request is allowed. The timestamp 1:00:01 is inserted and now the log size becomes 1.
Another request arrives at 1:00:30, the timestamp 1:00:30 is inserted and now the log size becomes 2. As our allowed rule is 2 requests per minute, this request also gets allowed.
Another request arrives at 1:00:50, the timestamp 1:00:30 is inserted and now the log size becomes 3. As our allowed rule is 2 requests per minute, this request gets rejected.
Another request arrives at 1:01:40, the timestamp 1:01:40 is inserted, however, requests sent before 1:00:40 becomes outdated and are removed from the log. Now the log size becomes 2. As our allowed rule is 2 requests per minute, this request gets allowed.
Advantages:
- This algorithm is very accurate. In any rolling window, requests will not exceed the rate limit.
Disadvantages:
- This algorithm consumes a lot of memory, as any request gets rejected, its timestamp might still be stored in the memory.
Sliding Window Counter Algorithm
This algorithm works on the hybrid approach that includes functionalities of both the fixed window counter and the sliding window log.
Here's a simplified example to illustrate the algorithm:
Condition: The rate limiter allows 7 requests per minute, out of which 5 requests are from the previous minute and 3 requests are from the current minute.
Now a new request arrives at a 30% position in the current minute.
We use the below formula to calculate the number of requests in the rolling window:
- Requests in the current window + requests in the previous window * overlap percentage of the rolling window and previous window.
We have 3 requests in the current window and 5 requests in the previous window.
- therefore, our limit would be 3 + 5 * 0.7% = 6.5 requests. and we round down to 6, which becomes our rate limit.
Since our maximum allow rate limit is 7, therefore, our new request gets passed through the rate limiter.
Advantages:
This rate limiter smooths out the spikes in traffic because the rate is based on the average rate of the previous window.
This rate limiter is memory efficient.
Disadvantages:
- This rate limiter works on the assumption that in the previous window, requests are evenly distributed. So we make an approximation of the actual rate.
Summarizing Up
In summary, rate limiters offer a range of benefits including preventing overload, protecting against attacks, ensuring fair resource allocation, improving scalability, enhancing stability and availability, safeguarding third-party integrations, and enabling usage-based billing. These benefits contribute to the overall reliability, performance, and security of a system.