Three common traffic limiting algorithms

When developing high-concurrency systems, there are three powerful tools to protect the system: caching, degradation, and limiting traffic. So what is flow limiting? As the name implies, limiting the flow is to limit the flow, just like you broadband packet 1 GIGAByte of data, used up. Through current limiting, we can control the QPS of the system well, so as to achieve the purpose of protecting the system. This article will introduce the common traffic limiting algorithms and their characteristics.

1. Counter algorithm

The counter algorithm is the simplest and easiest algorithm to implement in the current limiting algorithm. For example, we stipulate that for interface A, we can not access more than 100 times per minute. We can start by setting a counter that increments every time a request comes in. If the value of counter is greater than 100 and the interval between the request and the first request is less than 1 minute, then there are too many requests. If the interval between this request and the first request is greater than 1 minute and the value of counter is still within the flow limit range, then reset counter. The algorithm is shown as follows:

public class CounterTest {
    public long timeStamp = getNowTime();
    public int reqCount = 0;
    public final int limit = 100; // The maximum number of requests in the time window
    public final long interval = 1000; // Time window ms

    public boolean grant() {
        long now = getNowTime();
        if (now < timeStamp + interval) {
            // Within the time window
            reqCount++;
            // Determine whether the maximum number of requests is exceeded in the current time window
            return reqCount <= limit;
        } else {
            timeStamp = now;
            // Reset after timeout
            reqCount = 1;
            return true; }}public long getNowTime() {
        returnSystem.currentTimeMillis(); }}Copy the code

Although this algorithm is simple, there is a very fatal problem, that is, the critical problem, we see the following figure:



As can be seen from the figure above, if a malicious user sends 100 requests at 0:59 and another 100 requests at 1:00, then the user sends 200 requests in one second. We just specified a maximum of 100 requests per minute, which is 1.7 requests per second, and the user can exceed our rate limit instantaneously by popping requests at the reset node in the time window. Users could overwhelm our app with this flaw in the algorithm.

Smart friends may have noticed that the problem is actually due to our low statistical accuracy. So how to deal with this problem well? Or, how do you reduce the impact of critical problems? We can look at the sliding window algorithm below.

The sliding window

Rolling window, also known as rolling Window. To solve this problem, we introduce the sliding window algorithm. If you have learned the TCP network protocol, then you must be familiar with the term sliding window. Here is a good illustration of the sliding window algorithm:



In the figure above, the entire red rectangle represents a time window, in our case a time window is a minute. Then we divide the time window, for example, in the picture, we have divided the sliding window into 6 squares, so each one represents 10 seconds. Every 10 seconds, our time window slides one space to the right. Each grid has its own counter. For example, when a request arrives at 0:35 seconds, the counter from 0:30 to 0:39 is incremented by one.

So how does sliding Windows solve the critical problem just now? If you look at the figure above, 100 requests arriving at 0:59 will land in the gray grid, and requests arriving at 1:00 will land in the orange grid. When the time reaches 1:00, our window will move one space to the right, so the total number of requests in the time window at this time is 200, exceeding the limit of 100, so it can be detected that the current limit is reached.

Let me review the counter algorithm, and we can see that the counter algorithm is actually a sliding window algorithm. But it doesn’t divide the time window further, so there’s only one.

It can be seen that the more grids the sliding window is divided, the smoother the rolling of the sliding window will be, and the more accurate the statistics of current limiting will be.

2. Token bucket algorithm

Token bucket algorithm is one of the more common traffic limiting algorithms, which is roughly described as follows:

1) All requests require an available token before they can be processed;

2) According to the flow limiting size, set a certain rate to add the token to the bucket;

3) Set the maximum limit of placing tokens for the bucket. When the bucket is full, newly added tokens will be discarded or rejected;

4) After the request is reached, the token in the token bucket should be obtained first, and then other business logic can be carried out after holding the token. After processing the business logic, the token can be deleted directly;

5) The token bucket has a minimum limit. When the number of tokens in the bucket reaches the minimum limit, the token will not be deleted after the request is processed to ensure sufficient flow limiting;

3. Leaky bucket algorithm

Leaky bucket algorithm is actually very simple, can be roughly considered as the water leakage process, into the bucket at a certain rate of water outflow, at any rate of water inflow, when the water exceeds the bucket flow is discarded, because the bucket capacity is unchanged, to ensure the overall rate.