Linux轉(zhuǎn)發(fā)性能評估與優(yōu)化

線速問題

很多人對這個線速概念存在誤解。認(rèn)為所謂線速能力就是路由器/交換機(jī)就像一根網(wǎng)線一樣。而這，是不可能的。應(yīng)該考慮到的一個概念就是延遲。數(shù)據(jù)包進(jìn)入路由器或者交換機(jī)，存在一個核心延遲操作，這就是選路，對于路由器而言，就是路由查找，對于交換機(jī)而言，就是查詢MAC/端口映射表，這個延遲是無法避開的，這個操作需要大量的計算機(jī)資源，所以不管是路由器還是交換機(jī)，數(shù)據(jù)包在內(nèi)部是不可能像在線纜上那樣近光速傳輸?shù)?。類比一下你?jīng)過十字街頭的時候，是不是要左顧右盼呢？

那么，設(shè)備的線速能力怎么衡量呢？如果一個數(shù)據(jù)包經(jīng)過一個路由器，那么延遲必覽無疑，可是設(shè)備都是有隊列或者緩沖區(qū)的，那么試想一個數(shù)據(jù)包緊接一個數(shù)據(jù)包從輸入端口進(jìn)入設(shè)備，然后一個數(shù)據(jù)包緊接一個數(shù)據(jù)包從輸出端口發(fā)出，這是可以做到的，我們對數(shù)據(jù)包不予編號，因此你也就無法判斷出來的數(shù)據(jù)包是不是剛剛進(jìn)去的那個了，這就是線速。

我們可以用電容來理解轉(zhuǎn)發(fā)設(shè)備。有人可能會覺得電容具有通高頻阻低頻的功效，我說的不是這個，所以咱不考慮低頻，僅以高頻為例，電容具有存儲電荷的功能，這就類似存儲轉(zhuǎn)發(fā)，電容充電的過程類似于數(shù)據(jù)包進(jìn)入輸入隊列緩沖區(qū)，電容放電的過程類似于數(shù)據(jù)包從輸出緩沖區(qū)輸出，我們可以看到，在電流經(jīng)過電容的前后，其速度是不變的，然而針對具體的電荷而言，從電容放出的電荷絕不是剛剛在在另一側(cè)充電的那個電荷，電容的充電放電擁有固有延遲。

我們回到轉(zhuǎn)發(fā)設(shè)備。對于交換機(jī)和路由器而言，衡量標(biāo)準(zhǔn)是不同的。

對于交換機(jī)而言，線速能力是背板總帶寬，因為它的查表操作導(dǎo)致的延遲并不大，大量的操作都在數(shù)據(jù)包通過交換矩陣的過程，因此背板帶寬直接導(dǎo)致了轉(zhuǎn)發(fā)效率。而對于路由器，衡量標(biāo)準(zhǔn)則是一個端口每秒輸入輸出最小數(shù)據(jù)包的數(shù)量，假設(shè)數(shù)據(jù)包以每秒100個進(jìn)入，每秒100個流出，那么其線速就是100pps。

本文針對路由器而不針對交換機(jī)。路由器的核心延遲在路由查找，而這個查找不會受到數(shù)據(jù)包長度的影響，因此決定路由器線速能力的核心就在數(shù)據(jù)包輸出的效率，注意，不是數(shù)據(jù)包輸入的效率，因為只要隊列足夠長，緩存足夠大，輸入總是線速的。但是輸入操作就涉及到了如何調(diào)度的問題。這也就說明了為何很多路由器都支持輸出流量控制而不是輸入流量控制的原因，因為輸入流控即使完美完成，它也會受到路由器輸出端口自身輸出效率的影響，流控結(jié)果將不再準(zhǔn)確。

在寫這個方案的前晚，有一個故事。我最近聯(lián)系到了初中時一起玩搖滾玩音響的超級鐵的朋友，他現(xiàn)在搞舞臺設(shè)計，燈光音響之類的。我問他在大型舞臺上，音箱擺放的位置不同，距離后級，前置，音源也不同，怎么做到不同聲道或者相同聲道的聲音同步的，要知道，好的耳朵可以聽出來毫秒級的音差...他告訴我要統(tǒng)一到達(dá)時間，即統(tǒng)一音頻流到達(dá)各個箱子的時間，而這要做的就是調(diào)延遲，要求不同位置的箱子路徑上要有不同的延遲。這對我的設(shè)計方案的幫助是多么地大啊。

然后，在第二天，我就開始整理這個令人悲傷最終心碎的Linux轉(zhuǎn)發(fā)優(yōu)化方案。

聲明：本文只是一篇普通文章，記錄這個方案的點點滴滴，并不是一個完整的方案，請勿在格式上較真，內(nèi)容上也只是寫了些我認(rèn)為重要且有意思的。完整的方案是不便于以博文的形式發(fā)出來的。見諒。

問題綜述

Linux內(nèi)核協(xié)議棧作為一種軟路由運(yùn)行時，和其它通用操作系統(tǒng)自帶的協(xié)議棧相比，其效率并非如下文所說的那樣非常低。然而基于工業(yè)路由器的評判標(biāo)準(zhǔn)，確實是低了。

市面上各種基于Linux內(nèi)核協(xié)議棧的路由器產(chǎn)品，甚至網(wǎng)上也有大量的此類文章，比如什么將Linux變成路由器之類的，無非就是打開ip_forward，加幾條iptables規(guī)則，搞個配置起來比較方便的WEB界面...我想說這些太低級了，甚至超級低級。我很想談一下關(guān)于專業(yè)路由器的我的觀點，但是今天是小小的生日，玩了一天，就不寫了。只是把我的方案整理出來吧。

Linux的轉(zhuǎn)發(fā)效率到底低在哪兒？如何優(yōu)化？這是本文要解釋的問題。依然如故，本文可以隨意轉(zhuǎn)載并基于這個思路實現(xiàn)編碼，但是一旦用于商業(yè)目的，不保證沒有個人或組織追責(zé)，因此文中我盡量采用盡可能模糊的方式闡述細(xì)節(jié)。

瓶頸分析概述

1.DMA和內(nèi)存操作

我們考慮一下一個數(shù)據(jù)包轉(zhuǎn)發(fā)流程中需要的內(nèi)存操作，暫時不考慮DMA。

*)數(shù)據(jù)包從網(wǎng)卡拷貝到內(nèi)存

*)CPU訪問內(nèi)存讀取數(shù)據(jù)包元數(shù)據(jù)

*)三層報頭修改，如TTL

*)轉(zhuǎn)發(fā)到二層后封裝MAC頭

*)數(shù)據(jù)包從內(nèi)存拷貝到輸出網(wǎng)卡

這幾個典型的內(nèi)存操作為什么慢？為什么我們總是對內(nèi)存操作有這么大的意見？因為訪問內(nèi)存需要經(jīng)過總線，首先總線競爭(特別在SMP和DMA下)就是一個打群架的過程，另外因為內(nèi)存自身的速度和CPU相比差了幾個數(shù)量級，這么玩下去，肯定會慢啊！所以一般都是盡可能地使用CPU的cache，而這需要一定的針對局部性的數(shù)據(jù)布局，對于數(shù)據(jù)包接收以及其它IO操作而言，由于數(shù)據(jù)來自外部，和進(jìn)程執(zhí)行時的局部性利用沒法比。所以必須采用類似Intel I/OAT的技術(shù)才能改善。

1.1.Linux作為服務(wù)器時

