3. Rate Limit 基础概念：令牌桶算法、漏桶算法、滑动窗口算法原理与适用场景
在云原生网关的版本差异校验场景中，限流算法的选择直接决定了回滚护栏的精度与资源开销。本节将深入剖析三种主流限流算法的核心原理、数学建模与工程适用场景，为后续的版本差异校验提供理论基础。
3.1 令牌桶算法（ Bucket）
令牌桶算法是业界应用最广泛的限流算法，其核心思想是通过一个“桶”来平滑突发流量。系统以恒定速率向桶中放入令牌，每个请求需要消耗一个令牌才能被处理。桶的容量限制了最大突发流量。
核心公式： 令牌数 = min(桶容量, 上次令牌数 + (当前时间 - 上次时间) × 填充速率)
算法流程
- 初始化： 桶容量为
burst，填充速率为rate（令牌/秒），初始令牌数为burst。 - 请求到达： 计算当前桶内令牌数（考虑时间流逝产生的令牌）。
- 判断： 若桶内令牌数 ≥ 1，则消耗 1 个令牌，允许请求通过；否则拒绝请求。
- 更新： 记录当前时间，更新令牌数。
适用场景
- 允许突发流量： 如电商秒杀、热点新闻推送，短时间内允许超出平均速率的请求。
- API 网关全局限流： 需要平滑流量但容忍短时尖峰的场景。
- 版本差异校验： 当新版本上线时，允许突发流量快速验证，但限制长期平均速率。
工程建议： 在云原生网关中，令牌桶算法通常配合
burst 参数动态调整。版本回滚时，可临时增大 burst 以加速流量切换，但需注意后端服务的承载能力。
3.2 漏桶算法（Leaky Bucket）
漏桶算法将请求视为水滴，以恒定速率从桶底“漏出”处理。桶的容量限制了排队等待的请求数，超出容量的请求直接被丢弃。与令牌桶不同，漏桶算法强制输出速率恒定，不具备突发能力。
核心特性： 输出速率严格恒定，输入速率可波动但受桶容量限制。
算法流程
- 请求入桶： 请求到达时，若桶未满则加入队列尾部；若桶已满则拒绝。
- 恒定漏出： 系统以固定速率从队列头部取出请求进行处理。
- 队列管理： 桶容量即最大排队长度，超出部分直接丢弃。
适用场景
- 流量整形： 需要严格限制输出速率，如数据库连接池、下游服务保护。
- 削峰填谷： 将突发流量平滑为恒定速率，保护后端系统。
- 版本回滚场景： 当回滚到旧版本时，使用漏桶算法可确保旧版本不会因突发流量而过载。
注意： 漏桶算法不适合需要快速响应的场景。在版本差异校验中，若新版本需要快速放量验证，漏桶算法可能因强制恒定速率而延迟问题发现。
3.3 滑动窗口算法（Sliding Window）
滑动窗口算法将时间划分为多个小窗口，通过统计当前窗口内的请求数来判断是否限流。它解决了固定窗口算法的“临界突变”问题，精度更高，但需要维护窗口状态。
核心思想： 将时间窗口细分为 N 个子窗口，每次请求统计当前时间点所在窗口及之前 N-1 个子窗口的总请求数。
算法流程
- 划分窗口： 将时间窗口（如 1 秒）划分为 M 个子窗口（如 10 个 100ms 子窗口）。
- 请求计数： 每个子窗口独立计数，记录该时间段内的请求数。
- 滑动判断： 当前请求到达时，计算当前子窗口及之前 M-1 个子窗口的总请求数。
- 限流决策： 若总请求数超过阈值则拒绝，否则允许通过并更新当前子窗口计数。
适用场景
- 高精度限流： 需要精确控制每秒/每分钟请求数的场景，如 API 计费、SLA 保障。
- 版本灰度发布： 在版本差异校验中，滑动窗口可以精确控制新版本在单位时间内的请求比例。
- 防刷与安全： 需要检测短时间内的异常请求模式。
3.4 三种算法对比
| 特性 | 令牌桶算法 | 漏桶算法 | 滑动窗口算法 |
|---|---|---|---|
| 输出速率 | 允许突发，平均速率受限 | 严格恒定 | 窗口内平均速率受限 |
| 突发处理 | 支持（通过桶容量） | 不支持（强制平滑） | 有限支持（窗口内可突发） |
| 内存开销 | 低（仅维护令牌数和时间戳） | 低（仅维护队列长度） | 中（需维护 M 个子窗口计数） |
| 精度 | 中等（受令牌填充间隔影响） | 高（输出严格恒定） | 高（子窗口粒度可调） |
| 实现复杂度 | 低 | 低 | 中 |
| 版本差异校验适用性 | 适合突发验证场景 | 适合保护旧版本 | 适合精确比例控制 |
版本差异校验选型建议： 在云原生网关回滚护栏中，推荐组合使用令牌桶算法（处理突发验证）与滑动窗口算法（精确控制比例）。漏桶算法更适合作为后端服务的保护层，而非网关层的版本差异校验。