对BSD的新路由查找算法的理解
bsd的路由查找算法我研究过一段时间，当时我们要自己写一个路由查找模块，要扩展性好的，要紧凑的，耦合性低的，于是我就选择了bsd的radix算 法，它不同于linux的哈希表查找算法，linux内核实现了两种查找算法，一个是哈希表算法，一个是LC-trie算法，我感觉linux设计的东西 不是那么紧凑，但绝对是一件艺术品，比较适合有品味的人欣赏和使用，大多数人还是驯服不了它，唉，承认自己的品味低，只好选择radix算法了，这里我绝 对没有贬低它的意思，其实我自己比较欣赏radix的，呵呵。bsd强调的东西和linux不同，在统一性方面不管是windows还是bsd做的都要比 linux好。闲话不扯了。
基于radix树的查找算法中，bsd将一个ip地址分为解成了一个二进制比特串（计算机中它本身就是比特串，我是从读内核的人的角度分析的），然后在一颗二叉radix树中进行查找匹配，树的节点是需要测试的比特位，比如一个树节点的数据是15，那么当这个ip二进制串到达这里时就要测试第15位，如果 15为1，则向右拐，如果为0则向左拐，直到叶子节点，如果这个条目和需要的匹配则就是它了，如果不匹配，则回溯，不断的检查回溯过程中的掩码链表，以期 求得一个更大范围的普适路由。就是这样了，但是我们来看看会出现什么问题。
首先，整棵树是那么的紧凑以至于我们必须将它作为一个整体，linux就好得多了，内核中的路由表以fib_table为顶向下分为了好多层，比如 fn_zone,fib_node，fib_alias,fib_info,fib_nh，这么几层下来每层都是独立的，可灵活维护的，这看起来非常灵活，不需要整个路由表的全局锁，只有在写操作时有一个fib_hash_lock，只要分开的东西就可能被并行计算看到,因此这样会比较好，所有 linux的优点恰恰是bsd的缺点，要访问路由表时要全局加锁，一下子锁住全树，就像linux以前访问文件页高速缓存全局锁一样，这样在现代的多处理器环境下非常不利，于是它变化了。
新的bsd路由查找算法也是分层的，但是它的分层比linux更前进了一步，它不但将算法分层，还将ip地址分层，其实叫分级，把一个ip地址分为相等的 4份，每份8位，每8位每8位的进行匹配，这样只需要锁柱正在计算的8位就可以了，实际上，它将计算给分解了，这非常类似于虚拟地址到物理地址转化时的机 制，页目录负责高10位，页表负责中10位等等，而且恰恰巧的是，它就是这么实现的，本质上，它并没有改变原先的radix的实质，只不过将比较位数扩展 为了8位，以前的比较中，只比较1位非1即0，走形方向非左即右，现在比较8位，就不是非左即右了，而是成了n叉树，具体走哪一叉和原来一样，要看前一级的比较结果，这个算法实际上如果写得好的话，可以在原来的radix基础上扩充，我觉得这个新实现和linux内核的页高速缓存的radix树一样。
基于radix树的查找算法中，bsd将一个ip地址分为解成了一个二进制比特串（计算机中它本身就是比特串，我是从读内核的人的角度分析的），然后在一颗二叉radix树中进行查找匹配，树的节点是需要测试的比特位，比如一个树节点的数据是15，那么当这个ip二进制串到达这里时就要测试第15位，如果 15为1，则向右拐，如果为0则向左拐，直到叶子节点，如果这个条目和需要的匹配则就是它了，如果不匹配，则回溯，不断的检查回溯过程中的掩码链表，以期 求得一个更大范围的普适路由。就是这样了，但是我们来看看会出现什么问题。
首先，整棵树是那么的紧凑以至于我们必须将它作为一个整体，linux就好得多了，内核中的路由表以fib_table为顶向下分为了好多层，比如 fn_zone,fib_node，fib_alias,fib_info,fib_nh，这么几层下来每层都是独立的，可灵活维护的，这看起来非常灵活，不需要整个路由表的全局锁，只有在写操作时有一个fib_hash_lock，只要分开的东西就可能被并行计算看到,因此这样会比较好，所有 linux的优点恰恰是bsd的缺点，要访问路由表时要全局加锁，一下子锁住全树，就像linux以前访问文件页高速缓存全局锁一样，这样在现代的多处理器环境下非常不利，于是它变化了。
新的bsd路由查找算法也是分层的，但是它的分层比linux更前进了一步，它不但将算法分层，还将ip地址分层，其实叫分级，把一个ip地址分为相等的 4份，每份8位，每8位每8位的进行匹配，这样只需要锁柱正在计算的8位就可以了，实际上，它将计算给分解了，这非常类似于虚拟地址到物理地址转化时的机 制，页目录负责高10位，页表负责中10位等等，而且恰恰巧的是，它就是这么实现的，本质上，它并没有改变原先的radix的实质，只不过将比较位数扩展 为了8位，以前的比较中，只比较1位非1即0，走形方向非左即右，现在比较8位，就不是非左即右了，而是成了n叉树，具体走哪一叉和原来一样，要看前一级的比较结果，这个算法实际上如果写得好的话，可以在原来的radix基础上扩充，我觉得这个新实现和linux内核的页高速缓存的radix树一样。
经过这盘更改后效率当然提高了很多，每一级的计算要有8位参与，这个计算量恰好适合现代处理器的超标量以及超线程及多核进行并行处理，速度加快，而且一次 算8位，总的计算次数只有4次，不像以前的32次，每次1位还不够处理器塞牙缝呢，浪费了大量处理器，另外不再需要全局锁了，因为计算就不是全局的。更重 要的是，以前的一次比较1位根本无法利用cpu缓存，比较意味着处理器分支预测，你让处理器那么多次的猜你的心，它会疯的，而现在一次读入8个位，数据都 在缓存里面，随便用，当然比较还是也有分支预测失败，但是数据都在缓存，可以不必理会存储器，而以前的一次1位你根本不知道下面该取什么数据了，现在存储 器的带宽那么高全浪费了，就算你不让他浪费，结果该往左拐的预先取到右节点的数据，全错了，刷新缓存浪费更厉害。
本文转自 dog250 51CTO博客，原文链接:http://blog.51cto.com/dog250/1274168