3. 限流算法（上）：固定窗口计数器算法原理、滑动窗口日志算法原理、滑动窗口计数器算法原理
在模型 Serving 层，限流算法的选择直接决定了流量整形效果与资源保护能力。本章聚焦三种最基础的窗口类限流算法：固定窗口计数器、滑动窗口日志 与 滑动窗口计数器。理解它们的原理、边界与适用场景，是后续学习令牌桶、漏桶等高级算法的基础。
3.1 固定窗口计数器算法
固定窗口计数器是最直观的限流实现。它将时间划分为固定的窗口（如 1 秒），每个窗口内维护一个计数器，请求到达时计数器加 1；当计数器超过阈值时，拒绝后续请求；窗口结束时计数器归零。
3.1.1 核心流程
- 定义窗口大小
W（如 1000ms）与阈值limit（如 10）。 - 记录当前窗口起始时间戳
windowStart与计数器counter。 - 请求到达时，判断当前时间是否已超出
windowStart + W：- 若超出，重置
windowStart为当前时间，counter归零。 - 若未超出，检查
counter < limit：是则放行并递增；否则拒绝。
- 若超出，重置
3.1.2 临界问题（Traffic Burst at Boundary）
⚠ 经典缺陷：固定窗口在窗口切换瞬间可能出现两倍阈值的突发流量。例如窗口大小 1s、阈值 10，若前窗口最后 100ms 内通过 10 个请求，后窗口开始 100ms 内又通过 10 个请求，则 200ms 内实际通过了 20 个请求，远超阈值。
| 参数 | 值 | 说明 |
|---|---|---|
| 窗口大小 | 1000 ms | 时间粒度 |
| 阈值 | 10 req | 每窗口最大请求数 |
| 计数器 | int | 原子变量或 Redis INCR |
| 重置策略 | 窗口到期归零 | 硬边界 |
3.1.3 适用场景
- 对突发不敏感、允许短时毛刺的业务（如日志上报、非关键指标采集）。
- 实现简单，适合客户端限流或低精度保护。
- 配合预热或排队机制可缓解临界问题，但无法根除。
3.2 滑动窗口日志算法
滑动窗口日志（Sliding Window Log）通过记录每个请求的时间戳，在每次请求时统计当前时间往前一个窗口长度内的请求总数，从而精确控制任意时间窗口内的流量。它彻底解决了固定窗口的临界突发问题，但代价是存储与计算开销较高。
3.2.1 核心流程
- 维护一个有序集合（如 Redis ZSET、TreeSet），存储每个请求的时间戳。
- 请求到达时，计算窗口左边界
now - windowSize。 - 移除集合中所有小于左边界的过期时间戳（清理）。
- 统计集合中剩余元素数量
count。 - 若
count < limit，将当前时间戳加入集合并放行；否则拒绝。
3.2.2 优缺点对比
| 维度 | 说明 |
|---|---|
| 精度 | 理论最高，任意时刻窗口内请求数精确可控 |
| 内存占用 | O(N)，N 为窗口内请求数，高 QPS 下增长快 |
| 清理开销 | 每次请求需扫描过期数据，CPU 消耗随窗口大小线性增长 |
| 分布式友好 | 依赖 Redis ZSET 可做全局限流，但需注意大 Key 问题 |
💡 优化建议：可设置异步定时清理过期日志，减少每次请求的扫描量；或使用近似算法（如滑动窗口计数器）降低精度换取性能。
3.3 滑动窗口计数器算法
滑动窗口计数器（Sliding Window Counter）是固定窗口与滑动窗口日志的折中方案。它将窗口划分为多个小格子（sub-window），每个格子独立计数；滑动时仅统计当前时间所在格子及之前 N-1 个格子的总和，实现近似滑动效果。常见实现如 Redis 的 CL.THROTTLE 命令。
3.3.1 核心流程
- 将窗口
W划分为N个格子，每个格子时长W/N（如 1s 窗口分 10 格，每格 100ms）。 - 每个格子独立计数器，使用当前时间戳对格子时长取模定位格子索引。
- 请求到达时，计算当前格子索引，累加当前格子计数器。
- 统计当前格子及前
N-1个格子的计数器总和。 - 若总和
< limit，放行；否则拒绝。
3.3.2 格子粒度与精度
| 格子数 N | 精度 | 内存开销 | 典型场景 |
|---|---|---|---|
| 2 | 低（接近固定窗口） | 极低 | 快速原型 |
| 10 | 中（误差约 10%） | 低 | 生产常用 |
| 100 | 高（误差约 1%） | 中 | 高精度要求 |
📐 误差分析：滑动窗口计数器的误差来源于格子边界处的请求归属。当请求落在格子中间时，该格子被完整计入当前窗口，但实际该格子中部分请求可能属于上一个窗口。格子数越多，误差越小，但内存与计算开销线性增长。
3.4 三种算法对比总览
| 算法 | 精度 | 内存开销 | 临界突发 | 实现复杂度 | 推荐场景 |
|---|---|---|---|---|---|
| 固定窗口计数器 | 低 | O(1) | 有 | 极低 | 低精度、低并发、客户端限流 |
| 滑动窗口日志 | 最高 | O(N) | 无 | 高 | 高精度、低 QPS 或可接受清理开销 |
| 滑动窗口计数器 | 中-高 | O(N) | 基本消除 | 中 | 生产环境通用，平衡精度与性能 |
3.5 算法原理对比图
下图展示了三种算法在时间轴上的窗口划分方式与计数逻辑差异，帮助直观理解滑动与固定的本质区别。
3.6 选型建议
🎯 生产推荐：对于大多数模型 Serving 场景，滑动窗口计数器（N=10~20）是性价比最高的选择。它消除了固定窗口的临界突发问题，内存与 CPU 开销可控，且容易在 Redis 或本地内存中实现。若业务对精度有极致要求且 QPS 较低（如 <1000/s），可选用滑动窗口日志；若仅需粗粒度保护且允许短时毛刺，固定窗口计数器仍可胜任。
3.7 本章小结
- 固定窗口计数器：实现最简单，但存在窗口边界突发流量问题，适合低精度场景。
- 滑动窗口日志：精度最高，通过记录每个请求时间戳实现精确滑动，但存储与清理开销大。
- 滑动窗口计数器：折中方案，将窗口划分为多个格子，统计格子总和实现近似滑动，是生产环境的主流选择。
- 三种算法在精度、内存、实现复杂度上形成梯度，选型时应结合业务 QPS、精度要求与基础设施能力综合判断。