Sentinel core source code analysis ii
Ii. Sentinel core source code analysis
3. Sliding time window algorithm
The source code of sliding time window algorithm is divided into two parts: the statistics of the data, and the use of statistical data. However, before analyzing the source code, you need to understand the principle of the algorithm.
1. Time window flow limiting algorithm
Algorithm principle
The principle of the algorithm is that the system automatically selects the starting zero of a time window, and then divides the time axis into several time Windows of fixed length. So the algorithm is also called “fixed time window algorithm”.
When the request arrives, the system checks whether the current statistics in the time window where the request arrives exceeds the preset threshold. If no, the request passes; otherwise, the traffic is restricted.
Existing problems
This algorithm has such a problem: the statistics in two consecutive time Windows do not exceed the threshold, but the statistics in the time window length range across the window do.
2. Sliding time window flow limiting algorithm
Algorithm principle
The sliding time window current limiting algorithm solves the problem of fixed time window current limiting algorithm. It does not divide fixed starting point and end point of time window, but takes the arrival time of each request as the end point of statistical time window, and the starting point is the time point at which the end point pushes forward the time window. This time window is called a “sliding time window”.
Existing problems
Algorithm to improve
To solve the above problems, the system adopts a “compromise” improvement measure: the whole time axis is split into several “sample Windows”, the length of the sample window is smaller than the length of the sliding time window. When equal to sliding time window length, it becomes “fixed time window algorithm”. Generally, the length of the time window is an integer multiple of the length of the sample window.
So how do you determine if a request will pass? When the end time of the sample window is reached, the flow data in the sample window will be counted and recorded in each sample window. When a request arrives, the traffic data in the sample window at the current request time point will be collected, and then the statistics of other sample Windows in the time window at the current request time point will be obtained. If the sum does not exceed the threshold, the request will pass; otherwise, the traffic will be restricted.
