分布式 窗口算法 总结
前言
相关系列
- 《分布式 & 目录》
- 《分布式 & 窗口算法 & 总结》
- 《分布式 & 窗口算法 & 问题》
参考文献
- 《【算法】令牌桶算法》
固定窗口算法
简介
固定窗口算法是最简单的流量控制算法。固定窗口算法的核心原理是将系统的生命周期划分为一个个单位时间的固定窗口，随后再去限制这些固定窗口所能接收的请求数量。固定窗口算法通常在实现时会使用计数器去统计单位时间内已接收的请求总数，而一旦请求数量在下个固定窗口到来前到达阈值，那么系统就会拒绝掉后续的所有请求，直至下个固定窗口到来为止。
场景
- 限制网络带宽：控制访问流量；
- 功能分级：为不同级别的用户提供不同频率的服务，通过控制单位时间内最大访问数量的方式；
- 任务调度：限制任务执行频率以避免资源争用。
概念
- 计数器：一个简单的次数统计，通常使用Redis一类的中间件实现。
流程
- 系统每隔单位时间（通常是1s）的去清空计数器；
- 客户端访问系统，在网关被拦截。随后网关会判断当前请求是否免限流，是则直接访问；
- 如果当前请求不免限流，则网关会判断当前固定窗口接收的请求总数是否已达阈值，是则拒绝当前请求；否则允许当前请求访问系统。
缺点
无法限制请求的访问频率。固定窗口算法只能限制请求在单位时间内的整体数量，但却无法限制请求在单位时间内的整体频率，即请求可能不会均匀的散布在单位时间中，而是会在两个单位时间的起/终点处集中发生，并因此边界原因而出现超频问题。
以每秒50个请求的限制为例，这50个请求可能不会均匀散落于1s的单位时间中，而是集中在终点的0.1 ~ 0.2秒内发生。此时如果下个单位时间的50个请求也集中在起点的0.1 ~ 0.2秒内发生，那么就违背了固定窗口算法在单位时间内不允许请求总数超过阈值的规定。
滑动窗口算法
滑动窗口算法是固定窗口算法的优化版本，用于解决固定窗口算法的边界超频问题。滑动窗口算法与固定窗口算法的核心差异在于其将系统生命周期的时间分段由原本的绝对分段改为了以当前时刻为基点的相对分段，即系统统计的永远都是当前时刻所在单位时间内的请求数量。因此与固定窗口算法一个单位时间就是一个窗口不同，滑动窗口算法永远只有一个窗口，并且该窗口还会随着时间的推移而移动，这也是滑动窗口算法的名称由来。那么当前时刻具体又处于单位时间的那个位置呢？事实上滑动窗口算法会对单位时间进行更加细致的划分，例如将1s的单位时间划分为5个0.2s的区间，并为每个区间分配独立的计数器来追求更加平滑的限流效果，因此当前时刻必然会位于单位时间的最后一个区间划分上。
流程
- 系统每隔区间时段便滑动一个区间；
- 客户端访问系统，在网关被拦截。随后网关会判断当前请求是否免限流，是则直接访问；
- 如果当前请求不免限流，则网关会判断滑动窗口的单位时间内所有区间计数器统计的请求总数“和”是否已达阈值，是则拒绝当前请求；否则允许当前请求访问系统。
- 上述流程可以大幅降低边界超频问题的发生概率。依然以每秒50个请求的限制为例：如果系统在1.0 ~ 1.8区间内未曾收到任何请求，但在1.8 ~ 2.0区间内却集中接收了50个请求，那么整个单位时间内可接收的请求总数实际便已达到上限。这种情况下如果在2.0 ~ 2.2区间里又有50个请求访问系统，那么在固定窗口算法中是不会触发限流的，但是在滑动窗口算法中由于滑动窗口会剔除尾部/新增头部的1.0 ~ 1.2/2.0 ~ 2.2区间，因此整个单位时间所允许的请求数量依然达到了上限，因此是会触发限流的。而理论上只要区间划分的足够细致，那么最终的限流效果就越平滑，即边界超频的发生概率就越小。