- Enclosing class:
- SmoothRateLimiter
static final class SmoothRateLimiter.SmoothWarmingUp
extends SmoothRateLimiter
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)
Before going into the details of this particular function, let's keep in mind the basics:
1) The state of the RateLimiter (storedPermits) is a vertical line in this figure.
2) When the RateLimiter is not used, this goes right (up to maxPermits)
3) When the RateLimiter is used, this goes left (down to zero), since if we have storedPermits,
we serve from those first
4) When _unused_, we go right at the same speed (rate)! I.e., if our rate is
2 permits per second, and 3 unused seconds pass, we will always save 6 permits
(no matter what our initial position was), up to maxPermits.
If we invert the rate, we get the "stableInterval" (interval between two requests
in a perfectly spaced out sequence of requests of the given rate). Thus, if you
want to see "how much time it will take to go from X storedPermits to X+K storedPermits?",
the answer is always stableInterval * K. In the same example, for 2 permits per second,
stableInterval is 500ms. Thus to go from X storedPermits to X+6 storedPermits, we
require 6 * 500ms = 3 seconds.
In short, the time it takes to move to the right (save K permits) is equal to the
rectangle of width == K and height == stableInterval.
4) When _used_, the time it takes, as explained in the introductory class note, is
equal to the integral of our function, between X permits and X-K permits, assuming
we want to spend K saved permits.
In summary, the time it takes to move to the left (spend K permits), is equal to the
area of the function of width == K.
Let's dive into this function now:
When we have storedPermits <= halfPermits (the left portion of the function), then
we spend them at the exact same rate that
fresh permits would be generated anyway (that rate is 1/stableInterval). We size
this area to be equal to _half_ the specified warmup period. Why we need this?
And why half? We'll explain shortly below (after explaining the second part).
Stored permits that are beyond halfPermits, are mapped to an ascending line, that goes
from stableInterval to 3 * stableInterval. The average height for that part is
2 * stableInterval, and is sized appropriately to have an area _equal_ to the
specified warmup period. Thus, by point (4) above, it takes "warmupPeriod" amount of time
to go from maxPermits to halfPermits.
BUT, by point (3) above, it only takes "warmupPeriod / 2" amount of time to return back
to maxPermits, from halfPermits! (Because the trapezoid has double the area of the rectangle
of height stableInterval and equivalent width). We decided that the "cooldown period"
time should be equivalent to "warmup period", thus a fully saturated RateLimiter
(with zero stored permits, serving only fresh ones) can go to a fully unsaturated
(with storedPermits == maxPermits) in the same amount of time it takes for a fully
unsaturated RateLimiter to return to the stableInterval -- which happens in halfPermits,
since beyond that point, we use a horizontal line of "stableInterval" height, simulating
the regular rate.
Thus, we have figured all dimensions of this shape, to give all the desired
properties:
- the width is warmupPeriod / stableInterval, to make cooldownPeriod == warmupPeriod
- the slope starts at the middle, and goes from stableInterval to 3*stableInterval so
to have halfPermits being spend in double the usual time (half the rate), while their
respective rate is steadily ramping up