Redisson 滑动窗口限流

Redisson 滑动窗口限流器原理总结

核心思想

将时间划分为更细粒度的单元格（Cell），用一个固定长度的队列来模拟一个时间窗口在时间轴上的滑动。通过统计当前窗口内所有单元格的请求次数总和，来判断是否超出限流阈值。

核心组件与概念

1. 时间窗口（Window）

   • 用户定义的限流时间范围，例如 10秒内 允许 100次 请求。
   • 窗口会随着时间推移而“滑动”。

2. 单元格（Cell）

   • 为了降低精度损耗，将整个时间窗口划分为多个更小的、长度相等的时间单元。
   • 例如：一个 10秒 的窗口可以划分为 10 个 1秒 的单元格。
   • 作用：每个单元格独立存储该时间段内的请求计数。这样无需为每个请求记录时间戳，极大地节省了内存和计算资源。

3. 队列（Redis List）

   • 在 Redis 中，使用一个 List（列表） 数据结构来按时间顺序存储这些单元格。
   • 列表中的每个元素代表一个单元格，通常是一个键值对（或使用ZSet，但RRateLimiter常用List），包含：
     • 时间戳（或单元格的起始时间）
     • 计数（在该单元格时间段内发生的请求数）

工作流程（算法步骤）

假设我们有一个限流规则：在 10 秒内最多允许 100 次请求。

1. 初始化 & 划分单元格

   • Redisson 可能会将 10秒 的窗口划分为 10 个单元格，每个单元格跨度为 1秒。

2. 请求到来时（tryAcquire() 调用）

   • Step 1: 计算当前时间戳

     • 获取当前的 Unix 时间戳（毫秒或秒精度）。

   • Step 2: 清理过期单元格（滑动窗口的“滑动”）

     • 定义“过期”：所有结束时间小于 当前时间戳 - 窗口大小 的单元格都被视为过期。
     • 操作：从队列头部开始，逐个检查单元格的时间戳。如果过期，就将其从队列中弹出（lpop），并从总计数中减去该单元格的计数。
     • 这一步是实现“滑动”的关键：通过不断移除过期的数据，保证了窗口始终只包含最近 10秒 的数据。

   • Step 3: 计算当前窗口的总请求数

     • 清理后，队列中剩余的所有单元格都是当前有效窗口内的数据。
     • 将所有剩余单元格的计数累加，得到 当前总请求数。

   • Step 4: 判断是否允许通过

     • 如果 当前总请求数 >= 限流阈值 (100)，则请求被拒绝。
     • 如果 当前总请求数 < 限流阈值，则请求被允许。

   • Step 5: 记录本次请求（如果允许）

     • 获取当前时间所在的单元格。
     • 检查队列尾部的单元格：
       • 如果尾部单元格的时间范围包含了当前时间，则将该单元格的计数 +1。
       • 否则，说明需要创建一个新的单元格添加到队列尾部（rpush），并设置其计数为 1。

3. 原子性保证

   • 整个 Step 2 到 Step 5 的过程使用 Redis Lua 脚本执行。
   • 为什么？ Lua 脚本在 Redis 中是原子执行的，确保了清理过期数据、计算总数、判断和更新计数这一系列操作是线程安全的，不会出现竞态条件。这是实现高并发限流的核心保障。

技术亮点

1. 空间换时间：通过单元格划分，避免了为每个请求存储一个时间戳的巨大开销，只需维护固定数量的单元格，内存占用更小，性能更高。
2. 滑动精确：每次请求都会触发一次过期清理，保证了时间窗口的滑动非常精确和实时。
3. 原子操作：基于 Lua 脚本，所有逻辑在 Redis 端原子性完成，并发安全。
4. 高性能：大部分计算逻辑在 Redis 服务器端完成，网络传输开销小（通常只需一次 Lua 脚本调用）。

与其它算法的对比

笔记要点（一句话总结）

• 原理：将大窗口划分为小单元格，用队列维护，每次请求清理过期单元格并统计窗口内总数。
• 实现：基于 Redis List + Lua 脚本（保证原子性）。
• 关键：“滑动”通过清理队列头部的过期单元格来实现。
• 优点：在精度、内存和性能之间取得了最佳平衡，是生产环境最常用的限流方案之一。

-- 速率
local rate = redis.call("hget", KEYS[1], "rate")
-- 时间区间(ms)
local interval = redis.call("hget", KEYS[1], "interval")
local type = redis.call("hget", KEYS[1], "type")
assert(rate ~= false and interval ~= false and type ~= false, "RateLimiter is not initialized")

