線速問題

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

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

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

我們回到轉發設備。對于交換機和路由器而言，衡量標準是不同的。

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

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

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

然后，在第二天，我就開始整理這個令人悲傷最終心碎的Linux轉發優化方案。

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

問題綜述

Linux內核協議棧作為一種軟路由運行時，和其它通用操作系統自帶的協議棧相比，其效率并非如下文所說的那樣非常低。然而基于工業路由器的評判標準，確實是低了。

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

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

瓶頸分析概述

1.DMA和內存操作

我們考慮一下一個數據包轉發流程中需要的內存操作，暫時不考慮DMA。

*)數據包從網卡拷貝到內存

*)CPU訪問內存讀取數據包元數據

*)三層報頭修改，如TTL

*)轉發到二層后封裝MAC頭

*)數據包從內存拷貝到輸出網卡

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

1.1.Linux作為服務器時

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

1.2.Linux作為轉發設備時

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

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

2.網卡對數據包隊列Buff管理

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

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

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

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

如果沒有一個好的轉發表，那么Linux協議棧在海量路由存在時對于線速能力就是一個瓶頸，這是一個可擴展性問題。

另外，很多的查詢結果都是可以被在一個地方緩存的，但是Linux協議棧沒有這種緩存。比如，路由查詢結果就是下一跳，而下一跳和輸出網卡關聯，而輸出網卡又和下一跳的MAC地址以及將要封裝的源MAC地址關聯，這些本應該被緩存在一個表項，即轉發表項內，然而Linux協議棧沒有這么做。

4.不合理的鎖

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

你只需要保證內核本身不會崩掉即可，至于說IP轉發的錯誤，不管也罷，按照IP協議，它本身就是一個盡力而為的協議。

5.中斷與軟中斷調度

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

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

6.通用操作系統內核協議棧的通病

作為一個通用操作系統內核，Linux內核并非僅僅處理網絡數據，它還有很多別的子系統，比如各種文件系統，各種IPC等，它能做的只是可用，簡單，易擴展。

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

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

綜述：Linux轉發效率受到以下幾大因素影響

IO/輸入輸出的隊列管理/內存修改拷貝 （重新設計類似crossbar的隊列管理實現DMA ring交換）

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

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

中斷以及軟中斷調度

Linux轉發性能提升方案

概述

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

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

2.重新設計的基于定位而非最長前綴查找的轉發表

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

4.數據結構無鎖化（基于線程局部數據結構）

5.實現方式

5.1.驅動以及內核協議棧修改

5.2.完全的用戶態協議棧

5.3.評估：用戶態協議棧靈活，但是在某些平臺要處理空間切換導致的cache/tlb/mmu表的flush問題

內核協議棧方案

優化框架

0.例行優化

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

[ 可以參見《Effective Gigabit Ethernet Adapters-Intel千兆網卡8257X性能調優》]

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

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

4).如果不準備優化Netfilter，編譯內核時禁用Netfilter，節省指令

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

6).開啟網卡的硬件卸載開關（如果有的話）

7).最小化用戶態進程的數量，降低其優先級

8).原生網絡協議棧優化

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

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

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

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

宗旨：

原生協議棧的最優化方案

1.優化I/O，DMA，減少內存管理操作

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

[ Tips：16 lines 8 bits PCI-E總線拓撲(非crossbar！)的網絡線速不到滿載60% pps]

2).減少爭搶式DMA，減少鎖總線[Tips：優化指令LOCK，最好采用RISC，方可調高內核HZ]

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

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

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

宗旨：

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

2.優化中斷分發

1).增加長路徑支持，減少進程切換導致的TLB以及Cache刷新

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

3).犧牲用戶態進程的調度機會，全部精力集中于內核協議棧的處理，多CPU多路并行的

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

4).中斷處理線程化，內核線程化，多核心并行執行長路經，避免切換抖動

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

宗旨：

減少cache刷新和tlb刷新

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

3.優化路由查找算法

1).分離路由表和轉發表，路由表和轉發表同步采用RCU機制

2).盡量采用線程局部數據

每個線程一張轉發表（由路由表生成，OpenVPN多線程采用，但失敗），采用定位而非最長前綴查找（DxR或者我設計的那個）。若不采用為每個線程復制一份轉發表，則需要重新設計RW鎖或者使用RCU機制。

