五分鐘搞懂分散式流控演算法

流控是任何一個複雜系統都必須考慮的問題，本文介紹並比較了不同的流控演算法，從而幫助我們可以基於系統需求和架構選擇合適的方案。原文：Distributed Rate-Limiting Algorithms ^[1]

當我們設計分散式流控系統（distributed rate-limiting system）時，需要用到哪些工具和演算法？

Criteo是全球最大的廣告技術公司之一，隨著廣告市場的不斷髮展，Criteo在過去幾年裡一直致力於改進API，幫助客戶更好的通過可程式設計介面訪問需要的服務。

隨著越來越多的客戶使用新的API，很明顯，需要實現某種流量控制，以確保所有客戶端都能平等訪問資源，並保護API免受(惡意或錯誤的)頻繁呼叫。

流控似乎很簡單: 只允許給定的客戶端每分鐘執行X個呼叫。在單個伺服器例項上實現流控非常容易，可以很容易找到相關的庫來實現。但問題是我們的API託管在6個數據中心(歐洲、北美和亞洲)，每個資料中心都有多個例項，這意味著我們需要某種分散式流控系統。

流控不僅與呼叫次數有關，還需要和客戶端同步當前被限制的狀態(例如，使用專用的報頭和狀態碼)。但是本文將主要關注用於流控的演算法和系統。

利用負載均衡

在嘗試開發自己的系統之前，更重要的是檢視現有的基礎設施是否能夠提供想要的特性。

那麼，部署在資料中心所有例項之前，並且已經在負責檢查、路由流量的是什麼？負載均衡器。大多數負載均衡器都提供了流控特性或某種可用於實現流控的抽象。例如，HAProxy有現成的可用於設定流控的stick tables ^[2] ，可以在例項之間同步狀態，並且工作得很好。

不幸的是，負載均衡不支援我們需要的某些特性(動態限制、令牌自省token introspection、……)，因此我們需要自己實現這些特定的需求。

初級方案

會話粘連（Sticky sessions）

說到負載均衡，如果給定客戶端的負載並不均衡，並且總是與單個例項互動 ，那麼就不需要分散式流控系統。大多數客戶端訪問距離最近的資料中心(通過geo-DNS)，如果在負載均衡器上啟用“stickiness”，客戶端應該總是訪問相同的例項，這種情況下我們可以使用簡單的“本地”速率限制。

這在理論上可行，但在實踐中行不通。Criteo系統面臨的負載不是恆定的，例如，黑色星期五/Cyber Week是一年中最重要的時段。在此期間，團隊隨時處於戒備狀態，準備擴大基礎設施，以應對客戶不斷增長的需求。但是會話粘連和可伸縮性不能很好的配合(如果所有客戶端都粘連在舊例項上，那麼建立新例項又有什麼用呢?)

使用更智慧的會話粘連(在擴充套件時重新分配令牌)會有所幫助，但這意味著每次擴充套件時，客戶端都可能切換到另一個例項上，而且並不知道客戶端在前一個例項上執行了多少呼叫。本質上說，這將使我們的流控在每次伸縮時不一致，客戶端可能在每次系統面臨壓力時會進行更多呼叫。

Chatty伺服器

如果客戶端可以訪問任何例項，意味著“呼叫計數”必須在例項之間共享。一種方案是讓每個例項呼叫所有其他例項，請求給定客戶端的當前計數並相加。另一種方案反過來，每個伺服器向其他伺服器廣播“計數更新”。

這會造成兩個主要問題:

• 例項越多，需要進行的呼叫就越多。

• 每個例項都需要知道其他例項的地址，並且每次服務擴縮容時都必須更新地址。

雖然可以實現這個解決方案(本質上是一個點對點環，許多系統已經實現了)，但成本較高。

Kafka

如果不想讓每個例項都和其他例項通訊，可以利用Kafka同步所有例項中的計數器。

例如，當某個例項被呼叫時，就將一個事件推到對應的topic。這些事件會被滑動視窗聚合(Kafka Stream在這方面做得很好)，每個客戶端最後一分鐘的最新計數會被髮布到另一個topic上。然後，每個例項通過此topic獲得所有客戶端的共享計數。

問題在於Kafka本質上是非同步的，雖然通常延遲很小，但當API負載增加時，也會增加延遲。如果例項使用了過時的計數器，那麼可能會漏過那些本應被阻止的呼叫。

這些解決方案都有一個共同點: 當一切正常時，可以很好的工作，但當負載過重時，就會退化。我們的大部分系統都是這樣設計的，通常情況下沒有問題，但流控並不是典型元件，其目標就是保護系統的其他部分免受這種過重負載的影響。

