限流算法
漏桶算法
漏桶算法 是最为简单的限流算法，原理类似一个容积一定的木桶，有水源向该木桶加入水，但是流入的数量不确定，任意时刻的流入速率也是随机；而木桶底部有一个固定大小的洞，以恒定的速率向外漏水；这样，桶中流出水的速率恒定，而当桶满了的时候，水会自然地溢出。
其中：桶中的水类比网络请求；流入的水代表新到达的请求，而流出的水代表被系统处理的请求。
可以看到：新到达的请求量以及频率是不确定的，而整个桶却能保持一定的最大容量，并且以恒定的速率处理请求（漏出水）；当桶满时，即系统满负载时，新到达的请求被自然丢弃，这样即可确保系统能够始终以恒定的速率处理请求。
实际实现中，漏桶可以使用一个恒定容量的队列实现，系统以恒定的速率从队列中取出一定数量的请求进行处理；而当队满时，新到达的请求被丢弃。
优点：
- （强制）保证稳定的流量控制，适用于流量稳定，没有或较少突发流量的场景
- 易于理解，实现简单
缺点：
- 速度相对稳定，缺乏弹性
- 由于保持稳定的处理速率，导致无法应对突发流量（例如秒杀活动）
令牌桶算法
实际的网络应用中，常常存在着突发流量，此时 漏桶算法 便无法适应这种情况，令牌桶算法 能够在保持流量的平均传输速率时，也能允许一定的突发流量。
令牌桶算法 中，存在一个以大小一定的 令牌桶 ，用于存储一定数量的令牌，所有的数据都需要消耗令牌来放行；
而系统中有一个不断产生令牌的源，它向令牌桶中以恒定速率放入令牌。
而每一个数据包到达时，都要消耗与其大小相当数量的令牌；
如果桶中无令牌或令牌数量不足，则丢弃（或缓存）该数据包，否则将其放行（或处理）。
与 漏桶算法 不同，令牌桶算法 除了能够限制数据的平均传输速率外，还允许一定程度的突发传输。在突发流量的情况下爱，只要令牌桶中还存在足够的令牌，那么就允许不断传输数据，直到达到门限为止（取决于实际的配置）。
优点：
- 保证稳定的平均传输速率，同时允许一定程度的突发流量
缺点： - 内存消耗较大，例如对每一个用户都进行限制，就需要单独使用一个令牌桶，消耗大量资源
- 无法保证任一时刻速率的平滑性
固定窗口计数器算法
固定窗口计数器算法 将时间划分为若干固定大小的窗口，在每个窗口内统计请求数，超过一定阈值后，多余的请求会被拒绝，直到开始下一个窗口。每次窗口结束时重置计数器。
适用于系统总体流量平缓，有较少短时波动的场景。
优点：
- 原理简单，易于实现
- 允许瞬时高峰请求
缺点： - 在窗口边界处，两个窗口边缘的总请求数可以突破阈值，最高可达2倍
滑动窗口日志算法
滑动窗口日志算法 为解决 固定窗口计数法 在窗口边界处请求数突破阈值的问题。该算法随着时间推移不断移动窗口，记录通过请求的时间戳日志，对每个新请求，根据日志回溯最近窗口的访问量，若未超过阈值，则接受该请求并记录日志，否则拒绝请求。
优点：
- 流量控制精细，不存在窗口边界问题
缺点： - 系统复杂增加，需要维护更新日志
滑动窗口计数器算法
权衡了 固定窗口计数器算法 和 滑动窗口日志算法 ，并不记录窗口日志，而是对两个相邻窗口的请求数进行加权，计算公式为：
当 时接受请求，否则拒绝请求。
相较于 固定窗口计数器算法 ：
- 更精准，能平滑处理窗口边界
- 实现更复杂
相较于 固定窗口计数器算法 ：
- 计算更为简单，存储空间占用更少
- 但不够精确，窗口边界处仍能突破阈值
wechat
alipay