采用標(biāo)準(zhǔn)零拷貝map技術(shù)完全勝任。這是因為，運(yùn)行于Linux的服務(wù)器和線速轉(zhuǎn)發(fā)相比就是個蝸牛，服務(wù)器在處理客戶端請求時消耗的時間是一個硬性時間，無法優(yōu)化，這是代償原理。Linux服務(wù)唯一需要的就是能快速取到客戶端的數(shù)據(jù)包，而這可以通過DMA快速做到。本文不再具體討論作為服務(wù)器運(yùn)行的零拷貝問題，自己百度吧。

1.2.Linux作為轉(zhuǎn)發(fā)設(shè)備時

需要采用DMA映射交換的技術(shù)才能實現(xiàn)零拷貝。這是Linux轉(zhuǎn)發(fā)性能低下的根本。由于輸入端口的輸入隊列和輸出端口的輸出隊列互不相識，導(dǎo)致了不能更好的利用系統(tǒng)資源以及多端口數(shù)據(jù)路由到單端口輸出隊列時的隊列鎖開銷過大，總線爭搶太嚴(yán)重。DMA影射交換需要超級棒的數(shù)據(jù)包隊列管理設(shè)施，它用來調(diào)度數(shù)據(jù)包從輸入端口隊列到輸出端口隊列，而Linux幾乎沒有這樣的設(shè)施。

雖然近年在路由器領(lǐng)域有人提出了輸入隊列管理，但是這項技術(shù)對于Linux而言就是另一個世界，而我，把它引入了Linux世界。

2.網(wǎng)卡對數(shù)據(jù)包隊列Buff管理

在Linux內(nèi)核中，幾乎對于所有數(shù)據(jù)結(jié)構(gòu)，都是需要時alloc，完畢后free，即使是kmem_cache，效果也一般，特別是對于高速線速設(shè)備而言(skb內(nèi)存拷貝，若不采用DMA，則會頻繁拷貝，即便采用DMA，在很多情況下也不是零拷貝)。

即使是高端網(wǎng)卡在skb的buffer管理方面，也沒有使用完全意義上的預(yù)分配內(nèi)存池，因此會由于頻繁的內(nèi)存分配，釋放造成內(nèi)存顛簸，眾所周知，內(nèi)存操作是問題的根本，因為它涉及到CPU Cache，總線爭搶，原子鎖等，實際上，內(nèi)存管理才是根本中的根本，這里面道道太多，它直接影響CPU cache，后者又會影響總線...從哪里分配內(nèi)存，分配多少，何時釋放，何時可以重用，這就牽扯到了內(nèi)存區(qū)域著色等技術(shù)。通過分析Intel千兆網(wǎng)卡驅(qū)動，在我看來，Linux并沒有做好這一點。

3.路由查找以及其它查找操作

Linux不區(qū)分對待路由表和轉(zhuǎn)發(fā)表，每次都要最長前綴查找，雖然海量路由表時trie算法比hash算法好，但是在路由分布畸形的情況下依然會使trie結(jié)構(gòu)退化，或者頻繁回溯。路由cache效率不高（查詢代價太大，不固定大小，僅有弱智的老化算法，導(dǎo)致海量地址訪問時，路由cache沖突鏈過長），最終在內(nèi)核協(xié)議棧中下課。

如果沒有一個好的轉(zhuǎn)發(fā)表，那么Linux協(xié)議棧在海量路由存在時對于線速能力就是一個瓶頸，這是一個可擴(kuò)展性問題。

另外，很多的查詢結(jié)果都是可以被在一個地方緩存的，但是Linux協(xié)議棧沒有這種緩存。比如，路由查詢結(jié)果就是下一跳，而下一跳和輸出網(wǎng)卡關(guān)聯(lián)，而輸出網(wǎng)卡又和下一跳的MAC地址以及將要封裝的源MAC地址關(guān)聯(lián)，這些本應(yīng)該被緩存在一個表項，即轉(zhuǎn)發(fā)表項內(nèi)，然而Linux協(xié)議棧沒有這么做。

4.不合理的鎖

為何要加鎖，因為SMP。然而Linux內(nèi)核幾乎是對稱的加鎖，也就是說，比如每次查路由表時都要加鎖，為何？因為怕在查詢的期間路由表改變了...然而你仔細(xì)想想，在高速轉(zhuǎn)發(fā)情景下，查找操作和修改操作在單位時間的比率是多少呢？不要以為你用讀寫鎖就好了，讀寫鎖不也有關(guān)搶占的操作嗎(雖然我們已經(jīng)建議關(guān)閉了搶占)？起碼也浪費(fèi)了幾個指令周期。這些時間幾率不對稱操作的加鎖是不必要的。

你只需要保證內(nèi)核本身不會崩掉即可，至于說IP轉(zhuǎn)發(fā)的錯誤，不管也罷，按照IP協(xié)議，它本身就是一個盡力而為的協(xié)議。

5.中斷與軟中斷調(diào)度

Linux的中斷分為上半部和下半部，動態(tài)調(diào)度下半部，它可以在中斷上下文中運(yùn)行，也可以在獨(dú)立的內(nèi)核線程上下文中運(yùn)行，因此對于實時需求的環(huán)境，在軟中斷中處理的協(xié)議棧處理的運(yùn)行時機(jī)是不可預(yù)知的。Linux原生內(nèi)核并沒有實現(xiàn)Solaris，Windows那樣的中斷優(yōu)先級化，在某些情況下，Linux靠著自己動態(tài)的且及其優(yōu)秀的調(diào)度方案可以達(dá)到極高的性能，然而對于固定的任務(wù)，Linux的調(diào)度機(jī)制卻明顯不足。

而我需要做的，就是讓不固定的東西固定化。

6.通用操作系統(tǒng)內(nèi)核協(xié)議棧的通病

作為一個通用操作系統(tǒng)內(nèi)核，Linux內(nèi)核并非僅僅處理網(wǎng)絡(luò)數(shù)據(jù)，它還有很多別的子系統(tǒng)，比如各種文件系統(tǒng)，各種IPC等，它能做的只是可用，簡單，易擴(kuò)展。

Linux原生協(xié)議棧完全未經(jīng)網(wǎng)絡(luò)優(yōu)化，且基本裝機(jī)在硬件同樣也未經(jīng)優(yōu)化的通用架構(gòu)上，網(wǎng)卡接口在PCI-E總線上，如果DMA管理不善，總線的占用和爭搶帶來的性能開銷將會抵消掉DMA本意帶來的好處（事實上對于轉(zhuǎn)發(fā)而言并沒有帶來什么好處，它僅僅對于作為服務(wù)器運(yùn)行的Linux有好處，因為它只涉及到一塊網(wǎng)卡）

[ 注意，我認(rèn)為內(nèi)核處理路徑并非瓶頸，這是分層協(xié)議棧決定的，瓶頸在各層中的某些操作，比如內(nèi)存操作(固有開銷)以及查表操作(算法不好導(dǎo)致的開銷)]

綜述：Linux轉(zhuǎn)發(fā)效率受到以下幾大因素影響

IO/輸入輸出的隊列管理/內(nèi)存修改拷貝 （重新設(shè)計類似crossbar的隊列管理實現(xiàn)DMA ring交換）

各種表查詢操作，特別是最長前綴匹配，諸多本身唯一確定的查詢操作之間的關(guān)聯(lián)沒有建立

SMP下處理器同步（鎖開銷）（使用大讀鎖以及RCU鎖）以及cache利用率

中斷以及軟中斷調(diào)度

Linux轉(zhuǎn)發(fā)性能提升方案

概述

此方案的思路來自基于crossbar的新一代硬件路由器。設(shè)計要點：

1.重新設(shè)計的DMA包管理隊列（ 思路來自Linux O(1)調(diào)度器，crossbar陣列以及VOQ[虛擬輸出隊列]）

