Counter algorithm

Counter algorithm is one of the most simple and easy to implement current limiting algorithm. For example, we stipulate that for interface A, we can not access more than 100 times per minute. So what we can do is we can start by setting a counter that increments by 1 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 a 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:

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

In the figure above, we can see that a malicious user who sends 100 requests in 59 seconds and 100 requests in one minute actually sends 200 requests in one second. We just stipulated a maximum of 100 requests per minute, that is 1.7 requests per second at most. By making sudden requests at the reset node in the time window, the user can exceed our rate limit instantly. The user may crush our application instantly through this loophole 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. The slide window algorithm is well explained in the following diagram

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.

Bucket algorithm

Leaky Bucket algorithm, also known as leaky bucket. To understand the leaky bucket algorithm, let’s take a look at wikipedia’s illustration of the algorithm:

As you can see from the figure, the whole algorithm is actually quite simple. First of all, we have a bucket with a fixed capacity, and we have water coming in and water going out, and we can’t predict how much water is going to come in, and we can’t predict how fast it’s going to go. But for the water coming out, the bucket can fix the flow rate. Also, when the bucket is full, the excess water will overflow.

Replacing the water in the algorithm with the request in the real world, we can see that the leaky bucket algorithm inherently limits the speed of the request. When using the leaky bucket algorithm, we can guarantee that the interface will process requests at a constant rate. Our leak-bucket algorithm does not inherently have critical problems.

Token bucket algorithm

Token bucket algorithm, also known as token bucket. To understand the algorithm, let’s take a look at wikipedia’s illustration of the algorithm:

As we can see from the figure, the token bucket algorithm is slightly more complex than the leaky bucket algorithm. First, we have a fixed capacity bucket with tokens in it. The bucket is initially empty, and tokens fill the bucket at a constant rate r until the bucket reaches its capacity, and excess tokens are discarded. Every time a request comes in, an attempt is made to remove a token from the bucket, and if there is no token, the request cannot pass.

The token bucket

Token bucket algorithm is the most commonly used algorithm in Traffiffiffic Shaping and Rate Limiting. Typically, the token bucket algorithm is used to control the amount of data sent to the network and to allow the delivery of burst data (Encyclopedia).

In a seckill activity, the user’s request rate is variable, which we assume is 10r/s, and tokens are placed in the token bucket at a rate of 5 tokens per second, with a maximum of 20 tokens in the bucket. Think carefully if there is always a part of the request that is discarded.

Counter VS sliding window

The counter algorithm is the simplest algorithm and can be regarded as a low-precision implementation of the sliding window. Sliding Windows require more storage space to implement because they need to store multiple counters (one per cell). In other words, the higher the accuracy of the sliding window, the more storage space is required.

Leaky bucket vs. token bucket

The most obvious difference between the leaky bucket algorithm and the token bucket algorithm is that the token bucket algorithm allows a certain degree of burst traffic. Because of the default token bucket algorithm, taking tokens is not time consuming, that is, assuming there are 100 tokens in the bucket, 100 requests can be allowed through instantly. Token bucket algorithm is widely used in the industry because it is simple to implement, allows some traffic burst and is user-friendly. Of course, we need to do it on a case-by-case basis, there is only the best algorithm, there is no optimal algorithm.