-- {name}:value 分析后面的代码，这个key记录的是当前令牌桶中的令牌数
local valueName = KEYS[2]

-- {name}:permits 这个key是一个zset，记录了请求的令牌数，score则为请求的时间戳
local permitsName = KEYS[4]

-- 单机限流才会用到，集群模式不用关注
if type == "1" then
   valueName = KEYS[3]
   permitsName = KEYS[5]
end

-- 原版本有bug(https://github.com/redisson/redisson/issues/3197)，最新版将这行代码提前了
-- rate为1 arg1这里是 请求的令牌数量(默认是1)。rate必须比请求的令牌数大
assert(tonumber(rate) >= tonumber(ARGV[1]), "Requested permits amount could not exceed defined rate")

-- 第一次执行这里应该是null，会进到else分支
-- 第二次执行到这里由于else分支中已经放了valueName的值进去，所以第二次会进if分支
local currentValue = redis.call("get", valueName)
if currentValue ~= false then
   -- 从第一次设的zset中取数据，范围是0 ~ (第二次请求时间戳 - 令牌生产的时间)
   -- 可以看到，如果第二次请求时间距离第一次请求时间很短(小于令牌产生的时间)，那么这个差值将小于上一次请求的时间，取出来的将会是空列表。反之，能取出之前的请求信息
   -- 这里作者将这个取出来的数据命名为expiredValues，可认为指的是过期的数据
   local expiredValues = redis.call("zrangebyscore", permitsName, 0, tonumber(ARGV[2]) - interval)
   local released = 0
   -- lua迭代器，遍历expiredValues，如果有值，那么released等于之前所有请求的令牌数之和，表示应该释放多少令牌
   for i, v in ipairs(expiredValues) do
       local random, permits = struct.unpack("fI", v)
       released = released + permits
   end

   -- 没有过期请求的话，released还是0，这个if不会进，有过期请求才会进
   if released > 0 then
       -- 移除zset中所有元素，重置周期
       redis.call("zrem", permitsName, unpack(expiredValues))
       currentValue = tonumber(currentValue) + released
       redis.call("set", valueName, currentValue)
   end

   -- 这里简单分析下上面这段代码:
   -- 1. 只有超过了1个令牌生产周期后的请求，expiredValues才会有值。
   -- 2. 以rate为3举例，如果之前发生了两个请求那么现在released为2，currentValue为1 + 2 = 3
   -- 以此可以看到，redisson的令牌桶放令牌操作是通过请求时间窗来做的，如果距离上一个请求的时间已经超过了一个令牌生产周期时间，那么令牌桶中的令牌应该得到重置，表示生产rate数量的令牌。

   -- 如果当前令牌数 ＜ 请求的令牌数
   if tonumber(currentValue) < tonumber(ARGV[1]) then
       -- 从zset中找到距离当前时间最近的那个请求，也就是上一次放进去的请求信息
       local nearest = redis.call('zrangebyscore', permitsName, '(' .. (tonumber(ARGV[2]) - interval), tonumber(ARGV[2]), 'withscores', 'limit', 0, 1); 
       local random, permits = struct.unpack("fI", nearest[1])
       -- 返回 上一次请求的时间戳 - (当前时间戳 - 令牌生成的时间间隔) 这个值表示还需要多久才能生产出足够的令牌
       return tonumber(nearest[2]) - (tonumber(ARGV[2]) - interval)
   else
       -- 如果当前令牌数 ≥ 请求的令牌数，表示令牌够多，更新zset
       redis.call("zadd", permitsName, ARGV[2], struct.pack("fI", ARGV[3], ARGV[1]))
       -- valueName存的是当前总令牌数，-1表示取走一个
       redis.call("decrby", valueName, ARGV[1])
       return nil
   end
else
   -- set一个key-value数据 记录当前限流器的令牌数
   redis.call("set", valueName, rate)
   -- 建了一个以当前限流器名称相关的zset，并存入 以score为当前时间戳，以lua格式化字符串{当前时间戳为种子的随机数、请求的令牌数}为value的值。
   -- struct.pack第一个参数表示格式字符串，f是浮点数、I是长整数。所以这个格式字符串表示的是把一个浮点数和长整数拼起来的结构体。我的理解就是往zset里记录了最后一次请求的时间戳和请求的令牌数
   redis.call("zadd", permitsName, ARGV[2], struct.pack("fI", ARGV[3], ARGV[1]))
   -- 从总共的令牌数 减去 请求的令牌数。
   redis.call("decrby", valueName, ARGV[1])
   return nil
end