摘要：理解数组实现的滑动窗口，看下边这个图就可以了。第秒，开始计数，此时数组内开始存入计数周期，保存在数组第个位置，表示这是当前滑动窗口内的第个计数周期。
在FireflySoft.RateLimit之前的版本中，进程内滑动窗口的实现是基于MemoryCache做的，虽然能够正确的实现滑动窗口的算法逻辑，但是性能比较差，其吞吐量只有其它算法的1/4。性能为何如此之差呢？
我们先来看下滑动窗口的原理，这里给一张图：
如上图所示：
使用MemoryCache时，存储结构如下：
每个计数周期都作为一个缓存项目添加到MemoryCache中，缓存Key为计数周期的绝对时间，缓存值为当前周期的计数值，缓存过期时间为一个大于滑动窗口时间跨度的相对过期时间，这样不用自己编码删除过期的计数周期，而滑动窗口内的计数周期都能正常保留。
另外为了获得滑动窗口内部每个计数周期对应的缓存项，这里还额外缓存了第一个计数周期的缓存Key（即对应的绝对时间），这样就可以根据当前时间和计数周期的时间跨度计算出当前周期的缓存Key，从而可以再逐步向前推出4个计数周期的缓存Key。
如有兴趣，具体实现可以点击这里进入Github查看。
这个实现有两个问题：
这应该就是这个算法实现性能比较差的主要原因。
为什么要使用数组来实现滑动窗口呢？首先当然是数组可以实现滑动窗口，其次它可以解决MemoryCache实现中的两个问题，一是数组创建时就申请了固定大小的内存，后续计数都使用这块内存，不用再新申请；二是计算滑动窗口内的计数值只要把数组中每个元素的值加起来就行了，不用再一个个的寻找它们。
学过操作系统的同学可能比较了解，在操作系统中很多地方使用了环形队列，而环形队列是用数组实现的；滑动窗口可以理解为环形队列的一个特例，每次窗口滑动时，队列弹出一个，然后再进入一个。
理解数组实现的滑动窗口，看下边这个图就可以了。
假设滑动窗口的时间跨度还是5s，计数周期的时间跨度是1秒。
首先我们初始化一个容量为5的空数组，此时还没有开始计数，所以只是一个空数组。
然后随着时间的前进，滑动窗口的处理就是循环第5秒至第9秒之间的处理逻辑。
再说计数的处理：
这里摘抄一些代码，让大家感受更深入一些：
// 几个重要变量：保存计数周期的数组、代表滑动窗口的循环队列的头和尾SlidingWindowPeriod[] _queue;int _head = 0;int _tail = 0;// 省略很多代码....// 创建一个计数周期，这里是一个结构体var newPeriod = new SlidingWindowPeriod(){ // 为了方便确定当前请求的计数周期，计数周期的Key是一个时间刻度， Key = lastPeriod.Key + _statPeriodMilliseconds * i, CountValue = 0};// 循环队列尾加1// 如果超出了数组的索引范围，则代表需要替换数组中第1个位置的计数周期，然后队列尾来到数组中第1位_tail++;if (_tail == _length) _tail = 0;// 如果队列尾在数组中的索引小于等于队列头的索引，则队列头需要弹出数据，队列头的位置向后移动1位if (_tail <= _head){ _head++; // 如果队列头的索引会超出索引范围，则队列头归位到数组中的第1位 if (_head == _length) _head = 0;}// 将新的计数周期写入队列尾所在的数组位置_queue[_tail] = newPeriod;
这里边还会有一些特殊的处理，比如滑动窗口只包含一个小计数周期，再比如请求时间的前进是不均匀的（可能会跳过数个计数周期的时间跨度），都需要仔细考虑。
好了，以上就是本文的主要内容。
如果想了解完整的实现，查看全部代码，请点击进入GitHub。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/125674.html
摘要：你只可以看到在滑动窗口内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值。算法思路暴力破解法用两个指针，分别指向窗口的起始位置和终止位置，然后遍历窗口中的数据，求出最大值向前移动两个指针，然后操作，直到遍历数据完成位置。 Time：2019/4/16Title: Sliding Window MaximumDifficulty: DifficultyAuthor: 小鹿 题目...
摘要：代码实现代码实现接下来思考一个熔断器如何实现。同时熔断器的状态也需要依靠指标统计来实现可观测性，我们实现任何系统第一步需要考虑就是可观测性，不然系统就是一个黑盒。可能是，熔断器需要实时收集此数据。熔断方法，自动上报执行结果自动挡。。。为什么需要熔断微服务集群中，每个应用基本都会依赖一定数量的外部服务。有可能随时都会遇到网络连接缓慢，超时，依赖服务过载，服务不可用的情况,在高并发场景下如果此时...
摘要：你只可以看到在滑动窗口内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值。 这篇文章我们来看一道题目求滑动窗口最大值问题(在leetcode上的地址：滑动窗口最大值) 题目描述 给定一个长度为N的数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值。 示例: 输入: nu...
摘要：计数限流算法无论固定窗口还是滑动窗口核心均是对请求进行计数，区别仅仅在于对于计数时间区间的处理。令牌桶限流实现原理令牌桶限流的实现原理在有详细说明。因此由此为入口进行分析。目前可返回的实现子类包括及两种，具体不同下文详细分析。 限流 限流一词常用于计算机网络之中，定义如下： In computer networks, rate limiting is used to control t...
摘要：之前有了解到哥的一部分读者们没有充分搞清楚限流和熔断的关系。后者表示系统在同一时刻能处理的最大请求数量，比如次的并发。后续限流策略需要设定的具体标准数值就是从这些指标中来的。限流阈值不继续处理请求。 如果这是第二次看到我的文章，欢迎扫描文末二维码订阅我哟~本文长度为2869字，建议阅读8分钟。 可能你在网上看过不少「限流」相关的文章，但是z哥的这篇可能是最全面，最深入浅出的一篇了（容我...
阅读 3311·2023-01-11 11:02
阅读 3888·2023-01-11 11:02
阅读 2719·2023-01-11 11:02
阅读 4897·2023-01-11 11:02
阅读 4403·2023-01-11 11:02
阅读 5113·2023-01-11 11:02
阅读 4895·2023-01-11 11:02
阅读 3373·2023-01-11 11:02
