四种常用限流算法对比
date
Feb 9, 2022
slug
network-four-rate-limit-algorithms
status
Published
tags
系统和网络
summary
漏桶、令牌桶、固定窗口、滑动窗口限流
type
Post
Leaky Bucket 漏桶
漏桶可理解为是一个限定容量的请求队列。
想象有一个桶，有水（指请求或数据）从上面流进来，水从桶下面的一个孔流出来。水流进桶的速度可以是随机的，但是水流出桶的速度是恒定的。
当水流进桶的速度较慢，桶不会被填满，请求就可以被处理。
当水流进桶的速度过快时，桶会逐渐被填满，当水超过桶的容量就会溢出，即被丢弃。
结果
Token Bucket 令牌桶
在令牌桶算法中，系统会以一个固定的速率向桶中添加令牌。
当有请求（或数据包）到来时，会从桶中删除一定数量的令牌。如果桶中有足够的令牌，请求就可以立即处理；
如果桶中没有足够的令牌，请求就会被阻塞或丢弃，具体行为取决于具体的实现。
桶有容量限制，如果添加令牌时桶已满，新的令牌就会被丢弃。
结果
Fixed Window 固定窗口
在一个固定的时间窗口内，只允许一定数量的请求。
如果在这个时间窗口内的请求已经达到了限制，那么新的请求就会被拒绝，过了当前时间窗口后，会进入下一个时间窗口，并重置窗口内的请求数量，重新计算。
结果
Sliding Window 滑动窗口
在固定窗口限流算法中，如果大量请求在一个时间窗口的边界附近到达，可能会造成瞬时的流量突增。
滑动窗口随着时间的推移，动态统计请求量，避免了在窗口边界附近的流量突增。
结果
还有一种方式，不需要记录具体每个请求的时间点，而通过计算滑动窗口与固定窗口之间时间的偏移，估算出滑动窗口中请求量，这个方式不太准确，但节省了请求时间点的存储成本。
图中所示，已知设窗口大小为 1 小时即 60 分钟，每个窗口内可处理 100 请求，当前时间为 1:15。
在 [12:00–1:00) 的整个绿色窗口中一共有 84 个请求，在 [1:00 to 1:15) 的黄色窗口中，15 分钟内已经处理了 36 个请求，如何计算当前窗口剩余容量？
通过计算滑动窗口与前一窗口重叠部分占比，来估算前一窗口中被占用的容量，
(60分钟-15分钟)/60分钟 表示滑动窗口减去黄色当前窗口后，与绿色窗口的重叠，占绿色窗口整体的百分比，也就估算出重叠部分的请求量在总共 84 个请求的占比，得出 63 个请求，再加上当前窗口的 36 请求，一共是 99 请求，那么当前滑动窗口的剩余容量就是 100 - 99 = 1 个请求容量。结果
参考：
- 图解+代码|常见限流算法以及限流在单机分布式场景下的思考：https://segmentfault.com/a/1190000023552181
- Design a Scalable Rate Limiting Algorithm — System Design：https://medium.com/@NlognTeam/design-a-scalable-rate-limiting-algorithm-system-design-nlogn-895abba44b77
- How to Design a Scalable Rate Limiting Algorithm with Kong API：https://konghq.com/blog/how-to-design-a-scalable-rate-limiting-algorithm/
- 漏桶算法和令牌桶算法，区别到底在哪里？：https://xie.infoq.cn/article/4a0acdd12a0f6dd4a53e0472c
- Rate limiting using the Sliding Window algorithm：https://dev.to/satrobit/rate-limiting-using-the-sliding-window-algorithm-5fjn