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

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

Joshua Hoehne @Unsplash

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

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

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

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

利用負(fù)載均衡

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

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

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

初級(jí)方案

會(huì)話粘連（Sticky sessions）

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

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

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

Chatty服務(wù)器

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

這會(huì)造成兩個(gè)主要問(wèn)題:

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

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

Kafka

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

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

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

這些解決方案都有一個(gè)共同點(diǎn): 當(dāng)一切正常時(shí)，可以很好的工作，但當(dāng)負(fù)載過(guò)重時(shí)，就會(huì)退化。我們的大部分系統(tǒng)都是這樣設(shè)計(jì)的，通常情況下沒(méi)有問(wèn)題，但流控并不是典型組件，其目標(biāo)就是保護(hù)系統(tǒng)的其他部分免受這種過(guò)重負(fù)載的影響。

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

分布式算法

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

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

看看有哪些工具可用。

Barn Images @Unsplash

基于事件日志的滑動(dòng)窗口（Sliding window via event log）

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

:+1:優(yōu)點(diǎn)：

• 非常精確
• 簡(jiǎn)單

:-1:缺點(diǎn)：

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

固定窗口（Fixed window）

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

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

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

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

:+1:優(yōu)點(diǎn)：

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

:-1:缺點(diǎn)：

• 不準(zhǔn)確(最多會(huì)允許2倍調(diào)用)

令牌桶（Token bucket)

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

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

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

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

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

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

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

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

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

:+1:優(yōu)點(diǎn)：

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

:-1:缺點(diǎn)：

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

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

:trophy:最好的算法？

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

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

用固定窗口近似模擬滑動(dòng)窗口

如果沒(méi)有強(qiáng)大的事務(wù)支持，是否注定要使用不準(zhǔn)確的固定窗口算法？

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

通過(guò)60s固定窗口組合近似模擬60s滑動(dòng)窗口

例如:如果在00:01:43進(jìn)行了一次調(diào)用，遞增得到“00:01”計(jì)數(shù)器的值。由于這是當(dāng)前的日歷分鐘，現(xiàn)在包含00:01:00至00:01:43之間的調(diào)用數(shù)(最后17秒還沒(méi)有發(fā)生)。

但我們想要的是60s滑動(dòng)窗口中的調(diào)用數(shù)，意味著我們錯(cuò)過(guò)了00:00:43到00:01:00這段時(shí)間的計(jì)數(shù)。為此我們可以讀取“00:00”計(jì)數(shù)器，并以17/60的因子進(jìn)行調(diào)整，從而說(shuō)明我們只對(duì)最后17秒感興趣。

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

比較

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

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

它們?cè)诘谝环昼姷妮敵鍪窍嗤?，但很快就可以看到固定窗口版本在每分鐘?biāo)記處有很大的下降。固定窗口算法很少會(huì)超過(guò)100個(gè)調(diào)用的限制，這意味著會(huì)允許很多本應(yīng)被阻止的調(diào)用。

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

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

收益遞減

但我們能做得更好嗎？

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

我們看看組合5個(gè)15秒窗口會(huì)有什么效果:

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

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

結(jié)論

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