Implementation principle of RateLimiter SmoothWarmingUp

The entry point for creating a SmoothWarmingUp limiter is the RateLimiter create method, which looks like this: RateLimiter#create

public static RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) {  / / @ 1
    checkArgument(warmupPeriod >= 0."warmupPeriod must not be negative: %s", warmupPeriod);
    return create(
        SleepingStopwatch.createFromSystemTimer(), permitsPerSecond, warmupPeriod, unit, 3.0);
}
Copy the code

@1: Let’s look at the argument list first:

• Double permitsPerSecond the number of licenses issued per second, known as QPS.
• Long warmupPeriod warmupPeriod.
• TimeUnit unit warmupPeriod TimeUnit.

Code @2: Call the internal overloaded method to create SmoothWarmingUp.

RateLimiter#create

static RateLimiter create( SleepingStopwatch stopwatch, double permitsPerSecond, long warmupPeriod, TimeUnit unit, double coldFactor) {
    RateLimiter rateLimiter = new SmoothWarmingUp(stopwatch, warmupPeriod, unit, coldFactor);  / / @ 1
    rateLimiter.setRate(permitsPerSecond); / / @ 2
    return rateLimiter;
}
Copy the code

The two main steps to create a SmoothWarmingUp are to call its constructor first to create an instance of SmoothWarmingUp and then to call its setRate method to initialize the rate. ColdFactor is highlighted here, and the default is 3.0, the purpose of which is described in more detail below.

Let’s first focus on the implementation of the setRate method. The doSetRate method of its parent SmoothRateLimiter is eventually called.

SmoothRateLimiter#doSetRate

final void doSetRate(double permitsPerSecond, long nowMicros) {
    resync(nowMicros);   / / @ 1
    double stableIntervalMicros = SECONDS.toMicros(1L) / permitsPerSecond;   
    this.stableIntervalMicros = stableIntervalMicros;   / / @ 2
    doSetRate(permitsPerSecond, stableIntervalMicros);  / / @ 3
}
Copy the code

Code @ 1: Reset storeDperps and nextFreeTicketMicros within SmoothRateLimiter based on the current time, By free, you mean that you don’t have to wait to get permission to set your rate, which is key to understanding the generation of limiting permissions, more on that later.

@2: Calculate a stable time to obtain 1 license according to QPS. Issue 5 permits per second, i.e. speed limit is 5QPS, then the world interval for issuing a permit is 200ms, and the stableIntervalMicros variable is measured in subtlets.

Code @4: Call SmoothRateLimiter’s abstract method doSetRate to set the rate, which will call SmoothWarmingUp’s doSetRate method.

Before introducing the doSetRate method for SmoothWarmingUp, let’s take a look at the implementation of the Resync method.

SmoothRateLimiter#resync

void resync(long nowMicros) {
    if (nowMicros > nextFreeTicketMicros) {  / / @ 1
      double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();  / / @ 2
      storedPermits = min(maxPermits, storedPermits + newPermits);    / / @ 3
      nextFreeTicketMicros = nowMicros;   / / @ 4}}Copy the code

Code @1: If the current startup time is longer than nextFreeTicketMicros (the next time you can get a license for free), then the license needs to be recalculated, that is, you can add the license to the license pool again.

Code @2: The number of licenses that can be added based on the current time. Due to SmoothWarmingUp’s implementation of the warm-up mechanism, the average time to generate a license is not fixed. This is implemented by the coolDownIntervalMicros method, which will be explained later.

Code @3: Calculates the currently available licenses and adds the newly added licenses to the license pool, but does not exceed their maximum value.

Code @4: The next update increases the time for calculating permissions.

SmoothWarmingUp#coolDownIntervalMicros

double coolDownIntervalMicros(a) {
    return warmupPeriodMicros / maxPermits;
}
Copy the code

The implementation of this method is simple: divide the total time it took to generate these licenses by the number of licenses that have been generated so far to get the average generation time of one license at the current point in time.

Next, focus on the doSetRate method of SmoothWarmingUp.

SmoothWarmingUp doSetRate = SmoothWarmingUp doSetRate



SmoothWarmingUp notes to illustrate some of the main points of this image.

• There are two shaded areas in the figure, one is stable and the other is warm up period. In the preheating algorithm, the relationship between the two shadow areas is related to the cooling factor.
• ColdFactor represents the ratio of coldIntervalMicros to stableIntervalMicros.
• The ratio of warm up period shadow area to stable shadow area is equal to (coldIntervalMicros – stableIntervalMicros)/stableIntervalMicros, For example, if SmoothWarmingUp has a fixed cooling factor of 3, then the ratio of coldIntervalMicros to stableIntervalMicros is 3. So coldIntervalMicros minus stableIntervalMicros over stableIntervalMicros is equal to 2.
• In the warm-up algorithm, it is related to the integral in mathematics (the author has no knowledge of mathematics in this area), so only the conclusion is shown here, and the area of the shadow WARM UP PERIOD is equal to warmupPeriod, and the area of the shadow stable is equal to warmupPeriod/2.
• WarmupPeriod /2 = thresholdPermits * stableIntervalMicros
• WarmupPeriod = 0.5 * (stableInterval + coldInterval) * (maxpermit-thresholdpermits) (top bottom + Bottom bottom * height / 2)

With that in mind, let’s take a look at the code.

SmoothWarmingUp#doSetRate

void doSetRate(double permitsPerSecond, double stableIntervalMicros) { 
    double oldMaxPermits = maxPermits;
    double coldIntervalMicros = stableIntervalMicros * coldFactor;                / / @ 1
    thresholdPermits = 0.5 * warmupPeriodMicros / stableIntervalMicros;    / / @ 2
    maxPermits =
          thresholdPermits + 2.0 * warmupPeriodMicros / (stableIntervalMicros + coldIntervalMicros);   / / @ 3
    slope = (coldIntervalMicros - stableIntervalMicros) / (maxPermits - thresholdPermits);  / / @ 4
    if (oldMaxPermits == Double.POSITIVE_INFINITY) {
        storedPermits = 0.0;
    } else {
        storedPermits =
            (oldMaxPermits == 0.0)? maxPermits// initial state is cold
                : storedPermits * maxPermits / oldMaxPermits;    / / @ 5}}Copy the code

Code @1: Calculate the cooling interval (in microseconds) from the cooling factor, equal to the product of the cooling factor and stableIntervalMicros. From this we can derive the following basic concepts. Cooling factor coldFactor is the ratio of cooling interval to stable interval.

ThresholdPermits @2: Find thresholdPermits by warmupPeriod/2 = thresholdPermits * stableIntervalMicros

Code @3: warmupPeriod = 0.5 * (stableInterval + coldInterval) * (maxpermit-thresholdpermits)

@4: slope, indicating the growth rate of the number of permits from thresholdPermits to maxPermits from stableIntervalMicros to coldIntervalMicros.

Code @5: Update current stored licenses with maxPermits, i.e. the current number of permits remaining to be consumed.

SmoothWarmingUp acquire’s process is similar to SmoothBursty’s, so its flow chart is similar to the one below. The main difference is that the time to generate a license varies, mainly because it provides a warm-up mechanism.



If this article is helpful to you, please give it a thumbs up. Thanks.

Welcome to add the author micro signal (DINGwPMZ), add group discussion, the author quality column catalog: 1, source analysis RocketMQ column (40 +) 2, source analysis Sentinel column (12 +) 3, source analysis Dubbo column (28 +) 4, source analysis Mybatis column 5, source analysis Netty column (18 +) 6, source analysis JUC column Source code analysis (MyCat) for Elasticjob