Implementation principle of Alibaba Sentinel sliding Window

In order to realize the functions of current limiting and fusing, the first problem to be solved is how to collect the service (resource) call information in real time. For example, if the current limiting width of an interface is set to 1W/ TPS, how to determine the current TPS first? Alibaba Sentinel uses sliding window to realize real-time data statistics.

Warm tip: if you are not interested in the source code, you can skip to the end of the article and take a look at the design schematic of the sliding window before deciding whether you need to read the source code.

This program recording

• • 1. Core class diagram of sliding window
  • 2. Implementation principle of sliding window
  • • • 2.1 ArrayMetric
      • 2.2 LongAdder
      • • 2.2.1 Class diagram and core attributes
        • 2.2.2 currentWindow (), rounding
        • 2.2.3 isWindowDeprecated (), rounding
        • 2.2.4 getPreviousWindow (), rounding
        • 2.2.5 Sliding Window ICONS
  • 3, OccupiableBucketLeapArray explanation
  • • • 3.2 Constructors
      • 3.3 newEmptyBucket
      • 3.4 resetWindowTo
      • 3.5 addWaiting

1. Core class diagram of sliding window

Let’s first make a brief introduction to the core class above, focusing on the role and core attributes of the core class (focus on exploring its core data structure).

• Metric metrics collect core interfaces that define the number of successes, exceptions, blocks, TPS, and response time in a sliding window.
• ArrayMetric sliding window core implementation class.
• LeapArray sliding window top-level data structure, containing window data one by one.
• WindowWrap A wrapper class for each sliding window whose internal data structures are represented by MetricBucket.
• MetricBucket Measures buckets, such as number of passes, number of blocks, number of exceptions, number of successes, and response time, that have passed the future quota (number of preempts for the next sliding window).
• MetricEvent Indicator types, such as number of passes, number of blocks, number of exceptions, number of successes, and response time.

2. Implementation principle of sliding window

2.1 ArrayMetric

The entry class for the sliding window is ArrayMetric, and let’s take a look at its core code.

private final LeapArray<MetricBucket> data;   / / @ 1
public ArrayMetric(int sampleCount, int intervalInMs) {    / / @ 2
    this.data = new OccupiableBucketLeapArray(sampleCount, intervalInMs);
}
public ArrayMetric(int sampleCount, int intervalInMs, boolean enableOccupy) {   / / @ 3
	if (enableOccupy) {
		this.data = new OccupiableBucketLeapArray(sampleCount, intervalInMs);
	} else {
		this.data = newBucketLeapArray(sampleCount, intervalInMs); }}Copy the code

Code @1: The unique property of the ArrayMetric class, used to store data for each window, which is the focus of our next exploration.

@2, @3 This class provides two constructors with core arguments:

• Int intervalInMs indicates a collection interval, such as 1 second, 1 minute.
• Int sampleCount Number of samples sampled in a collection interval. Default is 2. For example, when intervalInMs = 1000, a collection interval contains two equal intervals, one of which is the sliding window.
• Boolean enableOccupy whether to allow preemption, namely the current timestamp already reach the limit, if you can take the next time the capacity of the window, corresponding LeapArray two implementation class here, if allowed to grab, OccupiableBucketLeapArray, Otherwise, BucketLeapArray.

Note that LeapArray’s generic class is MetricBucket, which stands for MetricBucket. You can think of a MetricBucket object as storing all metrics in a sampling time period, such as the number of passes, blocks, exceptions, successes, and response times in an abstract time period. The secret of its implementation is in LongAdder. This paper will not introduce this class in detail at first, and the subsequent articles will separately explore its implementation principle.

This time, instead of looking at the subclasses, let’s go the other way and look at the parent class.

2.2 LongAdder

2.2.1 Class diagram and core attributes

The core attributes of LeapArray are as follows:

• Int windowLengthInMs Interval for each window, in milliseconds.
• Int sampleCount number of samples, the number of sliding Windows contained in a statistical interval. In the same intervalInMs situation, the more sampleCount, the more accurate the sampled statistics, and the more memory required.
• Int intervalInMs Indicates a statistical interval.
• AtomicReferenceArray
  
  > array An array of sliding Windows at a statistical interval, where a sliding window is represented by a WindowWrap< MetricBucket >.
  

The meanings of the attributes above are derived from their constructors. See the constructors.

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.sampleCount = sampleCount;
    this.array = new AtomicReferenceArray<>(sampleCount);
}
Copy the code

Let’s move on to the LeapArray method and dive into the implementation details of sliding Windows.

2.2.2 currentWindow (), rounding

