京公网安备11010502063487号固定窗口、滑动窗口、令牌桶、漏桶这几种限流算法,在窗口边界、持续过载和周期性突发下各自会放行多少?每个 key 要多少状态?手写的令牌桶中间件并发下对不对?这篇用同一份实现的对照加 Go 的真实 HTTP 服务量出来。
限流器 | 放行(接受)的请求 | 任意 1 秒内最多放出多少个 -----------------+-----------+--------------- 固定窗口 | 200 | 200 滑动窗口日志 | 100 | 100 滑动窗口计数 | 110 | 110 令牌桶(burst 100) | 119 | 119 令牌桶(burst 20) | 39 | 39 漏桶(capacity 100) | 120 | 101 漏桶(capacity 20) | 40 | 40 固定窗口在 1.0 s 前后各放行一整个窗口的额度,1 秒里放出了 200 个(两倍限额);滑动窗口日志是精确的;滑动窗口计数是近似(上一窗口的计数按比例折算);令牌桶允许的突发由桶容量决定,漏桶(队列)把放出的节奏拉平到每 10 ms 一个
固定窗口在边界前后各放行一整个窗口的额度;滑动窗口日志精确;令牌桶的突发由桶容量决定;漏桶把放出的节奏拉平。
到达方式 | 限流器 | 每秒放行 最小 | 平均 | 最大 -----+--------+---------+-------+---- 均匀 | 固定窗口 | 100 | 100.0 | 100 均匀 | 滑动窗口日志 | 100 | 100.0 | 100 均匀 | 滑动窗口计数 | 100 | 100.0 | 100 均匀 | 令牌桶 | 100 | 100.0 | 100 均匀 | 漏桶 | 100 | 100.1 | 101 泊松 | 固定窗口 | 100 | 100.0 | 100 泊松 | 滑动窗口日志 | 97 | 99.0 | 100 泊松 | 滑动窗口计数 | 99 | 99.9 | 100 泊松 | 令牌桶 | 100 | 100.8 | 105 泊松 | 漏桶 | 100 | 100.0 | 100
长期过载下五种放行的平均速率都在限额附近,差别在突发和精度。
限流器 | 被拒绝 | 接受的请求等待时间 中位数 | p99 ----------------+-----------+---------------+------- 固定窗口 | 0 / 500 | 0 ms | 0 ms 滑动窗口日志 | 0 / 500 | 0 ms | 0 ms 滑动窗口计数 | 0 / 500 | 0 ms | 0 ms 令牌桶(burst 50) | 0 / 500 | 0 ms | 0 ms 令牌桶(burst 10) | 400 / 500 | 0 ms | 0 ms 漏桶(capacity 50) | 0 / 500 | 245 ms | 490 ms 漏桶(capacity 10) | 392 / 500 | 50 ms | 100 ms
令牌桶和窗口类放行突发不排队;漏桶把突发摊平,代价是延迟。
限流器 | allow() 速度 | 每个 key 的状态(Python 对象) -------+------------+---------------------- 固定窗口 | 5639 千次/秒 | 113 字节 滑动窗口日志 | 4771 千次/秒 | 4320 字节 滑动窗口计数 | 4124 千次/秒 | 121 字节 令牌桶 | 4842 千次/秒 | 161 字节 漏桶 | 4945 千次/秒 | 129 字节 滑动窗口日志要为每个放行的请求存一个时间戳,所以每个 key 的状态随限额线性增长;固定窗口、滑动窗口计数、令牌桶、漏桶每个 key 只存常数个数字
滑动窗口日志的状态随限额线性增长,其余四种是常数。
场景 | 请求总数 | 放行 | 429 | 理论上界 速率 × 时间 + burst | 每秒放行数 -------------+-------+-----+-------+----------------------+----------------------------- 200/s 开环,5 s | 1000 | 518 | 482 | 521 | [99, 100, 100, 100, 100, 19] 8 线程不限速,3 s | 42815 | 320 | 42495 | 321 | [100, 100, 100, 20] (连接类错误 0 次;不是超时,应为 0)
Go 版本在并发下的总放行数没有超过 速率 × 时间 + burst。