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

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

无锁并发布谷鸟过滤器将执行时间平均降低了 98.61%. 相比于基于细粒度锁的布谷鸟过滤器 (SLCF), 无锁并发
布谷鸟过滤器将查询吞吐平均提升 16.24 倍.

SLCF
GLCF
100 000 1 500
LFCF (ours) SLCF
执行时间 (ms) 75 000 吞吐 (MOPS) 1 000 GLCF
VQF
50 000
OHBBF
25 000 500 LFCF (ours)
0 0
0 0.5 1.0 1.5 2.0 2.5 3.0 0 0.5 1.0 1.5 2.0 2.5 3.0
偏度系数 偏度系数
(a) 并发写入执行时间 (b) 并发读取吞吐
图 6 执行时间和吞吐随偏度系数的变化

对于基于细粒度锁的布谷鸟过滤器 (SLCF), 随着数据集偏斜程度的增加, 线程间的锁争用加剧, 从而导致性
能下降. 对于基于全局锁的布谷鸟过滤器 (GLCF), 由于任何数据访问均需要获取全局锁, 因此数据偏斜程度的变
化并不会加剧锁争用程度. 反之, 随着数据偏斜程度的提高, 数据访问呈现出更好的局部性特征, 继而造成缓存命
中率提高, 故性能有所提升. 本文提出的无锁并发布谷鸟过滤器可以避免锁争用带来的性能开销, 并可充分利用缓
存局部性特征获得性能提升. 因此, 在并发读写场景下均表现出了最佳的执行时间和吞吐性能.

5 总结与展望

布谷鸟过滤器是一种应用广泛的近似成员资格查询数据结构. 设计并实现支持高并发的布谷鸟过滤器可以显
著提升现有系统吞吐以及数据处理能力, 对提升系统性能意义重大. 本文提出了一个支持无锁并发的布谷鸟过滤
器. 该过滤器通过两阶段查询协议、路径探查与元素迁移分离、基于多机器字比较并交换的原子迁移实现线程安
全的查询、插入和删除操作. 理论分析和实验结果表明, 无锁并发的布谷鸟过滤器显著提升了最新算法的并发性
能. 例如, 无锁并发布谷鸟过滤器的查询吞吐平均为使用细粒度锁的布谷鸟过滤器的查询吞吐的 1.94 倍. 后续工
作将使用无锁并发技术优化更多数据结构的性能 [50,51] . 此外, 还将考虑从存储角度出发, 利用非易失内存等新型存
储硬件特性 [52] , 进一步提升过滤器数据结构性能.

References:
[1] Cohen E. All-distances sketches, revisited: HIP estimators for massive graphs analysis. In: Proc. of the 33rd ACM SIGMOD-SIGACT-
SIGART Symp. on Principles of Database Systems. Snowbird: ACM, 2014. 88–99. [doi: 10.1145/2594538.2594546]
[2] Dai HP, Li M, Liu A. Finding persistent items in distributed datasets. In: Proc. of the 2018 IEEE Conf. on Computer Communications.
Honolulu: IEEE, 2018. 1403–1411. [doi: 10.1109/INFOCOM.2018.8486425]
[3] Mosharraf SIM, Adnan MA. Improving lookup and query execution performance in distributed big data systems using cuckoo filter.
Journal of Big Data, 2022, 9(1): 12. [doi: 10.1186/S40537-022-00563-W]
[4] Vora AV, Hegde S. Keyword-based private searching on cloud data along with keyword association and dissociation using cuckoo filter.
Int’l Journal of Information Security, 2019, 18(3): 305–319. [doi: 10.1007/s10207-018-0418-0]
[5] Zhao YK, Dai WC, Wang SR, Xi L, Wang SQ, Zhang F. A review of cuckoo filters for privacy protection and their applications.
Electronics, 2023, 12(13): 2809. [doi: 10.3390/ELECTRONICS12132809]
[6] Morales D, Agudo I, Lopez J. Private set intersection: A systematic literature review. Computer Science Review, 2023, 49: 100567. [doi:
10.1016/j.cosrev.2023.100567]
[7] Kumar M, Singh A. Probabilistic data structures in smart city: Survey, applications, challenges, and research directions. Journal of
Ambient Intelligence and Smart Environments, 2022, 14(4): 229–284. [doi: 10.3233/AIS-220101]