高可用之限流-05-slide window 滑动窗口

限流系列

开源组件 rate-limit: 限流
高可用之限流-01-入门介绍
高可用之限流-02-如何设计限流框架
高可用之限流-03-Semaphore 信号量做限流
高可用之限流-04-fixed window 固定窗口
高可用之限流-05-slide window 滑动窗口
高可用之限流-06-slide window 滑动窗口 sentinel 源码
高可用之限流-07-token bucket 令牌桶算法
高可用之限流 08-leaky bucket漏桶算法
高可用之限流 09-guava RateLimiter 入门使用简介 & 源码分析
滑动日志-Sliding Log

滑动日志算法，利用记载下来的用户的哀求时间，哀求数，当该用户的一个新的哀求进来时，比较这个用户在这个窗口内的哀求数是否超过了限定值，超过的话就拒绝这个哀求。
优点：

• 避免了固定窗口算法在窗口界限大概出现的两倍流量问题
  
• 由于是针对每个用户进行统计的，不会引发惊群效应
  

缺点：

• 需要保存大量的哀求日志
  
• 每个哀求都需要考虑该用户之前的哀求情况，在分布式体系中尤其难做到
  

时间比例

滑动窗口算法，联合了固定窗口算法的低开销和滑动日志算法能够办理的界限情况。

• 为每个窗口进行哀求量的计数
  
• 联合上一个窗口的哀求量和这一个窗口已经经过的时间来盘算出上限，以此平滑哀求尖锋
  

举例来说，限流的上限是每分钟 10 个哀求，窗口巨细为 1 分钟，上一个窗口中总共处理了 6 个哀求。
在假设这个新的窗口已经经过了 20 秒，那么 到现在为止允许的哀求上限就是 10 - 6 * (1 - 20 / 60) = 8。
滑动窗口算法是这些算法中最实用的算法：

• 有很好的性能
  
• 避免了漏桶算法带来的饥饿问题
  
• 避免了固定窗口算法的哀求量突增的问题
  

ps: 这里是一种思绪，但却不是正宗的滑动窗口算法。
滑动窗口

滑动窗口将固定窗口再等分为多个小的窗口。

滑动窗口可以通过更细粒度对数据进行统计。
在限流算法里：假设我们将1s划分为4个窗口，则每个窗口对应250ms。
假设恶意用户照旧在上一秒的最后一刻和下一秒的第一刻打击服务，按照滑动窗口的原理，此时统计上一秒的最后750毫秒和下一秒的前250毫秒，这种方式能够判断出用户的访问仍旧超过了1s的访问数量，因此依然会阻拦用户的访问。
特点

滑动窗口具有以下特点：
1、每个小窗口的巨细可以均等，dubbo的默认负载均衡算法random就是通过滑动窗口设计的，可以调整每个每个窗口的巨细，进行负载。
2、滑动窗口的个数及巨细可以根据实际应用进行控制
滑动时间窗口

滑动时间窗口就是把一段时间片分为多个窗口，然后盘算对应的时间落在谁人窗口上，来对数据统计；
如上图其实就是即时的滑动时间窗口，随着时间流失，最开始的窗口将会失效，但是也会生成新的窗口；sentinel的就是通过这个原理来实时的限流数据统计。
关于滑动窗口，这里介绍照旧比较简单，重要是大致的介绍滑动的原理以实时间窗口的设计；其实关于滑动窗口在我们学习的盘算机网络中也涉及到。
java 实现

伪代码

1. 全局数组 链表[]  counterList = new 链表[切分的滑动窗口数量];
2. //有一个定时器，在每一次统计时间段起点需要变化的时候就将索引0位置的元素移除，并在末端追加一个新元素。
3. int sum = counterList.Sum();
4. if(sum > 限流阈值) {
5.     return; //不继续处理请求。
6. }
8. int 当前索引 = 当前时间的秒数 % 切分的滑动窗口数量;
9. counterList[当前索引]++;
10. // do something...

复制代码

java 核心实现

该方法将时间直接切分为10分，然后逐步处理。
临时没有做更加细致的可设置化，后期考虑添加。

