1. Introduction to sliding Windows
The current mainstream flow limiting methods mainly include sliding window, leaky bucket and token bucket, while the sliding window is mainly used as the flow limiting algorithm in Sentinel. The figure below is at blog.csdn.net/weixin_4331…
It can be found that although sliding window is not evenly distributed in flow processing, it can deal with the sudden large flow most calmly, and it has the most convenient configuration adjustment. Therefore, sliding window is undoubtedly optimal in the processing of e-commerce shopping, commodity browsing and other scenes.
Sliding window algorithm, in fact, it is not difficult to understand, sliding window is more of an idea, in congestion control and flow limiting is widely used, not to say more, directly on the first problem to play. Deepen the impression.
Topic:
Given you an array of integers, given a given integer n, let you find the maximum number of consecutive n numbers added to the array.
In this case, the data is the sum of the arrays inside the sliding window. In this case, the data is the sum of the arrays inside the sliding window. As shown below:
The problem solving code
The code is relatively simple, here but more introduction, mainly is to understand what sliding window is a thing, the code is as follows:
public class WindowDemo {
public static void solution(int n){
// here simulates a sliding WindowData simulation process, WindowData represents the sliding window maintenance data
int WindowData = 0;
if(n<=0)
n=2;
// Slide on the data
int a[] = {-1.2.3.7, -10.6};
// Initialize, n is 2 by default
for(int i = 0; i < n; i++) WindowData = WindowData+a[i]; System.out.println("The data in the window is:"+WindowData);
int max = WindowData;
// Simulate the sliding statistics process
for(int i = n ; i < a.length ; i++){
// Slide forward one space
WindowData = WindowData+a[i]-a[i-n];
System.out.println("The data in the window is:"+WindowData);
// Update the maximum value
if(max < WindowData)
max = WindowData;
}
System.out.println("Maximum is"+max);
}
public static void main(String[] args) {
solution(2); }}Copy the codeThe output
2. The form of sliding window in Sentinel
Before entering the source code analysis, it is important to understand the form and use of sliding Windows in the Sentinel application, as well as the explanation of some key terms. Not much to say below, directly combined with the source code analysis.
2.1 Sample window WindowWrap
In the sentinel, whole sliding window, can understand into a sliding window on time axis, a sliding window will be split into many sample time window, the number of sample Windows default is 10, each sample window, will be assigned as a certain period of time the data statistics (request by number, number of threads statistics, etc.), Over time, new sample Windows will be created and old Windows will be deleted.
In Sentinel, the sample window is represented by a WindowWrap class, which contains the window start time (the start time of the window allocated to a certain period of time), window data, and the length of the window allocated to a certain period of time (how much time the window spans).
public class WindowWrap<T> {
// The length of the time period allocated to the window
private final long windowLengthInMs;
// Window start time
private long windowStart;
// Window data
private T value;
// constructor
public WindowWrap(long windowLengthInMs, long windowStart, T value) {
this.windowLengthInMs = windowLengthInMs;
this.windowStart = windowStart;
this.value = value;
}
public long windowLength(a) {
return windowLengthInMs;
}
public long windowStart(a) {
return windowStart;
}
public T value(a) {
return value;
}
public void setValue(T value) {
this.value = value;
}
public WindowWrap<T> resetTo(long startTime) {
this.windowStart = startTime;
return this;
}
// Check whether it is a time sample window. The window start time + window time length is less than the current time
public boolean isTimeInWindow(long timeMillis) {
return windowStart <= timeMillis && timeMillis < windowStart + windowLengthInMs;
}
@Override
public String toString(a) {
return "WindowWrap{" +
"windowLengthInMs=" + windowLengthInMs +
", windowStart=" + windowStart +
", value=" + value +
'} '; }}Copy the code2.2 Sliding window LeapArray
I just said that the sample window is responsible for the statistics and storage of a certain period of time, while the sliding window is made up of multiple sample Windows. In the source code of Sentinel, one of the sliding Windows is maintained by a leapArray. Here is part of his source code, and I will look at the source code to see how he stores the sample window.
public abstract class LeapArray<T> {
// Length of each sample window
protected int windowLengthInMs;
// Number of sample Windows
protected int sampleCount;
// How much time a sliding window spans in milliseconds
protected int intervalInMs;
// The number of seconds that a sliding window spans
private double intervalInSecond;
// Set of sample Windows, stored with AtomicReferenceArray, length sampleCount (number of sample Windows)
protected final AtomicReferenceArray<WindowWrap<T>> array;
private final ReentrantLock updateLock = new ReentrantLock();
// Initialize the parameters
public LeapArray(int sampleCount, int intervalInMs) {
AssertUtil.isTrue(sampleCount > 0."bucket count is invalid: " + sampleCount);
AssertUtil.isTrue(intervalInMs > 0."total time interval of the sliding window should be positive");
AssertUtil.isTrue(intervalInMs % sampleCount == 0."time span needs to be evenly divided");
this.windowLengthInMs = intervalInMs / sampleCount;
this.intervalInMs = intervalInMs;
this.intervalInSecond = intervalInMs / 1000.0;
this.sampleCount = sampleCount;
this.array = new AtomicReferenceArray<>(sampleCount);
}
/ /... Omit other code
}
Copy the codeAs you can see from this code, the sample window is stored in LeapArray with an AtomicReferenceArray of length sampleCount. This is probably the representation of sliding window in Sentinel, so sliding window is actually more of an idea, how to use and implement it can be in various forms.
2.3 Sample window data MetricBucket
In the sentinel source code, MetricBucket is used to store data within a certain period of time. In sentinel source code, MetricBucket is used to store data within a certain period of time.
private final LeapArray<MetricBucket> data;
Copy the codeThis class uses the LongAdder[] type to calculate the number of current requests. For those interested in LongAdder, you can view it online. The following code only shows a statistic of the number of requests passed, part of the source code is as follows
public class MetricBucket {
// count the number of events
private final LongAdder[] counters;
private volatile long minRt;
// constructor
public MetricBucket(a) {
MetricEvent[] events = MetricEvent.values();
this.counters = new LongAdder[events.length];
for (MetricEvent event : events) {
counters[event.ordinal()] = new LongAdder();
}
initMinRt();
}
/ /... Omit some code
public long get(MetricEvent event) {
return counters[event.ordinal()].sum();
}
// Add the number of passes to the counter
public MetricBucket add(MetricEvent event, long n) {
counters[event.ordinal()].add(n);
return this;
}
// Obtain the number of requests that pass in the current time range and compare it with the rule to determine whether to limit traffic
public long pass(a) {
return get(MetricEvent.PASS);
}
// New request passed, add statistics here
public void addPass(int n) {
add(MetricEvent.PASS, n);
}
/ /... Omit some code
}
Copy the code3. The whole process of data statistics by sliding window
So that gives you an idea of how a sliding window might be stored in Sentinel, and you have an idea of how a sliding window might be stored in Sentinel, but it doesn’t work. So what you need to think about is, when a request comes in at some point in time, how do you determine which sample window that request is in? Where to conduct statistics on his information data, whether the time period of his sample window is too many requests, and how to slide the sliding window are the focus of our subsequent consideration.
I’m going to show you how sentinel increases the number of requests that pass in a sample window at a certain time. Okay
3.1 The whole process of data statistics
Those who have read the previous articles know that the chain of responsibility will fire when it comes to StatisticSlot. If a request is passed after the subsequent operations are completed, we need to increase the number of requests that are passed during the current period as a reference for subsequent requests. The source code (from the StatisticSlot class) is as follows:
// Execute the next slot of the link to determine whether to limit traffic
fireEntry(context, resourceWrapper, node, count, prioritized, args);
// Increase the number of threads
node.increaseThreadNum();
// Add the number of requests to pass and update the slider window
node.addPassRequest(count);
Copy the codeThen we go to node.addPassRequest(count) and find that we are in the DefaultNode class and have called the addPassRequest() method of StatisticNode. None of that matters. Importantly, an ArrayMetric counter has been set up to count one-second and one-minute requests as follows (from the StatisticNode class) :
private transient volatile Metric rollingCounterInSecond = new ArrayMetric(SampleCountProperty.SAMPLE_COUNT,
IntervalProperty.INTERVAL);
@Override
public void addPassRequest(int count) {
rollingCounterInSecond.addPass(count);
rollingCounterInMinute.addPass(count);
}
Copy the codeLet’s move on to ArrayMetric’s addPass method, and here we’re starting to get to the heart of it. First we see a data variable in this class, and when we look at the type, it’s a very familiar one, the sliding window class we introduced earlier, LeapArray, Using MetricBucket as his window data type, which means we’re home, the source code is as follows (ArrayMetric) :
private final LeapArray<MetricBucket> data;
@Override
public void addPass(int count) {
// Get the sample window at the current time
WindowWrap<MetricBucket> wrap = data.currentWindow();
// Increase the number of requests passed
wrap.value().addPass(count);
}
Copy the codeThus, we finished the whole process of data statistics and increased the number of requests to the specified sample window.
3.2 Creation and update of sample Windows
In the addPass method of ArrayMeric, LeapArray is used to get the sample window that the current request time belongs to. So how does this step come about? Because the sliding window must slide over time. So let’s talk about creating and updating the sample window.
Continuing with the source code, you have now entered the method in the sliding window LeapArray class
public WindowWrap<T> currentWindow(a) {
// Get the current point in time
return currentWindow(TimeUtil.currentTimeMillis());
}
Copy the codeFollow up again into the most critical part of the code, first on the source code, slowly analysis
public WindowWrap<T> currentWindow(long timeMillis) {
if (timeMillis < 0) {
return null;
}
// Calculate the sample window ID of the current time, which is the index in the calculation data LeapArray
int idx = calculateTimeIdx(timeMillis);
// Calculate the start time of the current sample window
long windowStart = calculateWindowStart(timeMillis);
while (true) {
// Get the sample window of the current time
WindowWrap<T> old = array.get(idx);
// If the current sample window is null, it does not exist yet
if (old == null) {
// Create a time window
WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
if (array.compareAndSet(idx, null, window)) {
// Create a successful return window
return window;
} else {
Thread.yield();
}
// If the start time of the current sample window is the same as that of the calculated sample window
// The two samples are the same window
} else if (windowStart == old.windowStart()) {
return old;
// If the start time of the current sample window is greater than the calculated start time of the sample window
// The calculated sample window is out of date and the original sample window needs to be replaced
} else if (windowStart > old.windowStart()) {
if (updateLock.tryLock()) {
try {
return resetWindowTo(old, windowStart);
} finally{ updateLock.unlock(); }}else{ Thread.yield(); }}else if (windowStart < old.windowStart()) {
return newWindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis)); }}}Copy the codeLet’s analyze them sentence by sentence
3.2.1 calculateTimeIdx (timeMillis)
The first thing that catches your eye is this. This method looks simple and is actually very important. The source code is as follows:
private int calculateTimeIdx(/*@Valid*/ long timeMillis) {
// Divide the current time by the length of the sample window
long timeId = timeMillis / windowLengthInMs;
// Calculate current index so we can map the timestamp to the leap array.
return (int)(timeId % array.length());
}
Copy the codeWhen you first meet him, you will be confused. What is he doing? Let’s look at a picture
First of all, the timeId calculated above is actually the time interval divided according to the sample window on the time axis. As shown in the figure, 0-10t represents timeId 0, 10 T-20t represents timeId 1, and so on. Then what is the next step? It is the ID of the sample window assigned to this period of time. For example, timeId 0 will be assigned to A0, and timeId 3 will be assigned to A0.
calculateWindowStart(timeMillis);
Continue to the next step, this step is relatively simple, know the time period ID, his start time suddenly can know, the source code is as follows:
protected long calculateWindowStart(/*@Valid*/ long timeMillis) {
return timeMillis - timeMillis % windowLengthInMs;
}
Copy the codeSliding Windows for sliding and updating
Idx has been calculated previously, so we know which sample window to go to, so now there will be three situations, as follows:
- Old = array.get(idx); old = array.get(idx); old = array.get(idx);
if (old == null) {
// Create a time window
WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
if (array.compareAndSet(idx, null, window)) {
// Create a successful return window
return window;
} else{ Thread.yield(); }}Copy the code- In the second case, when the start time of the current sample period is found to be the same as the start time of the sample window under the IDX in the original sliding window, it indicates that the time period requested is still in this window, and the count should still be added in this window. You can continue to see the figure below. If a request is received between 50T and 60T, the sample window has been created, and certain data has been counted and is not outdated, the window can be directly returned. The source code is as follows
// If the start time of the current sample window is the same as that of the calculated sample window
// The two samples are the same window
else if (windowStart == old.windowStart()) {
return old;
}
Copy the code
- In the third case, the most critical case, there will be a window slide, as shown below.
As shown in the figure, when a request is made from 60T to 70T, after the above calculation, more than 60t is exactly divided by 10t per unit time interval until timeId is 6, which is mod the number of sample Windows in the sliding window to get 0, namely A0 sample window. The key finding, however, is that A0 is currently created at 30T-40T, which is the case with windowStart > old.windowStart(). What does that tell you, that the previous window is out of date, that the data in it is already a second old or more, Its internal statistics are no longer needed, so empty its internal data and respecify windowStart, which shows the situation shown in the figure, which means that the sliding window moves forward. The source code is as follows:
// If the start time of the current sample window is greater than the calculated start time of the sample window
// The calculated sample window is out of date and the original sample window needs to be replaced
else if (windowStart > old.windowStart()) {
if (updateLock.tryLock()) {
try {
return resetWindowTo(old, windowStart);
} finally{ updateLock.unlock(); }}else{ Thread.yield(); }}Copy the code3.2.4 Statistics and Maintenance
Above we have obtained the current request belongs to the sample window, the next is to update the sample window data, this is actually not difficult, the source code is as follows:
private final LeapArray<MetricBucket> data;
@Override
public void addPass(int count) {
// Get the sample window at the current time
WindowWrap<MetricBucket> wrap = data.currentWindow();
// Increase the number of requests passed
wrap.value().addPass(count);
}
Copy the codeThe value of the wrap is the MetricBucket, and the number of requests passed is increased by increasing the number of counters in the MetricBucket timer. The source code is as follows:
public MetricBucket add(MetricEvent event, long n) {
counters[event.ordinal()].add(n);
return this;
}
Copy the code4. To summarize
This article mainly introduces the sliding window for a QPS data storage and maintenance, then we will enter the source analysis of flowSlot, see how to use the information just counted for a flow limiting decision.