StatisticSlot There are mainly two types of data ：
- Number of threads
- Number of requests , That is to say QPS
It is relatively simple to count the number of threads , Through internal maintenance LongAdder Statistics of the current number of threads , Add 1, Thread execution completion 1, To get the number of threads .
about QPS The statistics of are more complicated , The principle of sliding window is used . Now let's focus on the details of the implementation .
Bucket
Sentinel Use Bucket Count the index data within a window , These metrics include the total number of requests 、 The total number of successes 、 Total exceptions 、 Total time 、 Minimum time 、 Maximum time consumption, etc , And one Bucket It can be a record 1s The data in , It can also be 10ms The data in , This length of time is called window time .
public class MetricBucket {
/**
* Store the count of each event , For example, the total number of exceptions 、 Total requests, etc
*/
private final LongAdder[] counters;
/**
* The minimum time spent in this event
*/
private volatile long minRt;
}Bucket The index data recorded over a period of time is a LongAdder Array ,LongAdder Ensure the atomicity of data modification , And the performance is better AtomicInteger Perform better . Each element of the array records the total number of requests for a time window 、 Number of abnormal 、 Time consuming .
Sentinel Using enumerated types MetricEvent Of ordinal Attribute as subscript , When you need to get Bucket Record the total number of successful requests or exceptions 、 Total request processing time , Depending on the type of event (MetricEvent) from Bucket Of LongAdder Get the corresponding... From the array LongAdder, And call sum Method to get ：
// Suppose the event is MetricEvent.SUCCESS
public long get(MetricEvent event) {
// MetricEvent.SUCCESS.ordinal() by 1
return counters[event.ordinal()].sum();
}When the number of requests needs to be recorded, the operation is as follows ：
// Suppose the event is MetricEvent.RT
public void add(MetricEvent event, long n) {
// MetricEvent.RT.ordinal() by 2
counters[event.ordinal()].add(n);
}
The sliding window
We want to know the number of successful requests processed by an interface per second ( success QPS)、 The average time taken for a request is (avg rt), We just need to control Bucket Just count the index data of one second of plutonium .Sentinel How to achieve it ？ It defines a Bucket Array , Locate the subscript of the array according to the timestamp . Suppose we need to count every 1 Number of requests processed in seconds , And only need to save the data of the last minute , that Bucket The size of the array can be set to 60, Every Bucket Of windowLengthInMs( Window time ) Size is 1000ms.
We can't and certainly don't need unlimited storage Bucket, If you only need to keep the data for one minute , Then we can put Bucket The size of is set to 60 And recycle , Avoid frequent creation Bucket. How to locate in this case Bucket Well ？ The method is to remove the millisecond part of the current timestamp and wait for the current second , Then take the remainder of the obtained seconds and the length of the array , You can get the current time window Bucket Position in the array .
For example, given a timestamp, calculate the array index ：
private int calculateTimeIdx(long timeMillis) {
/**
* Assume that the current timestamp is 1577017699235
* windowLengthInMs by 1000 millisecond （1 second ）
* be
* Turn milliseconds into seconds => 1577017699
* Then the length of the array is remainder => Index mapped to array
* Remainder is to recycle arrays
*/
long timeId = timeMillis / windowLengthInMs;
return (int) (timeId % array.length());
}
Because the array is recycled , The current timestamp and the timestamp before one minute and the timestamp after one minute will be mapped to the same one in the array Bucket, therefore , You must be able to judge what you have achieved Bucket Whether to count the indicator data in the current time window , This requires that each element of the array be stored Bucet The start timestamp of the time window . What about the starting time ？
protected long calculateWindowStart(long timeMillis) {
/**
* Suppose the window size is 1000 millisecond , That is, each element of the array stores 1 Second statistics
* timeMillis % windowLengthInMs Is to get the millisecond part
* timeMillis - Number of milliseconds = Second part
* This gives the start timestamp per second
*/
return timeMillis - timeMillis % windowLengthInMs;
}
WindowWrap
because Bucket Time window information is not saved by itself , therefore Sentinel to Bucket Add a packaging class WindowWrap, Used to record Bcuket Time window of .
public class WindowWrap<T> {
/**
* Window length （ millisecond ）
*/
private final long windowLengthInMs;
/**
* Start timestamp （ millisecond ）
*/
private long windowStart;
/**
* The content of the time window , stay WindowWrap This value is represented by generics in ,
* But it's actually MetricBucket class
*/
private T value;
public WindowWrap(long windowLengthInMs, long windowStart, T value) {
this.windowLengthInMs = windowLengthInMs;
this.windowStart = windowStart;
this.value = value;
}
}We just need to know the start time and the size of the window , Give a timestamp , You can know whether the timestamp is Bucket Window time .
/**
* Check whether the given timestamp is currently bucket in .
*
* @param timeMillis Time stamp , millisecond
* @return
*/
public boolean isTimeInWindow(long timeMillis) {
return windowStart <= timeMillis && timeMillis < windowStart + windowLengthInMs;
}Locate by timestamp Bucket
Bucket Used for statistics of various index data ,WindowWrap Used to record Bucket Time window information , Record the start time and size of the window ,WindowWrap An array is a sliding window .
When a request is received , An array index can be calculated according to the requested timestamp , From the sliding window (WindowWrap) Get one of WindowWrap, To obtain WindowWrap Packaged Bucket, call Bucket Of add Method to record the corresponding event .
/**
* Get from timestamp bucket
*
* @param timeMillis Time stamp （ millisecond ）
* @return If time is valid , Then the current bucket item is displayed at the provided timestamp ; If the time is invalid , Is empty
*/
public WindowWrap<T> currentWindow(long timeMillis) {
if (timeMillis < 0) {
return null;
}
// Get the array index to which the timestamp is mapped
int idx = calculateTimeIdx(timeMillis);
// Calculation bucket The start time of the time window
long windowStart = calculateWindowStart(timeMillis);
// Get... From the array bucket
while (true) {
WindowWrap<T> old = array.get(idx);
// Usually when the project starts , Time has not reached a cycle , The array is not full , There is no reuse stage , So the array element may be empty
if (old == null) {
// Create a new bucket, And create a bucket Wrappers
WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
// cas write in , Make sure threads are safe , Expect the element of the array subscript to be empty , Otherwise, do not write , It's reuse
if (array.compareAndSet(idx, null, window)) {
return window;
} else {
Thread.yield();
}
}
// If WindowWrap Of windowStart It is exactly the start time of the time window calculated by the current timestamp , Is what we want bucket
else if (windowStart == old.windowStart()) {
return old;
}
// Reuse the old bucket
else if (windowStart > old.windowStart()) {
if (updateLock.tryLock()) {
try {
// Reset bucket, And designate bucket The start time of the new time window
return resetWindowTo(old, windowStart);
} finally {
updateLock.unlock();
}
} else {
Thread.yield();
}
}
// Calculated current bucket The start time of the time window is greater than that currently stored in the array bucket The start time of the time window is still small ,
// Go straight back to an empty bucket Just go
else if (windowStart < old.windowStart()) {
return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
}
}
}The above code calculates the current time window through the current timestamp Bucket(new Bucket) Index in array , To stay Bucket The start time of the time window , Get from the array by index Bucket(old bucket).
- When the index does not exist Bucket when , Create a new Bucket, And thread safe write to the index , And then Bucket return
- When old Bucket Isn't empty , And old Bucket The start time of the time window is the same as the current calculated new Bucket The start time of the time window is equal , Then Bucket Is what we are looking for Bucket, Go straight back to
- When calculating new Bucket The start time of the time window is greater than that stored in the current array old Bucket The start time of the time window , You can reuse this old Bucket, Reset with thread safety
- When we calculate new Bucket The start time of the time window is less than that stored in the current array old Bucket The start time of the time window , Go straight back to an empty Bucket.
How to get the previous one of the current timestamp Bucket Well , The answer is to calculate the current... Based on the current timestamp Bucket Time window start time , Use current Bucket The start time of the time window minus the size of a window can locate the previous Bucket 了 .
Need to pay attention to when , Arrays are recycled , So at the moment Bucket Compared with the calculated Bucket It may differ by one sliding window or more than one , So it needs to be based on Bucket The start time of the time window of is compared with the current timestamp , If you cross a cycle, it is invalid .
summary
- WindowWrap For packing Bucket, With Bucket Together to create
- WindowWrap Array implementation sliding window ,Bucket Only responsible for statistics of various index data ,WindowWrap Used to record Bucket Time window information
- location Bucket It's actually positioning WindowWrap, Get WindowWrap You can get Bucket
![[PSO] Based on PSO particle swarm optimization, matlab simulation of the calculation of the lowest transportation cost of goods at material points, including transportation costs, agent conversion cos](/img/41/27ce3741ef29e87c0f3b954fdef87a.png)
