多布鲁姆过滤器检索算法研究

田小梅，胡 灿，李 浪

（1.衡阳师范学院 计算机科学与技术学院，湖南 衡阳 421002；2.湖南环境生物职业技术学院 艺术设计学院，湖南 衡阳 421005）

中国互联网络信息中心最近发布的《第36次中国互联网络发展状况统计报告》指出：截至2015年上半年止，我国网民数量占人口总数的48.8%，达6.68亿［1］。计算机网络的迅猛发展，产生了包括各类网络交互数据和业务数据在内的海量数据［2］，人类迎来了海量数据时代，开始用拍字节（PB，Petabyte，千万亿字节）作为基本单位来计量各类数据。海量数据的处理得到了越来越多人的重视，尤其是对于谷歌、百度、腾讯等涉及海量业务数据的公司。在PB、EB（Exabyte，1EB＝1024PB）乃至ZB（Zettabyte，1ZB＝1024EB）数量级的数据汪洋中定位和检索某个特定数据或特定数据记录，对于网络设计者和网络数据管理者来说是一个大的挑战。

1 处理海量数据的布鲁姆过滤器

处理海量数据，通常需要一个索引类型的数据结构，用于快速判断数据记录是否存在于数据集中。能用于处理海量数据的常用索引结构有哈希（hash）、位图（bitmap）、布鲁姆过滤器（Bloom fil－ter）、堆（heap）、映射化简（mapreduce）、特里树（trie tree）等。布鲁姆过滤器这一数据结构其空间复杂度和时间复杂度均较低，可以用于高效检索某元素是否归属某集合，但是，它有一定的误判可能：将原本不在某集合中的元素误判为该集合的成员，这种现象称假阳性现象。所以，布鲁姆过滤器检索算法不适合“零误判”的应用场合，但在允许少量误差的场合中，布鲁姆过滤器是一类处理海量数据的首选方案。

布鲁姆过滤器算法［3］最初是由Bloom提出的，当时的应用领域主要是拼写检查、数据库系统、文件系统等。计算机技术与互联网技术在高速发展，各类网络数据的规模在不断增长，布鲁姆过滤器算法相应地得到了前所未有的发展：新的应用领域以及变种层出不穷，被大量运用于各类分布式系统及网络系统［4］，如IP查找［5］、包分类［6］、网络测量与监测［7］、搜索引擎［8］、P2P 网络路由算法［9］、内容分发与数据同步［10－13］、网络 安全［14－15］、生物 工程［16－17］、分布式存储系统［18］、无线传感器网络［19］、云计算数据中心［20］等。

2 多布鲁姆过滤器检索算法

使用单个的布鲁姆过滤器结构即可查询元素是否属于某个集合，这一方法我们称其为单布鲁姆过滤器检索算法（图1）。有时，在各集合相应的布鲁姆过滤器结构已知的基础上，我们需要查询元素是否属于多个集合参与运算后的结果集合（并集、交集、差集等），这样，单布鲁姆过滤器检索算法存在无法胜任的情形。同时查询多个布鲁姆过滤器完成数据检索操作的方法称为多布鲁姆过滤器检索算法（如图2所示）。如何高效地在多个布鲁姆过滤器结构上完成检索操作，成为目前具有挑战性的课题领域。

图1 单布鲁姆过滤器检索算法

图2 多布鲁姆过滤器检索算法（以检索交集为例）

3 多布鲁姆过滤器检索算法应用与研究

与单布鲁姆过滤器检索算法的研究正在广泛开展不同，关于多布鲁姆过滤器检索算法的研究则要少得较多，概括地说主要有两个方面：①多布鲁姆过滤器直接检索算法（即并行布鲁姆过滤器）的应用研究；②多个布鲁姆过滤器间的代数运算及其应用研究。

3.1 多布鲁姆过滤器直接检索算法的应用

多布鲁姆过滤器直接检索算法并行查询多个布鲁姆过滤器，以获取特定信息。这类算法主要用于包分类系统、IP路由查找等方面。

