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

3352 软件学报 2025 年第 36 卷第 7 期

意, 基于细粒度锁的布谷鸟过滤器也可以降低不同线程独占某一内存空间的时间, 因此也实现了较高的性能. 但是
由于基于细粒度锁的布谷鸟过滤器每次加锁会产生一次缓存失效, 因此具有较高的加锁开销, 造成不同操作的吞
吐低于本文提出无锁并发布谷鸟过滤器.

SLCF LFCF (ours) SLCF LFCF (ours) SLCF LFCF (ours)
100 GLCF 300 GLCF 200 GLCF
吞吐 (MOPS) 60 OHBBF 吞吐 (MOPS) 200 OHBBF 吞吐 (MOPS) 150
VQF
VQF
80
100
40
100
20
0 0 50 0
14 8 16 32 64 14 8 16 32 64 14 8 16 32 64
线程数 线程数 线程数
(a) 插入操作吞吐 (b) 查询操作吞吐 (c) 删除操作吞吐
图 4 插入、查询和删除操作的吞吐量随线程数量的变化

4.3 评估数据集大小对算法吞吐的影响
本节评估了不同数据集大小对插入、查询和删除操作吞吐的影响. 具体来说, 本节将不同过滤器的容量设置
2 、 2 、 2 、 2 、 2 , 之后使用 64 个线程插入不同数量的元素, 并测量插入过程的吞吐. 之后使用 64 个线
24
23
26
27
25
为
程测量查询操作和删除操作的吞吐. 如图 5 所示, 无锁并发布谷鸟过滤器插入、查询和删除操作的吞吐平均是基
于细粒度锁的布谷鸟过滤器 (SLCF) 插入、查询和删除操作吞吐的 1.37 倍、1.94 倍以及 1.13 倍. 本节的结果表明
无锁并发布谷鸟过滤器针对具有不同数量元素的数据集均具有较高的吞吐.

125 250
SLCF LFCF (ours) 200
100
吞吐 (MOPS) 75 SLCF LFCF (ours) 吞吐 (MOPS) 200 VQF 吞吐 (MOPS) 150 SLCF LFCF (ours)
GLCF
400
OHBBF
GLCF
100
50
VQF
25
0 OHBBF 0 50 0 GLCF
2 23 2 24 2 25 2 26 2 27 2 23 2 24 2 25 2 26 2 27 2 23 2 24 2 25 2 26 2 27
数据集大小 数据集大小 数据集大小
(a) 插入操作吞吐 (b) 查询操作吞吐 (c) 删除操作吞吐
图 5 插入、查询和删除操作的吞吐随数据集中元素数量的变化

相比于其他基于锁的算法, 无锁并发布谷鸟过滤器具有更高的吞吐. 这是因为无锁并发布谷鸟过滤器具有可
以显著降低锁竞争开销. 具体来说, 以基于细粒度锁的布谷鸟过滤器 (SLCF) 为例, 加锁操作占基于细粒度锁的布
谷鸟过滤器 (SLCF) 查询操作总执行时间的 59% 以上. 而无锁并发布谷鸟过滤器可以消除高并发时锁竞争对过滤
器性能的影响. 因此, 无锁并发布谷鸟过滤器可以显著提升吞吐.

4.4 评估工作负载对算法执行时间的影响
本节评估了工作负载对算法执行时间的影响. 具体来说, 本节测量了当插入操作和查询操作的比例分别为 3:1
和 1:3 时, 不同算法执行所有操作所需时间. 表 1 展示了不同算法在 CAIDA、YCSB、Wiki 数据集上的实验结果.
如表 1 所示, 相比于基于细粒度锁的布谷鸟过滤器 (SLCF), 无锁并发布谷鸟过滤器将两种工作负载的平均执行时
间分别缩短了 13.56% 和 32.86%.
之所以能获得如此提升是因为本文提出的两阶段查询算法显著降低了无锁并发布谷鸟过滤器的查询开销. 因
此, 无锁并发布谷鸟过滤的查询操作相比于插入操作具有更大的提升. 继而在查询操作比例较大的工作负载中无
锁并发布谷鸟过滤器具有更高的性能. 注意, 在两类工作负载下, 基于全局锁的布谷鸟过滤器 (GLCF) 的执行时间
随着线程数量的增加而提升. 这是因为基于全局锁的布谷鸟过滤器 (GLCF) 的全局锁机制使得其所有操作只能依