This is the second day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

Token bucket algorithm and leak-bucket algorithm are common limiting algorithms. In Sential, they are used in current-limiting cold start mode and uniform queuing mode respectively.

Sential Flow control Effect:

  • RuleConstant.CONTROL_BEHAVIOR_DEFAULT) is the default traffic control mode. When QPS exceeds the threshold of any rule, a new request is rejected by throwing a FlowException.
  • CONTROL_BEHAVIOR_WARM_UP (Ruleconstant. CONTROL_BEHAVIOR_WARM_UP) indicates that the startup mode is warm or cold. When the system has been at a low water level for a long time, when the flow suddenly increases, directly pulling the system to a high water level can suddenly overwhelm the system. Through the “cold start”, the flow slowly increases to the upper limit of the threshold in a certain period of time, giving the cold system a time to warm up, preventing the cold system from being overwhelmed.
  • Uniform queuing :(ruleconstant. CONTROL_BEHAVIOR_RATE_LIMITER) strictly controls the interval for passing requests, that is, requests pass at an even speed. This applies to the leak-bucket algorithm. Requests can only be queued

Token bucket algorithm

The basic process of token bucket algorithm is as follows:

  1. The token bucket gets m tokens per second.
  2. The token bucket has a capacity of A. When the token bucket is full, excess tokens will be discarded.
  3. When an N-byte packet arrives, n tokens are consumed and the packet is sent.
  4. When insufficient tokens are consumed, the packet is discarded or cached.

The core idea of token bucket algorithm is to limit the average processing speed by limiting the rate of token bucket entry. In addition, as long as a token exists in the token bucket, data is allowed to be transmitted in a burst until the user-configured upper limit is reached, so it is suitable for traffic with burst characteristics.

There are two main ways to implement token buckets:

  • Scheduled task: Set the scheduled task per second to implement the bucket entry of tokens per second. The problem is that it will consume a lot of system resources. When the number of token buckets is large, it needs a lot of corresponding scheduled tasks.
  • Delay calculation: Count the interval time of token consumption (cooldown time), only when the token consumption, will get the number of tokens generated during this period according to the cooldown time.

In practice, we can use Guava’s RateLimiter utility class, which adopts the idea of delayed calculation.

Bucket algorithm

The leak-bucket algorithm forces the output rate of a constant regardless of the abruptness of the input data stream. When the input is idle, the algorithm does nothing. Just like using a leaky bucket with a hole at the bottom to receive water, water enters the leaky bucket, and the water in the bucket flows out through the hole below at a fixed rate. When the water inflow speed is too high, it will directly overflow. It can be seen that the leaky bucket algorithm can forcibly limit the data transmission rate. As shown below:

The implementation of leaky bucket algorithm often depends on the queue. If the queue is not full, the request is directly put into the queue, and then a processor takes out the request from the queue head for processing according to a fixed frequency. If the number of requests is large, the queue will be full and new requests will be discarded.