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

令牌桶限速器的基本原理

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

圖1 令牌桶圖示

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

存在的問題

在具體工程時(shí)間中，我們遇到了以下三個(gè)問題：

1. 精度問題

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

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

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

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

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

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

3. TCP對丟包敏感問題

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

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

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

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

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

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

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

圖4 反壓限速器

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

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

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

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

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

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

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

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

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

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

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

圖5 Carousel限速器

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

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

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

橫軸是時(shí)間（s)，豎軸是吞吐（Gbps），即每秒 iperf 報(bào)告出的當(dāng)前的吞吐性能?？梢钥吹饺胂蛄髁吭黾恿?500Mbps。更靠近 10Gbps。

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

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

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

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

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

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

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

2. 主動(dòng)限速（基于ECN或者修改TCP window選項(xiàng)）

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

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

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

4. 小結(jié)

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

審核編輯：劉清