常見限流策略

發表於 更新於 分類於 閱讀次數： Disqus：

先前已經有研究過熔斷機制屬於應用程式呼叫其他服務的時候，對方無法正常回應所採取的手段。限流則是針對自己的應用程式，去限制外部傳過來的請求數量，要做到這一點則必須要能夠知道自己的負載峰值大概在哪一個程度，在接近上限的時候才能夠啟動限流的干預機制，像是服務降級、或是直接拒絕請求

系統可用性相關文章

  1. Polly - 熔斷機制
  2. 常見限流策略

限流、熔斷的施作點

但其實熔斷除了可以做到應用程式呼叫服務的熔斷以外，也可以在被呼叫端，透過偵測系統效能相關指標而啟用熔斷

  • 前者是透過呼叫服務的回應情況來決定是否啟用熔斷（基於初始配置的熔斷閥值條件啟用熔斷）
  • 後者則是直接透過偵測系統的 CPU/IO/RAM 若是超過一定數值，則啟用熔斷（基於偵測相關效能指標啟用熔斷）

對於要在系統的何處實做限流、熔斷，可以參考下圖，會有比較直觀的瞭解

常見的限流策略

所謂的限流當然是為了要讓系統可以最大化的應對請求，所以最好限制的點能夠趨近於系統負載上限，因此對於系統進行壓測是很有必要的，只有先知道了系統的能力到哪裡，我們才能接著設定限流的策略

計數器 rate limit

在這裡又區分成固定窗口及滑動窗口演算法，都是基於計數器的原理判斷是否允許請求

  • 固定窗口：每一次進來的請求都將計數器累加，判斷若超過系統處理的能力，就拒絕該請求。
    （例如：每 1 秒鐘只能處理 10 個請求）
  • 滑動窗口：細分單位，將時間單位再往下切分成數個小區塊，每次滑動一小格。例如同樣是一秒鐘十個請求，每次計算可能就是統計 0.4 ~ 1.4 秒的請求數，下次就是 0.5 ~ 1.5 秒的請求數

上述這兩種其實很類似，在 Polly 裡面有一個 RateLimit 可以用來做速率的限制，其採用的方式是計數器，但因 RateLimit 並沒有在舊版本實作，實測 7.1.1 之前都沒有；測試 7.2.3 版才有，只是還是要搞懂一個觀念，計數器當然可以作為單體使用，也可以共用計數器，主要還是看怎麼設計限流

如果將應用程式視作一個整體，但是透過 docker 之類的方式部署多個，並透過 load Balance 讓外部訪問，那麼在這邊設計單點的計數器表示的是每一個部署點所能承受的量，這就沒有什麼意義了，既然都透過 docker ＋ load balance 來部署，當然要看的就是整體能夠承受多少流量，因此在這樣情況下，應該是採用共用的計數器才對。只是 polly 的計數器實做應該是放在記憶體中，這樣的方式僅能支援單點，並不支援 scale out，在分散式部署的情境，目前找到的方案都是自行實做計數器演算法，並透過 Redis + Lua Script，讓 Redis 來儲存計數

如何自行實做計數器演算法

在網路上有參考到一篇 C＃的範例文章，詳情可以前往Redis 限流觀看，大致上的思路如下

  1. 將計數器放在 Redis
  2. 採用 AOP 在需要限流的 Controller 或 Action 掛載 Attribute，更細緻一點可以將該 API 在單位時間內允許的請求數傳入參數控制計數器上限，也可以讓不同的 API 可以執行不同的限流閥值策略
  3. 於 Attribute 內實做限流的邏輯，例如
    • 限制 IP 每分鐘請求數
    • 限制登入的使用者每分鐘請求數

對於將計數器放在 Redis 上面，主要是因為 Redis 支援 Lua Script，且因為 Redis 保證執行 Lua Script 的時候是原子執行（這句話我有看沒有懂，但是官方Scripting with Lua說了在執行 Script 的時候，所有的服務器活動都會被阻止，而這就能確保不會有 race condition 的問題），所以關於計數器的部分，就需要自行查閱一下了

漏桶 leaky bucket

圖片取自 5 种限流算法，7 种限流方式，挡住突发流量？

就像是拿一個水桶，底下戳一個洞，漏下來的水始終是固定的速度；如果水倒的不多，水桶能夠承接的住，慢慢滴總會滴完；如果一次大量的水進來，那麼溢出的水就是被拒絕的請求。這些逸出的部分就是需要觸發流量干預的請求，像是是直接拒絕，或者是降級服務，也因為一次大量的水進來會有很多溢出，所以漏桶算法並不適合應付高併發的請求

令牌桶 token bucket

圖片取自 Token Bucket 令牌桶演算法

系統以固定的速率產生令牌，然後把令牌放到令牌桶裡面，而這個令牌桶有一個容量，如果滿了就不能再往裡面放令牌，多餘的令牌就會被丟掉。當一個請求進來的時候，需要先去令牌桶拿一令牌才可以往下執行，如果令牌桶裡面已經沒有令牌了，那麼就拒絕請求，令牌桶演算法可以應對大流量的突波，能應付多少就看令牌桶的大小有多少，因此在大量請求進來的時候，處理速度的上限是看桶的容量大小；而一般情況之下，處理的速度是看令牌產生的速度。

當然大方向是這個概念啦，細節的部分還是可以作一些變化，像是一開始的時候先將進來的請求進行分類，看看這個請求是否需要拿令牌，如果不需要拿令牌的就直接放行；需要拿令牌的就照先前說的看是要直接拒絕掉，或者是降級服務，若是感覺難以理解令牌桶演算法，那麼也可以自己想像一下醫院掛號的流程，應該多多少少可以找到相似的地方去理解概念。

結論

對於限流，不管是要自己開發或者是使用現成人家寫好的套件，最重要的還是要先理解概念，才知道人家的 API 每個參數的意義是什麼，否則連參數都不知道是什麼意義，也很難正確的使用套件。如果是知道概念了，但實做有點困難不知如何下手，也可以多多參考實際的範例，或者是 Github: FireflySoft.RateLimit，可以去看看原始碼應該會有些幫助

參考連結

限流概念及相關演算法

  1. 分布式系统关注点——限流该怎么做？
  2. 限流、熔断与降级
  3. 接口限流算法：漏桶算法&令牌桶算法
  4. 我司用了 6 年的 Redis 分布式限流器，可以说是非常厉害了！

    示意圖是中文的，解釋也很通俗易懂

  5. 帶你快速瞭解：限流中的漏桶和令牌桶演算法
  6. Token Bucket 令牌桶演算法

    理論的東西較多，建議只看圖即可

  7. 基于 Redis 和 Lua 的分布式限流
  8. 没有预热，不叫高并发「限流算法第三把法器：令牌桶算法」- 第 302 篇_悟纤的博客-程序员 ITS203

    這邊提供了一個簡易版本的範例

  9. FireflySoft.RateLimit 使用与原理
  10. Scripting with Lua
  11. 高併發整體可用性：一文詳解降級、限流和熔斷

程式碼範例

  1. Redis 限流

    C# 版本的 Redis 限流 POC，範例透過 AOP 可實現

  2. Github: TokenBucket

    另一個令牌桶演算法的實作範例

  3. Github: FireflySoft.RateLimit

    支援分散式部署，可參考其中的 Redis + LuaScript 範例