3).采用hash/trie方式以及DxR或者我設計的DxRPro定位結構

宗旨：

采用定位而非查找結構

采用局部表，避免鎖操作

4.優化lock

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

2).臨界區和內核線程關聯，不禁中斷，不禁搶占（其實內核編譯時搶占已經關閉了）

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

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

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

宗旨：鎖的粒度與且僅與臨界區資源關聯，粒度最小化

優化細節概覽

1.DMA與輸入輸出隊列優化

1.1.問題出在哪兒

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

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

我們以Intel千兆網卡驅動e1000e來說明上述的問題。順便說一句，Intel千兆驅動亦如此，其它的就更別說了，其根源在于通用的網卡驅動和協議棧設計并不是針對轉發優化的。

初始化：

創建RX ring：RXbuffinfo[MAX]

創建TX ring：TXbuffinfo[MAX]

RX過程：

i = 當前RX ring游歷到的位置;

while(RXbuffinfo中有可用skb) {

skb = RXbufferinfo[i].skb;

RXbuffinfo[i].skb = NULL;

i++;

DMA_unmap(RXbufferinfo[i].DMA);

[Tips：至此，skb已經和驅動脫離，完全交給了Linux協議棧]

[Tips：至此，skb內存已經不再由RX ring維護，Linux協議棧拽走了skb這塊內存]

OS_receive_skb(skb);

[Tips：由Linux協議棧負責釋放skb，調用kfree_skb之類的接口]

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

alloc_new_skb_from_kmem_cache_to_RXring_RXbufferinfo_0_to_MAX_if_possible;

[Tips：從Linux核心內存中再次分配skb]

}

}

TX過程：

skb = 來自Linux協議棧dev_hard_xmit接口的數據包;

i = TX ring中可用的位置

TXbufferinfo[i].skb = skb;

DMA_map(TXbufferinfo[i].DMA);

while(TXbufferinfo中有可用的skb) {

DMA_transmit_skb(TXbufferinfo[i]);

}

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

i = 傳輸完成的TXbufferinfo索引

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

skb = TXbufferinfo[i];

DMA_unmap(TXbufferinfo[i].DMA);

kfree(skb);

i++;

}

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

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

1.2.構建新的DMA ring buffer管理設施-VOQ，建立輸入/輸出網卡之間隊列的關聯。

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

如果類比高端路由器的crossbar交換陣列結構以及真實的VOQ實現，你會發現，在邏輯上，每一對可能的輸入/輸出網卡之間維護一條數據轉發通路是避免隊頭阻塞以及競爭的好方法。這樣排隊操作只會影響單獨的網卡，不需要再全局加鎖。在軟件實現上，我們同樣可以做到這個。你要明白，Linux的網卡驅動維護的隊列信息被內核協議棧給割裂，從此，輸入/輸出網卡之間彼此失聯，導致最優的二分圖算法無法實施。

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

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

最后，給出我的數據包隊列管理VOQ的設計方案草圖。

在我的這個針對Linux協議棧的VOQ設計中，VOQ總要要配合良好的輸出調度算法，才能發揮出最佳的性能。

2.分離路由表和轉發表以及建立查找操作之間的關聯

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

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

至于說查找操作之間的關聯，這也是一個深度優化，底層構建高速查詢流表實現協議棧短路（流表可參照conntrack設計），這個優化思想直接參照了Netfilter的conntrack以及SDN流表的設計。雖然IP網絡是一個無狀態網絡，中間路由器的轉發策略也應該是一個無狀態的轉發。然而這是形而上意義上的理念。如果談到深度優化，就不得不犧牲一點純潔性。

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

*流表緩存路由項

*流表緩存neighbour

*流表緩存NAT

*流表緩存ACL規則

*流表緩存二層頭信息

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

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

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

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

3.路由Cache優化

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

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

[ 利用互聯網訪問的時間局部性以及空間局部性（需要利用計數統計）]

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

*)預制常用IP地址到路由cache，實現一步定位

[ 所謂常用IP需要根據計數統計更新，也可以靜態設置]

4.Softirq在不支持RSS多隊列網卡時的NAPI調度優化

*)將設備按照協議頭hash值均勻放在不同CPU，遠程喚醒softirq，模擬RSS軟實現

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

1.所有的rx softirq內核線程組成一個數組

