Redisson 滑動(dòng)窗口限流

Redisson 滑動(dòng)窗口限流器原理總結(jié)

核心思想

將時(shí)間劃分為更細(xì)粒度的單元格（Cell），用一個(gè)固定長(zhǎng)度的隊(duì)列來(lái)模擬一個(gè)時(shí)間窗口在時(shí)間軸上的滑動(dòng)。通過(guò)統(tǒng)計(jì)當(dāng)前窗口內(nèi)所有單元格的請(qǐng)求次數(shù)總和，來(lái)判斷是否超出限流閾值。

核心組件與概念

  1. 時(shí)間窗口（Window）

    • 用戶(hù)定義的限流時(shí)間范圍，例如 10秒內(nèi) 允許 100次 請(qǐng)求。
    • 窗口會(huì)隨著時(shí)間推移而“滑動(dòng)”。

  2. 單元格（Cell）

    • 為了降低精度損耗，將整個(gè)時(shí)間窗口劃分為多個(gè)更小的、長(zhǎng)度相等的時(shí)間單元。
    • 例如：一個(gè) 10秒 的窗口可以劃分為 10 個(gè) 1秒 的單元格。
    • 作用：每個(gè)單元格獨(dú)立存儲(chǔ)該時(shí)間段內(nèi)的請(qǐng)求計(jì)數(shù)。這樣無(wú)需為每個(gè)請(qǐng)求記錄時(shí)間戳，極大地節(jié)省了內(nèi)存和計(jì)算資源。

  3. 隊(duì)列（Redis List）

    • 在 Redis 中，使用一個(gè) List（列表） 數(shù)據(jù)結(jié)構(gòu)來(lái)按時(shí)間順序存儲(chǔ)這些單元格。
    • 列表中的每個(gè)元素代表一個(gè)單元格，通常是一個(gè)鍵值對(duì)（或使用ZSet，但RRateLimiter常用List），包含：
      • 時(shí)間戳（或單元格的起始時(shí)間）
      • 計(jì)數(shù)（在該單元格時(shí)間段內(nèi)發(fā)生的請(qǐng)求數(shù)）

工作流程（算法步驟）

假設(shè)我們有一個(gè)限流規(guī)則：在 10 秒內(nèi)最多允許 100 次請(qǐng)求。

  1. 初始化 & 劃分單元格

    • Redisson 可能會(huì)將 10秒 的窗口劃分為 10 個(gè)單元格，每個(gè)單元格跨度為 1秒。

  2. 請(qǐng)求到來(lái)時(shí)（tryAcquire() 調(diào)用）

    • Step 1: 計(jì)算當(dāng)前時(shí)間戳

      • 獲取當(dāng)前的 Unix 時(shí)間戳（毫秒或秒精度）。

    • Step 2: 清理過(guò)期單元格（滑動(dòng)窗口的“滑動(dòng)”）

      • 定義“過(guò)期”：所有結(jié)束時(shí)間小于 當(dāng)前時(shí)間戳 - 窗口大小 的單元格都被視為過(guò)期。
      • 操作：從隊(duì)列頭部開(kāi)始，逐個(gè)檢查單元格的時(shí)間戳。如果過(guò)期，就將其從隊(duì)列中彈出（lpop），并從總計(jì)數(shù)中減去該單元格的計(jì)數(shù)。
      • 這一步是實(shí)現(xiàn)“滑動(dòng)”的關(guān)鍵：通過(guò)不斷移除過(guò)期的數(shù)據(jù)，保證了窗口始終只包含最近 10秒 的數(shù)據(jù)。

    • Step 3: 計(jì)算當(dāng)前窗口的總請(qǐng)求數(shù)

      • 清理后，隊(duì)列中剩余的所有單元格都是當(dāng)前有效窗口內(nèi)的數(shù)據(jù)。
      • 將所有剩余單元格的計(jì)數(shù)累加，得到 當(dāng)前總請(qǐng)求數(shù)。

    • Step 4: 判斷是否允許通過(guò)

      • 如果 當(dāng)前總請(qǐng)求數(shù) >= 限流閾值 (100)，則請(qǐng)求被拒絕。
      • 如果 當(dāng)前總請(qǐng)求數(shù) < 限流閾值，則請(qǐng)求被允許。

    • Step 5: 記錄本次請(qǐng)求（如果允許）

      • 獲取當(dāng)前時(shí)間所在的單元格。
      • 檢查隊(duì)列尾部的單元格：
        • 如果尾部單元格的時(shí)間范圍包含了當(dāng)前時(shí)間，則將該單元格的計(jì)數(shù) +1。
        • 否則，說(shuō)明需要?jiǎng)?chuàng)建一個(gè)新的單元格添加到隊(duì)列尾部（rpush），并設(shè)置其計(jì)數(shù)為 1。

  3. 原子性保證

    • 整個(gè) Step 2 到 Step 5 的過(guò)程使用 Redis Lua 腳本執(zhí)行。
    • 為什么？ Lua 腳本在 Redis 中是原子執(zhí)行的，確保了清理過(guò)期數(shù)據(jù)、計(jì)算總數(shù)、判斷和更新計(jì)數(shù)這一系列操作是線程安全的，不會(huì)出現(xiàn)競(jìng)態(tài)條件。這是實(shí)現(xiàn)高并發(fā)限流的核心保障。

