sentinel之滑动窗口实现 sentinel滑动窗口限流

本章主要来聊一下限流神奇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类型，实际用的是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

文章图片

问题
【sentinel之滑动窗口实现】这里是我看滑动窗口这块逻辑发现的问题，仅做探讨，先抛一副图来说

文章图片

比如我们在第0、1块的时候持续请求进来，假设每块都是 50 笔，此时已经生成2块了，随着时间进行，在 1100ms 时又有 50 笔请求进来，此时的请求会将第0块给重置到第二块中，由于第一块记录的50笔加上第二块新来的50笔总和并没有超过阈值100，所以不会被限流，但是实际上有可能第0块还有部分请求没处理完（假设有 30 笔是在 400ms 的时候进来的），那么理论上 400-1100ms（周期 700ms）这个时间段通过的请求就有 130 笔，超过了阈值，这就出现了固定窗口的问题。所以在 sentinel 代码中也指明了精度问题

文章图片

是不是我们得根据实际情况设置更多的块，细化时间窗口以达到更高的精读？欢迎留言给出你们的意见和想法。
总结
sentinel 源码的我们认为比较难的应该在限流这一块了，通过对源码的阅读学会了用除模运算来控制范围，知道如何实现滑动窗口。当然还是有一些精度的疑问存在的。
参考资料
https://juejin.cn/post/698285...