Ratelimiter source code analysis

As the saying goes, caching, current limiting and degradation are the three sharp swords of the system. When exporting data every morning in the project, the order transfer interface frequency is too high. The order system is worried that it will affect the use of the user side. Let's speed limit the call, so it's just used.

There are two common current limiting algorithms: leaky bucket algorithm and token bucket algorithm.

Leaky bucket algorithm

Leaky bucket algorithm: the request enters the "bucket" first, and then the bucket processes the request at a certain rate. If the request rate is too fast, it will cause bucket overflow. According to the description, the leaky bucket algorithm will forcibly limit the speed of request processing. No matter how fast or slow your request is, I handle it at this rate.

However, in many cases, in addition to limiting the average processing speed, it is also required to allow a certain degree of emergencies. In this case, the leaky bucket algorithm is not appropriate, and the token bucket algorithm is more appropriate.

Token Bucket

The principle of token bucket algorithm is that the system throws a certain number of tokens into the bucket at a constant rate, and the request can be processed only after getting the token. When there is no token in the bucket, the service can be denied.

Ratelimit in guava is the token bucket algorithm, which can support a certain degree of burst requests.

Output results:

As you can see, we generate tokens at a rate of 2 requests per second. For one, the total waiting time for the second and third acquisition requests is almost exactly 1 second. For two, when they acquire 10 tokens for the first time and acquire one request for the second time, they will almost wait for 5S (10 / 2 = 5). It can be seen that guava supports a certain degree of burst requests by limiting the waiting time of subsequent requests.

Next, analyze it through the source code!

When I first saw the algorithm description of token bucket, I thought there was a thread adding numbers to a place similar to a counter every x seconds

Guava's current limiting algorithm has two modes: one is stable speed, and the other is to slowly increase the speed of generating tokens until it is maintained at a stable speed. The principles of the two modes are similar, but there are differences in the calculation of the specific waiting time. The following specifically refers to the mode of stable speed.

Let's take a look at its acquire () method:

There are three main steps:

1. Calculate how long it takes to generate these number of tokens according to the parameters passed in when the limiter is created.

2. Let the thread block microtowait for such a long time (unit: microseconds)

3. How long has it been blocked in seconds

How does it calculate how long it takes? Let's look at the reserve (permits) method.

The final call is the reserveearliestavailable method. First look at the resync (now micros) method.

Nextfreeticketmicros means the time to be subtracted the next time it is acquired. If the acquire () method is called for the first time, nowmicros - nextfreeticketmicros is the time between initialization (nextfreeticketmicros will be assigned a value during initialization, see the ratelimiter constructor for details) and the first request.

The meaning of this method, If the current time is greater than the next acquisition time set in the previous round (because there is an early acquisition situation, for example, if 10 were directly obtained last time, the nextfreeticketmicros set in the previous round is the time + 5S of the previous round. As will be mentioned later), calculate how many tokens can be generated in this intermediate theory. For example, there is an interval of 1 second, and then stableintervalmicros = 5000 (when the generation speed is stable), then two tokens can be generated in the middle. Add the storedpermits originally stored. If it is larger than maxpermissions, the maximum can only store so many maxpermissions. If it is smaller than maxpermissions, it is storedpermits = originally stored + the number generated in the middle. At the same time, record the time to be subtracted for the next acquisition, That is, the current time (nextfreeticketmicros).

Next, continue to the reserveearliestavailable method:

Let's look at it line by line:

After the second line is set. Line 3 takes the time to be subtracted from the next acquisition as the return value (which is very important).

What do these two sentences mean?

In fact, these two sentences are the reasons why ratelimiter can handle sudden requests to a certain extent. If requiredpermissions = 10 and storedpermits we can save = 2, then freshpermissions = 8, that is, 8 more are taken. The sixth line is to calculate how long it will take to generate the eight extra values? It takes three seconds. Then, add these 3 seconds to the "time to be subtracted at the next acquisition" assigned earlier.

For example, if 10 are obtained at one time in 05 seconds, line 7 means the number of milliseconds of the system corresponding to nextfreeticketmicros = 13s. Then storedpermits is - 8. When the next request to call acquire (1) after one second, the resync method is due to nowmicros

That is, reserveandgetwaitlength will return max (13-6,0), that is, 7. The return value of this method is used for sleep threads, which is what we saw at the beginning:

To sum up, the most important values are now micros and nextfreeticketmicros. Nextfreeticketmicros will assign a time to the constructor at the beginning of the constructor execution. When acquire () is called for the first time, resync is executed and nextfreeticketmicros is set to the current time in acquire (). However, it should be noted that in reserveearliestavailable, the number of tokens requested is compared with the number of tokens currently stored. If the number of requested tokens is large, the accountant calculates the time required to generate these redundant tokens and adds them to nextfreeticketmicros, so as to ensure that the next time accquire() is called, it will be subtracted according to nextfreeticketmicros and nowmicros at that time. If > 0, it will need to wait until the corresponding time. It can also deal with the sudden increase of traffic.

So the most important thing is nextfreeticketmicros, which records the time when you can start generating tokens this time. For example, the current is 05s. If nextfreeticketmicros = 10, it means that it can't start generating tokens until 10s. Who told the previous one to take so much. As for whether it took more or just a token this time, the waiting time is so much. If you take more this time, you'll wait longer next time!

summary

The above is all about the common methods and source code analysis of ratelimiter in this paper. I hope it will be helpful to you. Interested friends can refer to: analysis of openfire cluster source code, method source code analysis of spring MVC after startup, java to check whether the native port is occupied, etc. Thank you for your support for the programming tips website!