2.重新設(shè)計的基于定位而非最長前綴查找的轉(zhuǎn)發(fā)表

3.長線程處理（中斷線程化，處理流水線化，增加CPU親和）

4.數(shù)據(jù)結(jié)構(gòu)無鎖化（基于線程局部數(shù)據(jù)結(jié)構(gòu)）

5.實現(xiàn)方式

5.1.驅(qū)動以及內(nèi)核協(xié)議棧修改

5.2.完全的用戶態(tài)協(xié)議棧

5.3.評估：用戶態(tài)協(xié)議棧靈活，但是在某些平臺要處理空間切換導(dǎo)致的cache/tlb/mmu表的flush問題

內(nèi)核協(xié)議棧方案

優(yōu)化框架

0.例行優(yōu)化

1).網(wǎng)卡多隊列綁定特定CPU核心（利用RSS特性分別處理TX和RX）

[ 可以參見《Effective Gigabit Ethernet Adapters-Intel千兆網(wǎng)卡8257X性能調(diào)優(yōu)》]

2).按照包大小統(tǒng)計動態(tài)開關(guān)積壓延遲中斷ThrottleRate以及中斷Delay(對于Intel千兆卡而言)

3).禁用內(nèi)核搶占，減少時鐘HZ，由中斷粒度驅(qū)動（見上面）

4).如果不準(zhǔn)備優(yōu)化Netfilter，編譯內(nèi)核時禁用Netfilter，節(jié)省指令

5).編譯選項去掉DEBUG和TRACE，節(jié)省指令周期

6).開啟網(wǎng)卡的硬件卸載開關(guān)（如果有的話）

7).最小化用戶態(tài)進(jìn)程的數(shù)量，降低其優(yōu)先級

8).原生網(wǎng)絡(luò)協(xié)議棧優(yōu)化

由于不再作為通用OS，可以讓除了RX softirq的task適當(dāng)饑餓

*CPU分組(考慮Linux的cgroup機(jī)制)，劃一組CPU為數(shù)據(jù)面CPU，每一個CPU綁定一個RX softirq或者

*增加rx softirq一次執(zhí)行的netdev_budget以及time limit，或者

*只要有包即處理，每一個?？刂泼?管理面的task可以綁在別的CPU上。

宗旨：

原生協(xié)議棧的最優(yōu)化方案

1.優(yōu)化I/O，DMA，減少內(nèi)存管理操作

1).減少PCI-E的bus爭用,采用crossbar的全交叉超立方開關(guān)的方式

[ Tips：16 lines 8 bits PCI-E總線拓?fù)?非crossbar！)的網(wǎng)絡(luò)線速不到滿載60% pps]

2).減少爭搶式DMA，減少鎖總線[Tips：優(yōu)化指令LOCK，最好采用RISC，方可調(diào)高內(nèi)核HZ]

[ Tips：交換DMA映射，而不是在輸入/輸出buffer ring之間拷貝數(shù)據(jù)！現(xiàn)在，只有傻逼才會在DMA情況拷貝內(nèi)存，正確的做法是DMA重映射，交換指針！]

3).采用skb內(nèi)存池，避免頻繁內(nèi)存分配/釋放造成的內(nèi)存管理框架內(nèi)的抖動

[ Tips：每線程負(fù)責(zé)一塊網(wǎng)卡(甚至輸入和輸出由不同的線程負(fù)責(zé)會更好)，保持一個預(yù)分配可循環(huán)利用的ring buffer，映射DMA]

宗旨：

減少cache刷新和tlb刷新，減少內(nèi)核管理設(shè)施的工作(比如頻繁的內(nèi)存管理)

2.優(yōu)化中斷分發(fā)

1).增加長路徑支持，減少進(jìn)程切換導(dǎo)致的TLB以及Cache刷新

2).利用多隊列網(wǎng)卡支持中斷CPU親和力利用或者模擬軟多隊列提高并行性

3).犧牲用戶態(tài)進(jìn)程的調(diào)度機(jī)會，全部精力集中于內(nèi)核協(xié)議棧的處理，多CPU多路并行的

[ Tips：如果有超多的CPU，建議劃分cgroup ]

4).中斷處理線程化，內(nèi)核線程化，多核心并行執(zhí)行長路經(jīng)，避免切換抖動

5).線程內(nèi)部，按照IXA NP微模塊思想采用模塊化(方案未實現(xiàn)，待商榷)

宗旨：

減少cache刷新和tlb刷新

減少協(xié)議棧處理被中斷過于頻繁打斷[ 要么使用IntRate，要么引入中斷優(yōu)先級]

3.優(yōu)化路由查找算法

1).分離路由表和轉(zhuǎn)發(fā)表，路由表和轉(zhuǎn)發(fā)表同步采用RCU機(jī)制

2).盡量采用線程局部數(shù)據(jù)

每個線程一張轉(zhuǎn)發(fā)表（由路由表生成，OpenVPN多線程采用，但失?。捎枚ㄎ欢亲铋L前綴查找（DxR或者我設(shè)計的那個）。若不采用為每個線程復(fù)制一份轉(zhuǎn)發(fā)表，則需要重新設(shè)計RW鎖或者使用RCU機(jī)制。

3).采用hash/trie方式以及DxR或者我設(shè)計的DxRPro定位結(jié)構(gòu)

宗旨：

采用定位而非查找結(jié)構(gòu)

采用局部表，避免鎖操作

4.優(yōu)化lock

1).查詢定位局部表，無鎖（甚至RW鎖都沒有）不禁止中斷

2).臨界區(qū)和內(nèi)核線程關(guān)聯(lián)，不禁中斷，不禁搶占（其實內(nèi)核編譯時搶占已經(jīng)關(guān)閉了）

3).優(yōu)先級鎖隊列替換爭搶模型，維持cache熱度

4).采用Windows的自旋鎖機(jī)制

[ Tips：Linux的ticket spin lock由于采用探測全局lock的方式，會造成總線開銷和CPU同步開銷，Windows的spin lock采用了探測CPU局部變量的方式實現(xiàn)了真正的隊列l(wèi)ock，我設(shè)計的輸入輸出隊列管理結(jié)構(gòu)(下面詳述)思路部分來源于Windows的自旋鎖設(shè)計]

宗旨：鎖的粒度與且僅與臨界區(qū)資源關(guān)聯(lián)，粒度最小化

優(yōu)化細(xì)節(jié)概覽

1.DMA與輸入輸出隊列優(yōu)化

1.1.問題出在哪兒

如果你對Linux內(nèi)核協(xié)議棧足夠熟悉，那么就肯定知道，Linux內(nèi)核協(xié)議棧正是由于軟件工程里面的天天普及的“一件好事”造成了轉(zhuǎn)發(fā)性能低效。這就是“解除緊密耦合”。

Linux協(xié)議棧轉(zhuǎn)發(fā)和Linux服務(wù)器之間的根本區(qū)別在于，后者的應(yīng)用服務(wù)并不在乎數(shù)據(jù)包輸入網(wǎng)卡是哪個，它也不必關(guān)心輸出網(wǎng)卡是哪一個，然而對于Linux協(xié)議棧轉(zhuǎn)發(fā)而言，輸入網(wǎng)卡和輸出網(wǎng)卡之間確實是有必要相互感知的。Linux轉(zhuǎn)發(fā)效率低的根本原因不是路由表不夠高效，而是它的隊列管理以及I/O管理機(jī)制的低效，造成這種低效的原因不是技術(shù)實現(xiàn)上難以做到，而是Linux內(nèi)核追求的是一種靈活可擴(kuò)展的性能，這就必須解除出入網(wǎng)卡，驅(qū)動和協(xié)議棧之間關(guān)于數(shù)據(jù)包管理的緊密耦合。

