Let me give you an example of why limiting traffic is necessary.
Tourist attractions there are usually the largest hotels “, could not have unlimited put tourists to enter, like the Forbidden City every day to sell eighty thousand tickets, only more than eighty thousand tourists, can’t buy a ticket to enter, because if the more than eighty thousand people, scenic spot of staff may be busy not to come over, overcrowded attractions may also affect tourists’ experiences and feelings, there will be a safety hazard;
It only sells N tickets. It’s a way of limiting traffic.
Flow limiting in software architecture
Traffic limiting in software architecture is similar. When the system resources are insufficient, it cannot cope with a large number of requests. In order to ensure the normal operation of services, the system will directly reject the redundant requests according to rules to achieve the effect of traffic limiting.
External traffic limiting: too many users, or the increase of traffic caused by a certain activity or hot issues; Malicious attacks, or crawlers grab data and so on. I don’t know if you have noticed, for example, on Double 11, just after 12 o ‘clock, some customers’ websites or apps will show the warning of failure to place orders, and some of them are blocked.
Internal flow limiting: most companies, systems and systems will call each other. If system A is called by system X, Y and Z, when the page view of system X increases, system A is suspended, and system Y and Z cannot be used normally (depending on system A).
Counter method
The principle of the counter method is to limit the number of requests processed per unit of time to a threshold.
For example, an interface can handle 1000 requests per minute, so you can set a counter. When one request comes, the counter increases by 1. If the counter exceeds 1000 within a minute, the subsequent requests will not be processed.
However, the disadvantage of this method is also obvious, because the request access is not necessarily smooth, if 0:59 1000 requests come, 1:01 is the next window, another 1000 requests come, but in fact 2000 requests come in three seconds, already exceeded our traffic limit;
public class CounterTest {
public static void main(String[] args) {
long timeStamp = System.currentTimeMillis();
int timeCount = 1;
int reqCount = 0; // Number of requests per unit of time
int reqCountTotal = 0; // Total requests
final int limit = 10; // The maximum number of requests in the time window
final long interval = 1000; // Time window ms
for(;;) {
// The current time
long now = System.currentTimeMillis();
if (now < timeStamp + interval) {
// In the window between
reqCount ++ ;
// There are no requests exceeding unit time
if(reqCount < limit){
reqCountTotal ++ ;
System.out.println(timeCount + ":" + reqCountTotal);
}
}else {
// Next time window
timeStamp = now;
reqCount = 0 ;
timeCount ++ ;
}
}
}
}
Copy the codeSliding window algorithm
Take the example above, one minute in six parts, 10 seconds each; Every 10 seconds, our time window will slide one grid to the right, each grid has an independent counter, we calculate the number of time window each time, can solve the problem in the counter method, and when the sliding window more grids, the more accurate the statistics will be.
For details, please refer to the picture below, which is quite clear:
Bucket algorithm
This algorithm is also very simple, that is, we have a fixed capacity of the bucket, some water in, some water out, we don’t need to control the speed of the flow in, we only need to control the speed of the flow out, if the water in too fast, the bucket is full, the excess water will overflow, does not affect the speed of the water out.
Token bucket algorithm
There is still a bucket with N tokens in it. All requests need to get an available token before they can be processed. If there is no token in the bucket, the service is denied. The token bucket algorithm works by filling the bucket with tokens at a constant rate.
Someone will put the bucket algorithm and the token bucket algorithm confusion, and in a sense, the token bucket algorithm is, indeed, the bucket algorithm, an improved both the difference is: bucket algorithm can forcibly limited data transfer rate, and the token bucket algorithm can in the limited data average transmission rate at the same time also allows some sort of emergency transport;
That is, if a token exists in the token bucket, traffic is allowed to be sent; If no token exists in the token bucket, traffic is not allowed to be sent. For example, if the bucket size is 100 and there are no requests, the number of tokens in the bucket is always 100. If a large number of requests come in a second, the 100 tokens can be “saved” and processed at a constant rate.
Taking an edge off Google’s open source Guava package, RateLimiter makes it easy to create a token bucket algorithm for the current limiter.
import java.util.concurrent.Executors;
import com.google.common.util.concurrent.ListeningExecutorService;
import com.google.common.util.concurrent.MoreExecutors;
import com.google.common.util.concurrent.RateLimiter;
public class RateLimiterTest {
public static void main(String[] args) {
testRateLimiter();
}
public static void testRateLimiter(a) {
ListeningExecutorService executorService = MoreExecutors
.listeningDecorator(Executors.newFixedThreadPool(5));
RateLimiter limiter = RateLimiter.create(4); // No more than 4 tasks per second are submitted
int num = 0 ;
for (;;) {
limiter.acquire(); Request RateLimiter, permitting will be blocked
num ++ ;
executorService.submit(new Task("is "+ num));
}
}
}
class Task implements Runnable{
String str;
public Task(String str){
this.str = str;
}
@Override
public void run(a) {
System.out.println("Task call execute.." + str);
}
}
Copy the codeUncle will point code | article “original”
