字節(jié)跳動在令牌桶限速器優(yōu)化上的實踐

限速器（rate limiter）是一個非?；A(chǔ)的網(wǎng)絡(luò)包處理功能，被廣泛應(yīng)用于各類網(wǎng)元設(shè)備，在流量調(diào)度、網(wǎng)絡(luò)安全等領(lǐng)域發(fā)揮著重要作用。常見的限速器的實現(xiàn)方式基于令牌桶（token bucket），盡管令牌桶的原理已經(jīng)被人熟知，在具體實踐中，我們也發(fā)現(xiàn)了一些挑戰(zhàn)和共性問題。本文總結(jié)了近兩年字節(jié)跳動系統(tǒng)與技術(shù)工程團(tuán)隊（簡稱 STE 團(tuán)隊）在限速器優(yōu)化方面的一些探索，將一些經(jīng)驗和教訓(xùn)總結(jié)出來，以饗讀者。

令牌桶限速器的基本原理

相信每個寫網(wǎng)絡(luò)包處理的工程師都寫過基本的令牌桶限速器。令牌桶是一個形象的描述，既可以想象有一個桶可以容納一定量的令牌（token），每放行一個數(shù)據(jù)包便消耗一定量的令牌，數(shù)據(jù)包的放行與否取決于令牌桶中的令牌個數(shù)。

圖1 令牌桶圖示

在具體實踐中，令牌桶具有實現(xiàn)簡單、效率高等特點，在很多場景下，提到限速器，基本是令牌桶的代名詞。

存在的問題

在具體工程時間中，我們遇到了以下三個問題：

1. 精度問題

實際工程實踐中，時間計量單位其實是受限于系統(tǒng)，比如時間戳可能是以微秒(us)為單位，而每次計算的時間差可能只有 1~2us。那么一個 PPS=300K 的限速器，可能一次計算，所產(chǎn)生的令牌是 0.3 個，容易被整數(shù)運算忽略。最終的結(jié)果則是，實際限制為 300K/s，最后效果是只有 250Kpps 流量放行。精度過低，效果不理想。

這種解決方式也比較簡單，可以讓一個數(shù)據(jù)包消耗的令牌量不是 1個，而是 1000個。這樣，即使 1us，令牌桶產(chǎn)生的令牌數(shù)是 300個，而非 0.3個，這樣便保證了精度。但此時又引入了新的問題，因為令牌數(shù)擴(kuò)大了 1000 倍，此時需要考慮令牌桶的深度是否會溢出 32bit。一旦溢出，則會出現(xiàn)其他詭異的問題。

2. 級聯(lián)補(bǔ)償問題

圖2 限速器級聯(lián)補(bǔ)償

我們在實踐中發(fā)現(xiàn)，多個限速器級聯(lián)的時候，需要補(bǔ)償令牌。比如對于限速器 A，這個包是放行，消耗了 A 的令牌。對于限速器 B，這個包是丟棄，因為 B 沒令牌了。此時包被丟了。那么此時 A 的令牌就白白消耗了，即消耗了 token，然后包還是丟了。如果想達(dá)到一個準(zhǔn)確的限速效果，限速器A的令牌應(yīng)該被補(bǔ)償。如圖 2 所示那樣。

級聯(lián)補(bǔ)償使得多個限速器互相耦合，在代碼編寫上也比較麻煩。我們在實際中發(fā)現(xiàn)，如果限速器 A 和限速器 B 的限速值接近，并且都有丟包，那么缺乏級聯(lián)補(bǔ)償會對精度有嚴(yán)重影響。但如果限速值差的很遠(yuǎn)，則對精度的影響沒有那么大。

3. TCP對丟包敏感問題

令牌桶是沒有緩存的，一旦速率超過限定值，則會出現(xiàn)丟包。而 TCP 協(xié)議則對丟包非常敏感，一旦出現(xiàn)丟包，TCP 的對速率的調(diào)整比較激進(jìn)。令牌桶這一特性使得他在應(yīng)用于 TCP 這種流量時，經(jīng)常會導(dǎo)致限制 100Mbps，實際上最多只能跑到 80Mbps，因為不斷的丟包導(dǎo)致 TCP 不斷地降低發(fā)送窗口。

在 vSwitch 的使用時，BPS （Bits Per Second）限速對 TCP 的損耗尤其大，這是因為，一般虛擬網(wǎng)卡都開啟了 TSO（TCP Segmentation Offload）優(yōu)化，開啟 TSO 情況下，主機(jī)向外發(fā)送的 TCP 包都很大，一個包有可能是 64K 字節(jié)，在這么大的情況下，隨便丟若干個包，就對 TCP 的速率影響非常明顯了。

第一次改進(jìn)：端口借貸反壓限速器

