共计 2448 个字符，预计需要花费 7 分钟才能阅读完成。
本章次要来聊一下限流神奇 sentinel 的滑动窗口逻辑，来看看它是如何实现限流的。
知识点
- 什么是滑动窗口协定
- 滑动窗口原理
- sentinel 如何实现的
什么是滑动窗口协定
在聊滑动窗口之前，咱们要先看一下固定窗口是什么，这里我间接援用掘金上叫 yz 的作者一张图：
从图中咱们能够看到就是将窗口分成固定大小的若干块，在每一块中都受到阈值的限度。然而这里存在一个毛病：如果申请是在 16t 到 26t 之间超过阈值的，固定窗口是辨认不进去的。
正是因为固定窗口存在这种缺点，所以才有了滑动窗口的呈现。在网络中，滑动窗口就是用于网络流量的管制的。它就是随着工夫不停向前挪动，保障单位工夫周期内的流量不会超过阈值。
滑动窗口原理
上面咱们来看一下滑动窗口的实现原理，先上图：
以这张图来介绍，对于固定窗口，咱们晓得如果有申请跨两个窗口并且在每个窗口中又没有达到阈值，则理论相加可能会超过阈值。而滑动窗口顾明思义是随着工夫一直滑动的，如上图，当一次申请在 0 -500ms 块中近 300ms 的时候一次发动 60 并发申请，窗口就会滑动到以 300ms 作为开始地位向后取 1000ms 单位的工夫作为新窗口，也就是 300-1300ms，而后在此工夫窗口中的申请都会统计起来和阈值做比拟判断，这样就解决了固定窗口申请超出阈值的问题。最不便的了解就是：以以后工夫作为截止工夫，向前取单位工夫窗口的长度作为一个窗口，而后不停向前滑动。
sentinel 是如何实现的
为什么要讲 sentinel 是如何实现的，因为我最近在看 sentinel 源码，并且发现如同不是依照下面那个滑动窗口的思路实现的，先发一下我看到的后果
我看了好几篇文章都是提到改良，其实 就是说原来的滑动窗口算法耗资源、性能不好，所以做了一些优化，然而在我看来是一种取舍，优化的后果就是没法齐全精细化统计单位窗口内的申请，看来看去我发现还是这幅图比拟合乎我的思路。上面上源码（基于 1.6.0 版本）
咱们晓得 sentinel 用责任链模式连贯所有插槽，每个规定对应一个插槽，其余逻辑都不看了，和限流无关，间接看 FlowSlot，这个插槽就是作用流控的
这里就点一下，其余逻辑不多介绍，间接看滑动窗口实现。先看下这个类 com.alibaba.csp.sentinel.node.StatisticNode，这个类就是对申请的信息进行收集统计，这里要关注一下rollingCounterInSecond 和rollingCounterInMinute，别离是每秒、没分钟进行滚动统计的变量，都是 ArrayMetric 类型。
看下 ArrayMetric 类
这个 data 是十分重要的，它是个 LeapArray<MetricBucket> 类型，理论用的是 OccupiableBucketLeapArray，看下构造函数
能够看到这里设置了工夫窗口大小以及块数，这个就是滑动窗口的设置，默认是 2 块，每块 500ms。
咱们在 qps 限流的时候会先去获取以后工夫窗口的所有曾经通过的 qps，而后去和阈值做比拟。这里的 data.currentWindow() 十分重要，sentinel 滑动窗口的实现原理就在这里
这里的 TimeUtil.currentTimeMillis() 可不是间接获取以后工夫，它是准实时的
这里我也有点懵，不晓得为什么不间接获取 System.currentTimeMillis()，而要通过一个线程不停去更新工夫，晓得起因的敌人能够留言。持续往下看
之前咱们说过 sentinel 默认将工夫窗口分为 2 块，calculateTimeIdx就是计算以后工夫应该属于哪一块，找对应的下标。这是滑动的外围逻辑 timeId % array.length() 这里用到了除模运算，将值固定在 array.length() 的范畴内。calculateWindowStart用于计算以后工夫对应的块的起始工夫。我把正文删掉，持续往下看
这里有 4 种状况：
1）以后块不存在，新建一个；
2）以后工夫属于以后块，间接返回；
3）以后工夫计算出的实践起始工夫大于以后块起始工夫，重置以后块为以后工夫并返回；
4）以后工夫计算出的实践起始工夫小于以后块起始工夫，工夫倒退，返回一个新块，个别不会产生，除非本人手动批改服务器工夫之类的操作；
要害看第 1、3 两种。
第一种不存在的状况下，会用 WindowWrap 来把以后窗口包装起来，并用 CAS 进行设置。WindowWrap比较简单，就是记录了窗口块工夫大小、起始工夫以及相干数据统计，次要看 newEmptyBucket，这里创立了一个新块
这个块自身就是 MetricBucket
所有申请的指标事件都用 LongAdder 来统计，蕴含这些事件
比方咱们获取已通过的的申请，则是获取 PASS 这个事件对应的数据。
再来看下第三种状况，这里会去重置窗口块
把块起始工夫设置为以后计算出来的块起始工夫，而后通过 reset 把所有事件的统计信息重置为 0
问题
这里是我看滑动窗口这块逻辑发现的问题，仅做探讨，先抛一副图来说
比方咱们在第 0、1 块的时候继续申请进来，假如每块都是 50 笔，此时曾经生成 2 块了，随着工夫进行，在 1100ms 时又有 50 笔申请进来，此时的申请会将第 0 块给重置到第二块中，因为第一块记录的 50 笔加上第二块新来的 50 笔总和并没有超过阈值 100，所以不会被限流，然而实际上有可能第 0 块还有局部申请没解决完（假如有 30 笔是在 400ms 的时候进来的），那么实践上 400-1100ms（周期 700ms）这个时间段通过的申请就有 130 笔，超过了阈值，这就呈现了固定窗口的问题。所以在 sentinel 代码中也指明了精度问题
是不是咱们得依据理论状况设置更多的块，细化工夫窗口以达到更高的精读？欢送留言给出你们的意见和想法。
总结
sentinel 源码的咱们认为比拟难的应该在限流这一块了，通过对源码的浏览学会了用除模运算来管制范畴，晓得如何实现滑动窗口。当然还是有一些精度的疑难存在的。
参考资料
https://juejin.cn/post/698285…
