流控是任何一個復(fù)雜系統(tǒng)都必須考慮的問題，本文介紹并比較了不同的流控算法，從而幫助我們可以基于系統(tǒng)需求和架構(gòu)選擇合適的方案。原文：Distributed Rate-Limiting Algorithms[1]

當我們設(shè)計分布式流控系統(tǒng)（distributed rate-limiting system）時，需要用到哪些工具和算法？

Joshua Hoehne @Unsplash

Criteo是全球最大的廣告技術(shù)公司之一，隨著廣告市場的不斷發(fā)展，Criteo在過去幾年里一直致力于改進API，幫助客戶更好的通過可編程接口訪問需要的服務(wù)。

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

流控似乎很簡單: 只允許給定的客戶端每分鐘執(zhí)行X個調(diào)用。在單個服務(wù)器實例上實現(xiàn)流控非常容易，可以很容易找到相關(guān)的庫來實現(xiàn)。但問題是我們的API托管在6個數(shù)據(jù)中心(歐洲、北美和亞洲)，每個數(shù)據(jù)中心都有多個實例，這意味著我們需要某種分布式流控系統(tǒng)。

流控不僅與調(diào)用次數(shù)有關(guān)，還需要和客戶端同步當前被限制的狀態(tài)(例如，使用專用的報頭和狀態(tài)碼)。但是本文將主要關(guān)注用于流控的算法和系統(tǒng)。

利用負載均衡

在嘗試開發(fā)自己的系統(tǒng)之前，更重要的是查看現(xiàn)有的基礎(chǔ)設(shè)施是否能夠提供想要的特性。

那么，部署在數(shù)據(jù)中心所有實例之前，并且已經(jīng)在負責(zé)檢查、路由流量的是什么？負載均衡器。大多數(shù)負載均衡器都提供了流控特性或某種可用于實現(xiàn)流控的抽象。例如，HAProxy有現(xiàn)成的可用于設(shè)置流控的stick tables[2]，可以在實例之間同步狀態(tài)，并且工作得很好。

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

初級方案

會話粘連（Sticky sessions）

說到負載均衡，如果給定客戶端的負載并不均衡，并且總是與單個實例交互??，那么就不需要分布式流控系統(tǒng)。大多數(shù)客戶端訪問距離最近的數(shù)據(jù)中心(通過geo-DNS)，如果在負載均衡器上啟用“stickiness”，客戶端應(yīng)該總是訪問相同的實例，這種情況下我們可以使用簡單的“本地”速率限制。

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

使用更智能的會話粘連(在擴展時重新分配令牌)會有所幫助，但這意味著每次擴展時，客戶端都可能切換到另一個實例上，而且并不知道客戶端在前一個實例上執(zhí)行了多少調(diào)用。本質(zhì)上說，這將使我們的流控在每次伸縮時不一致，客戶端可能在每次系統(tǒng)面臨壓力時會進行更多調(diào)用。

Chatty服務(wù)器

如果客戶端可以訪問任何實例，意味著“調(diào)用計數(shù)”必須在實例之間共享。一種方案是讓每個實例調(diào)用所有其他實例，請求給定客戶端的當前計數(shù)并相加。另一種方案反過來，每個服務(wù)器向其他服務(wù)器廣播“計數(shù)更新”。

這會造成兩個主要問題:

• 實例越多，需要進行的調(diào)用就越多。
• 每個實例都需要知道其他實例的地址，并且每次服務(wù)擴縮容時都必須更新地址。

雖然可以實現(xiàn)這個解決方案(本質(zhì)上是一個點對點環(huán)，許多系統(tǒng)已經(jīng)實現(xiàn)了)，但成本較高。

Kafka

如果不想讓每個實例都和其他實例通信，可以利用Kafka同步所有實例中的計數(shù)器。

例如，當某個實例被調(diào)用時，就將一個事件推到對應(yīng)的topic。這些事件會被滑動窗口聚合(Kafka Stream在這方面做得很好)，每個客戶端最后一分鐘的最新計數(shù)會被發(fā)布到另一個topic上。然后，每個實例通過此topic獲得所有客戶端的共享計數(shù)。