流控系統的目標是在系統負載較重時工作良好，其構建目標是為最差的1%而不是好的99%的情況服務。

分散式演算法

我們需要一箇中心化的同步儲存系統，以及為每個客戶端計算當前速率的演算法。記憶體快取(如Memcached或Redis)是理想的系統，但並不是所有的流控演算法都可以在快取系統中實現。下面我們看看有什麼樣的演算法。

簡化起見，我們考慮嘗試實現“每分鐘100次呼叫”的流控。

看看有哪些工具可用。

基於事件日誌的滑動視窗（Sliding window via event log）

如果想知道某個客戶端在過去一分鐘內進行了多少次呼叫，可以在快取中為每個客戶端儲存一個時間戳列表。每次呼叫時，相應的時間戳都會新增到列表中。然後迴圈遍歷列表中的每一項，丟棄超過一分鐘的舊項，並計算新項。

:+1:優點：

• 非常精確

• 簡單

:-1:缺點：

• 需要強大的事務支援(處理同一客戶端的兩個例項需要更新相同的列表)。

• 根據不同的呼叫限制和次數，儲存物件(列表)的大小可能相當大。

• 效能不穩定(更多的呼叫意味著需要處理更多的時間戳)。

固定視窗（Fixed window）

大多數分散式快取系統都有特定的、高效能的“計數器”抽象(一個可以自動增加的整數值，附加在一個字串鍵上)。

以“ {clientId} ”為key為每個客戶端維護一個計數器非常容易，但只會計算自計數器建立以來客戶端呼叫的次數，而不是最後一分鐘的次數。以“ {clientId}_{yyyyMMddHHmm} ”為key可以每分鐘都為客戶端維護一個計數器(換句話說: 以1分鐘為固定視窗)，查詢與當前時間相對應的計數器可以告訴我們這一分鐘客戶端執行的呼叫數量，如果這個值超過上限，就可以阻止呼叫。

請注意，這與“最近一分鐘”不是一回事。如果在上午07:10:23有一次呼叫，固定視窗計數器會顯示在上午07:10:00到07:10:23之間呼叫的數量。但我們真正想要的是早上07:09:23到07:10:23之間的呼叫數量。

在某種程度上，固定視窗演算法每過一分鐘都會“忘記”之前有多少次呼叫，因此客戶端理論上可以在07:09:59執行100次呼叫，然後在07:10:00執行100次額外的呼叫。

:+1:優點：

• 非常快(單個原子增量+讀取操作)

• 只需要非常基本的事務支援(原子計數器)

• 效能穩定

• 簡單

:-1:缺點：

• 不準確(最多會允許2倍呼叫)

令牌桶（Token bucket)

回到1994年，父母把你送到遊戲廳和朋友們一起玩《超級街霸2》。他們給你一個裝了5美元硬幣的小桶，然後去了街對面的酒吧，並且每個小時都會過來往桶裡扔5美元硬幣。因此你基本上被限制每小時玩5美元(希望你在《街頭霸王》中表現出色)。

這就是“令牌桶”演算法背後的主要思想: 與簡單計數器不同，“桶”儲存在每個客戶端快取中。桶是由兩個屬性組成的物件:

• 剩餘“令牌”的數量(或剩餘可以進行的呼叫的數量)

• 最後一次呼叫的時間戳。

當API被呼叫時，檢索桶，根據當前呼叫和最後一次呼叫之間的時間間隔，向桶中新增新的令牌，如果有多餘令牌，遞減並允許呼叫。

所以，和“街頭霸王”的例子相反，沒有“父母”幫我們每分鐘重新裝滿桶。桶在與令牌消耗相同的操作中被有效的重新填充(令牌的數量對應於上次呼叫之後的時間間隔)。如果最後一次呼叫是在半分鐘之前，那麼每分鐘100次呼叫的限制意味著將向桶中新增50個令牌。如果桶太“舊”(最後一次呼叫超過1分鐘)，令牌計數將重置為100。

事實上，可以在初始化的時候填充超過100個令牌(但補充速度為100令牌/分鐘): 這類似於“burst”功能，允許客戶端在一小段時間內超過流控的限制，但不能長期維持。

注意:正確計算要新增的令牌數很重要，否則有可能錯誤的填充桶。

該演算法提供了完美的準確性，同時提供了穩定的效能，主要問題是需要事務(不希望兩個例項同時更新快取物件)。

:+1:優點：

• 非常精確

• 快速

• 效能穩定

