如何使用数组实现滑动窗口

在FireflySoft.RateLimit之前的版本中，进程内滑动窗口的实现是基于MemoryCache做的，虽然能够正确的实现滑动窗口的算法逻辑，但是性能比较差，其吞吐量只有其它算法的1/4。性能为何如此之差呢？

滑动窗口的原理

我们先来看下滑动窗口的原理，这里给一张图：

如上图所示：

• 滑动窗口的时间跨度是5秒，每个计数周期的时间跨度是1秒，所以此处的滑动窗口包含5个计数周期。
• 随着时间的前进，滑动窗口包含的计数周期会以秒为单位向前移动，但始终是包含5个计数周期。
• 判断是否限流时，需要将当前滑动窗口包含的5个计数周期的计数值加起来。
• 相比固定窗口计数器算法，滑动窗口允许一些突发流量，如上图中的第7个计数周期。
• 
  

MemoryCache实现的滑动窗口

使用MemoryCache时，存储结构如下：

每个计数周期都作为一个缓存项目添加到MemoryCache中，缓存Key为计数周期的绝对时间，缓存值为当前周期的计数值，缓存过期时间为一个大于滑动窗口时间跨度的相对过期时间，这样不用自己编码删除过期的计数周期，而滑动窗口内的计数周期都能正常保留。

另外为了获得滑动窗口内部每个计数周期对应的缓存项，这里还额外缓存了第一个计数周期的缓存Key（即对应的绝对时间），这样就可以根据当前时间和计数周期的时间跨度计算出当前周期的缓存Key，从而可以再逐步向前推出4个计数周期的缓存Key。

如有兴趣，具体实现可以点击这里进入Github查看。

这个实现有两个问题：

• 每个计数周期都是一个单独的缓存项，随着时间的前进需要不断申请内存，在堆上申请内存是一个相对耗时的操作。
• 每次计数都要先计算出滑动窗口内当前的所有计数周期，然后再把它们一个个取出来，求计数值的和，计算量较多。

这应该就是这个算法实现性能比较差的主要原因。

基于数组的滑动窗口

为什么要使用数组来实现滑动窗口呢？首先当然是数组可以实现滑动窗口，其次它可以解决MemoryCache实现中的两个问题，一是数组创建时就申请了固定大小的内存，后续计数都使用这块内存，不用再新申请；二是计算滑动窗口内的计数值只要把数组中每个元素的值加起来就行了，不用再一个个的寻找它们。

学过操作系统的同学可能比较了解，在操作系统中很多地方使用了环形队列，而环形队列是用数组实现的；滑动窗口可以理解为环形队列的一个特例，每次窗口滑动时，队列弹出一个，然后再进入一个。

理解数组实现的滑动窗口，看下边这个图就可以了。

假设滑动窗口的时间跨度还是5s，计数周期的时间跨度是1秒。

首先我们初始化一个容量为5的空数组，此时还没有开始计数，所以只是一个空数组。

• 第1秒，开始计数，此时数组内开始存入计数周期，保存在数组第1个位置，(1)表示这是当前滑动窗口内的第1个计数周期。如果我们把滑动窗口看成一个环形队列，那么队列的头尾此时都是数组的第1个元素。
• 第2秒，数组又存入一个新的计数周期，保存在数组第2个位置，(2)表示这是当前滑动窗口内的第2个计数周期；此时队列的尾部来到了数组的第2个元素。
• 以此类推，时间来到第5秒，此时数组内的每个位置都会存入一个计数周期，滑动窗口内的计数周期也达到了5个；队列的尾部也来到了数组的最后一个元素。
• 第6秒，数组已经放不下第6个元素了，因为滑动窗口只需要最近的5个元素，所以我们可以丢弃数组中第1个元素中保存的计数周期，重新创建一个计数周期放进去。从滑动窗口的角度看，丢弃了一个计数周期，新创建的这个计数周期还是滑动窗口的第5个计数周期，原来的第(2)、(3)、(4)、(5)就变成了(1)、(2)、(3)、(4)。如果从循环队列的角度看，则队列头部弹出了一个元素，然后队列尾部增加了一个元素。
• 以此类推，时间来到第7秒，代表滑动窗口的循环队列又弹出了一个过期的计数周期，然后插入新的计数周期。
• 第9秒也是如此，只不过第9秒结束后，数组的存储结构又回到了第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。