限流算法（计数器/漏桶/令牌桶）

微信扫一扫关注公众号喜欢收藏+点赞👍 谢谢

计数器算法

固定窗口计数器

步骤

时间线划分为多个独立且固定大小窗口

落在每一个时间窗口内的请求就将计数器加 1

如果计数器超过了限流值，则后续落在该窗口的请求都会被拒绝

时间到达下一个时间窗口时，计数器会被重置为 0

缺陷

临界点问题：比如59秒时打满100个请求，60秒时重置，又打满100个请求，相当于1秒钟来了200个请求

资源浪费：我们希望100个请求可以均匀分在这一分钟内，但如果提前达到请求上限，剩余时间服务器就闲置了

滑动窗口计数器

将单位时间划分为多个区间，一般都是均分为多个小的时间段

每一个区间内都有一个计数器，有一个请求落在该区间内，则该区间内的计数器就会加一

每过一个时间段，时间窗口就会往右滑动一格，抛弃最老的一个区间，并纳入新的一个区间

计算整个时间窗口内的请求总数时会累加所有的时间片段内的计数器，总和超过了限制数，则拒绝接收请求

时间区间的精度越高，算法所需的空间容量就越大

漏桶算法

将每个请求放入固定大小的队列进行存储

队列以固定速率向外流出请求，如果队列为空则停止流出

如队列满了则多余的请求会被直接拒绝

当短时间内有大量的突发请求时，即使服务器负载不高，每个请求也都得在队列中等待一段时间才能被响应

令牌桶算法

以固定速率生成令牌并放入到令牌桶中

如果令牌桶满了则多余的令牌会直接丢弃

当请求到达时，会尝试从令牌桶中取令牌，取到了令牌的请求可以执行

如果桶空了，则拒绝该请求