HiPAC高性能规则匹配算法之查找过程

如果一个match落在了区间5，那么它到底匹配哪个Rule呢？在区间5从下到上贯穿一条线，首先穿透的是Rule1，因为它的优先级最高，所以便匹配Rule1；如果一个match落在了区间2呢，从下到上最先贯穿Rule3，因此它便匹配Rule3；如果一个match落在了区间1，那么由于只贯穿了Rule5，因此就匹配Rule5；如果落在了区间10，很抱歉，没有任何一条Rule被贯穿，说明没有任何规则被匹配！

       基本就是这样的！那么可能你会问，如果有多个match怎么办？比如下面的规则，我当然以我们最熟悉的iptables举例，虽然我要将HiPAC移植到iptables还需要几个周末：

iptables -A FORWARD -s $ip1 -d $ip2 -p udp -j DROP

在这个规则里，我一共展示了3个match，分别是ip1，ip2，udp，因此就需要3个上面的图吗？是的！这就是所谓的多维HiPAC匹配，只是个词汇罢了，我不喜欢引申定义。由于第一张图在某些区间已经排除了若干Rule，因此后面的图中很多的Rule便不用画出来了。

       为了展示一下整理的查找过程，我画了一个相对简单的图，一共3个match，具体的匹配过程都在图里面，就不再用文字细说了：

关于HiPAC算法要说的是优先级匹配是关键，如果还需要继续匹配match，我们说就是延展了一个维度，查找顺着树继续向下，如果不需要继续匹配match了，那么就在当前区间从下向上贯穿一条线，首先碰触到的Rule就是匹配的规则。在上图中有很多的Rule都被画成了虚线，这是因为该条Rule在上一个层次或者说维度已经被排除了，因此画贯穿线时应该忽略掉虚线。

       如果理解了这个过程，就会发现它是超级高效的，无须回溯，无须依赖复杂的hash算法，无须依赖hash散列的程度，和输入数据无关，多少个匹配就有多少层，至于如何来维护这个算法，那就是实现问题了。本质上这还是一个树型数据结构，巧妙点在于其结构。

       本文仅仅给出了一个概览，至于HiPAC算法的插入，删除，查找，背后有很复杂的数学原理，作为工程技术人员，理解这些数学是必要的，虽然关于HiPAC的HOWTO不多，但是相关论文还是不少的。

       就为了回复一封邮件，又写了一篇文章，老婆和丈母娘在看《红高粱》的大结局，小小在玩iPad，我在餐桌上画那个复杂的图，这就是不喝酒的好处，否则此时我估计又在梦里云游了....白天忙了一天，对于论坛以及远方朋友的相求，我还是必应的，就当是学习了。不过，我还是希望晚上到家不再动任何技术问题，起初强制自己晚上不再喝酒不是为了搞网络技术的，也不是为了写代码的，而是想给自己充下电，充实一下自己的，看点历史，洗涤一下心灵，比如还可以学学烹饪，装潢设计之类的。