布鲁姆过滤器算法在P2P系统中的应用

田小梅， 胡 灿

(1.湖南环境生物职业技术学院 艺术设计学院，湖南衡阳421005;2.湖南大学信息科学与工程学院，湖南 长沙410082)

自70年代由Burton Bloom创新性地提出以来，布鲁姆过滤器算法(Bloom filter，BF)[1]已被广泛用于各类网络及分布式系统，各种布鲁姆过滤器算法的变种和相关应用领域不断涌现[2].

1 布鲁姆过滤器算法

布鲁姆过滤器是一种空间高效的有损数据结构，支持快速的数据成员查询，能高效地过滤非集合成员.

通常我们使用布鲁姆过滤器的场景如下:将集合S表示到布鲁姆过滤器BF(S)中，在需要查询元素是否属于集合S时，使用BF(S)而不是S本身进行集合成员查询，节约存储空间及提高查询的时间效率.

2 P2P网络

对等网络(Peer to peer，P2P)是一类分布式网络，网络的参与者(称对等节点或Peer)共享他们所拥有的一部分硬件资源(处理能力、存储能力、网络连接能力、打印机等)，这些共享资源能被其它对等节点直接访问而无需经过中间实体.在此网络中的对等节点既是资源提供者(Server)，又是资源获取者(Client)[3].

P2P网络最大的优势是资源共享，从理论上讲，P2P网络的能力和资源是网络中各节点能力和资源的总和.为充分利用互联网节点的闲置计算能力或存储空间，通过P2P技术将计算任务或存储资料分散到网络的其它结点，各结点协同工作，得到各类文件共享系统、高性能计算系统、海量存储系统等P2P分布式系统.

3 互联网中的P2P应用实例

21世纪以来，互联网在现代社会中的作用越来越举足轻重，已经成为人类社会重要的信息基础设施，并强力渗透到政治、经济、社会、军事、科技文化、教育等各个领域，对人类的生活、工作及学习产生了日益深远的影响.事实上，互联网提供的即时通信、搜索、音乐、新闻、网络视频、娱乐等服务，都存在P2P技术的应用实例.下面是P2P技术在互联网中的一些应用实例.

即时通讯(Instant messenger，IM)软件，如 ICQ、QQ、UC、Yahoo Messenger、AOL Instant Messenger、KDT快递通、Openext、POCO、ezPeer等早已成为网民上网的必备工具，正在逐渐改变人们的沟通与交际方式.大多数的这类即时通讯软件都是基于P2P技术的，如 ICQ、QQ、MSN Messenger等.

美国Digital公司正在研制的Pandango搜索引擎就是一种基于P2P技术的搜索引擎，公司的首席执行官利亚德-梅达(Liad Meidar)表示，Pandango搜索引擎目前已经几近完成，公司正在与许多大名鼎鼎的门户网站、ISP以及网络公司协商合作事宜.就连著名的Google公司也宣称正在采用P2P技术来改进其现有的第二代搜索引擎，研发第三代搜索引擎.

Napster、Kuro、KuGou、Muper、百宝等 P2P 音乐共享软件，成为用户获取音乐文件的主要手段.例如，KuGou软件，积累了数万首数字音乐版权，拥有超过数亿的共享音乐文件，拥有上千万用户，深受广大用户的喜爱.

随着互联网的兴起，作为“新电子媒体”的网络逐渐成为一种新的新闻媒体类型.尤其是，很多基于P2P技术的视频直播系统(如 PPTV、PPStream等)的诞生对网络新闻的发展起到了极大的推进作用.

目前视频类网站运营成本中最大的部分是带宽成本，而P2P技术能有效降低服务器的负载，减少70%以上的带宽租用.P2P技术能在保证用户体验感的情况下，有效降低带宽租用成本，提高视频运营商的业务竞争力，有望成为互联网视频领域的主流技术.

许多网络在线游戏均是基于P2P技术的，如泡泡堂、街头篮球、跑跑卡丁车等.这对广大青少年用户来说是极富吸引力的娱乐方式.华中科技大学开发的Pktown大规模游戏对战服务平台[4]也基于P2P技术.

Farsite、Ocean Store等P2P海量数据存储软件，用于将网络上原本由专用服务器存储的数据对象分散到多个网络节点中存放，增加数据的可靠性和传输速度.

CNNIC的报告[5]指出:由于全球IPv4地址已于2011年2月分配完毕，我国IPv6地址数量在近一年内飞速增长，截至2012年6月底，我国拥有IPv6地址数量为12499块/32，全球排名第3位，仅次于巴西(65728块/32)和美国(18694块/32).由于IPv6使用128位IP地址，能使更多的节点加入P2P网络，而且，IPv6技术中加入了身份验证、数据一致性和保密性机制，能提高P2P网络的安全性.因此，IPv6地址的大规模部署能促进P2P技术的发展.

