2. 限流算法基础：令牌桶、漏桶、滑动窗口算法的原理与对比
在 OpenAPI 网关的限流熔断治理中，选择合适的限流算法直接决定了流量整形效果与系统稳定性。本节深入剖析三种主流限流算法的核心原理、数学模型与适用场景，并通过对比表格与架构图帮助建立直观认知。
2.1 令牌桶算法（Token Bucket）
令牌桶算法是业界应用最广泛的限流算法之一，其核心思想是：以恒定速率向桶中放入令牌，请求到达时必须从桶中获取到令牌才能被放行。桶的容量限制了突发流量的大小。
核心参数
| 参数 | 符号 | 说明 |
|---|---|---|
| 令牌生成速率 | r | 每秒向桶中放入的令牌数，即平均允许的请求速率 |
| 桶容量 | b | 桶最多能存放的令牌数，决定了突发流量的大小 |
| 当前令牌数 | c | 桶中当前可用的令牌数量 |
| 最后填充时间 | t_last | 上次计算令牌数的时间戳 |
算法流程
- 初始化：桶满（c = b），记录当前时间 t_last。
- 请求到达：计算自 t_last 以来应生成的令牌数 Δt × r，更新 c = min(b, c + Δt × r)，更新 t_last。
- 判断放行：若 c ≥ 1，则消耗 1 个令牌（c = c - 1），请求放行；否则请求被拒绝或排队。
关键特性：令牌桶允许一定程度的突发流量——只要桶中有足够的令牌，短时间内的请求可以全部通过。突发上限由桶容量 b 控制。
工程实践：在 Guava RateLimiter 和 Sentinel 中，令牌桶算法被广泛用于控制 API 调用频率。实际实现时通常采用“懒计算”方式，仅在请求到达时计算令牌增量，避免定时任务开销。
2.2 漏桶算法（Leaky Bucket）
漏桶算法将请求视为水滴，以恒定速率从桶底漏出，桶的容量限制了可堆积的请求数量。与令牌桶不同，漏桶强制输出速率完全平滑，不允许突发。
核心参数
| 参数 | 符号 | 说明 |
|---|---|---|
| 漏出速率 | r | 每秒从桶底漏出的请求数，即实际处理速率 |
| 桶容量 | b | 桶最多能容纳的等待请求数 |
| 当前水量 | w | 桶中当前等待处理的请求数 |
| 最后漏水时间 | t_last | 上次计算漏水量的时间戳 |
算法流程
- 请求到达：计算自 t_last 以来漏出的水量 Δt × r，更新 w = max(0, w - Δt × r)，更新 t_last。
- 判断入桶：若 w < b，则请求入桶（w = w + 1），等待后续漏出处理；否则请求被丢弃。
- 漏出处理：后台以恒定速率 r 从桶中取出请求进行处理。
注意：漏桶算法的输出速率严格恒定，即使上游流量突然增大，下游服务也不会感受到突发压力。但这也意味着当桶满时，所有超出的请求都会被直接丢弃，无法像令牌桶那样利用积攒的令牌应对突发。
2.3 滑动窗口算法（Sliding Window）
滑动窗口算法将时间划分为多个小窗口，通过统计当前窗口及之前窗口的请求总数来判断是否超过阈值。它是固定窗口算法的改进版本，解决了固定窗口在边界处的流量突刺问题。
核心参数
| 参数 | 符号 | 说明 |
|---|---|---|
| 窗口总时长 | W | 限流统计的时间跨度，如 1 秒、1 分钟 |
| 子窗口数 | n | 将总窗口划分为 n 个子窗口，通常 n ≥ 10 |
| 子窗口时长 | w | w = W / n，每个子窗口的统计粒度 |
| 阈值 | limit | 在总窗口时长内允许的最大请求数 |
算法流程
- 请求到达：确定当前时间所属的子窗口索引。
- 滑动统计：移除已过期子窗口（时间 < 当前时间 - W）的计数。
- 累加计数：将当前子窗口及所有未过期子窗口的请求数累加。
- 判断放行：若累加总数 < limit，则请求放行并增加当前子窗口计数；否则拒绝。
优势：滑动窗口通过细分子窗口实现了近似连续的统计，避免了固定窗口在窗口切换瞬间的流量突刺。子窗口越多，精度越接近真正的滑动时间窗，但内存开销也越大。
2.4 三种算法对比分析
| 对比维度 | 令牌桶 | 漏桶 | 滑动窗口 |
|---|---|---|---|
| 输出速率 | 平均速率可控，允许突发 | 严格恒定，完全平滑 | 平均速率可控，允许突发 |
| 突发处理 | 支持，由桶容量控制 | 不支持，桶满即丢弃 | 支持，由窗口阈值控制 |
| 实现复杂度 | 中等（需维护时间戳与计数器） | 低（队列 + 定时器） | 中等（需维护子窗口数组） |
| 内存开销 | 低（仅 2 个变量） | 低（仅队列指针） | 较高（n 个子窗口计数器） |
| 精度 | 高（连续时间模型） | 高（连续时间模型） | 取决于子窗口数量 |
| 适用场景 | 允许短时突发的 API 调用 | 要求输出绝对平滑的场景 | 分布式环境下的简单限流 |
| 典型实现 | Guava RateLimiter, Sentinel | Nginx limit_req, 队列系统 | Redis + Lua, 本地计数器 |
2.5 算法选择建议
- API 网关限流：优先选择令牌桶算法。它既能保证平均速率，又能应对突发流量，适合大多数 OpenAPI 调用场景。
- 下游保护：若下游服务对请求速率极其敏感（如数据库写入），使用漏桶算法强制平滑输出。
- 分布式简单限流：当需要跨多个节点共享限流状态时，滑动窗口 + Redis 是轻量级方案，实现简单且易于理解。
- 混合策略：生产环境中常采用“令牌桶 + 漏桶”组合——令牌桶控制入口速率，漏桶保护下游服务。
缓存一致性视角：在分布式限流中，令牌桶和滑动窗口的计数器需要跨节点同步。后续章节将详细讨论如何通过 Redis 原子操作、本地缓存预热与一致性哈希等手段，在保证限流精度的同时降低同步延迟。
2.6 分布式环境下的算法选型考量
在微服务架构中，限流算法需要跨多个网关节点协同工作。以下是分布式环境下的关键考量：
| 考量因素 | 令牌桶 | 漏桶 | 滑动窗口 |
|---|---|---|---|
| 状态同步 | 需同步令牌数，可用 Redis 原子操作 | 需同步队列状态，复杂度较高 | 需同步子窗口计数，Redis 支持良好 |
| 一致性要求 | 最终一致即可，允许少量偏差 | 强一致要求高，否则漏出速率不准 | 最终一致即可，子窗口粒度可调 |
| 性能开销 | 低（每次请求 1 次 Redis 操作） | 中（需维护队列） | 低（每次请求 1 次 Redis 操作） |
| 推荐方案 | Redis + Lua 原子脚本 | 本地队列 + 分布式协调 | Redis Sorted Set 或 Hash |