歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

Linux協議棧查找算法優化隨想

Linux的網絡協議棧實現可謂精確卻不失精巧,不必說Netfilter,單單說TC就夠了,但是有幾處硬傷,本文做一個不完備的記錄,就當是隨筆,不必當真。

0.查找的種類

Linux協議棧作為一個純軟件實現,保留了硬件接口,但是本文不涉及硬件。

在Linux的協議棧實現中,由於沒有硬件電路的固化,查找算法是難免的,比如路由查找,鄰居查找,conntrack查找,socket查找,不一而足。事實上,協議棧作為一個公共組織,為所有的數據包服務,如果一個數據包到達協議棧,處理邏輯必須幫它找到和它相關的數據結構,因此查找是必然的,即使在硬件中,也是這樣。但是查找分為兩種類型,這兩種類型的查找對性能的影響是不一致的。

0.1.查不到不創建

像路由查找這類,如果查找不到路由項,那麼就直接返回失敗,數據包就此丟棄。對於這類查找,表項的創建和刪除是特定事件(比如人為配置,網卡up/down等)觸發的,不是自動的。查找結果的成功與失敗所消耗的性能是一致的,所不同的協議棧對待成功與失敗的方式不同,因此本文不關注這類查找。

0.2.查不到即創建

像conntrack查找,鄰居查找這類,如果查找失敗,將會建立一個新的表項,因此查找結果的成功與失敗對性能的影響是完全不對稱的。如果查找失敗,性能損耗是巨大的,即使對於高效的hash算法,起碼你要遍歷完特定hash值指定的沖突鏈表才能發現失敗,這在平均看來已經是一筆很大的開銷了,然後發現失敗,這才是一個開始,接下來要分配內存,創建表項,這又是一筆很大的花費,既消耗了時間又消耗了空間。雖然空間損耗不可避免,但是我希望在必須分配內存創建表項之前,用最快的速度發現查找失敗。

0.3.介於0.1與0.2的查找

TCP socket查找介於0.1和0.2之間,對於Listen狀態socket的查找,它的目標是創建一個客戶socket,但是首先它要確保特定的TCP四元組不在ESTABLISHED狀態或者TW狀態的socket中被找到,如果存在大量的TW套接字,將會消耗大量的時間來證明“這麼多TW socket中沒有一個匹配它”。如果能快速說明這一點該多好啊。

而對於連Listen套接字都不匹配的元組,將會直接報告查找失敗。

接下來我將不那麼詳細分析幾種Linux內核協議棧中的查找方法。

2.nf_conntrack查找

Linux nf_conntrack優化的空間很大很大,測試表明,加入conntrack的內核協議棧在滿載情況下PPS(Packet Per Second)會下降一半,長連接最大連接數下降一半。對於短連接,即使將各個timeout時間設置很短,性能下降也很明顯。

新建conntrack表項的速度限制了新建連接的速度,而conntrack所能占用的內存大小以及一個conntrack表項持續的時間限制了最大的連接數量。在同時保持大量conntrack表項的情況下,如果HASHSIZE不夠大,那麼hash沖突鏈表將會很長,新建連接,即NEW conntrack的創建將會極其損耗資源,因為它必須在經過極大消耗後才會發現查找失敗,接下來才是干正事。如果在創建之前,快速發現查找失敗,將是一件好事。

3.路由cache查找

對於類似cache的查找,也是同樣的,比如路由cache的查找,我們知道,路由cache有一個過期時間,如果一台路由器的過境流量過多,將會有大量的路由項被cache,查找cache本身就是一筆很大的開銷,hash沖突的可能性很大,費了這麼大的勁還沒有查到,不得不進入slow路徑,簡直氣死人!

事實上,在存在大量過境流量時,路由cache的查找開銷將遠遠大於正規路由表查找的slow路徑開銷,也許正是因為這樣,Linux終於還是取消了路由cache。

4.ipset查找

對於ipset中的表項查找也類似,今天在醫院給小小看病的間隙,突然發現6.23版本的ipset擁有了timeout參數,支持了超時時間本身能做很多事,邏輯處理自動化了不少,但是協議棧並不知道一個表項是否已經因為過期而被刪除,個人覺得,像ipset查找這類,即使不攜帶timeout參數,如果能快速確定“不在set”中也是很好的,當然不能明確確定“不在set中”的時候,再進行特定數據結構的查找,比如hash,tree查找。