我們以Intel千兆網(wǎng)卡驅(qū)動e1000e來說明上述的問題。順便說一句，Intel千兆驅(qū)動亦如此，其它的就更別說了，其根源在于通用的網(wǎng)卡驅(qū)動和協(xié)議棧設(shè)計并不是針對轉(zhuǎn)發(fā)優(yōu)化的。

初始化：

創(chuàng)建RX ring：RXbuffinfo[MAX]

創(chuàng)建TX ring：TXbuffinfo[MAX]

RX過程：

i = 當(dāng)前RX ring游歷到的位置;

while(RXbuffinfo中有可用skb) {

skb = RXbufferinfo[i].skb;

RXbuffinfo[i].skb = NULL;

i++;

DMA_unmap(RXbufferinfo[i].DMA);

[Tips：至此，skb已經(jīng)和驅(qū)動脫離，完全交給了Linux協(xié)議棧]

[Tips：至此，skb內(nèi)存已經(jīng)不再由RX ring維護(hù)，Linux協(xié)議棧拽走了skb這塊內(nèi)存]

OS_receive_skb(skb);

[Tips：由Linux協(xié)議棧負(fù)責(zé)釋放skb，調(diào)用kfree_skb之類的接口]

if (RX ring中被Linux協(xié)議棧摘走的skb過多) {

alloc_new_skb_from_kmem_cache_to_RXring_RXbufferinfo_0_to_MAX_if_possible;

[Tips：從Linux核心內(nèi)存中再次分配skb]

}

}

TX過程：

skb = 來自Linux協(xié)議棧dev_hard_xmit接口的數(shù)據(jù)包;

i = TX ring中可用的位置

TXbufferinfo[i].skb = skb;

DMA_map(TXbufferinfo[i].DMA);

while(TXbufferinfo中有可用的skb) {

DMA_transmit_skb(TXbufferinfo[i]);

}

[異步等待傳輸完成中斷或者在NAPI poll中主動調(diào)用]

i = 傳輸完成的TXbufferinfo索引

while(TXbufferinfo中有已經(jīng)傳輸完成的skb) {

skb = TXbufferinfo[i];

DMA_unmap(TXbufferinfo[i].DMA);

kfree(skb);

i++;

}

以上的流程可以看出，在持續(xù)轉(zhuǎn)發(fā)數(shù)據(jù)包的時候，會涉及大量的針對skb的alloc和free操作。如果你覺得上面的代碼不是那么直觀，那么下面給出一個圖示：

頻繁的會發(fā)生從Linux核心內(nèi)存中alloc skb和free skb的操作，這不僅僅是不必要的，而且還會損害CPU cache的利用。不要寄希望于keme_cache，我們可以看到，所有的網(wǎng)卡和socket幾乎是共享一塊核心內(nèi)存的，雖然可以通過dev和kmem cache來優(yōu)化，但很遺憾，這個優(yōu)化沒有質(zhì)的飛躍。

1.2.構(gòu)建新的DMA ring buffer管理設(shè)施-VOQ，建立輸入/輸出網(wǎng)卡之間隊列的關(guān)聯(lián)。

類比Linux O(1)調(diào)度器算法，每一個cpu全局維護(hù)一個唯一的隊列，散到各個網(wǎng)卡，靠交換隊列的DMA映射指針而不是拷貝數(shù)據(jù)的方式優(yōu)化性能，達(dá)到零拷貝，這只是其一。關(guān)于交換DMA映射指針而不是拷貝數(shù)據(jù)這一點不多談，因為幾乎所有的支持DMA的網(wǎng)卡驅(qū)動都是這么做的，如果它們不是這么做的，那么肯定有人會將代碼改成這么做的。

如果類比高端路由器的crossbar交換陣列結(jié)構(gòu)以及真實的VOQ實現(xiàn)，你會發(fā)現(xiàn)，在邏輯上，每一對可能的輸入/輸出網(wǎng)卡之間維護(hù)一條數(shù)據(jù)轉(zhuǎn)發(fā)通路是避免隊頭阻塞以及競爭的好方法。這樣排隊操作只會影響單獨(dú)的網(wǎng)卡，不需要再全局加鎖。在軟件實現(xiàn)上，我們同樣可以做到這個。你要明白，Linux的網(wǎng)卡驅(qū)動維護(hù)的隊列信息被內(nèi)核協(xié)議棧給割裂，從此，輸入/輸出網(wǎng)卡之間彼此失聯(lián)，導(dǎo)致最優(yōu)的二分圖算法無法實施。

事實上，你可能覺得把網(wǎng)卡作為一個集合，把需要輸出的數(shù)據(jù)包最為另一個集合，轉(zhuǎn)發(fā)操作需要做的就是建立數(shù)據(jù)包和網(wǎng)卡之間的一條路徑，這是一個典型的二分圖匹配問題，然而如果把建立路徑的操作與二分圖問題分離，這就是不再是網(wǎng)卡和數(shù)據(jù)包之間的二分圖匹配問題了。因為分離出來的路由模塊導(dǎo)致了針對每一個要轉(zhuǎn)發(fā)的數(shù)據(jù)包，其輸出網(wǎng)卡是唯一確定的。這個問題變成了處理輸出網(wǎng)卡輸出操作的CPU集合和輸出網(wǎng)卡之間的二分圖匹配問題。

這里有一個優(yōu)化點，那就是如果你有多核CPU，那么就可以為每一塊網(wǎng)卡的輸出操作綁定一個唯一的CPU，二分圖匹配問題迎刃而解，剩下的就是硬件總線的爭用問題(對于高性能crossbar路由器而言，這也是一個二分圖匹配問題，但對于總線結(jié)構(gòu)的通用系統(tǒng)而言有點區(qū)別，后面我會談到)了，作為我們而言，這一點除了使用性價比更高的總線，比如我們使用PCI-E 16Lines 8 bits，沒有別的辦法。作為一個完全的方案，我不能寄希望于底層存在一個多核CPU系統(tǒng)，如果只有一個CPU，那么我們能寄希望于Linux進(jìn)程調(diào)度系統(tǒng)嗎？還是那個觀點，作為一個通用操作系統(tǒng)內(nèi)核，Linux不會針對網(wǎng)絡(luò)轉(zhuǎn)發(fā)做優(yōu)化，于是乎，進(jìn)程調(diào)度系統(tǒng)是此方案的另一個優(yōu)化點，這個我后面再談。

最后，給出我的數(shù)據(jù)包隊列管理VOQ的設(shè)計方案草圖。

在我的這個針對Linux協(xié)議棧的VOQ設(shè)計中，VOQ總要要配合良好的輸出調(diào)度算法，才能發(fā)揮出最佳的性能。

2.分離路由表和轉(zhuǎn)發(fā)表以及建立查找操作之間的關(guān)聯(lián)

Linux協(xié)議棧是不區(qū)分對待路由表和轉(zhuǎn)發(fā)表的，而這在高端路由器上顯然是必須的。誠然，我沒有想將Linux協(xié)議棧打造成比肩專業(yè)路由器的協(xié)議棧，然而通過這個排名第二的核心優(yōu)化，它的轉(zhuǎn)發(fā)效率定會更上一層樓。