我們在實踐中發(fā)現(xiàn)，級聯(lián)補(bǔ)償反饋問題雖然存在但不是非常突出，原因是一般級聯(lián)的限速器的限速值差距很大，比如單網(wǎng)卡的速率和整機(jī)速率，一般差距較大，不容易出現(xiàn)精度問題。最嚴(yán)重的問題是 TCP 丟包敏感導(dǎo)致的限速帶寬達(dá)不到，影響用戶體驗。由圖3所示，隨著 TCP RTT 的增加，實際可以達(dá)到的帶寬會明顯下降。

圖3 流量通過1Gbps限速器之后，實際獲得速率

反壓（backpressure），就是針對 TCP 對丟包敏感這一問題進(jìn)行的改進(jìn)。我們在第一次設(shè)計的時候，其實針對的是一個特定的場景。既虛機(jī)的虛擬網(wǎng)卡進(jìn)行限速。而且我們的限速器正好是每個網(wǎng)卡有一個特定的限速器。

每個虛擬網(wǎng)卡都有若干隊列，vSwitch 會持續(xù)的輪詢這些隊列拿到數(shù)據(jù)包發(fā)出。這些隊列本質(zhì)上其實就是包的緩存區(qū)。反壓，其實就是停止或者延緩對這些隊列的輪詢發(fā)包，讓數(shù)據(jù)包在隊列上堆積，而達(dá)到將壓力反饋到 Guest Kernel 的目的，這樣 Guest Kernel 的 TCP 棧就會感知到擁塞，調(diào)整發(fā)送的節(jié)奏。

圖4 反壓限速器

當(dāng)時我們設(shè)計反壓限速器的時候，有一個限制影響了最后的實現(xiàn)：

虛機(jī)的虛擬網(wǎng)卡沒有提供 Peek 功能，即 vSwitch 只是 Peek 數(shù)據(jù)包，而非真正將數(shù)據(jù)包從隊列中拿出。這一個限制導(dǎo)致了我們利用了“借貸”的思想。既設(shè)置一個開始輪詢的準(zhǔn)許時間點，如果當(dāng)前時間超過了準(zhǔn)許時間點，那么將隊列中的數(shù)據(jù)包一股腦全部發(fā)出，不考慮令牌是否足夠，如果令牌足夠則沒有問題，但是當(dāng)令牌不夠了，那么就考慮向未來借貸一筆令牌，反向計算出一個未來的時間戳，那么在這個時間戳之前，vSwitch 停止輪詢虛擬網(wǎng)卡。

借貸方法的提出，一開始只是為了性能考慮，避免好不容易將數(shù)據(jù)包從虛機(jī)隊列拷貝出來，卻發(fā)現(xiàn)令牌不夠又只能丟棄。既然不想丟棄，索性就向未來借貸一筆令牌都發(fā)出去。

如今回過頭來看這個設(shè)計，和 Peek 相比，其實有好有壞：

1）每次借貸的令牌量，不可控。這會導(dǎo)致公平性問題。大象流會不斷的獲取借貸資格，而小流則會趨向于餓死，在限速器競爭中，如果一方取得了優(yōu)勢，優(yōu)勢方容易持續(xù)獲得優(yōu)勢。

2）簡單的時間戳比較，開銷比 peek 低。如果能夠 peek 數(shù)據(jù)包，就不會有借貸的機(jī)制，也就沒有停止輪詢的可能，而是每次都會去虛擬隊列里查看，反而開銷有點大。

3）反過來，有 peek 功能的話，也可以先看看隊列里積壓的數(shù)據(jù)包，可以等待隊列積累了一定量數(shù)據(jù)包之后，計算將下一次 Batch 個數(shù)據(jù)包發(fā)出的時間戳，在此之前都停止輪詢。這對增加 batch 提升性能反而有好處。

反壓限速器因為反壓的是虛機(jī)的網(wǎng)卡隊列，只能對虛機(jī)往外發(fā)數(shù)據(jù)包有限制，而無法限制虛機(jī)的收方向的流量。這是因為我們無法反壓物理網(wǎng)卡的數(shù)據(jù)包，物理網(wǎng)卡的數(shù)據(jù)包可能發(fā)往不同的虛擬網(wǎng)卡，每個網(wǎng)卡的限速值是不一樣的，我們無法計算出一個確切的時間點，在這個時間點之前可以不用輪詢數(shù)據(jù)包。況且，物理網(wǎng)卡隊列滿了之后，只會丟包，而虛機(jī)網(wǎng)卡隊列滿了之后，可以反壓 TCP 協(xié)議棧，兩者效果是不一樣的。

因此在入向流量的限制上，我們只是延續(xù)了準(zhǔn)許時間戳的思想。如果當(dāng)前時間超過準(zhǔn)許時間，就放行所有數(shù)據(jù)包，如果沒有，則丟棄所有數(shù)據(jù)包。