5.Bloom過濾器

在上文中,我最終都表達了一種渴望,那就是盡快發現查找失敗,這樣就可以直接去干正事,而不必將時間花在一件必然失敗的事上,這代價也許對於OpenWRT這樣的煙囪垃圾能付得起,但是對於登上大雅之堂的Linux而言,絕對付不起。當然,幾乎所有的操作系統實現的協議棧,都和Linux一樣。

如何能快速發現查找失敗,這是一個根本問題,但是再抽象一點,那就是如何確定“一個元素一定不在一個集合中”。這件事有一個專門的理論去處理,那就是Bloom過濾器,它事實上在時間復雜度和空間復雜度上的效率都很高,但是天下沒有免費的午餐,代價是什麼?代價就是可能誤判!雖然可能誤判,但是這個算法還是可以確定一些事實的,如果它對每一個判斷的回答都是”可能“,那麼它就是不可用的,我們總是希望確定一些事實,100%地確定一些事實!為了更好的說明,我將其寫成一個函數r=B(x),如果返回0,那麼就說明x不在集合中,如果返回1,那麼就說明一個”可能“的事實,即x有y%的可能性不在集合中,具體y是多少,背後的數學其實也不復雜,但並不是本文的重點。

正規的hash表是用一個hash算法將搜索范圍縮小,然後在沖突鏈表中進行精確匹配,因此結果無疑是確定的。然而Bloom過濾算法並不維護沖突鏈表,它只是逐步用多個不同的hash算法將搜索范圍一步步縮小,即使這個范圍再小,也還是有沖突的可能,而這種可能就是誤判。Bloom過濾算法在數據結構上設計地十分精巧,如果使用N個hash算法,那麼只需維護一個N位的位圖,為集合添加一個元素的時候,為該元素應用每一個hash算法計算N個范圍從0到N-1的hash值Si,並在位圖中置位Si為1。現在判斷元素x是否在集合中,為x計算N個hash值Xi,將位圖上位於Xi上的所有值做與運算,結果為0的話,說明元素x一定不在集合中,如果它在的話,一定在添加的時候會將所有相關位設置為1。

6.應用Bloom過濾器

我在上述2-5小節所描述的查找算法開始之前部署一個Bloom過濾器,是不是更好呢?如果這個Bloom算法設計地足夠好,對於大多數情況,如果返回0,我就可以直接跳到創建操作的邏輯,省去了大量的遍歷時間。如果返回1,那麼仍然需要進行精確匹配,這相當於在我本來就覺得不好的算法基礎上又平添了一個Bloom過濾,情形惡化了。但是這就是代價!這就是冒險!我可以將責任推到”這個Bloom算法設計地不夠好“!另一方面,需要權衡計算N個hash的開銷和計算1個hash加上遍歷的開銷哪個大,此時不應該簡單分析時間復雜度,因為對於Bloom,如果N確定了,那麼時間復雜度無疑是O(1),難道一定比hash表的效率更好嗎?事實上我們應該取加權統計值,而這個值依賴於嚴格的性能壓力測試。

還是那句話,沒有免費的午餐,要麼使用硬件加速,此時你花費的是錢,要麼設計一個良好的算法,此時你付出的冒險以及算法失敗後的補償!

7.分級hash查找

像MMU中的頁表查找思想一樣,也和BSD中的路由查找算法的思想一樣,采用多層hash查找而不是單一hash加沖突鏈表遍歷。

我以conntrack查找為例,我可以將conntrack簡化為一個{IP1,IP2}對,第一個元素為鍵,第二個為值,這樣就可以將conntrack的查找做成BSD系統的路由查找的樣子,其中IP2可以被看成下一跳。或者別的......

我並不是說多級的hash算法要比單獨的hash算法更高效,而是說多級的hash表可以在多個CPU核心分別計算,多級hash表可以將每一個hash計算視為一個維度,每一個CPU核心計算一個維度的hash值,定位該維度的坐標,反觀單一hash表就不能利用多CPU核心優勢,你必須先計算好hash值才能定位hash桶從而遍歷沖突鏈表。在多CPU核心時代,傳統的基於時間復雜度計算分析性能的方式可能已經過時。

Copyright © Linux教程網 All Rights Reserved