Article directory
Preface
1. Counter (fixed time window) algorithm
principle
Code
Problems
2. Sliding time window algorithm
principle
Code
Problems
3. Leaky bucket algorithm
principle
Code
Problems
4. Token bucket algorithm
principle
Code
at last
This article will explain these four current limiting algorithms in detail and output code examples for implementing the current limiting algorithms.
The code is written according to my own understanding, and the function is implemented very simply. I also ask the bosses to communicate more and find bugs.
There is a poll below, can you help me vote
Preface
What is current limiting? Current limiting is to limit the flow. In high-concurrency and high-traffic scenarios, we need to do a good job of current limiting to prevent unnecessary impacts from sudden traffic, malicious attacks, and other large requests, and to ensure the normal operation of the business system.
How to limit the flow? First, we need to know the basic idea of current limiting, and secondly, we need to know several implementation methods of current limiting (here we call it current limiting algorithm).
The basic idea of current limiting is to reject or limit traffic after it exceeds a certain threshold within a unit time.
Currently, common current limiting algorithms include counter (fixed time window) algorithm, sliding time window algorithm, funnel algorithm, and token algorithm.
1. Counter (fixed time window) algorithm
The counter (fixed time window) algorithm is the simplest current limiting algorithm, and its implementation is relatively simple.
principle
The principle is: by maintaining a count value within a unit time, each time a request passes, the count value is increased by 1. When the count value exceeds the preset threshold, other requests within the unit time are rejected. If the unit time has expired, the counter is cleared and the next round of counting is started.
import java.util.Random;
public class Counter {
//time window
private final int interval = 1000;
//Threshold within the time window
private final int limit = 5;
private long lastTime = System.currentTimeMillis();
private int counter = 0;
public boolean tryAcquire() {
if (System.currentTimeMillis() < lastTime + interval) {
// within the time window
counter + + ;
} else {
//Recharge counter after exceeding the time window
lastTime = System.currentTimeMillis();
counter = 1;
}
return counter <= limit;
}
public static void main(String[] args) throws InterruptedException {
Counter counter = new Counter();
while (true) {
if (counter.tryAcquire()) {
System.out.println("Make a request");
} else {
System.out.println("The current is limited...");
}
Thread.sleep(100 * new Random().nextInt(5));
}
}
}
Problems
But there is a problem with this implementation, for example:
Assume that we set the threshold of requests allowed to pass within 1 second to 100. If 99 requests are sent in the last few milliseconds of the time window, and then 99 requests are sent at the beginning of the next time window, then this user is actually in one second. Obviously the threshold is exceeded but the current will not be limited. In fact, this is the critical value problem, so how to solve the critical value problem?
2. Sliding time window algorithm
principle
The sliding time window algorithm was born to solve the above-mentioned critical value problem of the fixed time window. To solve this critical value problem, obviously using only one window cannot solve the problem. Assume that we still set the number of requests allowed to pass in 1 second to 200, but here we need to divide 1 second into multiple grids, assuming it is divided into 5 grids (the more grids, the smoother the traffic transition), the window of each grid The time size is 200 milliseconds. Every 200 milliseconds, the window is moved forward one frame. For easier understanding, you can look at the picture below
The window is divided into five parts in the figure. The number in each small window indicates the number of requests in this window. Therefore, by observing the above figure, we can see that in the current window (200 milliseconds), as long as it exceeds 110, the current will be limited.
Code
Here I use LinkedList as a split window, which can quickly implement the function.
import java.util.LinkedList;
import java.util.Random;
public class MovingWindow {
//Time window/ms
private final int interval = 1000;
//Threshold within the time window
private final int limit = 5;
//Number of split windows
private int slotCount = 5;
private LinkedList
public MovingWindow() {
new Thread(() -> {
while (true) {
// Every 200 milliseconds, move the window forward one frame
if (slot.size() == slotCount) {
slot.poll();
}
slot.offer(new Node(System.currentTimeMillis()));
try {
Thread.sleep(interval / slotCount);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}).start();
}
public boolean tryAcquire() {
Node currWindow = getCurrWindow();
currWindow.setCount(currWindow.getCount() + 1);
return getCounter() <= limit;
}
private int getCounter() {
return slot.stream().mapToInt(Node::getCount).sum();
}
private Node getCurrWindow() {
if (slot.isEmpty()) {
while (true) {
if (slot.isEmpty()) {
try {
Thread.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
} else break;
}
}
return slot.getLast();
}
private class Node {
private int count;
private long time;
public Node(long time) {
this.time = time;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public long getTime() {
return time;
}
public void setTime(long time) {
this.time = time;
}
}
public static void main(String[] args) throws InterruptedException {
MovingWindow counter = new MovingWindow();
while (true) {
counter.slot.stream().forEach(node -> System.out.print(node.getTime() + “:” + node.getCount() + “|”));
if (counter.tryAcquire()) {
System.out.println(“Make a request”);
} else {
System.out.println(“The current is limited…”);
}
Thread.sleep(100 * new Random().nextInt(5));
}
}
}
Problems
So is the sliding window current limiting method perfect? If we observe carefully, we should be able to find the problem immediately, as shown below:
The requests from 0ms-1000ms and 200ms-1200ms are within the threshold we set, but the total number of requests from 100ms-1100ms is 220, which exceeds the threshold we set.
The sliding time window current limiting method is actually a variant of the counter algorithm, and there is still a critical value problem. And whether the traffic transition is smooth depends on the number of window grids we set. The more grids we set, the more accurate the statistics will be, but how many grids should be divided specifically?
3. Leaky bucket algorithm
The two algorithms introduced above have an unsmooth transition in traffic. The leaky bucket algorithm is introduced below.
principle
The leaky bucket algorithm limits the egress traffic rate to a constant, so the leaky bucket algorithm can smooth out bursts of traffic. As a traffic container, the leaky bucket can be regarded as a FIFO queue. When the inlet traffic rate is greater than the outlet traffic rate, because the traffic container is limited, the excess traffic will be discarded.
The figure below vividly illustrates the principle of the leaky bucket algorithm, in which the water droplets are the inlet flow, the leaky bucket is the flow container, and the water flowing out at a constant speed is the outlet flow.
Code
Here I use ArrayBlockingQueue as a leaky bucket, which can quickly implement the function.
import java.util.Random;
import java.util.concurrent.ArrayBlockingQueue;
public class Funnel {
//Exit traffic rate 1s 10
private int rate = 10;
//Leaky bucket
private ArrayBlockingQueue bucket;
public Funnel(int rate, int capacity) {
this.rate = rate;
this.bucket = new ArrayBlockingQueue(capacity);
int speed = 1000 / this.rate;
//Fixed rate dripping
new Thread(() -> {
while (true) {
bucket.poll();
try {
Thread.sleep(speed);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}).start();
}
public boolean tryAcquire() {
// Put water in the leaky bucket
return bucket.offer(this);
}
public static void main(String[] args) throws InterruptedException {
Funnel funnel = new Funnel(10, 100);
while (true) {
if (funnel.tryAcquire()) {
System.out.println(“Make a request”);
} else {
System.out.println(“The current is limited…”);
}
Thread.sleep(20 * new Random().nextInt(5));
}
}
}
Problems
Because the outflow rate of the leaky bucket algorithm is fixed, the leaky bucket algorithm does not support sudden outflow traffic. But in actual situations, traffic is often bursty.
4. Token bucket algorithm
The token bucket algorithm is an improved version of the leaky bucket algorithm and can support burst traffic. However, unlike the leaky bucket algorithm, tokens are stored in the leaky bucket of the token bucket algorithm instead of traffic.
principle
How does the token bucket algorithm support burst traffic? Initially, the token bucket is empty. We add tokens to the token bucket at a constant rate. When the token bucket is full, excess tokens will be discarded. When a request comes, it will first try to obtain a token from the token bucket (equivalent to removing a token from the token bucket). If the acquisition is successful, the request will be released. If the acquisition fails, the request will be blocked or rejected. Then when burst traffic comes, as long as the token bucket has enough tokens, the traffic will not be limited.
Code
import java.util.Random;
import java.util.concurrent.ArrayBlockingQueue;
public class Token {
//Add token rate 1s 10
private int rate = 10;
//Leaky bucket
private ArrayBlockingQueue bucket;
public Token(int rate, int capacity) {
this.rate = rate;
this.bucket = new ArrayBlockingQueue(capacity);
//Add tokens into the leaky bucket at a constant rate
int speed = 1000 / this.rate;
new Thread(() -> {
while (true) {
bucket.offer(this);
try {
Thread.sleep(speed);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}).start();
}
public boolean tryAcquire() {
// Get the token from the leaky bucket
return null != bucket.poll();
}
public static void main(String[] args) throws InterruptedException {
Token funnel = new Token(10, 100);
//Burst traffic after 8s
Thread.sleep(8000);
while (true) {
if (funnel.tryAcquire()) {
System.out.println(“Make a request”);
} else {
System.out.println(“The current is limited…”);
}
Thread.sleep(20 * new Random().nextInt(5));
}
}
}
at last
Perhaps you will use some ready-made current limiting components in your work, such as Spring Cloud’s Hystrix, Spring Cloud Alibaba’s Sentinel, or Google’s Guava current limiter. Its implementation principle is inseparable from the four current limiting algorithms mentioned above. We developers still need to know what they are and why.