技術(shù)亮點(diǎn)

  1. 空間換時(shí)間：通過(guò)單元格劃分，避免了為每個(gè)請(qǐng)求存儲(chǔ)一個(gè)時(shí)間戳的巨大開(kāi)銷(xiāo)，只需維護(hù)固定數(shù)量的單元格，內(nèi)存占用更小，性能更高。
  2. 滑動(dòng)精確：每次請(qǐng)求都會(huì)觸發(fā)一次過(guò)期清理，保證了時(shí)間窗口的滑動(dòng)非常精確和實(shí)時(shí)。
  3. 原子操作：基于 Lua 腳本，所有邏輯在 Redis 端原子性完成，并發(fā)安全。
  4. 高性能：大部分計(jì)算邏輯在 Redis 服務(wù)器端完成，網(wǎng)絡(luò)傳輸開(kāi)銷(xiāo)小（通常只需一次 Lua 腳本調(diào)用）。

與其它算法的對(duì)比

算法 優(yōu)點(diǎn) 缺點(diǎn)
固定窗口 實(shí)現(xiàn)簡(jiǎn)單，內(nèi)存占用小。 臨界問(wèn)題：在窗口切換時(shí)可能承受2倍于閾值的流量。
滑動(dòng)日志 精確度高。 內(nèi)存占用高（每個(gè)請(qǐng)求一個(gè)記錄），性能較差。
滑動(dòng)窗口（Redisson） 平衡之選：精度高，內(nèi)存占用相對(duì)固定窗口稍大但可控，性能好。 精度取決于單元格粒度，粒度越細(xì)越精確，但開(kāi)銷(xiāo)也越大。

筆記要點(diǎn)（一句話(huà)總結(jié)）

  • 原理：將大窗口劃分為小單元格，用隊(duì)列維護(hù)，每次請(qǐng)求清理過(guò)期單元格并統(tǒng)計(jì)窗口內(nèi)總數(shù)。
  • 實(shí)現(xiàn)：基于 Redis List + Lua 腳本（保證原子性）。
  • 關(guān)鍵：“滑動(dòng)”通過(guò)清理隊(duì)列頭部的過(guò)期單元格來(lái)實(shí)現(xiàn)。
  • 優(yōu)點(diǎn)：在精度、內(nèi)存和性能之間取得了最佳平衡，是生產(chǎn)環(huán)境最常用的限流方案之一。