struct task_struct rx_irq_handler[NR_CPUS];

2.所有的poll list組成一個數組

struct list_head polll[NR_CPUS];

3.引入一把保護上述數據的自旋鎖

spinlock_t rx_handler_lock;

4.修改NAPI的調度邏輯

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親和的結合，如果連DMA都不支持，那還優化個毛]

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

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

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

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

5.Linux調度器相關的修改

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

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

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

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

setbit(outcart, incard);

//只要有skb排隊，則將與輸出網卡關聯的輸出線程的虛擬時間減去一個值，該值由數據包長度與常量歸一化計算所得。

outcard_tx_task_dec_vruntime(outcard, skb->len);

對Linux CFS調度不熟悉的，可以自行google。事實上，一旦某個輸出網卡的輸出task開始運行，它也是按照這種基于虛擬時間流逝的CFS方式來調度數據包的，即摘下一個最值得發送的數據包隊列描述符放入TX ring。

最后有一個思考，如果不采用CFS而采用RT調度類是不是更好？單獨網卡輸出的實時性和多塊網卡輸出之間的公平性如何權衡？另外，采用RT調度類就一定帶有實時性嗎？

6.內置包分類和包過濾的情況

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

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

本節不多談，建議如下：

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

[Hipac算法類似于一種針對規則的預處理，將matches進行了拆分，采用多維區間匹配算法]

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

7.作為容器的skb

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

其實還有更加高效的做法，那就是卡車將貨物運輸到另一個港口或者運輸到陸地目的地后，不必空車返回，而是直接排入目的港口或者目的地的出港隊列，等待運輸貨物滿載返回所屬的港口。但是對于Linux而言，由于需要路由查找后才知道卡車返回哪里，因此在出發的時候，卡車并不能確定它一定會返回它所屬的港口...因此需要對包管理隊列做一定的修正，即解除網卡的RX ring和skb的永久綁定關系。為了統一起見，新的設計將路由到本機的數據包也作為轉發處理，只是輸出網卡變成了一個BSD socket，新的設計如下圖所示：

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

用戶態協議棧方案

1.爭議

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

2.爭議解決方案

可以采用Intel I/OAT的DCA技術，避免上下文切換導致的cache抖動

3.采用PF_RING的方式

修改驅動，直接與DMA buffer ring關聯（參見內核方案的DMA優化）。

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

并行流水線處理每一層，流水級數為同時處理的包的數量，CPU核心數+2，流水數量為處理模塊的數量。

[ 流水線倒立]

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

穩定性

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

在多網卡DMA情況下，對于通過的基于PCI-E的設備而言，總線上的群毆是很激烈的，這是總線這種拓撲結構所決定的，和總線類型無關，再考慮到系統總線和多CPU核心，這種群毆會更加激烈，因為CPU們也會參與進來。群毆的時候，打翻桌椅而不是扳倒對方是很常有的事，只要考慮一下這種情況，我就想為三年前我與客戶的一次爭吵而向他道歉。

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

VOQ設計后良好的副作用-QoS

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

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

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

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

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

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

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

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

總線拓撲和Crossbar

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

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

但是對于通用系統架構，一般都是采用PCI-E總線連接各個網卡，這是一種典型的總線結構，根本就沒有所謂的交換網絡。因此所謂的仲裁就是總線仲裁，這并不是我關注的重點，誰讓我手上只有一個通用架構的設備呢？！我的優化不包括總線仲裁器的設計，因為我不懂這個。

因此，對于通用架構總線拓撲的Linux協議棧轉發優化而言，虛擬輸出隊列VOQ關聯在輸入網卡還是輸出網卡，影響不會太大。但是考慮到連續內存訪問帶來的局部性優化，我還是傾向將VOQ關聯到輸出網卡。如果VOQ關聯到輸入網卡，那么在進行輸出調度的時候，輸出網卡的輸出線程就要從輸出位圖指示的每一個待發送數據的輸入網卡VOQ中與自己關聯的隊列調度數據包，無疑，這些隊列在內存中是不連續的，如果關聯到輸出網卡，對于每一個輸出網卡而言，VOQ是連續的。如下圖所示：

實現相關

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

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

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

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

關于快速查找表的實現，目前的思路是優化nf_conntrack，做多級hash查找。

審核編輯：湯梓紅