在大約三個月前，我參照DxR結(jié)構(gòu)以及借鑒MMU思想設(shè)計了一個用于轉(zhuǎn)發(fā)的索引結(jié)構(gòu)，可以實現(xiàn)3步定位，無需做最長前綴匹配過程，具體可以參見我的這篇文章 《以DxR算法思想為基準(zhǔn)設(shè)計出的路由項定位結(jié)構(gòu)圖解》，我在此就不再深度引用了。需要注意的是，這個結(jié)構(gòu)可以根據(jù)現(xiàn)行的Linux協(xié)議棧路由FIB生成，而且在路由項不規(guī)則的情況下可以在最差情況下動態(tài)回退到標(biāo)準(zhǔn)DxR，比如路由項不可匯聚，路由項在IPv4地址空間劃分區(qū)間過多且分布不均。我將我設(shè)計的這個結(jié)構(gòu)稱作DxR Pro++。

至于說查找操作之間的關(guān)聯(lián)，這也是一個深度優(yōu)化，底層構(gòu)建高速查詢流表實現(xiàn)協(xié)議棧短路（流表可參照conntrack設(shè)計），這個優(yōu)化思想直接參照了Netfilter的conntrack以及SDN流表的設(shè)計。雖然IP網(wǎng)絡(luò)是一個無狀態(tài)網(wǎng)絡(luò)，中間路由器的轉(zhuǎn)發(fā)策略也應(yīng)該是一個無狀態(tài)的轉(zhuǎn)發(fā)。然而這是形而上意義上的理念。如果談到深度優(yōu)化，就不得不犧牲一點純潔性。

設(shè)計一個流表，流的定義可以不必嚴(yán)格按照五元組，而是可以根據(jù)協(xié)議頭的任意字段，每一個表項中保存的信息包括但不限于以下的元素：

*流表緩存路由項

*流表緩存neighbour

*流表緩存NAT

*流表緩存ACL規(guī)則

*流表緩存二層頭信息

這樣可以在協(xié)議棧的底層保存一張可以高速查詢的流表，協(xié)議棧收到skb后匹配這張表的某項，一旦成功，可以直接取出相關(guān)的數(shù)據(jù)(比如路由項)直接轉(zhuǎn)發(fā)，理論上只有一個流的第一個數(shù)據(jù)包會走標(biāo)準(zhǔn)協(xié)議棧的慢速路徑(事實上，經(jīng)過DxR Pro++的優(yōu)化，一經(jīng)不慢了...)。在直接快速轉(zhuǎn)發(fā)中，需要執(zhí)行一個HOOK，執(zhí)行標(biāo)準(zhǔn)的例行操作，比如校驗和，TTL遞減等。

關(guān)于以上的元素，特別要指出的是和neighbour與二層信息相關(guān)的。數(shù)據(jù)轉(zhuǎn)發(fā)操作一向被認(rèn)為瓶頸在發(fā)不在收，在數(shù)據(jù)發(fā)送過程，會涉及到以下耗時的操作：>添加輸出網(wǎng)卡的MAC地址作為源-內(nèi)存拷貝>添加next hop的MAC地址作為目標(biāo)-內(nèi)存拷貝又一次，我們遇到了內(nèi)存操作，惱人的內(nèi)存操作！如果我們把這些MAC地址保存在流表中，可以避免嗎？貌似只是可以快速定位，而無法避免內(nèi)存拷貝...再一次的，我們需要硬件的特性來幫忙，這就是分散聚集I/O(Scatter-gather IO)，原則上，Scatter-gather IO可以將不連續(xù)的內(nèi)存當(dāng)成連續(xù)的內(nèi)存使用，進(jìn)而直接映射DMA，因此我們只需要告訴控制器，一個將要發(fā)送的幀的MAC頭的位置在哪里，DMA就可以直接傳輸，沒有必要將MAC地址拷貝到幀頭的內(nèi)存區(qū)域。如下圖所示：

特別要注意，上述的流表緩存項中的數(shù)據(jù)存在大量冗余，因為next hop的MAC地址，輸出網(wǎng)卡的MAC地址，這些是可以由路由項唯一確定的。之所以保存冗余數(shù)據(jù)，其原則還是為了優(yōu)化，而標(biāo)準(zhǔn)的通用Linux內(nèi)核協(xié)議棧，它卻是要避免冗余的...既然保存了冗余數(shù)據(jù)，那么慢速路徑的數(shù)據(jù)項和快速路經(jīng)的數(shù)據(jù)項之間的同步就是一個必須要解決的問題。我基于讀寫的不對稱性，著手采用event的方式通知更新，比如慢速路徑中的數(shù)據(jù)項(路由，MAC信息，NAT，ACL信息等)，一旦這些信息更改，內(nèi)核會專門觸發(fā)一個查詢操作，將快速流表中與之相關(guān)的表項disable掉即可。值得注意的是，這個查詢操作沒必要太快，因為相比較快速轉(zhuǎn)發(fā)而言，數(shù)據(jù)同步的頻率要慢天文數(shù)字個數(shù)量級...類似Cisco的設(shè)備，可以創(chuàng)建幾個內(nèi)核線程定期刷新慢速路徑表項，用來發(fā)現(xiàn)數(shù)據(jù)項的更改，從而觸發(fā)event。

[Tips：可以高速查找的流表結(jié)構(gòu)可用多級hash（采用TCAM的類似方案），也可以借鑒我的DxR Pro++結(jié)構(gòu)以及nf-HiPac算法的多維區(qū)間匹配結(jié)構(gòu)，我個人比較推崇nf-HiPac]

3.路由Cache優(yōu)化

雖說Linux的路由cache早已下課，但是它下課的原因并不是cache機(jī)制本身不好，而是Linux的路由cache設(shè)計得不好。因此以下幾點可以作為優(yōu)化點來嘗試。

*)限制路由軟cache的大小，保證查找速度[實施精心設(shè)計的老化算法和替換算法]

[ 利用互聯(lián)網(wǎng)訪問的時間局部性以及空間局部性（需要利用計數(shù)統(tǒng)計）]

[ 自我PK：如果有了我的那個3步定位結(jié)構(gòu)，難道還用的到路由cache嗎]

*)預(yù)制常用IP地址到路由cache，實現(xiàn)一步定位

[ 所謂常用IP需要根據(jù)計數(shù)統(tǒng)計更新，也可以靜態(tài)設(shè)置]

4.Softirq在不支持RSS多隊列網(wǎng)卡時的NAPI調(diào)度優(yōu)化

*)將設(shè)備按照協(xié)議頭hash值均勻放在不同CPU，遠(yuǎn)程喚醒softirq，模擬RSS軟實現(xiàn)

目前的網(wǎng)絡(luò)接收軟中斷的處理機(jī)制是，哪個CPU被網(wǎng)卡中斷了，哪個CPU就處理網(wǎng)卡接收軟中斷，在網(wǎng)卡只能中斷固定CPU的情況下，這會影響并行性，比如只有兩塊網(wǎng)卡，卻有16核CPU。如何將盡可能多的CPU核心調(diào)動起來呢？這需要修改網(wǎng)絡(luò)接收軟中斷處理邏輯。我希望多個CPU輪流處理數(shù)據(jù)包，而不是固定被中斷的數(shù)據(jù)包來處理。修改邏輯如下：

1.所有的rx softirq內(nèi)核線程組成一個數(shù)組

struct task_struct rx_irq_handler[NR_CPUS];

2.所有的poll list組成一個數(shù)組

struct list_head polll[NR_CPUS];

3.引入一把保護(hù)上述數(shù)據(jù)的自旋鎖

spinlock_t rx_handler_lock;

4.修改NAPI的調(diào)度邏輯

void __napi_schedule(struct napi_struct *n)

{

unsigned long flags;

static int curr = 0;

unsigned int hash = curr++%NR_CPUS;

local_irq_save(flags);

spin_lock(&rx_handler_lock);

list_add_tail(&n->poll_list, polll[hash]);

local_softirq_pending(hash) |= NET_RX_SOFTIRQ;

spin_unlock(&rx_handler_lock);

local_irq_restore(flags);

}

