厦门网站建设公司怎么选,母婴网站源码dede,企企管理云平台,公众号运营收费标准固定算法
原理#xff1a;固定算法是将时间线分隔成固定大小的时间窗口#xff0c;每个窗口都会有个计数器#xff0c;用来记录窗口时间范围内的请求总数#xff0c;如果窗口的请求总数达到最大限定值#xff0c;会认定流量超限。比如将窗口大小设为1分钟#xff0c;每分…固定算法
原理固定算法是将时间线分隔成固定大小的时间窗口每个窗口都会有个计数器用来记录窗口时间范围内的请求总数如果窗口的请求总数达到最大限定值会认定流量超限。比如将窗口大小设为1分钟每分钟请求最大数为2 请求在00:00:24时刻到来的时候会落在窗口1内计数器值为1下一个请求在00:00:36时刻也会落在窗口1内计数器值1变成第三个请求在00:00:49时刻来到此时计数器值已达到最大限定值2请求会被拒掉最后一个请求在00:01:12到来会落在窗口2内。
固定算法的缺点
固定算法只能判断单个窗口内的请求总数但是无法判断相邻的两个窗口落在相邻窗口的两个请求时间间隔完全有可能在一个窗口时间范围内。比如00:00:58和00:00:59两个时刻各有一个请求过来窗口1的计数器值为2 第三个请求在00:01:01到来会落在窗口2内但是00:00:58和00:01:01之间没有超过一个单元时间1分钟但是请求总数已经超过最大限定值2。
滑动窗口算法
为了优化固定算法的缺点将固定大小的时间窗口分成更小的时间窗口比如1min的窗口分成6个10s的小窗口。
实现一简单无脑版
思路
1. 使用一个MapcounterMap 用来存储每个时间戳的请求总数
2. 请求到来时会将单位时间之前now-timeUnit的所有请求记录全部清除
3. 统计单位时间timeUnit内的请求总数
4. 判断请求总数是否超过请求阈值capacity超过则返回false
5. 没有超过,则记录当前时间戳和请求。源码
public class SlidingWindow3 {/*** 单位时间请求阈值*/private int capacity;/*** 单位时间/ms*/private long timeUnit;/*** 时间戳计数器*/private MapLong,Integer counterMap new HashMap();public SlidingWindow3(int capacity, long timeUnit) {this.capacity capacity;this.timeUnit timeUnit;}public synchronized boolean tryAcquire() {long now System.currentTimeMillis();long start now-timeUnit;IteratorMap.EntryLong, Integer iterator counterMap.entrySet().iterator();while (iterator.hasNext()){if(iterator.next().getKey()start){iterator.remove();}}iterator counterMap.entrySet().iterator();int totalCount 0;while (iterator.hasNext()){totalCount iterator.next().getValue();}if(totalCount capacity){return false;}if(counterMap.containsKey(now)){counterMap.put(now,counterMap.get(now)1);}else {counterMap.put(now,1);}return true;}
}测试 public static void main(String[] args) throws InterruptedException {SlidingWindow3 slidingWindow new SlidingWindow3(2, 1000);for (int j 0; j 10; j) {System.out.println(第 j 轮测试);int concurrency 30;CyclicBarrier cyclicBarrier new CyclicBarrier(concurrency);for (int i 1; i concurrency; i) {new Thread(Thread: i) {Overridepublic void run() {try {cyclicBarrier.await();if (slidingWindow.tryAcquire()) {System.out.println(name: Thread.currentThread().getName() get permit);}} catch (InterruptedException e) {e.printStackTrace();} catch (BrokenBarrierException e) {e.printStackTrace();}}}.start();}Thread.sleep(3 * 1000L);}}结果 参考
《Rate-Limiter-Part1》