第二次改進(jìn)：Carousel限速器

Carousel 限速器是 Google 在 SIGCOMM 17' 上的論文提出的一種限速器算法[2]，實際上想法也很簡單，即給每個數(shù)據(jù)包計算一個發(fā)出的時間戳，如果當(dāng)前時間戳小于發(fā)出時間戳，則緩存在一個時間輪里，即不是丟包，而是將數(shù)據(jù)包延遲發(fā)送。

圖5 Carousel限速器

我們基于這個算法基本原理，在 OVS-DPDK 實現(xiàn)了一個類似限速器，這中間有很多細(xì)節(jié)決定了算法的參數(shù)，比如一次輪詢的時間粒度是 1us 還是 10us ？實際使用的限速器的速率區(qū)間在什么范圍？是 300Kpps 還是 3Mpps？這些都直接決定了算法的參數(shù)設(shè)置，諸多細(xì)節(jié)就不展開說明了。

Carousel 最大的一個好處是引入了緩存。時間輪的本質(zhì)就是一個緩存，這個對 TCP 流量有明顯的好處，同時，時間輪也解決了虛機(jī)入向流量的無法反壓的問題，使得所有的流量都能統(tǒng)一在一個時間輪下。第三個好處，可能有點意想不到，就是它一定程度的消除了級聯(lián)補(bǔ)償?shù)谋匾?，因為?shù)據(jù)包不在丟包，而是延遲發(fā)送。在沒有丟包的情況下，不需要級聯(lián)補(bǔ)償。

下圖是在限速 10Gbps 下，通過 iperf 工具，測試 100s 情況下，虛機(jī)出入向，在使用老的反壓限速器和新的 Carousel 限速器的對比效果。

橫軸是時間（s)，豎軸是吞吐（Gbps），即每秒 iperf 報告出的當(dāng)前的吞吐性能。可以看到入向流量增加了 500Mbps。更靠近 10Gbps。

出向吞吐性能，可以看出 Carousel 限速器更加穩(wěn)定：

這些改進(jìn)的源頭，都來自于緩存對 TCP 流量的平滑作用。

未來的改進(jìn)和小結(jié)

1. 進(jìn)一步改進(jìn)

基于借貸機(jī)制的反壓限速，當(dāng)限速值較大時，因借貸超發(fā)的數(shù)據(jù)包對整個限速抖動影響是有限的。比如限速 1G，在某個時刻超發(fā)幾個包，對限速的抖動影響是比較小的。但是如果限速值很小，比如小到 5Mbps，那么超發(fā)幾個數(shù)據(jù)包的影響就會比較大。此時，通過時間戳控制虛機(jī)端口的輪詢，會帶來 ON-OFF 效應(yīng)，既在虛機(jī)看來，出向流量的路徑上，好像有一個閘門，一會打開，一會關(guān)閉。

但這只是在虛機(jī)發(fā)送端視角看到的情況，接收端因為有時間輪的調(diào)節(jié)，速率會比較穩(wěn)定。為在發(fā)送端帶來比較穩(wěn)定的體驗，需要將反壓的效果更加細(xì)化，既降低超發(fā)的幾率。

此外，基于端口粒度的限速可以通過控制端口的輪詢來實現(xiàn)，但是對于粒度小于端口的限速，則不好實現(xiàn)反壓。為了實現(xiàn)更細(xì)粒度的反壓，Google 在論文 PicNIC[3] 中，在Carousel 之上，利用 virtio 支持 OOO completion (亂序完成) 的特點，實現(xiàn)了更細(xì)粒度的反壓，這些都為進(jìn)一步優(yōu)化限速器提供了思路。

2. 主動限速（基于ECN或者修改TCP window選項）

我們可以在 vSwitch 中對 TCP 的 Window 窗口進(jìn)行跟蹤修改，協(xié)商一個小窗口進(jìn)行的方式，獲得更平穩(wěn)的 TCP 吞吐。同時ECN標(biāo)記也可以在 vSwitch 中進(jìn)行感知，通過直接或者間接的方式反饋到虛機(jī)內(nèi)部，或者影響 vSwitch 的輪詢頻率。

3. 鎖機(jī)制改進(jìn)

以上所有的限速器改進(jìn)均是針對網(wǎng)絡(luò)方面，系統(tǒng)方面由于多核存在，而限速器的粒度經(jīng)?？缭骄€程，如何設(shè)計一個無鎖的限速器也是一個值得探索的方向。

4. 小結(jié)

從限速器的改進(jìn)歷史中可以看出，當(dāng)前的算法已經(jīng)越來越和實際場景相關(guān)。算法不再只是一個獨立的組件，而越來越和實際的運行系統(tǒng)和產(chǎn)品特性緊密耦合。

審核編輯：劉清