public WindowWrap<T> currentWindow(long timeMillis) { 
	if (timeMillis < 0) {
		return null;
	}
	int idx = calculateTimeIdx(timeMillis);  / / @ 1
	long windowStart = calculateWindowStart(timeMillis); / / @ 2
	while (true) { // An infinite loop is used to find the current time window. This loop is needed because multiple threads may be fetching the current time window.
		WindowWrap<T> old = array.get(idx);  / / @ 3
       		 if (old == null) {  / / @ 4
			WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
           		 if (array.compareAndSet(idx, null, window)) {  / / @ 5
				return window;
           		 } else{ Thread.yield(); }}else if (windowStart == old.windowStart()) { / / @ 6
			return old;
       		 } else if (windowStart > old.windowStart()) {  / / @ 7
			if (updateLock.tryLock()) {
               			 try {
					return resetWindowTo(old, windowStart);
                		} finally{ updateLock.unlock(); }}else{ Thread.yield(); }}else if (windowStart < old.windowStart()) { / / @ 8
            		return newWindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis)); }}}Copy the code

2.2.3 isWindowDeprecated (), rounding

Next, let’s look at the window expiration mechanism.

public boolean isWindowDeprecated(/*@NonNull*/ WindowWrap<T> windowWrap) {
    return isWindowDeprecated(TimeUtil.currentTimeMillis(), windowWrap);
}
public boolean isWindowDeprecated(long time, WindowWrap<T> windowWrap) {
	return time - windowWrap.windowStart() > intervalInMs;
}
Copy the code

The validity of the sliding window is judged by the fact that when the interval between the system time and the start timestamp of the sliding window is greater than one collection time, it means that the sliding window has expired. That is, starting from the current window, usually contains valid Windows for sampleCount valid sliding Windows.

2.2.4 getPreviousWindow (), rounding

public WindowWrap<T> getPreviousWindow(long timeMillis) {
    if (timeMillis < 0) {
		return null;
    }
    int idx = calculateTimeIdx(timeMillis - windowLengthInMs); / / @ 1
    timeMillis = timeMillis - windowLengthInMs;
    WindowWrap<T> wrap = array.get(idx);
    if (wrap == null || isWindowDeprecated(wrap)) {                 / / @ 2
		return null;
    }
   if (wrap.windowStart() + windowLengthInMs < (timeMillis)) {   / / @ 3
		return null;
    }
    return wrap;
}
Copy the code

2.2.5 Sliding Window ICONS

After the above analysis, we should be able to draw the implementation schematic of the sliding window implementation, although there is a core method (resetWindowTo) that has not been analyzed.



Next, a simple illustration of the above figure: The following example uses a sampling interval of 1 s and a sampling number of 2.

First, a LeapArray will be created, and an array with element 2 will be held internally. At the beginning of collection, the first and second subscripts of the array will be null. For example, the current time is located to subscript 0 through calculateTimeIdx, and there is no sliding window, a sliding window will be created. Then the sliding window will collect indicators, and a second sampling window will be created after 500ms of 1s.

Then the time will advance 1s, and it will locate at the subscript 0 again, but it will not be empty at this time, because the data collected in the last second will be discarded (MetricBucket value), and then reset the windowStart of the window. This is where the resetWindowTo method comes in.

Appeared in the ArrayMetric constructor LeapArray BucketLeapArray and OccupiableBucketLeapArray two implementations of the type.

Including BucketLeapArray is simpler, not in-depth study, here we will discuss the next OccupiableBucketLeapArray implementation principle, namely support preemption “token” in the future.

3, OccupiableBucketLeapArray explanation

3.2 Constructors

public OccupiableBucketLeapArray(int sampleCount, int intervalInMs) {
    super(sampleCount, intervalInMs);
    this.borrowArray = new FutureBucketLeapArray(sampleCount, intervalInMs);
}
Copy the code

As can be seen from the constructor, not only is a regular LeapArray created, corresponding to a collection cycle, but also a borrowArray will be created, which will also contain a collection cycle.

3.3 newEmptyBucket

public MetricBucket newEmptyBucket(long time) {
	MetricBucket newBucket = new MetricBucket();   / / @ 1
	MetricBucket borrowBucket = borrowArray.getWindowValue(time);  / / @ 2
	if(borrowBucket ! =null) {  
		newBucket.reset(borrowBucket);  
	}
	return newBucket;
}
Copy the code

3.4 resetWindowTo

protected WindowWrap<MetricBucket> resetWindowTo(WindowWrap<MetricBucket> w, long time) {      
    w.resetTo(time);
    MetricBucket borrowBucket = borrowArray.getWindowValue(time);
    if(borrowBucket ! =null) {
        w.value().reset();
        w.value().addPass((int)borrowBucket.pass());
    } else {
        w.value().reset();
    }
    return w;
}
Copy the code

When a sliding window is out of date, it needs to be reset. This is the same idea as newEmptyBucket’s core idea: if there is a borrowed situation, it needs to be reset with a license that has been used in the future.

3.5 addWaiting

public void addWaiting(long time, int acquireCount) {
	WindowWrap<MetricBucket> window = borrowArray.currentWindow(time);
	window.value().add(MetricEvent.PASS, acquireCount);
}
Copy the code