• 優化初始令牌數量可以允許客戶端“burst”呼叫

:-1:缺點：

• 更復雜

• 需要強大的事務支援

漏桶(Leaky bucket):該演算法的另一個版本。在這個版本中，呼叫堆積在bucket中，並以恆定的速率(匹配速率限制)處理。如果桶溢位，則拒絕呼叫。這實現起來比較複雜，但可以平滑服務負載(這可能是您想要的，也可能不是)。

:trophy:最好的演算法？

比較這三種演算法，令牌桶似乎在效能和準確性方面提供了最好的折衷。但只有當系統提供良好的事務支援時，才有可能實現。如果有Redis叢集，這是完美方案(甚至可以實現基於Lua的演算法，直接執行在Redis叢集上，以提高效能)，但Memcached只支援原子計數器，而不是事務。

可以基於Memcached實現令牌桶的樂觀併發（optimistic concurrent）版本 ^[3] ，但這更加複雜，而且樂觀併發的效能在負載較重的情況下會下降。

用固定視窗近似模擬滑動視窗

如果沒有強大的事務支援，是否註定要使用不準確的固定視窗演算法？

算是吧，但還有改進的空間。請記住，固定視窗的主要問題是它每過一分鐘都會“忘記”之前發生的事情，但我們仍然可以訪問相關資訊(在前一分鐘的計數器中)，所以可以通過計算加權平均值來估計前一分鐘的呼叫次數。

例如:如果在00:01:43進行了一次呼叫，遞增得到“00:01”計數器的值。由於這是當前的日曆分鐘，現在包含00:01:00至00:01:43之間的呼叫數(最後17秒還沒有發生)。
但我們想要的是60s滑動視窗中的呼叫數，意味著我們錯過了00:00:43到00:01:00這段時間的計數。為此我們可以讀取“00:00”計數器，並以17/60的因子進行調整，從而說明我們只對最後17秒感興趣。

如果負載不變，這一近似是完美的。但如果大多數呼叫都集中在前一分鐘，那就會獲得一個高估的值。而當大多數呼叫都集中在前一分鐘結束後，這個數字就會被低估。

比較

為了更準確的瞭解精度差異，最好是在相同的條件下模擬兩種演算法。

下面的圖顯示了“固定計數器”演算法在輸入隨機流量時將返回什麼。灰色的線是一個“完美”的滑動視窗輸出，該視窗在任何時間點對應於過去60秒內的呼叫次數，這是我們的目標。 橙色虛線表示固定視窗演算法對相同流量的“計數”。

它們在第一分鐘的輸出是相同的，但很快就可以看到固定視窗版本在每分鐘標記處有很大的下降。固定視窗演算法很少會超過100個呼叫的限制，這意味著會允許很多本應被阻止的呼叫。

下面的圖表示相同的場景，具有相同的流量，但使用了近似的滑動視窗。同樣，灰色線代表“完美”滑動視窗。 橙色虛線表示近似演算法。

在每分鐘標記附近不再看到下降，可以看到新版本演算法與完美演算法更接近，它有時略高，有時略低，但總體上是巨大的進步。

收益遞減

但我們能做得更好嗎？

我們的近似演算法只使用當前和以前的60秒固定視窗。但是，也可以使用幾個更小的子視窗，一種極端方法是使用60個1s視窗來重建最後一分鐘的流量。顯然這意味著為每個呼叫讀取60個計數器，這將極大增加效能成本。不過我們可以選擇任意固定視窗時間，從中擬合近似值。視窗越小，需要的計數器就越多，近似值也就越精確。

我們看看組合5個15秒視窗會有什麼效果:

正如預期的那樣，準確率有所提高，但仍然不夠完美。

我們處在一個經典的 更好的準確性=更差的效能 的情況下。沒有絕對的最佳方案，必須平衡對於準確性和效能的要求，找到最適合的解決方案。如果你只關心保護自己的服務不被過度使用，而不需要持續控制，那麼甚至最簡單的固定視窗就可能是可行的解決方案。

結論

流控是一種非常容易描述但卻隱藏了很多複雜性的特性。希望本文能夠幫助你理解在複雜分散式系統中實現流控所涉及的工具和演算法。

你好，我是俞凡，在Motorola做過研發，現在在Mavenir做技術工作，對通訊、網路、後端架構、雲原生、DevOps、CICD、區塊鏈、AI等技術始終保持著濃厚的興趣，平時喜歡閱讀、思考，相信持續學習、終身成長，歡迎一起交流學習。

微信公眾號：DeepNoMind

- END -