CNNIC发布的《第30次中国互联网络发展状况统计报告》[5]还指出，由于当前智能手机的功能越来越强大，价格却越来越低，加上移动上网应用软件的大量涌现，2012年上半年，通过手机接入互联网的网民数量达到3.88亿，比台式电脑用户多出800万，手机上网用户首次超越台式电脑上网用户，手机成为我国网民的第一大上网终端.可以断言，智能手机的普及势必会推动移动P2P计算的进一步发展.

从以上的种种实例可以看到，P2P无疑是目前互联网上最为广泛的技术应用.而且，这种优势随着IPv6地址的广泛部署和智能手机的广泛普及必将持续下去.

4 布鲁姆过滤器算法在P2P系统中的应用研究

布鲁姆过滤器在P2P网络中的主要作用是汇总各类资源如文件、关键字或其它对象，使用布鲁姆过滤器汇总后，空间占用比直接存储原始集合要少几个数量级.布鲁姆过滤器可用于P2P系统中关键字检索、资源路由、远程数据调和、社会网络及P2P副本一致性维护等应用场合.

4.1 关键字检索

在Cuena-Acuna等人提出的PlanetP系统[6]中，使用布鲁姆过滤器存储对象的关键字，而不是存储对象标识符.比如说，存储对象标识符需64位，而使用布鲁姆过滤器后每个对象却只要8位或16位就可.在中等规模的P2P网络中，每个节点均存储其它节点的布鲁姆过滤器表示的关键字列表是不难做到的.

现今流行的Gnutella2协议[7]使用布鲁姆过滤器高效地表示文件的关键字列表.在Gnutella2文件共享系统中，使用两层体系结构，由超节点层和叶节点层组成.叶节点发送本地文件的关键字列表(布鲁姆过滤器)给某超节点，超节点收集所属叶节点的布鲁姆过滤器，将其归并到一个总布鲁姆过滤器再发送给相邻的超节点.当叶节点需要查询文件，首先从它连接的超节点的索引中寻找，如果找到了文件，则直接根据文件所存储的机器的地址建立连接，如果没有找到，则超节点把这个查询请求发给它连接的其他超节点，直到得到想要的资源.

随着在网络上用于数据交换的可扩展标记语言(XML)的普及，大量的数据源用XML格式表示或编码.因此，查询和检索网络上的XML数据受到了数据库文献的极大重视.同时，P2P计算模式推动了互联网上更灵活的自主数据共享.P2P系统中的XML数据检索已吸引了研究团体和工业界的广大专业人士的研究.文献[8]针对结构化P2P系统提出了一种以布鲁姆过滤器为基础的用于XML数据检索的关键字搜索框架，在该框架中，XML索引使用布鲁姆过滤器编码.与传统的全索引方案相比，基于布鲁姆过滤器的关键字搜索方法查询响应时间短，系统具数据规模可扩展性和网络规模可扩展性.

4.2 资源路由

Rhea和Kubiatowicz等人设计了一种概率路由算法[9]用于 OceanStore[10]项目的资源定位，这种路由机制称为资源路由.在请求某文件时，首先使用概率路由算法查找，当请求文件已被复制到请求系统附近时能较快地完成资源定位.在OceanStore系统中，如果使用概率路由算法查找失败，则再使用Tapestry协议实施确定的搜索算法.OceanStore系统中使用的衰减布鲁姆过滤器(Attenuated Bloom filter)是一个由d个基本布鲁姆过滤器组成的数组，其中，第i个基本布鲁姆过滤器保存的是i跳可达的文件记录.在该系统中，节点为每个邻居节点均维护一个衰减布鲁姆过滤器，衰减布鲁姆过滤器的更新通过广播机制实现.当然，这种资源路由机制也能用于与其他P2P网络[11-13]中的确定性路由机制配合使用.

Cai和 Wang在 Foreseer系统[14]中提出使用地理局部性和时间局部性分别构建邻居覆盖网和朋友覆盖网来提高系统的搜索效率.系统中的每一个对等节点均维护有少量邻居和朋友的内容过滤器作为分布式索引.

4.3 远程数据同步

布鲁姆过滤器可用于P2P网络中的集合调和或数据同步[15-19].通常，在这类应用中，布鲁姆过滤器被用于精简表示自身节点已经拥有的条目，对等节点发送一个这样的布鲁姆过滤器给另一对等节点，接收节点根据接收到的布鲁姆过滤器找出发送节点所缺少的条目，并将这部分条目发送回发起方.这样，调和或同步过程中只需发送对方节点缺失的条目，而不需发送所有条目，从而节约带宽、提高效率.但由于布鲁姆过滤器假阳性的存在，接收节点在查找时，会遗漏部分条目，通常可配合使用纠删码以完成调和[17].