[ Tips：注意和DMA/DCA，CPU cache親和的結(jié)合，如果連DMA都不支持，那還優(yōu)化個毛]

理論上一定要做基于傳輸層以及傳輸層以下的元組做hash，不能隨機(jī)分派，在計算hash的時候也不能引入任何每包可變的字段。由于某些高層協(xié)議比如TCP以及絕大多數(shù)的基于非TCP的應(yīng)用協(xié)議是高度按序的，中間節(jié)點的完全基于數(shù)據(jù)包處理的并行化會引起數(shù)據(jù)包在端節(jié)點的亂序到達(dá)，從而引發(fā)重組和重傳開銷。自己為了提高線速能力貌似爽了一把，卻給端主機(jī)帶來了麻煩。然而我目前沒有考慮這個，我只是基于輪轉(zhuǎn)調(diào)度的方式來分發(fā)poll過程到不同的CPU來處理，這顯然會導(dǎo)致上述的亂序問題。

若想完美解決上述問題，需要增加一個調(diào)度層，將RX softirq再次分為上下兩半部RX softirq1和RX softirq2，上半部RX softirq1僅僅是不斷取出skb并分派到特定CPU核心，下半部才是協(xié)議棧處理，修改NAPI的poll邏輯，每當(dāng)poll出來一個skb，就計算這個skb的hash值，然后將其再次分派到特定的CPU的隊列中，最后喚醒有skb需要處理的CPU上的RX softirq2，這期間需要引入一個位圖來記錄有無情況。

但是有一個需要權(quán)衡的邏輯，是不是真的值得將RX softirq做再次分割，將其分為上下半部，這期間的調(diào)度開銷和切換開銷到底是多少，需要基準(zhǔn)測試來評估。

*)延長net softirq的執(zhí)行時間，有包就一直dispatch loop。管理/控制平面進(jìn)程被劃分到獨(dú)立的cgroup/cpuset中。

5.Linux調(diào)度器相關(guān)的修改

這個優(yōu)化涉及到方案的完備性，畢竟我們不能保證CPU核心的數(shù)量一定大于網(wǎng)卡數(shù)量的2倍(輸入處理和輸出處理分離)，那么就必須考慮輸出事件的調(diào)度問題。

依照數(shù)據(jù)包隊列管理的設(shè)計方案，考慮單CPU核心，如果有多塊網(wǎng)卡的輸出位圖中有bit被置位，那么到底調(diào)度哪一個網(wǎng)卡進(jìn)行輸出呢？這是一個明確的task調(diào)度問題。你放心把這個工作交給Linux內(nèi)核的調(diào)度器去做嗎？我不會。

因為我知道，雖然有好幾個網(wǎng)卡可能都有數(shù)據(jù)包等待發(fā)送，但是它們的任務(wù)量并不同，這又是一個二分圖問題。我需要三個指標(biāo)加權(quán)來權(quán)衡讓哪個網(wǎng)卡先發(fā)送，這三個指標(biāo)是，隊頭等待時間，隊列數(shù)據(jù)包長度總和以及數(shù)據(jù)包數(shù)量。由此可以算出一個優(yōu)先級prio，總的來講就是虛擬輸出隊列中等待越久，數(shù)據(jù)包越多，長度越長的那個網(wǎng)卡最值得發(fā)送數(shù)據(jù)。計算隊列總長勢必會引發(fā)非局部訪問，比如訪問其它網(wǎng)卡的虛擬輸出隊列，這就會引發(fā)鎖的問題，因此考慮簡單情形，僅僅使用一個指標(biāo)，即數(shù)據(jù)包長度。在Linux當(dāng)前的CFS調(diào)度器情形下，需要將排隊虛擬輸出隊列的數(shù)據(jù)包長度與task的虛擬時間，即vruntime關(guān)聯(lián)，具體來講就是，在輸入網(wǎng)卡對輸出網(wǎng)卡的輸出位圖置位的時候，有下列序列：

//只要有skb排隊，無條件setbit

setbit(outcart, incard);

//只要有skb排隊，則將與輸出網(wǎng)卡關(guān)聯(lián)的輸出線程的虛擬時間減去一個值，該值由數(shù)據(jù)包長度與常量歸一化計算所得。

outcard_tx_task_dec_vruntime(outcard, skb->len);

對Linux CFS調(diào)度不熟悉的，可以自行g(shù)oogle。事實上，一旦某個輸出網(wǎng)卡的輸出task開始運(yùn)行，它也是按照這種基于虛擬時間流逝的CFS方式來調(diào)度數(shù)據(jù)包的，即摘下一個最值得發(fā)送的數(shù)據(jù)包隊列描述符放入TX ring。

最后有一個思考，如果不采用CFS而采用RT調(diào)度類是不是更好？單獨(dú)網(wǎng)卡輸出的實時性和多塊網(wǎng)卡輸出之間的公平性如何權(quán)衡？另外，采用RT調(diào)度類就一定帶有實時性嗎？

6.內(nèi)置包分類和包過濾的情況

這是一個關(guān)于Netfilter優(yōu)化的話題，Netfilter的性能一直被人詬病，其很大程度上都是由于iptables造成的，一定要區(qū)分對待Netfilter和iptables。當(dāng)然排除了這個誤會，并不表明Netfilter就完全無罪。Netfilter是一個框架，它本身在我們已經(jīng)關(guān)閉了搶占的情況下是沒有鎖開銷的，關(guān)鍵的在它內(nèi)部的HOOK遍歷執(zhí)行中，作為一些callback，內(nèi)部的邏輯是不受控制的，像iptables，conntrack(本來數(shù)據(jù)結(jié)構(gòu)粒度就很粗-同一張hash存儲兩個方向的元組，又使用大量的大粒度鎖，內(nèi)存不緊張時我們可以多用幾把鎖，空間換自由，再說，一把鎖能占多大空間啊)，都是吃性能的大戶，而nf-HiPac就好很多。因此這部分的優(yōu)化不好說。

不過建議還是有的，為一段臨界區(qū)加鎖的時候千萬不要盲目，如果一個數(shù)據(jù)結(jié)構(gòu)被讀的頻率比被寫的頻率高很多，以至于后者可以被忽略的地步，那么勸各位不要鎖定它，即使RW鎖，RCU鎖都不要，而是采用復(fù)制的形式，拷貝出一個副本，然后讀副本，寫原本，寫入原本后采用原子事件的方式通知副本失效。比如上面提到的關(guān)于快速流表的同步問題，一旦路由發(fā)生變化，就觸發(fā)一個原子事件，查詢快速流表中與之相關(guān)的項，失效掉它。查詢可以很慢，因為路由更新的頻率很低。

本節(jié)不多談，建議如下：

*)預(yù)處理ACL或者NAT的ruleset（采用nf-hipac方案替換非預(yù)處理的逐條匹配）

[Hipac算法類似于一種針對規(guī)則的預(yù)處理，將matches進(jìn)行了拆分，采用多維區(qū)間匹配算法]

*)包調(diào)度算法（CFS隊列，RB樹存儲包到達(dá)時間*h(x)，h為包長的函數(shù)）

7.作為容器的skb

