Current limiting principle and actual combat
There are three algorithms for interface traffic limiting, namely, counter traffic limiting, leaky bucket algorithm and token bucket algorithm
Counter current limiting principle
Principle: Within a time window (interval), there is a limit on the number of requests that can be processed. The number of requests that exceed the limit is not processed.
Code implementation
@Slf4j
public class CountLimiter {
private static long startTime = System.currentTimeMillis();
// Time interval
private static long interval = 1000;
// The maximum number of requests processed within the interval
private static long maxCount = 2;
/ / counter
private static AtomicInteger accumulator = new AtomicInteger();
// Within 1 second, only 2 requests are allowed. If the time slice is checked, the initialization parameter enters a new time slice
private static long tryAcquire(long taskId, int turn){
long nowTime = System.currentTimeMillis();
If the number is less than or equal to the maximum number of allowed requests within a period of time, the number is returned
if (nowTime < startTime + interval){
int count = accumulator.incrementAndGet();
if (count <= maxCount){
return count;
}else {
return-count; }}else {
// Reset the counter and start time
synchronized (CountLimiter.class){
log.info("TaskId {}, turn{}..", taskId, turn);
if (nowTime > startTime + interval){
accumulator.set(0); startTime = nowTime; }}return 0; }}private ExecutorService pool = Executors.newFixedThreadPool(10);
@Test
public void testLimit(a){
AtomicInteger limited = new AtomicInteger(0);
final int threads = 2;
final int turns = 20;
CountDownLatch countDownLatch = new CountDownLatch(threads);
long start = System.currentTimeMillis();
for (int i = 0; i < threads; i++){ pool.submit(() -> {try {
for (int j = 0; j < turns; j++) {
long taskId = Thread.currentThread().getId();
long index = tryAcquire(taskId, j);
if (index <= 0){
limited.getAndIncrement();
}
Thread.sleep(200); }}catch (InterruptedException e) {
e.printStackTrace();
}
countDownLatch.countDown();
});
}
try {
countDownLatch.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
float time = (System.currentTimeMillis() - start) /1000F;
log.info("Limit times are:" + limited.get() + ", pass times are :"+(threads*turns - limited.get()));
log.info("The restricted proportion is:"+ (float)limited.get()/((float) threads*turns));
log.info("Running time:"+time); }}Copy the codeLeakage bucket current limiting principle and Java reference implementation
Basic principle of leakage bucket flow limiting
1) Water flows into the drain bucket at any rate through the water inlet (corresponding to client request). 2) The capacity of the leakage bucket is fixed, and so is the rate of discharge. 3) The leakage bucket capacity is unchanged. If the processing speed is too slow, the water in the bucket will exceed the capacity of the bucket, and the water flowing in the back will overflow, indicating that the request is rejected.
private static long lastOutTime = System.currentTimeMillis();
// The outflow rate is 2 per second
private static int rate = 2;
// The amount of water left
private static long water = 0;
/** * false: not restricted * true: restricted *@param taskId
* @param turns
* @return* /
public synchronized static boolean tryAcquire(long taskId, int turns){
long now = System.currentTimeMillis();
long pastTime = now - lastOutTime;
long outWater = pastTime * rate/ 1000;
water = water -outWater;
log.info("water {} pastTime {} outWater {}",water ,pastTime, outWater);
if (water < 0){
water = 0;
}
if (water <= 1){
lastOutTime = now;
water ++ ;
return false;
}else {
return true; }}Copy the codeToken bucket flow limiting principle and Java reference implementation
The general rules of token bucket flow limiting are as follows:
(1) The inlet puts the token into the bucket at a certain speed. (2) The capacity of token is fixed, but the speed of release is not fixed. As long as there are remaining tokens in the bucket, the application can be successful once the request comes, and then release. (3) If the token is issued slower than the request arrives, there are no tokens in the bucket and the request is rejected.
@Slf4j
public class TokenBucketLimiter {
// When the last token was issued
public long lastTime = System.currentTimeMillis();
// The capacity of a bucket
public int capacity = 2;
// Token generation speed per second
public int rate = 2;
// The number of current tokens
public int tokens;
// Return value description
/** * false: not restricted * true: restricted *@param taskId
* @param turns
* @return* /
public synchronized boolean tryAcquire(long taskId, int applyCount){
long now = System.currentTimeMillis();
// Time interval
long gap = now - lastTime;
// The current number of tokens
tokens = Math.min(capacity, (int)(tokens+gap*rate/1000));
log.info("tokens {} capacity {} gap {}",tokens ,capacity, gap);
if (tokens < applyCount){
log.info("The flow is restricted... {} ,applyCount:{}",taskId,applyCount);
return true;
}else {
tokens -= applyCount;
lastTime = now;
log.info("Remaining token.." + tokens);
return false; }}private ExecutorService pool = Executors.newFixedThreadPool(10);
@Test
public void testLimit(a){
AtomicInteger limited = new AtomicInteger(0);
final int threads = 2;
final int turns = 20;
CountDownLatch countDownLatch = new CountDownLatch(threads);
long start = System.currentTimeMillis();
for (int i = 0; i < threads; i++){ pool.submit(() -> {try {
for (int j = 0; j < turns; j++) {
long taskId = Thread.currentThread().getId();
boolean isLimited = tryAcquire(taskId, 1);
if (isLimited){
limited.getAndIncrement();
}
Thread.sleep(200); }}catch (InterruptedException e) {
e.printStackTrace();
}
countDownLatch.countDown();
});
}
try {
countDownLatch.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
float time = (System.currentTimeMillis() - start) /1000F;
log.info("Limit times are:" + limited.get() + ", pass times are :"+(threads*turns - limited.get()));
log.info("The restricted proportion is:"+ (float)limited.get()/((float) threads*turns));
log.info("Running time:"+time); }}Copy the code