由于IPv6地址的广泛使用，传统包分类器变得越来越复杂，流标识符（包含源IP、目标IP的五元组）数量越来越多，从而导致包分类过程中使用的缓存也越来越大，流标识符的检索过程越来越慢。文献［21］使用并行布鲁姆过滤器构建包分类缓存，一个哈希函数对应一个布鲁姆过滤器结构，将流标识符映射到多个布鲁姆过滤器。当数据包到达时，并行检索所有布鲁姆过滤器，如果所有二进制位均为1，则认定数据包在缓存中，然后将其进行转发。实验结果表明：与精确缓存方案相比，这种近似缓存策略其检索速度更快，存储效率更高。

文献［22］则指出，文献［21］的包分类方法具有能耗大及呑吐量低的缺点，针对其缺陷，提出了新的包分类程序：将多个布鲁姆过滤器结构组织成二叉树的形式，实验数据表明该算法具有更少的能耗以及更大的呑吐量。

文献［23］将布鲁姆过滤器用于IP查找过程中的最长前缀匹配过程。一个布鲁姆过滤器对应一个IP前缀长度，在查找匹配的最长前缀过程中并行检索这一系列的布鲁姆过滤器结构。

事实上，文献［21］和文献［23］等工作是在多个布鲁姆过滤器结构上完成并行检索，查找并集成员的具体应用实例。文献［24］则系统地分析了双（多）布鲁姆过滤器直接检索算法检索并集、交集成员等的性能问题，并给出了相关的应用场合，从而将多布鲁姆过滤器直接检索算法的检索范围从并集拓展到了交集、补集、差集或对称差。

3.2 布鲁姆过滤器代数运算与应用

早在2002年，Whitaker等人就在Icarus系统中将布鲁姆过滤器用于路由环路检测［25］，其具体过程为：长度不大的小型布鲁姆过滤器被加入数据包的头部，用于映射数据包转发路径上已访问的节点列表，同时，每个节点设置一个与数据包内布鲁姆过滤器等长的掩码（该掩码实际上就是一个仅包含节点自身地址信息的布鲁姆过滤器），当数据包到达某节点时，将节点的掩码与数据包中的小型布鲁姆过滤器逐位完成“或”运算（即“并”运算），比较运算前后的布鲁姆过滤器，若相同，则说明在该节点处极可能形成了环路。

文献［26］使用类似于文献［25］的包内布鲁姆过滤器以及“位或”运算，完成P2P网络中的副本维护工作。它所采用的副本维护机制与文献［25］中的环路检测机制相似：将副本更新报文传播时经过的节点地址列表用布鲁姆过滤器表示，添加到副本更新报文的头部。根据副本更新报文中布鲁姆过滤器的变化情况，判断是否需要更新目标节点的副本。

布鲁姆过滤器并运算也能用于关键字检索，譬如，Gnutella2文件共享协议［27］将在文件中抽取的关键字映射到布鲁姆过滤器结构中。Gnutella2中的节点分属于两个层次：超节点层、叶节点层。叶节点发送本地布鲁姆过滤器给上层的超节点，超节点则合并它下层所有叶节点的布鲁姆过滤器，并将合并后的布鲁姆过滤器传送给与其相邻的超节点。在进行关键字检索时，叶节点首先检索与它直接相连的超节点，若检索不成功，则由超节点将关键字检索请求转发给相邻超节点。

Rhea和Kubiatowicz则使用布鲁姆过滤器的并运算来查找资源的位置，并称这种算法为资源路由算法［28］。资源路由表在构造过程中使用了布鲁姆过滤器的并运算。当节点收到文件共享请求时，首先在其资源路由表中查找，若查找失败，则再使用Tapestry等确定性路由协议进行搜索。

标准布鲁姆过滤器使用比特向量保存数据信息，文献［29］的研究工作表明：可使用多个比特向量“位或”、“位与”运算后得到的新比特向量来检索并集、交集元素。

文献［30］则完整地定义了标准布鲁姆过滤器的并运算、交运算，且将并运算推广到了其它使用比特向量作为存储结构的布鲁姆过滤器，如动态布鲁姆过滤器、多维布鲁姆过滤器、多维动态布鲁姆过滤器等。