1. /**
2. * 全局的限制次数
3. *
4. * 固定时间窗口
5. * @author houbinbin
6. * Created by bbhou on 2017/9/20.
7. * @since 0.0.5
8. */
9. public class LimitFixedWindow extends LimitAdaptor {
11.     /**
12.      * 日志
13.      * @since 0.0.4
14.      */
15.     private static final Log LOG = LogFactory.getLog(LimitFixedWindow.class);
17.     /**
18.      * 上下文
19.      * @since 0.0.4
20.      */
21.     private final ILimitContext context;
23.     /**
24.      * 计数器
25.      * @since 0.0.4
26.      */
27.     private AtomicInteger counter = new AtomicInteger(0);
29.     /**
30.      * 限制状态的工具
31.      *
32.      * 避免不同线程的 notify+wait 报错问题
33.      *
34.      * @since 0.0.4
35.      */
36.     private CountDownLatch latch = new CountDownLatch(1);
38.     /**
39.      * 构造器
40.      * @param context 上下文
41.      * @since 0.0.4
42.      */
43.     public LimitFixedWindow(ILimitContext context) {
44.         this.context = context;
46.         // 定时将 count 清零。
47.         final long interval = context.interval();
48.         final TimeUnit timeUnit = context.timeUnit();
50.         // 任务调度
51.         ExecutorServiceUtil.singleSchedule(new Runnable() {
52.             @Override
53.             public void run() {
54.                 initCounter();
55.             }
56.         }, interval, timeUnit);
57.     }
59.     @Override
60.     public synchronized void acquire() {
62.         // 超过阈值，则进行等待
63.         if (counter.get() >= this.context.count()) {
64.             try {
65.                 LOG.debug("[Limit] fixed count need wait for notify.");
66.                 latch.await();
67.                 LOG.debug("[Limit] fixed count need wait end ");
68.                 this.latch = new CountDownLatch(1);
69.             } catch (InterruptedException e) {
70.                 Thread.currentThread().interrupt();
71.                 LOG.error("[Limit] fixed count is interrupt", e);
72.             }
73.         }
75.         // 结束
76.         int value = this.counter.incrementAndGet();
77.         LOG.debug("[Limit] fixed count is " + value);
78.     }
80.     /**
81.      * 初始化计数器
82.      * @since 0.0.4
83.      */
84.     private void initCounter() {
85.         LOG.debug("[Limit] fixed count init counter start");
87.         // 通知可以继续执行（这里不能无脑 notify）会卡主
88.         if(this.counter.get() >= this.context.count()) {
89.             this.counter = new AtomicInteger(0);
91.             LOG.debug("[Limit] fixed count notify all start");
92.             latch.countDown();
93.             LOG.debug("[Limit] fixed count notify all end");
94.         }  else {
95.             this.counter = new AtomicInteger(0);
96.         }
97.     }
99. }

复制代码

基于 queue 的解法

另外一种解法，个人也是比较喜欢的。
直接创建一个队列，队列巨细便是限制的数量。
直接对比队首队尾的时间，从而保证固定当达到指定固定的次数时，时间一定是满意的。
ps: 这个后续在看看，不一定是滑动窗口的。

1. public class LimitSlideWindowQueue extends LimitAdaptor {
3.     private static final Log LOG = LogFactory.getLog(LimitSlideWindowQueue.class);
5.     /**
6.      * 用于存放时间的队列
7.      * @since 0.0.3
8.      */
9.     private final BlockingQueue<Long> timeBlockQueue;
11.     /**
12.      * 当前时间
13.      * @since 0.0.5
14.      */
15.     private final ICurrentTime currentTime = Instances.singleton(CurrentTime.class);
17.     /**
18.      * 等待间隔时间
19.      * @since 0.0.5
20.      */
21.     private final long intervalInMills;
23.     /**
24.      * 构造器
25.      * @param context 上下文
26.      * @since 0.0.3
27.      */
28.     public LimitSlideWindowQueue(ILimitContext context) {
29.         this.timeBlockQueue = new ArrayBlockingQueue<>(context.count());
30.         this.intervalInMills = context.timeUnit().toMillis(context.interval());
31.     }
33.     @Override
34.     public synchronized void acquire() {
35.         long currentTimeInMills = currentTime.currentTimeInMills();
37.         //1. 将时间放入队列中 如果放得下，直接可以执行。反之，需要等待
38.         //2. 等待完成之后，将第一个元素剔除。将最新的时间加入队列中。
39.         boolean offerResult = timeBlockQueue.offer(currentTimeInMills);
40.         if(!offerResult) {
41.             //获取队列头的元素
42.             //1. 取出头节点，获取最初的时间
43.             //2. 将头结点移除
44.             long headTimeInMills = timeBlockQueue.poll();
46.             //当前时间和头的时间差
47.             long durationInMills = currentTimeInMills - headTimeInMills;
48.             if(intervalInMills > durationInMills) {
49.                 //需要沉睡的时间
50.                 long sleepInMills = intervalInMills - durationInMills;
51.                 DateUtil.sleep(sleepInMills);
52.             }
54.             currentTimeInMills = currentTime.currentTimeInMills();
55.             boolean addResult = timeBlockQueue.offer(currentTimeInMills);
56.             LOG.debug("[Limit] acquire add result: " + addResult);
57.         }
58.     }
60. }

复制代码

参考资料

限流技术总结
固定窗口和滑动窗口算法相识一下
Sentinel之滑动时间窗口设计（二）
限流滑动窗口
限流算法之固定窗口与滑动窗口
限流--基于某个滑动时间窗口限流
【限流算法】java实现滑动时间窗口算法
谈谈高并发体系的限流
TCP协议的滑动窗口详细是怎样控制流量的？
漏铜令牌桶

漏桶算法&令牌桶算法理解及常用的算法
流量控制算法——漏桶算法和令牌桶算法
Token Bucket 令牌桶算法
华为-令牌桶算法
简单分析Guava中RateLimiter中的令牌桶算法的实现

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。