preface

This article has been included in Github- Java3C, which contains my series of articles, welcome everyone Star.

In my “Super Architect” column, I wrote an article called “Graph code practice traffic limiting Algorithm (1)”. We explained two commonly used traffic limiting algorithms through diagrams and codes: fixed time window and sliding time window algorithm.

Today we continue with two other traffic limiting algorithms: leaky bucket and token bucket.

Bucket algorithm

Leak-bucket algorithm is more flexible in the face of current limiting, and there is no direct violent rejection.

Algorithm analysis

Its principle is very simple, can be considered to be the process of water leakage. Pour water into the drain bucket at any rate and drain water at a constant rate. When the water exceeds the capacity of the bucket, it overflows, or is discarded. Because the bucket capacity is constant, the overall rate is guaranteed.

  • The inflow of water droplets, which can be viewed as requests to access the system, is at an indeterminate rate.
  • The bucket capacity generally indicates the number of requests that the system can handle.
  • If the bucket is full, the limit threshold is reached and the drop is discarded (request rejected)
  • The outgoing water droplets are constantly filtered, and the corresponding service processes requests at a fixed rate.

Pseudo code

    /** * System initialization time */
    private long currentTime = System.currentTimeMillis();
    
    /** ** ** ** /
    private long water = 0;

    /** * Drain bucket outflow rate */
    private long leakyRate = 1;

    /** * Leaky bucket capacity */
    private long leakyCapacity = 100;

    /** * Current limiting - leakage bucket algorithm * at a fixed speed out of the flow, at any speed into the maximum trigger current limiting */
    public boolean leakyBucketAlgorithm(a) {
        long now = System.currentTimeMillis();
        water = Math.max(0, water - (now - currentTime) * leakyRate);
        currentTime = now;
        if (water <= leakyCapacity) {
            water++;
            return true;
        } else {
            return false; }}Copy the code

The advantages and disadvantages

During normal traffic, the system processes requests at a fixed rate, which is what we want. However, in the face of sudden traffic, the leaky bucket algorithm will still handle requests in a conventional way, which is not desirable. When traffic changes suddenly, we want the system to process requests as quickly as possible to improve the user experience.

Token bucket algorithm

In the face of burst traffic, we can use the token bucket algorithm to limit traffic.

Algorithm analysis

  • There is a token manager who puts tokens into the token bucket at a fixed speed according to the flow limit.
  • If the token count is full and exceeds the token bucket capacity limit, it is discarded.
  • When the system receives a user request, it first goes to the token bucket and asks for a token. If the token is given, the business logic of the request is processed;
  • If the token is not available, the request is simply rejected.

Pseudo code

    /** * System initialization time */
    private long currentTime = System.currentTimeMillis();

    /** * token generation rate */
    private long tokenRate = 1;

    /** * Token bucket capacity */
    private long tokenCapacity = 100;

    /** * The current number of tokens in the bucket */
    private long token = 0;

    /** ** Flow limiting - Token bucket algorithm * Puts tokens into the bucket at a fixed speed, takes them out at any speed, triggers flow limiting when the token is empty */
    public boolean tokenBucketAlgorithm(a) {
        long now = System.currentTimeMillis();
        token = Math.min(tokenCapacity, token + (now - currentTime) * tokenRate);
        currentTime = now;
        if (token < 1) {
            return false;
        } else {
            token--;
            return true; }}Copy the code

The advantages and disadvantages

If the token issuing strategy is correct, the system will not be overwhelmed and the utilization of the machine will increase. Guava’s RateLimiter stream limiting component is based on the token bucket algorithm.

The last

Creation is not easy, thank you for your likes!! 🙏 🙏