skb作為一個數(shù)據(jù)包的容器存在，它要和真正的數(shù)據(jù)包區(qū)分開來，事實上，它僅僅作為一個數(shù)據(jù)包的載體，像一輛卡車運(yùn)載數(shù)據(jù)包。它是不應(yīng)該被釋放的，永遠(yuǎn)不該被釋放。每一塊網(wǎng)卡都應(yīng)該擁有自己的卡車車隊，如果我們把網(wǎng)卡看作是航空港，Linux路由器看作是陸地，那么卡車從空港裝載貨物(數(shù)據(jù)包)，要么把它運(yùn)輸?shù)侥硞€目的地(Linux作為服務(wù)器)，要么把它運(yùn)輸?shù)搅硪粋€空港(Linux作為轉(zhuǎn)發(fā)路由器)，其間這輛卡車運(yùn)送個來回即可，這輛卡車一直屬于貨物到達(dá)的那個空港，將貨物運(yùn)到另一個空港后空車返回即可?？ㄜ嚨氖褂貌槐?a target="_blank">中心調(diào)度，更無需用完后銷毀，用的時候再造一輛(Linux的轉(zhuǎn)發(fā)瓶頸即在此?。?！)。

其實還有更加高效的做法，那就是卡車將貨物運(yùn)輸?shù)搅硪粋€港口或者運(yùn)輸?shù)疥懙啬康牡睾螅槐乜哲嚪祷?，而是直接排入目的港口或者目的地的出港隊列，等待運(yùn)輸貨物滿載返回所屬的港口。但是對于Linux而言，由于需要路由查找后才知道卡車返回哪里，因此在出發(fā)的時候，卡車并不能確定它一定會返回它所屬的港口...因此需要對包管理隊列做一定的修正，即解除網(wǎng)卡的RX ring和skb的永久綁定關(guān)系。為了統(tǒng)一起見，新的設(shè)計將路由到本機(jī)的數(shù)據(jù)包也作為轉(zhuǎn)發(fā)處理，只是輸出網(wǎng)卡變成了一個BSD socket，新的設(shè)計如下圖所示：

其實，類比火車和出租車我們就能看到這個區(qū)別。對于火車而言，它的線路是固定的，比如哈爾濱到漢口的火車，它屬于哈爾濱鐵路局，滿客到達(dá)漢口后，下客，然后漢口空車重新上客，它一定返回哈爾濱。然而對于出租車，就不是這樣，嘉定的滬C牌的出租車?yán)碚撋蠈儆诩味ǎ痪茌d情況下，一個人打車到松江，司機(jī)到松江后，雖然期待有人打他的車回嘉定，但是乘客上車后(路由查找)，告訴司機(jī)，他要到閔行，到達(dá)后，又一人上車，說要到嘉興...越走越遠(yuǎn)，但事實就是這樣，因為乘客上車前，司機(jī)是不能確定他要去哪里的。

用戶態(tài)協(xié)議棧方案

1.爭議

在某些平臺上，如果不解決user/kernel切換時的cache，tlb刷新開銷，這種方案并不是我主推的，這些平臺上不管是寫直通還是寫回，訪問cache都是不經(jīng)MMU的，也不cache mmu權(quán)限，且cache直接使用虛地址。

2.爭議解決方案

可以采用Intel I/OAT的DCA技術(shù)，避免上下文切換導(dǎo)致的cache抖動

3.采用PF_RING的方式

修改驅(qū)動，直接與DMA buffer ring關(guān)聯(lián)（參見內(nèi)核方案的DMA優(yōu)化）。

4.借鑒Tilera的RISC超多核心方案

并行流水線處理每一層，流水級數(shù)為同時處理的包的數(shù)量，CPU核心數(shù)+2，流水?dāng)?shù)量為處理模塊的數(shù)量。

[ 流水線倒立]

本質(zhì)上來講，用戶態(tài)協(xié)議棧和內(nèi)核協(xié)議棧的方案是雷同的，無外乎還是那幾種思想。用戶態(tài)協(xié)議棧實現(xiàn)起來限制更少，更靈活，同時也更穩(wěn)定，但是并不是一味的都是好處。需要注意的是，大量存在的爭議都是形而上的，仁者見仁，智者見智。

穩(wěn)定性

對于非專業(yè)非大型路由器，穩(wěn)定性問題可以不考慮，因為無需7*24，故障了大不了重啟一下而已，無傷大雅。但是就技術(shù)而言，還是有幾點要說的。在高速總線情形下，并行總線容易竄擾，內(nèi)存也容易故障，一個位的錯誤，一個電平的不穩(wěn)定都會引發(fā)不可預(yù)知的后果，所以PCI-E這種高速總線都采用串行的方式傳輸數(shù)據(jù)，對于硬盤而言，SATA也是一樣的道理。

在多網(wǎng)卡DMA情況下，對于通過的基于PCI-E的設(shè)備而言，總線上的群毆是很激烈的，這是總線這種拓?fù)浣Y(jié)構(gòu)所決定的，和總線類型無關(guān)，再考慮到系統(tǒng)總線和多CPU核心，這種群毆會更加激烈，因為CPU們也會參與進(jìn)來。群毆的時候，打翻桌椅而不是扳倒對方是很常有的事，只要考慮一下這種情況，我就想為三年前我與客戶的一次爭吵而向他道歉。

2012年，我做一個VPN項目，客戶說我的設(shè)備可能下一秒就會宕機(jī)，因為不確定性。我說if(true) {printf("cao ni ma! ")(當(dāng)然當(dāng)時我不敢這么說);確定會執(zhí)行嗎？他說不一定。我就上火了...可是現(xiàn)在看來，他是對的。

VOQ設(shè)計后良好的副作用-QoS

VOQ是本方案的一個亮點，本文幾乎是圍繞VOQ展開的，關(guān)于另一個亮點DxR Pro，在其它的文章中已經(jīng)有所闡述，本文只是加以引用而已。臨近末了，我再次提到了VOQ，這次是從一個宏觀的角度，而不是細(xì)節(jié)的角度來加以說明。

只要輸入緩沖區(qū)隊列足夠大，數(shù)據(jù)包接收幾乎就是線速的，然而對于輸出，卻受到了調(diào)度算法，隊頭擁塞等問題的影響，即輸入對于系統(tǒng)來講是被動的，中斷觸發(fā)的，而輸出對于系統(tǒng)來講則是主動的，受制于系統(tǒng)的設(shè)計。因此對于轉(zhuǎn)發(fā)而言“收易發(fā)難”就是一個真理。因此對于QoS的位置，大多數(shù)系統(tǒng)都選擇在了輸出隊列上，因為輸入隊列上即便對流量進(jìn)行了干預(yù)，流量在輸出的時候還是會受到二次無辜的干預(yù)，而這會影響輸入隊列上的QoS干預(yù)效果。我記得曾經(jīng)研究過Linux上的IMQ輸入隊列流控，當(dāng)時只是關(guān)注了實現(xiàn)細(xì)節(jié)，并沒有進(jìn)行形而上的思考，現(xiàn)在不了。

有了VOQ以后，配合設(shè)計良好的調(diào)度算法，幾乎解決了所有問題，這是令人興奮的。上文中我提到輸出操作的時候，輸出線程采用基于數(shù)據(jù)包長度以及虛擬時間的加權(quán)公平調(diào)度算法進(jìn)行輸出調(diào)度，但是這個算法的效果只是全速發(fā)送數(shù)據(jù)包。如果這個調(diào)度算法策略化，做成一個可插拔的，或者說把Linux的TC模塊中的框架和算法移植進(jìn)來，是不是會更好呢？

唉，如果你百度“路由器 線速”，它搜出來的幾乎都是“路由器 限速”，這真是一個玩笑。其實對于轉(zhuǎn)發(fā)而言，你根本不用添加任何TC規(guī)則就能達(dá)到限速的效果，Linux盒子在網(wǎng)上上一串，馬上就被自動限速了，難道不是這樣嗎？而加上VOQ以后，你確實需要限速了。就像在擁擠的中國城市中區(qū)，主干道上寫著限速60，這不是開玩笑嗎？哪個市中心的熙熙攘攘的街道能跑到60....但是一旦上了高速，限速100/120，就是必須的了。

VOQ設(shè)計后良好的副作用-隊頭擁塞以及加速比問題

用硬件路由器的術(shù)語，如果采用將數(shù)據(jù)包路由后排隊到輸出網(wǎng)卡隊列的方案，那么就會有多塊網(wǎng)卡同時往一塊網(wǎng)卡排隊數(shù)據(jù)包的情況，這對于輸出網(wǎng)卡而言是被動的，這又是一個令人悲傷的群毆過程，為了讓多個包都能同時到達(dá)，輸出帶寬一定要是各個輸入帶寬的加和，這就是N倍加速問題，我們希望的是一個輸出網(wǎng)卡主動對數(shù)據(jù)包進(jìn)行調(diào)度的過程，有序必然高效。這就是VOQ設(shè)計的精髓。

對于Linux而言，由于它的輸出隊列是軟件的，因此N加速比問題變成了隊列鎖定問題，總之，還是一個令人遺憾的群毆過程，因此應(yīng)對方案的思想是一致的。因此在Linux中我就模擬了一個VOQ。從這里我們可以看出VOQ和輸出排隊的區(qū)別，VOQ對于輸出過程而言是主動調(diào)度的過程，顯然更加高效，而輸出排隊對于輸出過程而言則是一個被動被爭搶的過程，顯然這是令人感到無望的。

需要說明的是，VOQ只是一個邏輯上的概念，類比了硬件路由器的概念。如果依然堅持使用輸出排隊而不是VOQ，那么設(shè)計多個輸出隊列，每一個網(wǎng)卡一個隊列也是合理的，它甚至更加簡化，壓縮掉了一個網(wǎng)卡分派過程，簡化了調(diào)度。于是我們得到了Linux VOQ設(shè)計的第三版：將虛擬輸出隊列VOQ關(guān)聯(lián)到輸出網(wǎng)卡而不是輸入網(wǎng)卡(下面一小節(jié)我將分析原因)。

總線拓?fù)浜虲rossbar

