乐趣区

关于java:限流算法原理和实现

jiezi

限流原理与实战

接口限流的算法次要有 3 种，别离是计数器限流、漏桶算法和令牌桶算法

计数器限流原理

原理：在一个工夫窗口（距离）内，所解决的申请的最大数量是有限度的，对超过限度的局部申请不做解决。

代码实现 

@Slf4j
public class CountLimiter {private static long startTime = System.currentTimeMillis();
      // 工夫距离
    private static long interval = 1000;
      // 工夫距离内最大解决申请数
    private static long maxCount = 2;
      // 计数器
    private static AtomicInteger accumulator = new AtomicInteger();

    // 在 1 秒内，只容许 2 个申请接入，如若查过工夫片，则初始化参数进入新的一轮工夫片
    private static long tryAcquire(long taskId, int turn){long nowTime = System.currentTimeMillis();
          // 在时间段内，且数量小于等于最大容许申请值，则返回数量
        if (nowTime < startTime + interval){int count = accumulator.incrementAndGet();
            if (count <= maxCount){return count;}else {return -count;}
        }else {
        // 不为一个时间段，则重置计数器和开始工夫
            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(){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("限度次数为：" + limited.get() + "，通过次数为:"+(threads*turns - limited.get()));

        log.info("限度比例为："+(float)limited.get()/((float) threads*turns));
        log.info("运行时长："+time);
    }
}

复制代码

漏桶限流原理和 Java 参考实现

漏桶限流的基本原理

1）水通过进水口（对应客户端申请）以任意速率流入漏桶。2）漏桶的容量是固定的，出水（放行）速率也是固定的。3）漏桶容量是不变的，如果处理速度太慢，桶内水量会超出桶的容量，前面流入的水就会溢出，示意申请回绝。

 private static long lastOutTime = System.currentTimeMillis();

    // 流出速率每秒 2 个
    private static int rate = 2;

    // 残余水的量
    private static long water = 0;

    /**
     * false: 没有被限度
     * true: 被限流
     * @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;}
    }
复制代码

令牌桶限流原理和 Java 参考实现

令牌桶限流大抵的规定如下：

（1）进水口依照某个速度向桶中放入令牌。（2）令牌的容量是固定的，然而放行的速度是不固定的，只有桶中还有残余令牌，一旦申请过去就能申请胜利，而后放行。（3）如果令牌的发放速度慢于申请到来的速度，桶内就无令牌可领，申请就会被回绝。

@Slf4j
public class TokenBucketLimiter {
    // 上一次令牌发放的工夫
    public long lastTime = System.currentTimeMillis();
    // 桶的容量
    public int capacity = 2;
    // 令牌生成速度个 / 秒
    public int rate = 2;
    // 以后令牌的数量
    public int tokens;

    // 返回值阐明
    /**
     * false: 没有被限度
     * true: 被限流
     * @param taskId
     * @param turns
     * @return
     */
    public synchronized boolean tryAcquire(long taskId, int applyCount){long now = System.currentTimeMillis();
        // 工夫距离
        long gap = now - lastTime;
        // 以后令牌数
        tokens = Math.min(capacity, (int)(tokens+gap*rate/1000));
        log.info("tokens {} capacity {} gap {}",tokens ,capacity, gap);
        if (tokens < applyCount){log.info("被限流了.. {} ,applyCount:{}",taskId,applyCount);
            return true;
        }else {
            tokens -= applyCount;
            lastTime = now;
            log.info("残余令牌.." + tokens);
            return false;
        }
    }

    private ExecutorService pool = Executors.newFixedThreadPool(10);

    @Test
    public void testLimit(){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("限度次数为：" + limited.get() + "，通过次数为:"+(threads*turns - limited.get()));

        log.info("限度比例为："+(float)limited.get()/((float) threads*turns));
        log.info("运行时长："+time);

    }

}

参考：《2020 最新 Java 根底精讲视频教程和学习路线！》
链接：https://juejin.cn/post/693747…

退出移动版