StatisticSlot mainly counts two types of data:
- Number of threads
- Number of requests, i.e. QPS
The statistics of the number of threads is relatively simple. It is the statistics of the current number of threads through the internal maintenance of LongAdder. Add 1 for each thread, and subtract 1 after thread execution, so as to obtain the number of threads.
The statistics of QPS are more complex, in which the principle of sliding window is used. Now let's focus on the details of the implementation.
Bucket
Sentinel uses a Bucket to count various indicator data within a window. These indicator data include total requests, total successes, total exceptions, total time, minimum time, maximum time, etc. a Bucket can record data within 1s or 10ms. This time length is called window time.
public class MetricBucket {
/**
* Store the count of each event, such as the total number of exceptions, the total number of requests, etc
*/
private final LongAdder[] counters;
/**
* Minimum time spent in this event
*/
private volatile long minRt;
}Bucket records various indicator data over a period of time using a LongAdder array. LongAdder ensures the atomicity of data modification, and its performance is better than AtomicInteger. Each element of the array records the total number of requests, different constants and partial time-consuming of a time window.
Sentinel uses the ordinal attribute of the enumeration type MetricEvent as the subscript. When it is necessary to obtain the total number of successful requests or exceptions and the total request processing time of the Bucket record, it can obtain the corresponding LongAdder from the LongAdder array of the Bucket according to the event type (MetricEvent) and call the sum method to obtain:
// Suppose the event is metricevent SUCCESS
public long get(MetricEvent event) {
// MetricEvent.SUCCESS.ordinal() is 1
return counters[event.ordinal()].sum();
}When the number of requests needs to be recorded, the operations are as follows:
// Suppose the event is metricevent RT
public void add(MetricEvent event, long n) {
// MetricEvent.RT.ordinal() is 2
counters[event.ordinal()].add(n);
}
sliding window
We want to know the number of successful requests processed per second (successful QPS) and the average request time (avg rt) of an interface. We only need to control the Bucket to count the indicator data of plutonium per second. How is Sentinel implemented? It defines a Bucket array and locates the subscript of the array according to the timestamp. Assuming that we need to count the number of requests processed every 1 second and only need to save the data of the last minute, the size of Bucket array can be set to 60, and the size of windowlengthinms (window time) of each Bucket is 1000ms.
We can't and certainly don't need to store buckets indefinitely. If we only need to keep data for one minute, we can set the Bucket size to 60 and recycle it to avoid frequent Bucket creation. How to locate a Bucket in this case? The method is to remove the millisecond part of the current timestamp, wait for the current second, and then take the remainder of the obtained second and the length of the array to get the position of the Bucket of the current time window in the array.
For example, calculate the array index for a given timestamp:
private int calculateTimeIdx(long timeMillis) {
/**
* Assume the current timestamp is 1577017699235
* windowLengthInMs 1000 milliseconds (1 second)
* be
* Convert milliseconds to seconds = > 1577017699
* Then remainder the array len gt h = > map to the index of the array
* Remainder is used to recycle arrays
*/
long timeId = timeMillis / windowLengthInMs;
return (int) (timeId % array.length());
}
Because the array is used circularly, the current timestamp, the timestamp before one minute and the timestamp after one minute will be mapped to the same Bucket in the array. Therefore, it must be able to judge whether the obtained Bucket is the indicator data in the current time window. Therefore, each element of the array must store the start timestamp of the Bucket time window. What about the start time?
protected long calculateWindowStart(long timeMillis) {
/**
* Suppose the window size is 1000 milliseconds, that is, each element of the array stores statistics for 1 second
* timeMillis % windowLengthInMs Is to get the millisecond part
* timeMillis - Milliseconds = second part
* This gives the start timestamp per second
*/
return timeMillis - timeMillis % windowLengthInMs;
}
WindowWrap
Because the Bucket itself does not save the time window information, Sentinel adds a wrapper class WindowWrap to the Bucket to record the time window of the bcucket.
public class WindowWrap<T> {
/**
* Window length (MS)
*/
private final long windowLengthInMs;
/**
* Start timestamp (MS)
*/
private long windowStart;
/**
* The content of the time window is generically represented in WindowWrap,
* But it's actually the MetricBucket class
*/
private T value;
public WindowWrap(long windowLengthInMs, long windowStart, T value) {
this.windowLengthInMs = windowLengthInMs;
this.windowStart = windowStart;
this.value = value;
}
}As long as we know the start time and window time size of the window, given a timestamp, we can know whether the timestamp is within the window time of the Bucket.
/**
* Check whether the given timestamp is in the current bucket.
*
* @param timeMillis Timestamp, MS
* @return
*/
public boolean isTimeInWindow(long timeMillis) {
return windowStart <= timeMillis && timeMillis < windowStart + windowLengthInMs;
}Locate the Bucket by timestamp
Bucket is used to count various indicator data. WindowWrap is used to record the time window information of bucket, the start time of window and the size of window. WindowWrap array is a sliding window.
When a request is received, an array index can be calculated according to the time stamp of the request, and a WindowWrap can be obtained from the sliding window (WindowWrap), so as to obtain the Bucket wrapped by WindowWrap, and call the add method of the Bucket to record the corresponding events.
/**
* Get bucket based on Timestamp
*
* @param timeMillis Timestamp (MS)
* @return If the time is valid, the current bucket item is displayed at the provided timestamp; Null if the time is invalid
*/
public WindowWrap<T> currentWindow(long timeMillis) {
if (timeMillis < 0) {
return null;
}
// Gets the array index to which the timestamp is mapped
int idx = calculateTimeIdx(timeMillis);
// Calculate the start time of the bucket time window
long windowStart = calculateWindowStart(timeMillis);
// Get bucket from array
while (true) {
WindowWrap<T> old = array.get(idx);
// Generally, when the project is started, the time does not reach a cycle, the array is not fully stored, and the reuse stage is not reached, so the array elements may be empty
if (old == null) {
// Create a new bucket and create a bucket wrapper
WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
// cas writing ensures thread safety. It is expected that the elements of the array subscript are empty. Otherwise, it will not be written, but reused
if (array.compareAndSet(idx, null, window)) {
return window;
} else {
Thread.yield();
}
}
// If the windowStart of WindowWrap is exactly the start time of the time window calculated by the current timestamp, it is the bucket we want
else if (windowStart == old.windowStart()) {
return old;
}
// Reuse old bucket s
else if (windowStart > old.windowStart()) {
if (updateLock.tryLock()) {
try {
// Reset the bucket and specify the start time of the new time window of the bucket
return resetWindowTo(old, windowStart);
} finally {
updateLock.unlock();
}
} else {
Thread.yield();
}
}
// The calculated start time of the current bucket time window is smaller than that of the bucket currently stored in the array,
// Just return an empty bucket directly
else if (windowStart < old.windowStart()) {
return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
}
}
}
protected WindowWrap<MetricBucket> resetWindowTo(WindowWrap<MetricBucket> w, long time) {
// Update the start time and reset value.
// Reset windowStart
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;
}The above code calculates the index of the Bucket(new Bucket) of the current time window in the array through the current timestamp, and obtains the Bucket(old bucket) from the array through the index based on the start time of the Bucket time window.
- When there is no Bucket in the index, create a new Bucket, write it to the index thread safely, and then return the Bucket
- When the old Bucket is not empty and the start time of the old Bucket time window is equal to the start time of the currently calculated new Bucket time window, the Bucket is the Bucket to be found and returned directly
- When the start time of the calculated new Bucket time window is greater than the start time of the old Bucket time window stored in the current array, the old Bucket can be reused for thread safe reset
- When the calculated start time of the new Bucket time window is less than the start time of the old Bucket time window stored in the current array, an empty Bucket is returned directly.
How to obtain the previous Bucket of the current timestamp? The answer is to calculate the time window start time of the current Bucket according to the current timestamp. The previous Bucket can be located by subtracting a window size from the time window start time of the current Bucket.
It should be noted that the array is used circularly, so the current Bucket and the calculated Bucket may differ by one or more sliding windows. Therefore, it is necessary to compare the start time of the Bucket window with the current timestamp. If it spans a cycle, it will be invalid.
summary
- WindowWrap is used to wrap a Bucket and is created with the Bucket
- WindowWrap array realizes sliding window. Bucket is only responsible for statistics of various indicator data. WindowWrap is used to record the time window information of bucket
- Locating a Bucket is actually locating WindowWrap. When you get WindowWrap, you can get the Bucket