真正的硬件路由器，比如Cisco，華為的設(shè)備，路由轉(zhuǎn)發(fā)全由線卡硬件執(zhí)行，數(shù)據(jù)包在此期間是靜止在那里的，查詢轉(zhuǎn)發(fā)表的速度是如此之快，以至于相對將數(shù)據(jù)包挪到輸出網(wǎng)卡隊列的開銷，查表開銷可以忽略。因此在真正的硬件路由器上，如何構(gòu)建一個高性能交換網(wǎng)絡(luò)就是重中之重。

不但如此，硬件路由器還需要考慮的是，數(shù)據(jù)包在路由查詢過后是由輸入處理邏輯直接通過交換網(wǎng)絡(luò)PUSH到輸出網(wǎng)卡隊列呢，還是原地不動，然后等待輸出邏輯通過交換網(wǎng)絡(luò)把數(shù)據(jù)包PULL到那里。這個不同會影響到交換網(wǎng)絡(luò)仲裁器的設(shè)計。如果有多個網(wǎng)卡同時往一個網(wǎng)卡輸出數(shù)據(jù)包，PUSH方式可能會產(chǎn)生沖突，因為在Crossbar的一條路徑上，它相當(dāng)于一條總線，而且沖突一般會發(fā)生在交換網(wǎng)絡(luò)內(nèi)部，因此這種PUSH的情況下，一般會在交換網(wǎng)絡(luò)內(nèi)部的開關(guān)節(jié)點上攜帶cache，用來暫存沖突仲裁失敗的數(shù)據(jù)包。反之，如果是PULL方式，情況就有所不同。因此把輸出隊列放在交換網(wǎng)絡(luò)的哪一側(cè)帶來的效果是不同的。

但是對于通用系統(tǒng)架構(gòu)，一般都是采用PCI-E總線連接各個網(wǎng)卡，這是一種典型的總線結(jié)構(gòu)，根本就沒有所謂的交換網(wǎng)絡(luò)。因此所謂的仲裁就是總線仲裁，這并不是我關(guān)注的重點，誰讓我手上只有一個通用架構(gòu)的設(shè)備呢？！我的優(yōu)化不包括總線仲裁器的設(shè)計，因為我不懂這個。

因此，對于通用架構(gòu)總線拓?fù)涞腖inux協(xié)議棧轉(zhuǎn)發(fā)優(yōu)化而言，虛擬輸出隊列VOQ關(guān)聯(lián)在輸入網(wǎng)卡還是輸出網(wǎng)卡，影響不會太大。但是考慮到連續(xù)內(nèi)存訪問帶來的局部性優(yōu)化，我還是傾向?qū)OQ關(guān)聯(lián)到輸出網(wǎng)卡。如果VOQ關(guān)聯(lián)到輸入網(wǎng)卡，那么在進(jìn)行輸出調(diào)度的時候，輸出網(wǎng)卡的輸出線程就要從輸出位圖指示的每一個待發(fā)送數(shù)據(jù)的輸入網(wǎng)卡VOQ中與自己關(guān)聯(lián)的隊列調(diào)度數(shù)據(jù)包，無疑，這些隊列在內(nèi)存中是不連續(xù)的，如果關(guān)聯(lián)到輸出網(wǎng)卡，對于每一個輸出網(wǎng)卡而言，VOQ是連續(xù)的。如下圖所示：

實現(xiàn)相關(guān)

前面我們提到skb只是作為容器(卡車)存在。因此skb是不必釋放的。理想情況下，在Linux內(nèi)核啟動，網(wǎng)絡(luò)協(xié)議棧初始化的時候，根據(jù)自身的硬件性能和網(wǎng)卡參數(shù)做一次自測，然后分配MAX個skb，這些skb可以先均勻分配到各個網(wǎng)卡，同時預(yù)留一個socket skb池，供用戶socket取。后面的事情就是skb運(yùn)輸行為了，卡車開到哪里算哪里，運(yùn)輸過程不空載。

可能你會覺得這個沒有必要，因為skb本身甚至整個Linux內(nèi)核中絕大部分內(nèi)存分配都是被預(yù)先分配并cache的，slab就是做這個的，不是有kmem_cache機(jī)制嗎？是這樣的，我承認(rèn)Linux內(nèi)核在這方面做得很不錯。但是kmem_cache是一個通用的框架，為何不針對skb再提高一個層次呢？每一次調(diào)用alloc_skb，都會觸發(fā)到kmem_cache框架內(nèi)的管理機(jī)制做很多工作，更新數(shù)據(jù)結(jié)構(gòu)，維護(hù)鏈表等，甚至可能會觸及到更加底層的伙伴系統(tǒng)。因此，期待直接使用高效的kmem_cache并不是一個好的主意。

你可能會反駁說萬一系統(tǒng)內(nèi)存吃緊也不釋放嗎？萬事并不絕對，但這并不是本文的范疇，這涉及到很多方面，比如cgroup等。

針對skb的修改，我添加了一個字段，指示它的所屬地(某個網(wǎng)卡？socket池？...)，當(dāng)前所屬地，這些信息可以維護(hù)skb不會被free到kmem_cache，同時也可以最優(yōu)化cache利用率。這部分修改已經(jīng)實現(xiàn)，目前正在針對Intel千兆卡的驅(qū)動做進(jìn)一步修改。關(guān)于DxR Pro的性能，我在用戶態(tài)已經(jīng)經(jīng)過測試，目前還沒有移植到內(nèi)核。

關(guān)于快速查找表的實現(xiàn)，目前的思路是優(yōu)化nf_conntrack，做多級hash查找。

審核編輯：湯梓紅