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是多少，背后的数学其实也不复杂，但并不是本文的重点。