Page 430 - 《软件学报》2025年第7期

王瀚橙 等: 无锁并发布谷鸟过滤器 3351

要求. 因此无锁并发布谷鸟过滤器为无锁过滤器.

4 实验评估

本节首先介绍实验设置, 包括实验平台、对比算法、评估指标、数据集和参数设置. 之后本节从以下 4 个方
面评估无锁并发布谷鸟过滤器的性能: (1) 评估线程数对算法吞吐的影响, 本节通过分别测量插入、查询和删除操
作的吞吐随线程数量的变化实现这一目的; (2) 评估数据集大小对算法吞吐的影响, 本节通过测量插入、查询和删
除操作的吞吐随数据集大小的变化实现这一目的; (3) 评估工作负载对算法执行时间的影响, 本节通过测量不同线
程数量下执行时间随工作负载的变化实现这一目的; (4) 评估数据偏斜对算法执行时间和吞吐的影响, 本节通过分
别在并发写入和读取场景下测量执行时间和吞吐随数据偏度的变化实现这一目的.

4.1 实验设置
实验平台: 本文使用一台配备了两颗 20 核 40 线程的 Intel Xeon Gold 5218R CPU 以及 64 GB 内存的标准服
务器评估了不同算法的性能. 本文使用 C++17 实现无锁并发布谷鸟过滤器, 并将其开源 (https://github.com/wang
hanchengchn/lock-free-concurrent-cuckoo-filter). 所有实验均使用 GCC 8.5.0 编译器编译并运行在 CentOS Linux
release 8.2.2004 操作系统上. 此外, 编译器的优化等级为 O3.
对比算法: 本文使用 4 个最新的并发算法和无锁并发布谷鸟过滤器进行对比. 上述 4 个最新的对比算法分别
为: 向量商过滤器 (VQF) [32] 、单哈希块布隆过滤器 (OHBBF) [45] 、基于细粒度锁的布谷鸟过滤器 (SLCF) [17] 和基于
全局锁的布谷鸟过滤器 (GLCF) [17] .
评估指标: 本文在 3 个指标上评估了无锁并发布谷鸟过滤器的性能. (1) 吞吐量. 本文将其定义为单位时间可
以成功执行的操作数量, 单位为百万次操作每秒 (MOPS). (2) 执行时间. 本文将其定义为执行一组操作所需的时
间, 其中不同类别的操作数量按照比例设定, 例如插入操作数量:查询操作数量=3:1. 单位为毫秒 (ms). (3) 最大负
载因子. 本文将其定义为指定过滤器的容量后, 对一个未插入任何元素的过滤器不断插入元素, 直到各线程均返回
插入失败时, 实际插入的元素数量占过滤器容量的比例.
数据集: 本文在 4 个数据集上评估了算法的性能. (1) 模拟数据集. 本文随机生成了 5 个具有不同元素数量的
24
23
25
27
26
数据集, 每个数据集中的元素数量分别为 2 、 2 、 2 、 2 、 2 . 本文将具有 2 26 个不同元素数量的数据集作为
默认数据集. (2) CAIDA 数据集 [46] . CAIDA 数据集是一个收集自骨干网络流量的真实数据集. 本文使用的数据集
中具有 483 481 个不同的元素. (3) YCSB 数据集 [47] . 该数据集包含了使用 YCSB 生成器生成的 2 千万个不同的元
素. (4) Wiki 数据集 [48] . 该数据集是维基百科编辑提交的时间戳, 具有 90 437 011 个不同的元素.
参数设置: 为了公平地比较不同算法的吞吐, 本文的参数设置需要保证不同 AMQ 数据结构的内存空间消耗、
误报率相同. 在保证上述要求的前提下, 本文依照算法的默认参数设置设定了不同算法的参数. 所有算法的参数设
置也已开源 (https://github.com/wanghanchengchn/lock-free-concurrent-cuckoo-filter).

4.2 评估线程数对算法吞吐的影响
本节评估了不同过滤器的插入、查询和删除操作的吞吐随线程数量的变化. 具体来说, 本节将不同过滤器的
2 . 之后使用不同数量的线程向不同过滤器中插入其容量 90% 数量的元素, 并测量插入过程中的吞
26
容量设置为
吐. 此外, 本节还测量了使用不同数量的线程执行查询和删除操作的吞吐. 需要注意, 在插入过程中, 所有的过滤器
均可填充到其容量的 90% 以上 (即所有过滤器的最大负载因子均可到达 90% 以上). 如图 4 所示, 无锁并发布谷鸟
过滤器插入、查询和删除操作的吞吐平均是基于细粒度锁的布谷鸟过滤器 (SLCF) 插入、查询和删除操作吞吐
的 1.15 倍、1.65 倍以及 1.21 倍. 并且当线程数量小于 32 时, 无锁并发布谷鸟过滤器实现了几乎线性的并发扩展
性. 由于本文使用的机器每颗 CPU 只有 20 核 40 线程, 因此当线程数为 64 时, 由于跨 CPU 访问数据的问题, 并发
可扩展性略微受到影响, 但依然展现出了亚线性的并发扩展性.
无锁并发布谷鸟过滤器之所以能实现上述亚线性扩展性能, 是因为本文提出的路径探查与元素迁移分离技术
可让原子操作更快地完成. 这一设计降低了不同线程独占某一内存空间的时间, 继而提升了并发可扩展性. 需要注