Hash 的工程优势: port range 匹配

昨天和朋友聊到 “如何匹配一个 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 \cdot {\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 的理由。

浙江温州皮鞋湿，下雨进水不会胖。