RateLimiter analysis of current limiting series (I): smoothburst
RateLimiter analysis of current limiting series (2): SmoothWarmingUp
1, Introduction
SmoothWarmingUp is another current limiting tool provided by guava. Different from smoothburst, SmoothWarmingUp adds a preheating process on the basis of fixed speed, which can better deal with sudden traffic. In addition, it is slower to provide traffic during initialization and small traffic, which is also in line with the actual application scenario.
This implements the following function:
^ throttling
|
3*stable + /
interval | /.
(cold) | / .
| / . <-- "warmup period" is the area of the trapezoid between
2*stable + / . halfPermits and maxPermits
interval | / .
| / .
| / .
stable +----------/ WARM . }
interval | . UP . } <-- this rectangle (from 0 to maxPermits, and
| . PERIOD. } height == stableInterval) defines the cooldown period,
| . . } and we want cooldownPeriod == warmupPeriod
|---------------------------------> storedPermits
(halfPermits) (maxPermits)
In the annotation of SmoothWarmingUp class, the principle is also described. As shown in the figure above, there is a certain mathematical relationship between the speed control interval of traffic and the number of stored tokens
- The number of tokens storedPermits has two key values: threshold and Max, and interval also has two key values: stable and cold. When storedPermits is between 0 – threshold, the interval is fixed to stable; When storepermissions is between threshold – max, the interval increases evenly.
- The process from max to threshold is called warm up, and the process from 0 to max is called cool down. Warm up is the token consumption process, and cool dowm is the token generation process.
- According to the calculus calculation, the time required for the warming up stage is the area of the trapezoidal part in the figure above, which is called the warm up period. warmUpPeriod = (stable+cold) * (max-threshold) / 2
- There are two hard codes in this class:
(1) coldInterval = 3 * stableInterval, then warmupperiod = 2 * stable * (max threshold)
(2) The rectangular area (during constant rate) is half of the trapezoid, that is, stable * threshold = warmUpPeriod/2, and max = 2 * threshold can be obtained. So in the figure above, halfpermissions is used to represent threshold.
Finally, warmUpPeriod = stable * max. - The cooldown time is from 0 to maxpermissions, and height = = stableinterval. At this time, coolDownPeriod=warmUpPeriod. This is also the purpose of the above hard coding.
2, Create and initialize
1. Member variables
private final long warmupPeriodMicros; private double slope; private double halfPermits;
This article only introduces the member variables defined in SmoothWarmingUp. The member variables inherited from the parent class have been mentioned in the previous introduction to smoothburst. You can review what you don't know.
warmupPeriodMicros as mentioned in the introduction, the time required for the warmingUp process is the trapezoidal area in the introduction diagram.
Half permissions, as mentioned in the introduction, is a threshold for flow rate control
Slope represents the change rate of the interval from halfpermits to maxpermits, that is, the slope of the trapezoidal slope in the profile. slope = (maxPermits - halfPermits) / (coldInterval - stableInterval)
2. RateLimiter#create
public static RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) {
checkArgument(warmupPeriod >= 0, "warmupPeriod must not be negative: %s", warmupPeriod);
return create(SleepingStopwatch.createFromSystemTimer(), permitsPerSecond, warmupPeriod, unit);
}
static RateLimiter create(
SleepingStopwatch stopwatch, double permitsPerSecond, long warmupPeriod, TimeUnit unit) {
RateLimiter rateLimiter = new SmoothWarmingUp(stopwatch, warmupPeriod, unit);
rateLimiter.setRate(permitsPerSecond);
return rateLimiter;
}
As you can see, basically the same as the creation of smoothburst, call the constructor and set the rate.
3. SmoothWarmingUp#doSet
@Override
final void doSetRate(double permitsPerSecond, long nowMicros) {
resync(nowMicros);
double stableIntervalMicros = SECONDS.toMicros(1L) / permitsPerSecond;
this.stableIntervalMicros = stableIntervalMicros;
doSetRate(permitsPerSecond, stableIntervalMicros);
}
@Override
void doSetRate(double permitsPerSecond, double stableIntervalMicros) {
double oldMaxPermits = maxPermits;
maxPermits = warmupPeriodMicros / stableIntervalMicros;
halfPermits = maxPermits / 2.0;
// Stable interval is x, cold is 3x, so on average it's 2x. Double the time -> halve the rate
double coldIntervalMicros = stableIntervalMicros * 3.0;
slope = (coldIntervalMicros - stableIntervalMicros) / halfPermits;
if (oldMaxPermits == Double.POSITIVE_INFINITY) {
// if we don't special-case this, we would get storedPermits == NaN, below
storedPermits = 0.0;
} else {
storedPermits = (oldMaxPermits == 0.0)
? maxPermits // initial state is cold
: storedPermits * maxPermits / oldMaxPermits;
}
}
As you can see, the overall logic is,
- Set the value of the member variable according to the mathematical relationship described in the previous introduction
- Compared with smoothburst, the number of inventory tokens storePermits is first calculated to the current time according to the original rate (resync method), and then scaled equally. However, for initialization, storepermissions is initialized to maxpermissions instead of 0. At this time, the traffic processing is slow and meets the actual needs.
3, Current limiting judgment
We ignore what has been introduced in smoothburst's analysis and go directly to the difference between the two.
@Override
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
//Update inventory token
resync(nowMicros);
long returnValue = nextFreeTicketMicros;
//The token in the inventory that needs to be consumed by this request
double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
//Insufficient tokens need to be prepaid
double freshPermits = requiredPermits - storedPermitsToSpend;
//Time required for advance
long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
+ (long) (freshPermits * stableIntervalMicros);
//Update inventory token and corresponding calculated time
this.nextFreeTicketMicros = nextFreeTicketMicros + waitMicros;
this.storedPermits -= storedPermitsToSpend;
//It can be seen that even if the token of this request is insufficient, the time of advance token will not affect this request, and wisdom will affect subsequent requests
return returnValue;
}
You can see that the actual difference lies in the storedPermitsToWaitTime method. This method is fixed to 0 in smoothburst, that is, it does not take time, but it is not in SmoothWarmingUp.
/**
* Translates a specified portion of our currently stored permits which we want to
* spend/acquire, into a throttling time. Conceptually, this evaluates the integral
* of the underlying function we use, for the range of
* [(storedPermits - permitsToTake), storedPermits].
*
* <p>This always holds: {@code 0 <= permitsToTake <= storedPermits}
*/
abstract long storedPermitsToWaitTime(double storedPermits, double permitsToTake);
You can first look at the notes to understand the function of the method: the current limiting effect is achieved by consuming the time of inventory tokens.
@Override
long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {
//The partial token to the right of halfpermissions
double availablePermitsAboveHalf = storedPermits - halfPermits;
long micros = 0;
// measuring the integral on the right part of the function (the climbing line)
if (availablePermitsAboveHalf > 0.0) {
//Some tokens to be consumed on the right side of halfpermissions
double permitsAboveHalfToTake = min(availablePermitsAboveHalf, permitsToTake);
//The time required for permitsAboveHalfToTake is actually the calculation of trapezoidal area
micros = (long) (permitsAboveHalfToTake * (permitsToTime(availablePermitsAboveHalf)
+ permitsToTime(availablePermitsAboveHalf - permitsAboveHalfToTake)) / 2.0);
//All that's left is the token that needs to be consumed on the left side of halfpermissions
permitsToTake -= permitsAboveHalfToTake;
}
// measuring the integral on the left part of the function (the horizontal line)
//The token on the left of halfPermits consumes the time required to calculate the rectangular area
micros += (stableIntervalMicros * permitsToTake);
return micros;
}
private double permitsToTime(double permits) {
return stableIntervalMicros + permits * slope;
}
storedPermits is the number of tokens in stock. permitsToTake is the number of tokens that need to be consumed from stock. According to the previous introduction, the consumption speed of halfPermits is different
stable + /.
interval | / .
| / .
| / .
| / .
| / * .
| / * .
| / * .
stable +----------/ * .
interval | * . * .
| * . * .
| * . * ·
| * . * .
| * . * .
| * . * .
| * . * .
|---------------------------------> storedPermits
(halfPermits) (maxPermits)
A B
On the original icon, assuming that the number of tokens needs to be consumed from B to a, that is, B-A=permitsToTake, the graphic area between a and B is the time we need to calculate
Then, the calculation method comes out. It is divided into two parts. The left side of halfPermits is a rectangle and the right side is a trapezoid
(1) Trapezoidal part
B = storePermits，
Trapezoidal height: storepermissions - halfpermissions,
Upper bottom (long part): stableIntervalMicros + (storepermissions - halfpermissions) * slope;
Bottom (short part): stable intervalmicros
Final: S (trapezoid) = 0.5 * (stableIntervalMicros + (storepermissions - halfpermissions) * slope + stableIntervalMicros) * (storepermissions - halfpermissions)
That is, in the code
micros = (long) (permitsAboveHalfToTake * (permitsToTime(availablePermitsAboveHalf)
+ permitsToTime(availablePermitsAboveHalf - permitsAboveHalfToTake)) / 2.0);
(2) Rectangular section: remaining storepermissions * stableintervalmicros
This is the logic for calculating the token time consumed by storedPermitsToWaitTime.
4, Summary
Smoothburst has no time for token consumption. As long as there are enough tokens in stock, the current limiter will not have any delay effect on traffic.
Therefore, for the scenario with stable traffic, smoothburst can meet the needs and ensure that the traffic passes at the specified rate (1/stableInterval per second). However, in the case of traffic fluctuation, for example, in extreme cases, the inventory reaches maxpermissions. Once there is sudden traffic at this time, the traffic passing through the log in one second will be: maxpermissions + 1/stableInterval, which will put great pressure on the service and may be unbearable,
SmoothWarmingUp is different. Not only does it take time to generate tokens, but even if there are enough tokens, it also takes a certain time for token consumption. In this way, it is officially guaranteed that in the case of sudden traffic, there will be no scenario in which a large amount of traffic passes through the service at one time.
5, Parameter extraction of version difference coldFactor
This analysis of DateLimiter, including smoothburst and SmoothWarmingUp, is based on the version of guava18. Although the principle and logic of subsequent versions remain unchanged, there are some differences in code. The main differences are:
coldInterval = 3 * stableInteravl is no longer hard coded in SmoothWarmingUp, but extracts the magnification as a member variable coldFactor
Therefore, there will be some subtle differences in code implementation. However, the setting of this member variable is not provided externally, but hard coded as 3 in the create method of the creation and initialization of SmoothWarmingUp provided externally in DateLimter.
The main differences are as follows:
- The token threshold is no longer half the half permissions of maxpermissions, so we rename it threaholdpermissions to define this threshold.
thresholdPermits = 0.5 * warmupPeriodMicros / stableIntervalMicros;
maxPermits =
thresholdPermits + 2.0 * warmupPeriodMicros / (stableIntervalMicros + coldIntervalMicros);
- stableInterval * maxpermissions = warmupperiod is no longer valid. In order to ensure coolDownPeriod=warmUpPeriod, the generation rate of inventory tokens is no longer stableinval, but warmupperiod / maxpermissions.
Embodied in the resync method, the token generation rate is extracted as a separate method coolDownIntervalMicros().
void resync(long nowMicros) {
// if nextFreeTicket is in the past, resync to now
if (nowMicros > nextFreeTicketMicros) {
double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
storedPermits = min(maxPermits, storedPermits + newPermits);
nextFreeTicketMicros = nowMicros;
}
}
/**
* Returns the number of microseconds during cool down that we have to wait to get a new permit.
*/
abstract double coolDownIntervalMicros();
@Override
double coolDownIntervalMicros() {
return warmupPeriodMicros / maxPermits;
}