1 counter method

The counter method is the simplest and easiest to implement among the current limiting algorithms. For example, we stipulate that for interface A, we can't access more than 100 times in one minute. So we can do this: at the beginning, we can set a counter, and each time a request comes in, counter is added 1. If the counter value is greater than 100 and the interval between the request and the first request is within one minute, then there are too many requests. If the interval between the request and the first request is greater than one minute and the counter value is within the flow limit, the counter is reset.

 

 

Pseudo code for the specific algorithm:

/**
 * The simplest counter current limiting algorithm
 */
public class Counter {
    public long timeStamp = System.currentTimeMillis();//current time
    public int reqCount = 0;//Initialization Counter
    public final int limit = 100;//Maximum number of requests in time window
    public final long interval = 1000 * 60;//time window ms9

    public boolean limit() {
        long now = System.currentTimeMillis();
        if (now < timeStamp + interval) {
            //Within the time window
            reqCount++;
            //Determine if the maximum number of request controls is exceeded in the current time window
            return reqCount <= limit;
        } else {
            timeStamp = now;
            //Reset after timeout
            reqCount = 1;
            return true;
        }
    }
}

2. Sliding time window algorithm

Slide the time window, also known as rolling window. To solve the problem of low statistical accuracy of counter method, a sliding window algorithm is introduced. Here is a good illustration of the sliding window algorithm:

 

 

 

In the figure above, the entire red rectangle represents a time window, in our case a time window is one minute. Then we divide the time windows, such as in the figure, and we divide the sliding window into six panes, so each one represents 10 seconds. Every 10 seconds, our time window slides one space to the right. Each grid has its own counter. For example, when a request arrives at 0:35 seconds, the counter for 0:30-0:39 will be added 1.
The counter algorithm is actually a sliding window algorithm. It just doesn't divide the time window further, so it only has one.
Thus, the more grids the sliding window divides into, the smoother the sliding window scrolls and the more accurate the flow-limiting statistics are.
Pseudo code for the specific algorithm:

/**
 * *Sliding Time Window Limiting Implementation
 * *Assuming a service can only process up to 100 requests per second, we can set a sliding time window of one second.
 * *There are 10 grids in the window, each of which moves once every 100 milliseconds, each time recording the number of current service requests
 *
 */
public class SlidingTimeWindow {
    //Number of service visits you can place in Redis Implement access counting for distributed systems in
    Long counter = 0L;
    //Use LinkedList To record the 10 grids of the sliding window.
    LinkedList<Long> slots = new LinkedList<Long>();

    public static void main(String[] args) throws InterruptedException {
        SlidingTimeWindow timeWindow = new SlidingTimeWindow();
        new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    timeWindow.doCheck();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }).start();
        while (true) {
            //TODO Judging current limit markers
            timeWindow.counter++;
            Thread.sleep(new Random().nextInt(15));
        }
    }

    private void doCheck() throws InterruptedException {
        while (true) {
            slots.addLast(counter);
            if (slots.size() > 10) {
                slots.removeFirst();
            }
            //Compare the last one with the first one, and limit the flow if the difference is more than 100
            if ((slots.peekLast() - slots.peekFirst()) > 100) {
                System.out.println("The current is limited.");
                //TODO Modify the current limit label to true
            } else {
                //TODO Modify the current limit label to false
            }
            Thread.sleep(100);//Because there are 10 grids, a check is performed every 100 milliseconds (1 second/10).
        }
    }
}

3. Leakage bucket algorithm

 

 

 

As we can see from the diagram, the whole algorithm is actually very simple. First, we have a bucket with a fixed capacity where water flows in and water flows out. For incoming water, we cannot predict how much water will flow in or how fast it will flow. But for water that flows out, this bucket can fix the rate at which water flows out. Also, when the bucket is full, excess water will overflow.
By replacing the water in the algorithm with the request in practice, we can see that the leaky bucket algorithm naturally limits the speed of the request. When the leaky bucket algorithm is used, we can guarantee that the interface will handle requests at a constant rate. So the leaky bucket algorithm is not inherently critical.
The specific pseudocode is as follows:

/**
 * *Leaky bucket current limiting algorithm
 * 
 */
public class LeakyBucket {
    public long timeStamp = System.currentTimeMillis();//current time
    public long capacity;//Capacity of barrel
    public long rate;//The speed at which water leaks(Number of requests the system can handle per second)
    public long water;//Current water volume(Current cumulative requests)9

    public boolean limit() {
        long now = System.currentTimeMillis();
        water = Math.max(0, water - ((now - timeStamp) / 1000) * rate);//Perform leak first, meter
        timeStamp = now;
        if ((water + 1) < capacity) {
            //Try adding water,And the water is not full yet
            water += 1;
            return true;
        } else {
            //Refuse to add water when water is full
            return false;
        }
    }
}

4 Token Bucket Algorithm

 

 

 

From the diagram, we can see that the token bucket algorithm is slightly more complex than the leaky bucket algorithm. First, we have a bucket with a fixed capacity in which tokens are stored. The bucket is empty at first, and token fills the bucket at a fixed rate r until it reaches the capacity of the bucket, and the extra tokens are discarded. Whenever a request comes in, it attempts to remove a token from the bucket, and the request cannot pass without a token.
The specific pseudocode is as follows:

/**
 * Token Bucket Current Limiting Algorithm
 */
public class TokenBucket {
    public long timeStamp = System.currentTimeMillis();//current time
    public long capacity;//Capacity of barrel
    public long rate;//Token Placement Speed
    public long tokens;//Current number of tokens 9

    public boolean grant() {
        long now = System.currentTimeMillis();
        //Add token first
        tokens = Math.min(capacity, tokens + (now - timeStamp) * rate);
        timeStamp = now;
        if (tokens < 1) {
            //Less than one token,Then reject
            return false;
        } else {
            //There are also tokens, pick up tokens
            tokens -= 1;
            return true;
        }
    }
}

Summary of Current Limiting Algorithms

Counter VS Slide Window:

1 The counter algorithm is the simplest algorithm and can be seen as a low-precision implementation of a sliding window.

2 Sliding windows require more storage space to implement because they need to store multiple counters (one copy per grid).

3 That is, the higher the precision of the sliding window, the larger the storage space required.

Leakage bucket algorithm VS token bucket algorithm:

1 The most obvious difference between the leaky bucket algorithm and the token bucket algorithm is that the token bucket algorithm allows a certain degree of bursting traffic.

2 Remove because of the default token bucket algorithm token It does not take time, that is, assume there are 100 in the bucket token Then you can accept it instantly

3 Of course, we need specific analysis, only the most appropriate algorithm, no optimal algorithm.