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核心時代，傳統的基於時間復雜度計算分析性能的方式可能已經過時。