問題在于Kafka本質(zhì)上是異步的，雖然通常延遲很小，但當API負載增加時，也會增加延遲。如果實例使用了過時的計數(shù)器，那么可能會漏過那些本應(yīng)被阻止的調(diào)用。

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

流控系統(tǒng)的目標是在系統(tǒng)負載較重時工作良好，其構(gòu)建目標是為最差的1%而不是好的99%的情況服務(wù)

分布式算法

我們需要一個中心化的同步存儲系統(tǒng)，以及為每個客戶端計算當前速率的算法。內(nèi)存緩存(如Memcached或Redis)是理想的系統(tǒng)，但并不是所有的流控算法都可以在緩存系統(tǒng)中實現(xiàn)。下面我們看看有什么樣的算法。

簡化起見，我們考慮嘗試實現(xiàn)“每分鐘100次調(diào)用”的流控。

看看有哪些工具可用。

基于事件日志的滑動窗口（Sliding window via event log）

如果想知道某個客戶端在過去一分鐘內(nèi)進行了多少次調(diào)用，可以在緩存中為每個客戶端存儲一個時間戳列表。每次調(diào)用時，相應(yīng)的時間戳都會添加到列表中。然后循環(huán)遍歷列表中的每一項，丟棄超過一分鐘的舊項，并計算新項。

??優(yōu)點：

• 非常精確
• 簡單

??缺點：

• 需要強大的事務(wù)支持(處理同一客戶端的兩個實例需要更新相同的列表)。
• 根據(jù)不同的調(diào)用限制和次數(shù)，存儲對象(列表)的大小可能相當大。
• 性能不穩(wěn)定(更多的調(diào)用意味著需要處理更多的時間戳)。

固定窗口（Fixed window）

大多數(shù)分布式緩存系統(tǒng)都有特定的、高性能的“計數(shù)器”抽象(一個可以自動增加的整數(shù)值，附加在一個字符串鍵上)。

以“{clientId}”為key為每個客戶端維護一個計數(shù)器非常容易，但只會計算自計數(shù)器創(chuàng)建以來客戶端調(diào)用的次數(shù)，而不是最后一分鐘的次數(shù)。以“{clientId}_{yyyyMMddHHmm}”為key可以每分鐘都為客戶端維護一個計數(shù)器(換句話說: 以1分鐘為固定窗口)，查找與當前時間相對應(yīng)的計數(shù)器可以告訴我們這一分鐘客戶端執(zhí)行的調(diào)用數(shù)量，如果這個值超過上限，就可以阻止調(diào)用。

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

在某種程度上，固定窗口算法每過一分鐘都會“忘記”之前有多少次呼叫，因此客戶端理論上可以在07:09:59執(zhí)行100次調(diào)用，然后在07:10:00執(zhí)行100次額外的調(diào)用。

??優(yōu)點：

• 非常快(單個原子增量+讀取操作)
• 只需要非?；镜氖聞?wù)支持(原子計數(shù)器)
• 性能穩(wěn)定
• 簡單

??缺點：

• 不準確(最多會允許2倍調(diào)用)

令牌桶（Token bucket)

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

這就是“令牌桶”算法背后的主要思想: 與簡單計數(shù)器不同，“桶”存儲在每個客戶端緩存中。桶是由兩個屬性組成的對象:

• 剩余“令牌”的數(shù)量(或剩余可以進行的調(diào)用的數(shù)量)
• 最后一次調(diào)用的時間戳。

當API被調(diào)用時，檢索桶，根據(jù)當前調(diào)用和最后一次調(diào)用之間的時間間隔，向桶中添加新的令牌，如果有多余令牌，遞減并允許調(diào)用。

