昨天和朋友聊到 “如何匹配一個 port range”，覺得挺有意思，簡單寫篇散文。

回想起十多年前，我移植并優化了 nf-HiPAC，當時還看不上 ipset hash，后來大約七八年前，我又舔 nftables，因為用它可直接寫多維樹匹配，更早之前，Linux 內核 Hash 路由查找算法被 trie 替代時，我就寫文捧過一番，我是有多么看不上 Hash，似乎任何一棵 Tree 都吊打 hash。

多年以后反思，如果再讓我做同樣的需求，我定會 Hash 做到底，不會再動 Tree 的主意。Hash 實現最簡單，并可隨內存線性擴展，在大多數場景下也不會比 Tree 差，只有純理工科背景且未被工程教訓毒打過的副經理才會拎出 Tree 更好的例外作為替換 Hash 的理由。

匹配 port range，想當然的算法是構建區間查找樹，當年看 Linux 內核 mmap 實現時看到過 Linux 文件映射就是用區間樹實現，所以但凡和區間關聯的，我都會去安利區間樹，也因此當年優化 nf-HiPAC 時也就是選定了它，但在實現過程中遇到了極大的困難，于是我就偷了個懶。

有意思的是，這個偷懶很值得。

我沒有用實際 rule 中的 port range 直接構建區間樹，而將整個 port 空間分為一致 500 個端口一組的等距區間，然后將實際 rule 的 port range 往上蓋，在等距邊界處做 split。比如 rule 的 range 1234~1400，則 1000~1500 等距區間就被分為了 3 部分，這 3 部分作為匹配 1000~1500 后的二級匹配，執行一個線性遍歷就完了。

我當時非常看不起線性遍歷，所以一直耿耿于懷，我當時不知道，幾十以內的線性遍歷其實是無傷遍歷，更何況個位數。巧的是我當時能力不足以讓我繼續優化成 Tree，就保留了 “二分等距區間查找 + 線性遍歷” 的 “拙劣” 實現，沒想到它工作得非常好。

回想起來，這種等距區間分割，讓規則中的 port range 適配它的做法，依然屬于橫豎顛倒，撥云見日。我對這種方法論的掌握已經深入了內心，下意識而為之。

現如今，我連等距區間樹也要扔掉，用 hash 替代等距區間樹，就是另一個新的算法：

Hash 相比樹的缺點在于要遍歷沖突鏈表，比如 Linux 內核里的 hlist。假設 hash 算法足夠優秀(沒得說，都不差)，hlist 中元素的個數是可隨著內存增加減小的，而樹的操作無論多好的 CPU 始終是 log 級。

雖然 Hash 要額外處理沖突，但樹也不是一步到位的，加上樹的平衡，鎖等復雜操作，在通用軟件場景下，其性價比遠小于 Hash。假設 50000 并發，2000 個 hash bucket，平均只需要遍歷 25 次，而采用二叉樹需要 15 次操作，但算上其插入，平衡操作，是要比 hash 更昂貴的。二叉樹只在更大并發時才凸顯優勢，其操作量隨數據量 log 增長，而線性增長的 hash 操作亦可通過增加內存抵消操作數量。但如若真遇到海量并發，通用軟件本身就成了瓶頸。

確保下面的區域：

顯然，x 會隨內存增加向右線性延展，，而 log 曲線 $y=\alpha ?{\log }_{2}x$ 則會因 CPU 性能提升而下壓。純算法分析，log 下壓更明顯，但純算法分析，Hash 簡直就是 O(1)，所以二者并非簡單的時間空間較勁二選一，而是呼吁架構的改變。

其實說白了就是 Hash 簡單易實現沒 bug，特別是頻繁增刪查的場景，一個反面案例來自 David Miller 對 IPv6 路由查找的 “優化”，惹了不少麻煩(詳見 3.10 內核中 IPv6 的缺陷)，要是用 Hash 實現，不可能有這事。

說點形而上。

Hash 和 Tree 實際上代表了計算在空間和時間分別展開的兩個方向，Hash 的 O(1) 約束下，1 倍的規模增量可帶來1 次操作增量，需要 1 倍的內存來抵消這 1 次的操作以維持 O(1)，操作時間不變，對于二叉樹，1 倍的規模增量同樣帶來 1 次操作增量(每增加 1 層，葉子節點數量增加 1 倍)，但這次操作無法抵消，時間永遠隨規模增加而單調遞增，然而由于二叉樹在操作過程中天然保序，就意味著其不真需要額外預留 1 倍空間以支撐規模。

時間不可壓縮，但空間可壓縮，這是時空的本質不同，接受一個隨規模遞增得慢的時間，去壓縮空間，這是所有機器的實現方式。背后是一個選擇問題，我們是選擇在時間中等待，去壓縮空間，還是選擇線性擴展空間，只為不等待，還是那個 “矩” 的長寬權衡。

直白說，空間不可無限擴展，我們傾向于壓縮它，我們設計的機器也是，而時間總是流逝不可壓縮，我們傾向于高效利用它，我們設計的機器也是。物件越來越多時，我們傾向于將它們分類疊放以便查找而不是在更大的空間平攤以便一眼瞅，空間的擴張總有極限，而時間卻無限延展。空間是共享的，我們的一生時間卻是私人的。

但我們還是希望有套稍微大一點哪怕極簡的房子，在多數場景，它比緊湊的裝修和儲物分類更簡單，更令人舒適，這還不夠的話，就看看我們智人的歷史，看看我們作為自己是如何學會 “集約(字面意思)” 的，我們的所謂文明，就是這種方式，所以我們設計的機器也是這種方式，但在大多數時間，我們卻是用相反的方式：

首先要地盤，其次不要太大，這就是選擇 hash 的理由。

浙江溫州皮鞋濕，下雨進水不會胖。