分佈式限流：基於 Redis 的有序集合

本文作者是來自國外一家名爲 ClassDojo 的科技公司，其分享了在企業構建推送通知服務的限流器實踐。該服務要求具備以下標準的限流功能：

分佈式：限流器可以在多個進程之間共享。這就需要使用外部鍵值存儲，我們選擇了 Redis，因爲系統的其他地方也使用了 redis。
滾動窗口：如果我們設置每分鐘最多 10 條消息，我們不希望用戶在 0:59 能收到 10 條消息，在 1:01 又收到 10 條消息。
消息之間要保持最小間隔時間：不管限流 rate 選擇設置多大，強制要求連續的消息之間保持最小間隔，這樣接收者忙碌的時候不會有煩人的聲音或提醒。

我們查看了可用的限流器選擇，但在 NPM（node.js 包管理，他們的服務應該是基於 node.js 開發）未找到符合上述要求的包。所以決定自己寫，你可以在這裏下載。

方案一：token buckets(令牌桶)

使用滾動窗口限流的經典算法是令牌桶 (或漏桶算法)。下面是它的工作原理:

每個用戶都有一個關聯的桶，其中包含許多令牌（tokens）。
用戶發起推送操作，就檢查對應桶裏 tokens 的數量。
如果桶是空的，用戶已經達到限流條件，操作就被阻止。
否則，就從桶中拿掉一個 token（對於特殊操作可以多拿幾個 tokens）然後正常執行操作，例如推送通知。
隨着時間的推移，我們會以設定的速率將所有桶重新裝滿 tokens，直到桶滿爲止。

這是一種非常聰明的算法，只佔用很少的空間 (每個用戶只佔用一個整數計數器)，但是這種直接的實現有一個很大的缺陷——一些進程需要不斷地填充桶。由於有數百萬用戶，而且每次填充操作都需要寫操作，這對我們的 Redis 實例來說是一個不可持續的負載。這裏有一個更高級的方法:

每個用戶都有兩個與之相關的鍵: 令牌桶，以及桶最後一次被重新填充的時間戳。
當用戶試圖執行一個操作時，我們獲取存儲的時間戳。
我們計算自上次請求以來應該向用戶授予多少 tokens。
然後，我們可以使用這個新的 token 計數繼續算法。
不幸的是，這個算法也有問題：當兩個進程需要共享限流器時，它將失敗。Redis 可以將操作批處理爲一個原子操作，但要計算給用戶多少令牌，我們至少需要兩次訪問 Redis：一次獲取最後的時間戳，一次設置新令牌計數。如果不深入研究 Redis Lua 腳本 (我們沒有任何經驗，而且很難在測試中模擬)，我們無法找到一種方法將所有需要的操作組合成一個單一的 Redis 原子操作。正因爲如此，如果兩個使用限流器的客戶端都試圖以同一個用戶操作，我們可以得到以下操作序列:
用戶有足夠的 token。
自上次操作以來，還沒有足夠的時間來授予更多的令牌。
客戶端 1 獲取存儲的時間戳和令牌計數。
客戶端 2 獲取存儲的時間戳和令牌計數。
客戶端 1 計算不需要添加令牌，允許操作，並告訴 redis 設置令牌計數爲 0。
客戶端 2 計算也不需要添加令牌，允許操作，並告訴 redis 設置令牌計數爲 0。
不用說，這並不理想。如果我們有幾十個進程在處理推送通知負載，那麼用戶可能會同時收到數十個推送。

更好方法：sorted sets（有序集合）

幸運的是，Redis 有另一個數據結構，我們可以用來防止這些競爭條件 - 有序集合。這是我們想出的算法:

每個用戶有一個有序集合。key 和 value 相同，等於執行操作時的 (微秒) 時間。
當用戶試圖執行操作，我們首先刪除集合中所有在一個間隔之前發生的元素。這可以通過 Redis 的 ZREMRANGEBYSCORE 命令來完成。
使用 ZRANGE(0， -1) 來獲取集合中的所有元素
使用 ZADD 將當前時間戳添加到集合中
設置 TTL 等於限流間隔 (節省空間)。
在所有操作完成後，我們計算獲取的元素的數量。如果它超過了限制，不允許操作執行。
還可以將獲取的最後添加的元素與當前的時間戳進行比較。如果他們離得太近，我們也不允許操作。
這種方法的優點是，所有的 Redis 操作都可以作爲一個原子操作執行，使用 MULTI 命令。這意味着，如果兩個進程都試圖以同一用戶執行一個操作，它們就不可能沒有最新的信息，從而防止上述問題的發生。它還允許我們對想要跟蹤的兩種速率使用一個限流器 (即每分鐘不超過 10 條消息或每 3 秒不超過 2 條消息)。

然而，這種方法有一個瑕疵——我們不受影響，但可能不適合他人的要求。在我們的算法中，你可以看到一個操作是否被阻塞是在所有 Redis 操作完成後決定的。這意味着被阻止的操作仍然算作操作。所以，如果用戶持續超過速率限制，他們的任何操作都將不被允許 (在前幾次之後)，而不是允許偶爾的操作通過。

模塊

我們在 npm 上開源了我們的限制器，作爲 rolling-rate-limiter 模塊。它可以使用 Redis 後端，或者，如果你不需要在多進程中運行你的限流器，在內存中操作 (使用一個簡單的數組而不是排序集)。這裏有一個例子:

/*  Setup:  */

  var RateLimiter = require("rolling-rate-limiter");
  var Redis = require("redis");
  var client = Redis.createClient(config);

  var limiter = RateLimiter({
    redis: client,
    namespace: "UserLoginLimiter"
    interval: 1000
    maxInInterval: 10
    minDifference: 100
  });

  /*  Action:  */

  function attemptAction(userId, cb) {
    limiter(userId, function(err, timeLeft) {
      if (err) {

        // redis failed or similar.

      } else if (timeLeft > 0) {

        // 超出限制, 操作被阻止
        // timeLeft是允許進行下一個操作之前的毫秒數
        // 注意，這可以被當作一個布爾值，因爲0代表false

      } else {

        // 未超過限額，允許操作

      }
    });
  }

你也可以很容易地使用它與中間件結合對請求限速，如下所示:

var limiter = RateLimiter({
    redis: redisClient,
    namespace: "requestRateLimiter",
    interval: 60000,
    maxInInterval: 100,
    minDifference: 100
  });

  app.use(function(req, res, next) {

    // "req.ipAddress" 可以用任何唯一的用戶標識符替換
    limiter(req.ipAddress, function(err, timeLeft) {
      if (err) {
        return res.status(500).send();
      } else if (timeLeft) {
        return res.status(429).send("You must wait " + timeLeft + " ms before you can make requests.");
      } else {
        return next();
      }
    });

  });

你可以在 Github 上查看源代碼。我們希望這將有助於您編寫 Node.js 應用程序!

總結

本文介紹了一種基於 Redis 有序集合實現的分佈式限流器，該方法特別適合軟件通知服務限流。當然每種算法都不是放之四海而皆準的，需要根據自己的場景來選擇或者改造。雖然文章使用的是 node.js 實現，讀者也可以嘗試用 Go 來實踐下。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/3mF7k4-tinW_DHq26G-wNA

方案一：token buckets(令牌桶)

更好方法：sorted sets（有序集合）

模塊

總結

猜你喜歡