分布式服务之限流算法-滑动窗口基于Redis实现

限流器有多种算法，比如固定窗口、滑动窗口、漏桶、令牌桶等，我们这里给一个简易的基于Redis的分布式滑动窗口限流器方案。

如：1 分钟限流 1000 请求。

方案一：分桶滑动窗口

把 1分钟这60s 窗口切分成 60 个 1s 的小桶，sum 最近 60 桶的次数。

逻辑：

• 桶 key：limit:xxx:秒时间戳（前缀 + 秒级时间戳，精确到秒）
• 每个桶记录当前这 1 秒内的请求计数
• 限流判断逻辑：
  1. 拿到当前时间，算出当前属于哪个秒桶；
  2. 找出当前秒以及往前 59 秒，一共 60 个桶；
  3. Redis 批量读取这 60 个 key，sum 所有计数值；
  4. 如果 sum <1000 则放行，当前桶 + 1；否则拒绝。
  5. 旧桶（超过 60s）可以设置过期时间自动清理。

问题

1. 每次请求都要读取最多 60 个 key，网络开销大
2. 非原子性：mget + incr 两步，存在竞态
3. 桶边界毛刺：拆分窗口不可避免
4. key 数量多

优化竞态

有mget，incr操作，可以利用lua脚本做原子性处理。

方案二：利用zset结构，一个key

方案二是对方案一的优化，使用一个key（并发高的时候，可能造成大key。如果上限1000也没问题）。

zset 滑动窗口方案，一个 zset 维护所有请求时间点，不是分桶。

1. 每个请求作为 zset 里一条 member，score 是请求时间戳（为了排序，删除）；
2. 每次清理 60s 前数据，zcard 统计数量。

优缺点

1. 优点：没有分桶粒度误差（每个请求都记录了下来）、一个redis key解决
2. 缺点：请求量大的时候 zset 元素会很多，1000 个请求就 1000 条 member。(不是incr这种计数)

• key：limit:resource:zset
• member：随机唯一值（只要记录下来本次请求），score：请求时间戳（毫秒）

逻辑：

1. 移除所有 score <(now - 60000) 的记录（清除窗口外请求）
2. 获取 zset 元素总数 zcard
3. 如果总数 <1000：添加当前请求，返回放行；否则拒绝

• 分布式