4.4 社会P2P网络

布鲁姆过滤器也被用于社会P2P网络，例如社会 P2P 文件共享系统 Tribler[20].Tribler使用布鲁姆过滤器来维护在对等节点间同步的社会信任网络.布鲁姆过滤器被用于筛选出已由消息目标节点通过群发现消息所知晓的对等节点.在Tribler中，使用一个大小为260字节的布鲁姆过滤器，信息就能到达两对等节点共同的朋友的朋友，从而对等节点能在短时间内与成千上万个对等节点交换信息.

4.5 P2P副本一致性维护

在副本更新报文的头部增加一个用布鲁姆过滤器表示的地址链表，每个节点均有一个相应长度的掩码，该掩码与副本更新报文头部中的布鲁姆过滤器进行“或”运算，如果布鲁姆过滤器发生了改变，则使用副本更新报文更新该节点的副本，否则，表示该节点的副本已进行过更新[21].

5 结束语

由于具有节约存储空间、快速查询集合成员的优点，布鲁姆过滤器在需要共享数据信息的大型分布式应用系统中有巨大的应用潜力.尤其是伴随着P2P技术在互联网中的广泛部署及应用，布鲁姆过滤器算法在P2P系统中的应用正呈现如火如荼的发展态势.

[1] BLOOM B H.Space/time trade-offs in hash coding with allowable errors[J].Communications of the ACM，1970，13(7):422-426.

[2] 谢 鲲，文吉刚，张大方等.布鲁姆过滤器查询算法[J].软件学报，2009，20(1):96-108.

[3] 斯太门兹等.P2P系统及其应用[M].机械工业出版社.2008.

[4] JIN H，YAO H，LIAO X，et al.PKTown:A peer-to-peer middleware to support multiplayer online games[A].Proceedings of the International Conference on Multimedia and Ubiquitous Engineering[C]，2007.54-59.

[5] 中国互联网络信息中心，第30次中国互联网络发展状况统计报 告[R].http://www.cnnic.org.cn/hlwfzyj/hlwxzbg/hlwtjbg/201207/t20120723_32497.htm，2012.7.19.

[6] CUENCA-ACUNA F M，PEERY C，MARTIN R P，et al.Planetp:Using gossiping to build content addressable peerto-peer information sharing communities[A].Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing[C]，2003.236-246.

[7] STOKES.M.Gnutella2 Specifications Part One[J].http://www.gnutella2.com/gnutella2_search.htm.

[8] HE W，LV T.Bloom filter-based keyword search over XML data in structured Peer-to-Peer systems[A].Proceedings of the 3rd IEEE International Conference on Computer Science and Information Technology[C]，2010.177-181.

[9] RHEA S，KUBIATOWICZ J.Probabilistic location and routing[A].Proceedings of the INFOCOM 2002[C]，2002.1248-1257.

[10] KUBIATOWICZ J，BINDEL D，CHEN Y，et al.Oceanstore:An architecture for global-scale persistent storage[J].ACM Sigplan Notices，2000，35(11):190-201.

[11] ROWSTRON A，DRUSCHEL P.Storage management and caching in PAST，a large-scale，persistent peer-to-peer storage utility[A].Proceedings of the Eighteenth ACM Symposium on Operations Systems Principles[C]，2001.188-201.

[12] RATNASAMY S，FRANCIS P，HANDLEY M，et al.A scalable content-addressable network[J].ACM SIGCOMM Computer Communication Review，2001，31(4):161-172.

[13] STOICA I，MORRIS R，KARGER D，et al.Chord:A scalable peer-to-peer lookup service for internet applications[J].ACM SIGCOMM Computer Communication Review，2001，31(4):149-160.

[14] CAI H，WANG J.Exploiting geographical and temporal locality to boost search efficiency in peer-to-peer systems[J].IEEE Transactions on Parallel and Distributed Systems，2006，17(10):1189-1203.

[15] STAROBINSKI D，TRACHTENBERG A，AGARWAL S.Efficient PDA synchronization[J].IEEE Transactions on Mobile Computing，2003，2(1):40-51.

[16] MINSKY Y，TRACHTENBERG A，Efficient reconciliation of unordered databases[R].TR1999-1778.Cornell University，1999.

[17] 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.

[18] 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.

[19] SKJEGSTAD M，MASENG T.Low complexity set reconciliation using Bloom filters[A].Proceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing[C]，San Jose，California，2011.33-41.

[20] POUWELSE J A，GARBACKI P，WANG J，et al.TRIBLER:a social‐based peer‐to‐peer system[J].Concurrency and Computation:Practice and Experience，2008，20(2):127-138.

[21] 谢 鲲，张大方，谢高岗等.基于轨迹标签的无结构P2P副本一致性维护算法[J].软件学报，2007，18(1):105-116.