滑动窗口算法

固定窗口的边界突发问题，来自于把时间切成一个个区块。一个请求要么落在这个区块里，要么落在那个区块里，而跨越区块交界处的一段时间，可能会承受两倍于限额的流量。

不再使用区块，问题自然消失。这里的两种算法，都以"以正在判断的这个请求为终点"的窗口来度量流量，它们的区别只在于各自记住了多少信息。

滑动窗口日志

为每一个被接受的请求都保留一个时间戳。当新请求到达时，向前回溯一个窗口长度，数一数里面有多少个请求，再做判断。

窗口是每次都重新计算的，所以它会跟在每个请求后面移动。还是同一个停车场的例子，三十秒窗口，限额为五：

时间	到达数	窗口回溯到	窗口内计数	结果
0秒	1	0秒	0	接受
5秒	2	0秒	1	两个都接受，计数变为3
15秒	2	0秒	3	两个都接受，计数变为5
25秒	1	0秒	5	拒绝，已达限额
35秒	1	5秒	4	接受，0秒的请求已过期移出窗口
40秒	3	10秒	3	两个接受，第三个拒绝

在35秒时，窗口起点是5秒，所以来自0秒的请求已经落在窗口之外，不再计入。这种"逐渐过期"正是整个机制的核心：容量是随着旧请求陆续退出窗口而逐步恢复的，而不是像重置那样一次性全部恢复。

任何连续三十秒的时间段内，请求数都不会超过五个。这正是固定窗口无法保证的事。

Juno滑动窗口日志 它和固定窗口的区别，在于窗口边界所处的位置。固定窗口的边界固定在时钟上，对所有人来说都是同一个位置。

而这里的边界跟在正在判断的请求后面，每次都会移动。没有人会经历"重置"，也没有人需要等待重置发生。

Juno滑动窗口日志 这也顺带解决了"断供期"的问题。一个一次性用光配额的客户端，会随着旧请求逐个过期而逐个恢复容量，而不是要等到整个区块结束。

这更接近人们对限流应有的直观感受，也正因如此，在那些拒绝合法客户端代价高昂的接口上，为这份精确性买单是值得的。

Juno滑动窗口日志 它的代价是：每个客户端要占用与限额成正比的内存。限额为5就存五个时间戳；限额为10,000就要为每个客户端存一万个，而且旧记录需要不断清理，否则列表会无限增长。

在Redis里，这通常做成每个客户端一个按时间戳排序的有序集合（sorted set），每次请求时都要修剪掉已过期的部分。

相比固定窗口只需一次原子自增，这里要多好几步操作，而且这些操作仍然必须是原子的，否则并发请求各自读到的都是已经过时的计数。

在限额较小时，这种方式便宜且明显正确。但在限额较大时，它会让你的限流器成为整个请求处理中最昂贵的部分。

滑动窗口计数器

日志算法的代价在于那一串时间戳。计数器用两个整数就换来了大部分的精确度。

回到固定窗口的思路：为当前窗口和上一个窗口各保留一个计数，然后根据上一个窗口还有多少比例仍落在滑动回溯范围内，给它的计数加权：

x        = 我们处于当前窗口的进度，用小数表示
weighted = (1 - x) * previousCount + currentCount

若 weighted + 1 <= limit 则接受

以三十秒窗口、限额为5、且上一个窗口已经满额为例：

时间	进入窗口的时长	1 - x	加权计数	加上这次请求	结果
35秒	5秒，即1/6	5/6	5/6 × 5 + 0 = 4.17	5.17	拒绝，超过5
40秒	10秒，即1/3	2/3	2/3 × 5 + 0 = 3.33	4.33	接受
40秒（再次）	10秒，即1/3	2/3	2/3 × 5 + 1 = 4.33	5.33	拒绝

(1 - x) * previousCount 这一项就是估算值：随着当前窗口逐渐填满，上一个窗口留在视野内的部分越来越少，它的贡献也就平滑地淡出。

每个客户端只需两个计数器，完全不用时间戳。

Juno滑动窗口计数器 这个公式做的事情其实很简单。在窗口刚开始的时候，上一个窗口的大部分计数仍然算在你头上；到了窗口后段，算的就少了。

它没有去检查哪些具体请求还落在范围内，而是假设它们是均匀分布的，直接取一个比例。这样更便宜，而且结果也八九不离十。

Juno滑动窗口计数器 注意表格中的第三行。同一时刻的两个请求，得到了不同的结果，因为第一个被接受的请求会让 currentCount 自增，而第二个请求是按新的总数来判断的。

这是正确的行为，测试时值得留意：在紧凑的循环中连续发出请求，结果会取决于这一毫秒内已经有多少请求被接受了。