文献［31］的作者指出：标准布鲁姆过滤器间除可进行并运算、交运算之外，还能完成其它代数运算，如补运算、减运算及异或运算，详尽地讨论了标准布鲁姆过滤器各种代数运算的性质，得出如下结论：标准布鲁姆过滤器并运算后的新比特向量与并集的标准布鲁姆过滤器向量是一致的；交运算后的新比特向量与交集的标准布鲁姆过滤器比特向量相比，其非零比特数量稍多，从而产生了稍高的假阳性比率；使用标准布鲁姆过滤器并运算或交运算检索并集或交集元素时均不会产生假阴性误判；但补、减、异或等运算则因为会有较严重的假阴性误判问题，不能用于检索补集、差集或对称差元素。

文献［32］则研究计数器向量布鲁姆过滤器间的代数运算，定义了计数布鲁姆过滤器的并、交、补、减及异或运算，从理论分析和实验验证两个角度对计数布鲁姆过滤器代数运算的特性进行了探讨，得到如下结论：计数布鲁姆过滤器并、交、补、减及异或运算后的新计数器向量能用于检索并集、交集、补集、差集及对称差元素，不会发生假阴性误判。在此基础上，我们提出了一种使用计数布鲁姆过滤器减运算的数据同步方法［12］，新算法能在单轮消息交换过程中完成精确的数据同步。

4 结束语

在各类分布式网络系统中，常常运用布鲁姆过滤器来高效存储各类海量数据，以支持数据同步、内容分发、资源路由等应用中的快速检索，在这类应用中，需要同时检索多个布鲁姆过滤器结构。在多个布鲁姆过滤器结构上高效地完成海量数据的检索，是多布鲁姆过滤器检索算法的主要目标。目前有关多布鲁姆过滤器检索算法的研究工作不多；同时，这些应用研究工作通常集中在多布鲁姆过滤器代数运算中的并运算，以及使用多个布鲁姆过滤器直接检索并集成员这两个方面，对于其他方面，如多布鲁姆过滤器代数运算中交、减运算等的应用，所做的研究工作不多，因此，在多布鲁姆过滤器检索算法领域还存在不少的研究空间。

［1］中国互联网络信息中心，第36次中国互联网络发展状况统 计 报 告 ［R］.http：／／www.cnnic.cn／hlwfzyj／hlwxzbg／hlwtjbg／201507／P020150723549500667087.pdf，2015.7.23.

［2］冯丹.海量存储系统及技术研究进展 ［M］.中国计算机科学技术发展报告2010.北京：机械工业出版社.2011：46－71.

［3］BLOOM B H.Space／time trade－offs in hash coding with allowable errors ［J］.Communications of the ACM，1970，13（7）：422－426.

［4］TARKOMA S，ROTHENBERG C，LAGERSPETZ E.Theory and practice of bloom filters for distributed systems［J］.IEEE Communications Surveys ＆ Tutorials，2012，14（1）：131－155.

［5］YANG T，XIE G G，DUAN R A，et al.Towards practical use of Bloom Filter based IP lookup in operational network ［A］.Proceedings of the Network Operations and Management Symposium（NOMS）2014［C］，2014.1－4.

［6］CHEN Y，OGUNTOYINBO O.Power efficient packet classification using cascaded bloom filter and off－theshelf ternary CAM for WDM networks［J］.Computer Communications，2009，32（2）：349－356.

［7］吴桦，龚俭，杨望.一种基于双重 Counter Bloom Filter的长 流 识 别 算 法 ［J］.软 件 学 报，2010，21（5）：1115－1126.

［8］PANG M，XU G.A personalized search engine research based on Bloom filter［A］.Proceedings of the 2011International Conference on Electric Engineering and Computer（MEC）［C］，Jilin，China，2011.2365－2368.

［9］KUMAR A，XU J，ZEGURA E W.Efficient and scalable query routing for unstructured peer－to－peer networks［A］.Proceedings of the INFOCOM 2005［C］，Miami，FL，United States，2005.1162－1173.

［10］EPPSTEIN D，GOODRICH M T，UYEDA F，et al.What’s the difference？Efficient set reconciliation without prior context［A］.Proceedings of the ACM SIGCOMM 2011［C］，Toronto，Ontario，Canada，2011.218－229.

