用于联盟链的布隆过滤器优化

doi:10.3969/j.issn.0255-8297.2022.04.006

摘要/Abstract

摘要： 布隆过滤器常用于联盟链Hyperledger Fabric状态数据库LevelDB的读性能优化，但布隆过滤器本身存在误报现象，且LevelDB只能对布隆过滤器进行统一配置而无法自适应调整。为此，提出一种单元化的部分计数式布隆过滤器（partial counting Bloom filter,PCBF）构造方案，设计可并行计算的元素插入与查询机制并结合双重哈希及非加密哈希来实现快速插入与查询；基于开启过滤器单元与访问次数构建排序字符串表优先级，使用时间片轮询算法对过滤器单元进行自适应调整，实现了资源的合理分配。实验结果表明： PCBF具有较高的插入效率，并能减少20%左右的误报数量，适用于联盟链的高并发场景。

关键词: 区块链, Hyperledger Fabric, LevelDB, 布隆过滤器, 日志结构合并树

Abstract: Bloom filters are frequently used for read performance optimization of Hyperledger Fabric state database LevelDB, but they suffer from false positives, and LevelDB asks Bloom filters working in a uniform rather than adaptively adjusted configuration. In this paper, a unitized partial counting Bloom filter (PCBF) construction scheme is proposed by using a parallel element insertion and query computing mechanism, which combines double Hash and non-encrypted Hash to achieve fast insertion and query. Sorted string table (SSTable) priority is constructed based on open filter units and access times, while the filter units are adaptively adjusted by using a time-slice polling algorithm to achieve reasonable resource allocation. Experiments show that PCBF has a high insertion efficiency and can reduce the total number of false positives by about 20%, proving the feasibility of PCBF in high concurrency scenarios of permissioned blockchain.

Key words: blockchain, Hyperledger Fabric, LevelDB, Bloom filter, log structured merge tree (LSM tree)

中图分类号:

TP309

吴亦涵, 黄建华, 邵兴辉, 王诚. 用于联盟链的布隆过滤器优化[J]. 应用科学学报, 2022, 40(4): 611-622.

WU Yihan, HUANG Jianhua, SHAO Xinghui, WANG Cheng. Bloom Filter Optimization for Consortium Blockchain[J]. Journal of Applied Sciences, 2022, 40(4): 611-622.

参考文献

[1] Nakamoto S.Bitcoin:a peer-to-peer electronic cash system[R/OL].(2008-10-31)[2021-07-01].https://www.debr.io/article/21260-bitcoin-a-peer-to-peer-electronic-cash-system.
[2] 袁勇,王飞跃.区块链技术发展现状与展望[J].自动化学报, 2016, 42(4):481-494.Yuan Y, Wang F Y.Blockchain:the state of the art and future trends[J].Acta Automatica Sinica, 2016, 42(4):481-494.(in Chinese)
[3] Zheng Z, Xie S, Dai H, et al.An overview of blockchain technology:architecture, consensus, and future trends[C]//2017 IEEE International Congress on Big Data, 2017:557-564.
[4] Androulaki E, Barger A, Bortnikov V, et al.Hyperledger Fabric:a distributed operating system for permissioned blockchains[C]//Proceedings of the Thirteenth EuroSys Conference, 2018:1-15.
[5] Thakkar P, Nathan S, Viswanathan B.Performance benchmarking and optimizing Hyperledger Fabric blockchain platform[C]//2018 IEEE 26th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, 2018:264-276.
[6] 郭上铜,王瑞锦,张凤荔.区块链技术原理与应用综述[J].计算机科学, 2021, 48(2):271-281.Guo S T, Wang R J, Zhang F L.Summary of principle and application of blockchain[J].Computer Science, 2021, 48(2):271-281.(in Chinese)
[7] Ma X, Ma W, Liu X.A cross domain authentication scheme based on blockchain technology[J].Acta Electonica Sinica, 2018, 46(11):2571-2579.
[8] 吴尚宇,谢婧雯,王毅.面向键值存储的日志结构合并树优化技术[J].计算机研究与发展, 2020, 57(11):2432-2441.Wu S Y, Xie J W, Wang Y.Optimization of LSM-Tree for key-value stores[J].Journal of Computer Research and Development, 2020, 57(11):2432-2441.(in Chinese)
[9] O'neil P, Cheng E, Gawlick D, et al.The log-structured merge-tree (LSM-tree)[J].Acta Informatica, 1996, 33(4):351-385.
[10] Pugh W.Skip lists:a probabilistic alternative to balanced trees[J].Communications of the ACM, 1990, 33(6):668-676.
[11] Lu L, Pillai T S, Gopalakrishnan H, et al.Wisckey:separating keys from values in SSDconscious storage[J].ACM Transactions on Storage, 2017, 13(1):1-28.
[12] Zhang J, Wu S, Tan Z, et al.S3:a scalable in-memory skip-list index for key-value store[J].Proceedings of the VLDB Endowment, 2019, 12(12):2183-2194.
[13] Balmau O, Guerraoui R, Trigonakis V, et al.FloDB:unlocking memory in persistent key-value stores[C]//Proceedings of the Twelfth European Conference on Computer Systems, 2017:80-94.
[14] Ahmad M Y, Kemme B.Compaction management in distributed key-value datastores[J].Proceedings of the VLDB Endowment, 2015, 8(8):850-861.
[15] 王鹏超,杜慧敏,曹广界,等.基于布隆过滤器的精确匹配算法设计与实现[J].计算机科学, 2015, 42(增刊1):429-434.Wang P C, Du H M, Cao G J, et al.Design and implement of exact matching algorithm based on Bloom filter[J].Computer Science, 2015, 42(Suppl.1):429-434.(in Chinese)
[16] Fan B, Andersen D G, Kaminsky M, et al.Cuckoo filter:practically better than Bloom[C]//Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies, 2014:75-88.
[17] Bloom B H.Space/time trade-offs in Hash coding with allowable errors[J].Communications of the ACM, 1970, 13(7):422-426.
[18] Kirsch A, Mitzenmacher M.Less Hashing, same performance:building a better Bloom filter[C]//European Symposium on Algorithms.Berlin, Heidelberg:Springer, 2006:456-467.
[19] Lim H, Andersen D G, Kaminsky M.Towards accurate and fast evaluation of multi-stage log-structured designs[C]//The 14th USENIX Conference on File and Storage Technologies FAST, 2016:149-166.
[20] Patgiri R.HFIL:a high accuracy Bloom filter[C]//2019 IEEE 21st International Conference on High Performance Computing and Communications, IEEE 17th International Conference on Smart City, IEEE 5th International Conference on Data Science and Systems (HPCC/SmartCity/DSS), 2019:2169-2174.
[21] Harter T, Borthakur D, Dong S, et al.Analysis of HDFS under HBase:a facebook messages case study[C]//The 12th{USENIX}Conference on File and Storage Technologies FAST, 2014:199-212.
[22] Lai C, Jiang S, Yang L, et al.Atlas:Baidu's key-value storage system for cloud data[C]//201531st Symposium on Mass Storage Systems and Technologies, IEEE, 2015:1-14.