Juno滑动窗口计数器 这种近似已经足够精确，能撑得起互联网级别的规模。Cloudflare曾公布过来自27万个来源、共4亿次请求的数据：其中只有0.003%的判断结果与精确计数不同，且没有出现漏判放行的假阳性。

有三个来源的请求略微超过了阈值却被放行了，而真实速率与近似值之间的平均误差为6%。

为了这点误差，换来的是每个客户端只需两个整数而不是一整串列表，这笔交易正是它成为生产环境常见选择的原因。

与固定窗口在边界处放行200个请求相比，日志算法恰好允许100个，计数器则允许101个。计数器多出来的这一个请求，正是近似算法带来的偏差，但它不会是真正伤害你的那个问题。

两者分歧之处

计数器假设上一个窗口的请求是均匀分布的。但现实中它们很少真的均匀分布，而哪个算法更宽松，取决于请求实际聚集在什么位置。

请求聚集在上一个窗口靠前的位置。 日志算法会真实地回溯三十秒，发现这些较早的请求已经落在窗口之外，于是放行更多请求。而计数器仍然会把它们的一部分算进去，因此会拒绝。

这种情况下日志算法更宽松，因为计数器把容量看得比实际情况更紧张。

请求聚集在上一个窗口靠后的位置。 这时日志算法仍然能看到它们，因而拒绝；而计数器已经把上一个窗口的大部分计数淡出了。这种情况下计数器更宽松，因为它低估了那些流量发生的时间有多近。

所以误差是双向的，这正是它可以被接受的原因。它并不是系统性地偏袒客户端或偏袒服务器中的某一方。

Juno两者分歧之处 计数器并不记录任何事情具体发生在什么时候。它只知道数量，而对时间只能猜测。

有时这个猜测比较宽松，有时比较严格，而具体是哪种，完全取决于那些请求真实到达的时间点。

Juno两者分歧之处 选择时值得弄清楚误差的方向。在"放行过多流量会很危险"的接口上，需要重点考虑的是计数器对后段聚集流量的那种宽松。

而在"拒绝合法客户端代价高昂"的接口上，需要重点考虑的则是它对前段聚集流量的那种严格，因为这会带来客服工单。

Juno两者分歧之处 理论上，通过刻意安排流量的分布来钻窗口的空子，对两种算法都可行，但计数器更容易被利用，因为它的盲区是可预测的：把请求集中安排在窗口末尾，下一个窗口的估算就会低估它们。

但实际操作中，攻击者需要知道你的窗口长度和边界对齐方式，这虽然可以推测出来，但很费工夫，而收益也只是多蹭到几个额外请求而已，不值得专门去防范。

真正值得去做的防范，是不要只依赖单一的限流器。同时设置一个按秒计的限额和一个按分钟计的限额，就能堵住大部分"钻窗口空子"的手法，因为针对某一个窗口精心设计的突发流量，放到另一个窗口下看仍然是突发流量。

动手试一试

三十秒窗口，限额为5，上一个窗口已经接受了5个请求。当前窗口目前还没有任何请求。

1. 用计数器算法判断，33秒时的一个请求会被接受吗？
2. 当前窗口进行到什么时刻，第一个请求才会被接受？
3. 流量条件不变，但上一个窗口的5个请求全部发生在它的第一秒内。33秒时的请求，哪种算法会放行？为什么？

对照一下你的答案

1. 拒绝。 在33秒时，你处于这个三十秒窗口的第3秒，所以 x 是1/10。加权计数是 0.9 × 5 + 0 = 4.5，再加上这次请求得到5.5，超过了限额5。

2. 在36秒时。 你需要满足 (1 - x) × 5 + 1 <= 5，也就是 (1 - x) × 5 <= 4，即 1 - x <= 0.8，也就是 x >= 0.2。三十秒窗口的五分之一是6秒，所以第一个可被接受的请求出现在36秒。

3. 日志算法会放行；计数器仍然拒绝。 日志算法回溯到3秒。之前的五个请求全部发生在这之前，所以它们都已经过期移出窗口，计数为0。

计数器完全不知道它们具体发生在什么时候，只能假设均匀分布，仍然把4.5计入其中。这正是这种近似算法要付出的实际代价：客户端在过去三十秒内其实什么都没发送，却依然被拒绝了。

接下来的方向

这两种算法都在强制执行一个平均值，都把突发流量当成需要防止的东西。但很多突发流量其实是正常合理的——比如一个页面同时加载六个资源，这并不是滥用行为。

令牌桶采取了相反的思路：它有意允许突发流量，然后让客户端花时间去"赚取"下一次突发的资格。