［11］BYERS J，CONSIDINE J，MITZENMACHER M，et al.Informed content delivery across adaptive overlay networks［J］.ACM SIGCOMM Computer Communication Review，2002，32（4）：47－60.

［12］田小梅，张大方，谢鲲，等.基于计数布鲁姆过滤器的集合调和算法 ［J］.通信学报，2012，33（8）：119－127.

［13］ZHAO T，LIU Z，YAN W，et al.BFBD：A Bloom Filter based Buffering Data Dissemination algorithm for Vehicular Ad hoc Networks ［A］.Proceedings of the 2011IEEE Consumer Communications and Networking Conference（CCNC）［C］，Las Vegas，USA，2011.447－481.

［14］MARKKU A ，TUOMAS A，MIKKO S.Denial－ofservice attacks in bloom－filter－based forwarding ［J］.IEEE／ACM Transactions on Networking （TON），2014，22（5）：1463－1476.

［15］GERAVAND Shahabeddin， AHMADI Mahmood.Bloom filter applications in network security：A stateof－the－art survey［J］.Computer networks，2013，57（18）：4047－4064.

［16］MELSTED P，PRITCHARD J K.Efficient counting of k－mers in DNA sequences using a bloom filter ［J］.BMC bioinformatics，2011，12（1）：1－7.

［17］RATHGEB C，BREITINGER F，Busch C.Alignmentfree cancelable iris biometric templates based on daptive bloom filters ［A］.Proceedings of the International Conference on Biometrics 2013［C］，2013：1－8.

［18］PHYU M P，THEIN N L.Efficient storage management for distributed storage system ［A］.Proceedings of the SPIE －The International Society for Optical Engineering 2012［C］，2012.

［19］LI G L，GUO L J，GAO X，et al.Bloom filter based processing algorithms for the multi－dimensional event query in wireless sensor networks［J］.Journal of network and computer applications，2014，37 （1）：323－333.

［20］LI D，CUI H，HU Y，et al.Scalable data center multicast using multi－class Bloom Filter［A］.Proceedings of the 19th IEEE International Conference on Network Protocols［C］，Vancouver，BC，2011.266－275.

［21］CHANG F，FENG W，LI K.Approximate caches for packet classification［A］.Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies （INFOCOM） ［C］，2004.2196－2207.

［22］YU H，MAHAPATRA R N.A Power and Throughput－Efficient Packet Classifier with n Bloom Filters［J］.IEEE Transactions on Computers，2011，60（8）：1182－1193.

［23］DHARMAPURIKAR S，KRISHNAMURTHY P，TAYLOR D E.Longest prefix matching using bloom filters［J］.IEEE／ACM Transactions on Networking（TON），2006，14（2）：397－409.

［24］田小梅，张大方，史长琼，等.双布鲁姆过滤器法查询集合成员 ［J］.计算机工程与应用，2012，48（28）：10－15.

［25］WHITAKER A，WETHERALL D.Forwarding without loops in icarus［A］.Proceedings of the Fifth IEEE Conference on Open Architectures and Network Programming［C］，2002.63－75.

［26］谢鲲，张大方，谢高岗，等.基于轨迹标签的无结构P2P副本一致性维护算法 ［J］.软件学报，2007，18（1）：105－116.

［27］STOKES.M.Gnutella2Specifications Part One［EB／OL］. http：／／www. gnutella2. com／gnutella2 ＿search.htm.

［28］RHEA S，KUBIATOWICZ J.Probabilistic location and routing［A］.Proceedings of the INFOCOM 2002 ［C］，2002.1248－1257.

［29］BRODER A，MITZENMACHER M.Network applications of bloom filters：A survey ［J］.Internet Mathe－matics，2005，1（4）：485－509.

［30］GUO D，WU J，CHEN H，et al.Theory and network applications of dynamic bloom filters［A］.Proceedings of the INFOCOM 2006［C］，Washington，2006.1－12.

［31］谢鲲，张大方，文吉刚，等.布鲁姆过滤器代数运算探讨 ［J］.电子学报，2008，36（5）：869－874.

［32］田小梅，张大方，谢鲲，等.计数布鲁姆过滤器代数运算 ［J］.计算机学报，2012，35（12）：2598－2617.