-- 速率
local rate = redis.call("hget", KEYS[1], "rate")
-- 時(shí)間區(qū)間(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 分析后面的代碼，這個(gè)key記錄的是當(dāng)前令牌桶中的令牌數(shù)
local valueName = KEYS[2]

-- {name}:permits 這個(gè)key是一個(gè)zset，記錄了請(qǐng)求的令牌數(shù)，score則為請(qǐng)求的時(shí)間戳
local permitsName = KEYS[4]

-- 單機(jī)限流才會(huì)用到，集群模式不用關(guān)注
if type == "1" then
   valueName = KEYS[3]
   permitsName = KEYS[5]
end

-- 原版本有bug(https://github.com/redisson/redisson/issues/3197)，最新版將這行代碼提前了
-- rate為1 arg1這里是 請(qǐng)求的令牌數(shù)量(默認(rèn)是1)。rate必須比請(qǐng)求的令牌數(shù)大
assert(tonumber(rate) >= tonumber(ARGV[1]), "Requested permits amount could not exceed defined rate")

-- 第一次執(zhí)行這里應(yīng)該是null，會(huì)進(jìn)到else分支
-- 第二次執(zhí)行到這里由于else分支中已經(jīng)放了valueName的值進(jìn)去，所以第二次會(huì)進(jìn)if分支
local currentValue = redis.call("get", valueName)
if currentValue ~= false then
   -- 從第一次設(shè)的zset中取數(shù)據(jù)，范圍是0 ~ (第二次請(qǐng)求時(shí)間戳 - 令牌生產(chǎn)的時(shí)間)
   -- 可以看到，如果第二次請(qǐng)求時(shí)間距離第一次請(qǐng)求時(shí)間很短(小于令牌產(chǎn)生的時(shí)間)，那么這個(gè)差值將小于上一次請(qǐng)求的時(shí)間，取出來(lái)的將會(huì)是空列表。反之，能取出之前的請(qǐng)求信息
   -- 這里作者將這個(gè)取出來(lái)的數(shù)據(jù)命名為expiredValues，可認(rèn)為指的是過(guò)期的數(shù)據(jù)
   local expiredValues = redis.call("zrangebyscore", permitsName, 0, tonumber(ARGV[2]) - interval)
   local released = 0
   -- lua迭代器，遍歷expiredValues，如果有值，那么released等于之前所有請(qǐng)求的令牌數(shù)之和，表示應(yīng)該釋放多少令牌
   for i, v in ipairs(expiredValues) do
       local random, permits = struct.unpack("fI", v)
       released = released + permits
   end

   -- 沒(méi)有過(guò)期請(qǐng)求的話(huà)，released還是0，這個(gè)if不會(huì)進(jìn)，有過(guò)期請(qǐng)求才會(huì)進(jìn)
   if released > 0 then
       -- 移除zset中所有元素，重置周期
       redis.call("zrem", permitsName, unpack(expiredValues))
       currentValue = tonumber(currentValue) + released
       redis.call("set", valueName, currentValue)
   end

   -- 這里簡(jiǎn)單分析下上面這段代碼:
   -- 1. 只有超過(guò)了1個(gè)令牌生產(chǎn)周期后的請(qǐng)求，expiredValues才會(huì)有值。
   -- 2. 以rate為3舉例，如果之前發(fā)生了兩個(gè)請(qǐng)求那么現(xiàn)在released為2，currentValue為1 + 2 = 3
   -- 以此可以看到，redisson的令牌桶放令牌操作是通過(guò)請(qǐng)求時(shí)間窗來(lái)做的，如果距離上一個(gè)請(qǐng)求的時(shí)間已經(jīng)超過(guò)了一個(gè)令牌生產(chǎn)周期時(shí)間，那么令牌桶中的令牌應(yīng)該得到重置，表示生產(chǎn)rate數(shù)量的令牌。

   -- 如果當(dāng)前令牌數(shù) ＜ 請(qǐng)求的令牌數(shù)
   if tonumber(currentValue) < tonumber(ARGV[1]) then
       -- 從zset中找到距離當(dāng)前時(shí)間最近的那個(gè)請(qǐng)求，也就是上一次放進(jìn)去的請(qǐng)求信息
       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])
       -- 返回 上一次請(qǐng)求的時(shí)間戳 - (當(dāng)前時(shí)間戳 - 令牌生成的時(shí)間間隔) 這個(gè)值表示還需要多久才能生產(chǎn)出足夠的令牌
       return tonumber(nearest[2]) - (tonumber(ARGV[2]) - interval)
   else
       -- 如果當(dāng)前令牌數(shù) ≥ 請(qǐng)求的令牌數(shù)，表示令牌夠多，更新zset
       redis.call("zadd", permitsName, ARGV[2], struct.pack("fI", ARGV[3], ARGV[1]))
       -- valueName存的是當(dāng)前總令牌數(shù)，-1表示取走一個(gè)
       redis.call("decrby", valueName, ARGV[1])
       return nil
   end
else
   -- set一個(gè)key-value數(shù)據(jù) 記錄當(dāng)前限流器的令牌數(shù)
   redis.call("set", valueName, rate)
   -- 建了一個(gè)以當(dāng)前限流器名稱(chēng)相關(guān)的zset，并存入 以score為當(dāng)前時(shí)間戳，以lua格式化字符串{當(dāng)前時(shí)間戳為種子的隨機(jī)數(shù)、請(qǐng)求的令牌數(shù)}為value的值。
   -- struct.pack第一個(gè)參數(shù)表示格式字符串，f是浮點(diǎn)數(shù)、I是長(zhǎng)整數(shù)。所以這個(gè)格式字符串表示的是把一個(gè)浮點(diǎn)數(shù)和長(zhǎng)整數(shù)拼起來(lái)的結(jié)構(gòu)體。我的理解就是往zset里記錄了最后一次請(qǐng)求的時(shí)間戳和請(qǐng)求的令牌數(shù)
   redis.call("zadd", permitsName, ARGV[2], struct.pack("fI", ARGV[3], ARGV[1]))
   -- 從總共的令牌數(shù) 減去 請(qǐng)求的令牌數(shù)。
   redis.call("decrby", valueName, ARGV[1])
   return nil
end
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容