Cuckoo++哈希表：面向网络应用的高性能哈希表

下载PDF摘要：哈希表是许多网络应用程序(例如，连接跟踪、防火墙、网络地址翻译器)的基本数据结构。其中，布谷鸟散列表通过允许使用非常少的内存访问(2到3次每查找)来处理查找，从而提供了出色的性能。然而，对于大型表，布谷鸟散列表仍然受内存限制，并且每次内存访问都会影响性能。在本文中，我们提出了对杜鹃哈希表的算法改进，允许消除一些不必要的内存访问，这些修改是在不改变原有杜鹃哈希表的性质的情况下进行的，因此所有现有的理论分析仍然适用。在单核上，我们的哈希表实现了每秒3700万次正向查找(即，当表中存在查找的关键字时)，每秒6000万次负向查找，比DPDK中包含的实现提高了50%。在以正向查找为主的18核上，我们的实现实现了每秒496M次查找，比DPDK提高了45%。