In the first and second articles, the principle of Guava token bucket algorithm is introduced respectively, and the SmothBursty current limiter of token is produced at a fixed rate. But in a real environment, if you want to be in the initial stage or a while system is called again, have a preheating process, which starts in the production of token rate slower, and then gradually accelerated, after preheating stage to the normal production rate, just like the vehicle start-up phase, starting from 1 first, gradually accelerated, band 2 and 3 until the fastest 6 files.
Ratelimite.java provides an implementation of this algorithm.
FIG. 1
The implementation class it returns is SmoothWarmingUp, the embedded class in SmoothRateLimiter. Java.
SmoothWarmingUp is a SmoothWarmingUp SmoothWarmingUp.
Figure 2
The X-axis represents the number of tokens stored in the token bucket, and the Y-axis represents the rate of flow limiting, in unit of the generation rate of a token. X*Y represents the rectangular area enclosed by the coordinate axes, i.e. (token production rate) * (token quantity). What does it mean? Yes, it represents how long it takes to produce n tokens, which is calculated using points. The ladder-shaped area on the right represents the total token production time in the warm-up area, while the rectangular area on the lower left represents the token production time in the stable period. Let’s use a concrete example to illustrate.
FIG. 3
Here 2.0 stands for QPS, 4000 for warmup of 4 seconds, and 3.0 for coldFactor, so
Stable Interval =1/QPS=1/2=0.5 seconds =500 milliseconds,
Coldinterval =coldFactor*stable interval=1500 ms.
Set the token bucket parameters with the initialization function:
FIG. 4
ThresholdPermits is set to
Thresholdinfo = 0.5 *warmupPeriodMicros /
stableIntervalMicros;
The 0.5 * 4000/500 = 4,
maxPermits=thresholdPermits +
2.0 * warmupPeriodMicros /
(stableIntervalMicros +coldIntervalMicros);
Maxperage is the bottom of the ladder on the right, while warmupPeriodMicros is the area of trapezoid, so maxperage is derived using the area formula of trapezoid. Slope represents the slope of an oblique line, which is used to calculate the token production time in the warm-up area. In the initial state, the token bucket is in the cooling state, that is, the production rate of the token bucket is the slowest in the initial state, storedPermits equals Maxpermits.
Figure 5
When we get the token from limiter above,
Figure 6
“R0.00, R1.38, R1.13, R0.88, R0.63, R0.50, R0.50, R0.50” Mon reference com.google.com. Util. Concurrent. The testWarmUp RateLimiterTest method).
As we know from the previous article, R stands for delay time, for example: R0.00 stands for no delay in obtaining a token, and R1.38 stands for waiting 1.38 seconds to obtain a token.
I =0, the first loop, from the first article we know that Ratelimiter is the idea of eating beyond its seed, because nextFreeTicketMicros initial value is 0, the current clock is also 0, so the delay is 0, the time to produce the token is used to compensate for the next consumption, which is the area of the first small trapezoid on the right.
Figure 7
AvailablePermitsAboveThreshold is stored is greater than the threshold, the number of token loop for the first time,
AvailablePermitsAboveThreshold = maxpermits – threshold = 4,
PermitsAboveThresholdToTake are apply for a number of token is 1,
Private double permitsToTime (double permits) used to calculate a little on the height of the upper and bottom trapezoid, here permitsToTime (availablePermitsAboveThreshold) obtained under floor height, permitsToTime(availablePermitsAboveThreshold –
PermitsAboveThresholdToTake) is on the bottom level, so
StoredPermitsToWaitTime token method is production time, the number of token in the storage is greater than the threshold, namely availablePermitsAboveThreshold > 0.0, the area of the calculation on the right side of the small ladder, Here the result is 1.38 seconds. Conversely, calculate the area of the small rectangle on the left.
When I = 1,2,3, repeat the second cycle. The delay time corresponds to the area of the second, third and fourth small trapezoids, and the area decreases, being 1.13, 0.88 and 0.63, respectively.
When I =4, the total time is 1.38, 1.13, 0.88, and 0.63, which add up to 4.02 (due to rounding error, the value is not exactly 4). The warmup period has passed, so it enters the stable period. The area of the small rectangle on the left is micros += (long) (stableIntervalMicros * permitsToTake), the height is stableIntervalMicros, 0.5 seconds, permitsToTake is 1, i.e. the production time is 0.5 seconds.
I = 5,6,7,8 repeat the process. The production time of the last cycle will be reimbursed by subsequent applicants.
At this point, warm up mode ratelimiter source code introduction finished, have a problem can pay attention to the public number, reply can be.
Related articles:
Guava token bucket algorithm implementation source code analysis (a)
Guava token bucket algorithm implementation source code analysis (two)