所以，和“街頭霸王”的例子相反，沒有“父母”幫我們每分鐘重新裝滿桶。桶在與令牌消耗相同的操作中被有效的重新填充(令牌的數(shù)量對應(yīng)于上次調(diào)用之后的時間間隔)。如果最后一次調(diào)用是在半分鐘之前，那么每分鐘100次調(diào)用的限制意味著將向桶中添加50個令牌。如果桶太“舊”(最后一次調(diào)用超過1分鐘)，令牌計數(shù)將重置為100。

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

注意: 正確計算要添加的令牌數(shù)很重要，否則有可能錯誤的填充桶。

該算法提供了完美的準確性，同時提供了穩(wěn)定的性能，主要問題是需要事務(wù)(不希望兩個實例同時更新緩存對象)。

圖片

100次調(diào)用/分鐘的令牌桶的分步示例

??優(yōu)點：

• 非常精確
• 快速
• 性能穩(wěn)定
• 優(yōu)化初始令牌數(shù)量可以允許客戶端“burst”調(diào)用

??缺點：

• 更復(fù)雜
• 需要強大的事務(wù)支持

漏桶(Leaky bucket): 該算法的另一個版本。在這個版本中，調(diào)用堆積在bucket中，并以恒定的速率(匹配速率限制)處理。如果桶溢出，則拒絕調(diào)用。這實現(xiàn)起來比較復(fù)雜，但可以平滑服務(wù)負載(這可能是您想要的，也可能不是)。

??最好的算法？

比較這三種算法，令牌桶似乎在性能和準確性方面提供了最好的折衷。但只有當系統(tǒng)提供良好的事務(wù)支持時，才有可能實現(xiàn)。如果有Redis集群，這是完美方案(甚至可以實現(xiàn)基于Lua的算法，直接運行在Redis集群上，以提高性能)，但Memcached只支持原子計數(shù)器，而不是事務(wù)。

可以基于Memcached實現(xiàn)令牌桶的樂觀并發(fā)（optimistic concurrent）版本[3]，但這更加復(fù)雜，而且樂觀并發(fā)的性能在負載較重的情況下會下降。

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

如果沒有強大的事務(wù)支持，是否注定要使用不準確的固定窗口算法？

算是吧，但還有改進的空間。請記住，固定窗口的主要問題是它每過一分鐘都會“忘記”之前發(fā)生的事情，但我們?nèi)匀豢梢栽L問相關(guān)信息(在前一分鐘的計數(shù)器中)，所以可以通過計算加權(quán)平均值來估計前一分鐘的調(diào)用次數(shù)。

圖片

通過60s固定窗口組合近似模擬60s滑動窗口

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

如果負載不變，這一近似是完美的。但如果大多數(shù)調(diào)用都集中在前一分鐘，那就會獲得一個高估的值。而當大多數(shù)調(diào)用都集中在前一分鐘結(jié)束后，這個數(shù)字就會被低估。

比較

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

下面的圖顯示了“固定計數(shù)器”算法在輸入隨機流量時將返回什么?；疑木€是一個“完美”的滑動窗口輸出，該窗口在任何時間點對應(yīng)于過去60秒內(nèi)的呼叫次數(shù)，這是我們的目標。橙色虛線表示固定窗口算法對相同流量的“計數(shù)”。

圖片

它們在第一分鐘的輸出是相同的，但很快就可以看到固定窗口版本在每分鐘標記處有很大的下降。固定窗口算法很少會超過100個調(diào)用的限制，這意味著會允許很多本應(yīng)被阻止的調(diào)用。

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

圖片

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

收益遞減

但我們能做得更好嗎？

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

圖片

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

圖片

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

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

結(jié)論

流控是一種非常容易描述但卻隱藏了很多復(fù)雜性的特性。希望本文能夠幫助你理解在復(fù)雜分布式系統(tǒng)中實現(xiàn)流控所涉及的工具和算法。

References:[1] Distributed Rate-Limiting Algorithms: https://medium.com/criteo-engineering/distributed-rate-limiting-algorithms-a35f7e24783[2] Introduction to HAProxy stick tables: https://www.haproxy.com/blog/introduction-to-haproxy-stick-tables/[3] Optimistic currency control: https://en.wikipedia.org/wiki/Optimistic_concurrency_control