滑动窗口算法

发表于 分类于

TCP 滑动窗口 (流控)：

1
2
3
4
5
TCP 发送窗口:
                  ← 已发送已确认 → ← 已发送未确认 → ← 未发送可发送 → ← 不可发送 →
                  |_______________|_________________|_________________|_____________|
                  ↑               ↑                 ↑                 ↑
                 left          SND.UNA           SND.NXT       SND.UNA + snd_wnd

TCP 的流量控制核心就是滑动窗口——接收方通过 ACK 告诉发送方 rwnd (接收窗口大小)，发送方控制未确认的字节数不超过这个窗口。

分布式限流滑动窗口：

固定窗口计数器最大的问题是边界突刺——09:59:59 和 10:00:01 两秒内可能发送两倍限流量的请求。滑动窗口解决这个问题：

1
2
3
4
5
6
7
8
滑动窗口限流 (窗口 = 60s, 粒度 = 6 格每 10s):
        ┌───┬───┬───┬───┬───┬───┐
  now → │g0 │g1 │g2 │g3 │g4 │g5 │  ← 每格记录该 time slot 内的请求数
        └───┴───┴───┴───┴───┴───┘
        ↑ 窗口覆盖范围 (过去 60 秒)

当前窗口计数 = g0+g1+g2+g3+g4+g5
下一时刻: 指针前进 → 覆盖范围右移 → 最左边格清零 → 新格开始计数

实现可以用数组 + 指针循环移动，也可以用 Redis ZSET（score 为时间戳，ZREMRANGEBYSCORE 删除过期元素，ZCARD 获取窗口内计数）。Sentinel/Gateway 的限流模块广泛使用滑动窗口算法。