# Common Current Limiting Algorithms

## 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.

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

private void doCheck() throws InterruptedException {
while (true) {
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();
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.```

Posted by echoindia756 on Mon, 18 Apr 2022 01:53:39 +0930