基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和算法

田小梅，張大方，謝鯤，胡燦，楊曉波，史長(zhǎng)瓊,3

(1. 湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙410082; 2. 湖南環(huán)境生物職業(yè)技術(shù)學(xué)院 信息技術(shù)系，湖南 衡陽421005；3. 長(zhǎng)沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，湖南 長(zhǎng)沙410114)

1 引言

在分布式系統(tǒng)中，假定2節(jié)點(diǎn)A、B分別擁有數(shù)據(jù)集合SA、SB，節(jié)點(diǎn)A和B進(jìn)行數(shù)據(jù)交換得到并集SA∪SB的過程稱集合調(diào)和[1]。也就是說，集合調(diào)和是通過分布式節(jié)點(diǎn)進(jìn)行數(shù)據(jù)交換獲得2節(jié)點(diǎn)數(shù)據(jù)集合并集的過程。集合中的元素可以是P2P系統(tǒng)中的文件塊或路由協(xié)議中的鏈路狀態(tài)分組標(biāo)記等。集合調(diào)和在分布式文件分發(fā)、閑談協(xié)議等分布式計(jì)算領(lǐng)域是一個(gè)重要的基本問題。一般說來，集合調(diào)和可以用于需要對(duì)無序分布式數(shù)據(jù)維護(hù)一致性的任意系統(tǒng)中。集合調(diào)和已廣泛應(yīng)用于分布式數(shù)據(jù)庫與文件系統(tǒng)[2]、信息安全[3,4]、閑談協(xié)議[5]、移動(dòng)數(shù)據(jù)庫同步[6]、資源定位系統(tǒng)[7]等領(lǐng)域。集合調(diào)和過程最關(guān)鍵的問題是如何高效計(jì)算集合差集的問題。集合調(diào)和中查找差集的技術(shù)亦可用于網(wǎng)絡(luò)分布式系統(tǒng)中的去重過程，如數(shù)據(jù)域系統(tǒng)[8,9]和文件系統(tǒng)[10,11]，它們首先找出交集中的數(shù)據(jù)，刪除重復(fù)數(shù)據(jù)并用指針代替，從而達(dá)到節(jié)約空間的目的。

很明顯，完成集合調(diào)和的最直接方法就是節(jié)點(diǎn)B直接傳輸集合SB給節(jié)點(diǎn)A，節(jié)點(diǎn)A計(jì)算得到并集SA∪SB。在大規(guī)模系統(tǒng)中，集合SB數(shù)據(jù)量非常龐大，直接傳輸集合SB要消耗大量的帶寬。因此，目前大多數(shù)方法都是先通過某種方法計(jì)算出差集 SB-SA，節(jié)點(diǎn)B僅傳輸SB-SA給節(jié)點(diǎn)A，從而節(jié)約了帶寬使用量。其通常步驟如下：首先將集合SA使用某種數(shù)據(jù)結(jié)構(gòu)表示，節(jié)點(diǎn)A傳輸該數(shù)據(jù)結(jié)構(gòu)給節(jié)點(diǎn)B，節(jié)點(diǎn)B計(jì)算出差集SB-SA，然后節(jié)點(diǎn)B傳輸SB-SA給節(jié)點(diǎn)A，節(jié)點(diǎn)A求出SA∪SB。在此過程中，集合SA的表示往往要求精簡(jiǎn)的數(shù)據(jù)結(jié)構(gòu)來表示。通常，為節(jié)約帶寬和減少網(wǎng)絡(luò)延時(shí)，在分布式系統(tǒng)中，集合調(diào)和時(shí)傳輸消息比特?cái)?shù)及數(shù)據(jù)交換輪數(shù)往往要求盡可能低。這是分布式系統(tǒng)進(jìn)行集合調(diào)和的最基本要求。

日志記錄系統(tǒng)是另一類常見的集合調(diào)和方法，每節(jié)點(diǎn)額外維護(hù)一個(gè)具有時(shí)間戳的更新日志(log)，當(dāng)需要調(diào)和時(shí)，節(jié)點(diǎn)B傳輸自上次調(diào)和以來的所有更新信息給節(jié)點(diǎn)A，節(jié)點(diǎn)A根據(jù)更新信息完成調(diào)和。日志記錄系統(tǒng)由于維護(hù)開銷大，會(huì)增加系統(tǒng)設(shè)計(jì)的難度，其應(yīng)用范圍得到一定的限制[12,13]。此類方法由于在調(diào)和前需要記錄數(shù)據(jù)更新信息等背景知識(shí)(prior context)，可稱為有狀態(tài)集合調(diào)和(stateful set reconciliation)。本文將不借助日志記錄等背景知識(shí)的集合調(diào)和方法稱為無狀態(tài)集合調(diào)和。無狀態(tài)集合調(diào)和由于不需維護(hù)狀態(tài)信息，可擴(kuò)展性好，使用簡(jiǎn)單，更易于應(yīng)用于各分布式系統(tǒng)。下文僅討論無狀態(tài)集合調(diào)和法。

目前，無狀態(tài)集合調(diào)和方法可分為2大類：精確集合調(diào)和和近似集合調(diào)和。精確集合調(diào)和[1,6,14～17]能得到差集(SB-SA)的準(zhǔn)確成員，但存在網(wǎng)絡(luò)傳輸消息比特?cái)?shù)大或消息交換輪數(shù)較多的缺點(diǎn)，如特征多項(xiàng)式集合調(diào)和法。近似集合調(diào)和[13,18,19]則只能得到SB-SA的大部分元素，但其優(yōu)點(diǎn)是：僅需單輪數(shù)據(jù)交換。

首先，本文通過理論分析和模擬實(shí)驗(yàn)證實(shí)：計(jì)數(shù)布魯姆過濾器的減運(yùn)算能支持集合的差集查詢。利用這一結(jié)論，本文提出一種基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和方法(如圖1所示)，其具體過程如下：數(shù)據(jù)集合SA、SB分別用計(jì)數(shù)布魯姆過濾器表示，節(jié)點(diǎn)A傳送SA的計(jì)數(shù)布魯姆過濾器表示給節(jié)點(diǎn)B，節(jié)點(diǎn)B利用計(jì)數(shù)布魯姆過濾器減運(yùn)算得到的過濾器，查詢SB中的差集元素SB-SA，將得到的SB-SA返回給A，A然后計(jì)算SA∪SB，完成集合調(diào)和。使用基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和方法能找出所有差集(SB-SA)元素。基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和法既具有精確集合調(diào)和法能得到全部SB-SA元素的優(yōu)點(diǎn)，也具有近似集合調(diào)和法僅需單輪消息交換的優(yōu)點(diǎn)。

圖1 基于CBF的集合調(diào)和

本文第2節(jié)簡(jiǎn)單介紹精確集合調(diào)和、近似集合調(diào)和方法。第 3節(jié)描述基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和方法。第4節(jié)是基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和的性能分析及模擬實(shí)驗(yàn)部分。第5節(jié)是結(jié)束語。

2 集合調(diào)和

集合調(diào)和在分布式系統(tǒng)中具有廣泛的應(yīng)用范圍。在內(nèi)容分發(fā)網(wǎng)絡(luò)或P2P系統(tǒng)中，由于網(wǎng)絡(luò)異構(gòu)性和網(wǎng)絡(luò)波動(dòng)(churn)的普遍存在，既便各對(duì)等節(jié)點(diǎn)同時(shí)從服務(wù)器端接收相同內(nèi)容，其所接收到的文件塊也往往存在顯著的差異，此時(shí)，充分利用對(duì)等節(jié)點(diǎn)之間的連接帶寬，在對(duì)等節(jié)點(diǎn)間僅僅傳輸對(duì)方節(jié)點(diǎn)缺失的文件內(nèi)容，實(shí)現(xiàn)知情內(nèi)容分發(fā)[18]，可以提高下載速度、縮短下載時(shí)間。或者，由于覆蓋網(wǎng)中網(wǎng)絡(luò)連接的短暫性，服務(wù)器和對(duì)等節(jié)點(diǎn)間的連接斷開，在此極端情況下，對(duì)等節(jié)點(diǎn)需要從其他對(duì)等節(jié)點(diǎn)獲取剩余文件塊。這些情況下，發(fā)送節(jié)點(diǎn)B若能找出接收節(jié)點(diǎn)A缺失的文件塊，僅傳送SB-SA中文件塊給A，可以達(dá)到合理利用網(wǎng)絡(luò)帶寬、快速獲取全文的目的。

2.1 精確集合調(diào)和

精確集合調(diào)和最直觀的方法是節(jié)點(diǎn)B直接發(fā)送SB所有元素給節(jié)點(diǎn)A，設(shè)元素位串長(zhǎng)度為len，此時(shí)需傳輸 O(|SB|len)bit消息[18]，本文稱為完整集合傳輸法。如果改為傳送關(guān)鍵字的有序列表(關(guān)鍵字列表傳輸法)，則可改善通信效率，僅需傳輸 O(|SB|log(u))bit消息。當(dāng)|SB|、len或u值較大時(shí)，完整集合傳輸法或關(guān)鍵字列表傳輸法所需傳輸?shù)南⒈忍財(cái)?shù)較大，將消耗較多的網(wǎng)絡(luò)帶寬，在實(shí)際系統(tǒng)中較少使用。

還有一種常用的精確集合調(diào)和方法是特征多項(xiàng)式插值法(CPISync, characteristic polynomials interpolation)[1]。設(shè) d=|SA-SB|+|SB-SA|，集合 SA、SB分別用特征多項(xiàng)式 CP(SA)、CP(SB)表示，節(jié)點(diǎn) A、B各自對(duì)相同的(≥ d)個(gè)求值點(diǎn)進(jìn)行多項(xiàng)式求值，得到最后進(jìn)行插值與因式分解，恢復(fù)差集元素。使用特征多項(xiàng)式插值法進(jìn)行集合調(diào)和，A節(jié)點(diǎn)僅需傳送O(d×logu)bit數(shù)據(jù)消息給B節(jié)點(diǎn)，u為全集U的規(guī)模；在應(yīng)用該法前，需將全集 U中所有位串(串長(zhǎng)為len)映射為有限域Fq(q≥2logu)中的元素，且必須事先知道d的上界值，若未知，則必須通過A、B之間的多輪消息交換估算出d的合理上界，其中消息交換傳送的求值總數(shù)每輪遞增c倍。此法需進(jìn)行插值與因式分解，計(jì)算時(shí)間復(fù)雜度為Θ(d3)。文獻(xiàn)[1]的作者后又改進(jìn)了該特征多項(xiàng)式插值法，使其只需Θ(d)計(jì)算時(shí)間復(fù)雜度，但以A、B之間更多的消息交換輪數(shù)(O(logpd))為代價(jià)，其中p為劃分系數(shù)[14]。一輪消息交換至少需一個(gè) RTT(常為1.5s)，這種多輪消息交換在很多對(duì)時(shí)間要求較高的系統(tǒng)中是應(yīng)該盡量避免的。

針對(duì)CPISync法在無法獲知對(duì)稱差大小時(shí)需多輪消息交換的缺點(diǎn)，文獻(xiàn)[17]提出了一種基于布魯姆過濾器的精確集合調(diào)和(BFESR, Bloom filter based exact set reconciliation)方法，首先使用2節(jié)點(diǎn)的布魯姆過濾器估算出2集合的對(duì)稱差規(guī)模，然后再運(yùn)行CPISync算法。BFESR算法中，可用來估算對(duì)稱差規(guī)模的方法有2種：內(nèi)積法和準(zhǔn)交集查詢法[17]。使用BFESR方法，若調(diào)用一次CPISync算法不能調(diào)和成功，則增加一定的特征多項(xiàng)式值再次調(diào)用CPISync調(diào)和算法,直到得到準(zhǔn)確的并集元素。由于 BFESR方法使用內(nèi)積法或準(zhǔn)交集查詢法獲取了對(duì)稱差規(guī)模的大致范圍，從而避免了文獻(xiàn)[1]所用的試探法需大量試探次數(shù)(消息交換輪數(shù))的缺點(diǎn)，僅需少量的消息交換次數(shù)即能實(shí)現(xiàn)集合調(diào)和。實(shí)驗(yàn)表明：大多數(shù)情況下僅需單輪消息交換即能成功，是一種調(diào)和效率高的精確集合調(diào)和方法。尤其值得注意的是，設(shè)準(zhǔn)交集查詢法估算出的對(duì)稱差規(guī)模為d0，若首輪消息交換即在節(jié)點(diǎn)間傳送(1+a)d0個(gè)特征多項(xiàng)式值，并選取合適的a值，則BFESR方法可使用單輪消息交換完成調(diào)和。如文獻(xiàn)[17]的實(shí)驗(yàn)環(huán)境中，取a=0.05則能在單輪消息交換后完成調(diào)和。

文獻(xiàn)[20]則提出了使用多個(gè)短的布魯姆過濾器進(jìn)行集合調(diào)和的方法。調(diào)和節(jié)點(diǎn)多次交換布魯姆過濾器和數(shù)據(jù)元素直到2節(jié)點(diǎn)包含相同的元素為止。該方法與文獻(xiàn)[18]中使用糾錯(cuò)碼和布魯姆過濾器的方法相比，具有較低的計(jì)算復(fù)雜度，但其代價(jià)是消耗較多的帶寬及需要較多的消息交換輪數(shù)。

2.2 近似集合調(diào)和

近似集合調(diào)和方法通常的調(diào)和步驟如下：節(jié)點(diǎn)A傳遞集合 SA的近似表示(如散列后的集合(hash(SA))[18]、比特向量布魯姆過濾器表示的集合(BF(SA))[18]或集合的近似調(diào)和樹[19](ART(SA))等)給節(jié)點(diǎn)B，節(jié)點(diǎn)B據(jù)此查詢SB中元素y是否包含在集合A的近似表示中，若查詢結(jié)果為是，則判定y不屬于差集SB-SA，若查詢結(jié)果為否，則判定y屬于差集SB-SA，節(jié)點(diǎn)B返回找到的SB-SA元素給節(jié)點(diǎn)A。

上述近似集合調(diào)和方法都存在如下可能：元素y( y ∈SB-SA)與元素x(x∈SA)的散列值或布魯姆過濾器表示相同，從而B錯(cuò)誤地判定 y ∈SA，以致不能得到SB-SA的所有元素。也就是說，這些近似集合調(diào)和方法在查詢差集時(shí)都存在假陰性誤判(false negatives)，即原本屬于SB-SA的元素可能被判為不屬于SB-SA。

最近，文獻(xiàn)[13]提出了一種使用 Difference Digest結(jié)構(gòu)的近似集合調(diào)和，本地節(jié)點(diǎn)傳遞由可逆布魯姆過濾器(IBF, invertible Bloom filter)[21]組成的Strata estimator給遠(yuǎn)程節(jié)點(diǎn)，遠(yuǎn)程節(jié)點(diǎn)據(jù)此估算出對(duì)稱差規(guī)模d值，并返回相應(yīng)的可逆布魯姆過濾器，本地節(jié)點(diǎn)對(duì)可逆布魯姆過濾器減運(yùn)算后得到的可逆布魯姆過濾器譯碼，獲取 SB-SA和SA-SB中的元素。該方法能以接近于1的概率使用單輪消息交換找出對(duì)稱差元素，從而達(dá)到調(diào)和的目的，其傳輸消息比特?cái)?shù)與 d log(u)成正比。這種方法與本文提出的方法都借助于布魯姆過濾器減運(yùn)算來完成調(diào)和，但Difference Digest法存在一定的調(diào)和失敗率，而本文提出的方法則能確保調(diào)和成功。

通常，近似集合調(diào)和方法僅需1輪消息交換即可得到SB-SA的大部分元素。此時(shí)，盡管可以使用糾錯(cuò)碼恢復(fù)其余未被找出的差集元素[18]，但該機(jī)制會(huì)增加實(shí)現(xiàn)難度及處理需求，從而其應(yīng)用受到限制。

精確集合調(diào)和中的特征多項(xiàng)式插值調(diào)和法在事先能確定|SA-SB|和|SB-SA|大致值的情況下，僅需單輪消息交換即能找出所有差集元素，如不能事先確定d的近似值，則需多輪消息交換才能恢復(fù)差集元素。文獻(xiàn)[20]中的精確集合調(diào)和方法由于需要多次交換布魯姆過濾器結(jié)構(gòu)，同樣存在需要多輪消息交換的缺點(diǎn)。而基于布魯姆過濾器的精確集合調(diào)和[17]雖然可通過參數(shù)的調(diào)整使得算法能以接近于1的概率使用單輪消息交換完成調(diào)和，但其無法保證 100%的一次插值成功率(即調(diào)用一次 CPISync插值算法即調(diào)和成功的概率)。近似集合調(diào)和過程盡管僅需單輪消息交換，但有少量差集元素會(huì)被遺漏。在不傳遞集合SA的完整形式且無法獲知|SB-SA|或|SA-SB|的情況下，本文提出的基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和方法能做到使用單輪消息交換獲得所有差集元素，不會(huì)產(chǎn)生遺漏。

3 基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和

3.1 計(jì)數(shù)布魯姆過濾器

布魯姆過濾器用于對(duì)集合進(jìn)行簡(jiǎn)潔表示，支持元素的快速成員查詢，同時(shí)帶有一定的假陽性比率，即有一定數(shù)量的不在集合中的元素被判為屬于該集合。標(biāo)準(zhǔn)布魯姆過濾器[22]能支持元素的插入及成員查詢，不支持元素的刪除。標(biāo)準(zhǔn)布魯姆過濾器由于使用比特向量表示元素集合，其中的單個(gè)比特只能取值0或1，0表示沒有元素映射到該位置，1表示有元素映射到該位置，而不能表示有多少個(gè)元素映射到該位置。計(jì)數(shù)布魯姆過濾器 (CBF,counting Bloom filter)[23]則用計(jì)數(shù)器向量代替標(biāo)準(zhǔn)布魯姆過濾器的比特向量，計(jì)數(shù)器的長(zhǎng)度為r，插入元素時(shí)將對(duì)應(yīng)的k(k為散列函數(shù)個(gè)數(shù))個(gè)計(jì)數(shù)器的值分別加1，刪除元素時(shí)將對(duì)應(yīng)的k個(gè)計(jì)數(shù)器的值分別減1。計(jì)數(shù)布魯姆過濾器除支持集合元素的插入與查詢外，還支持集合元素的刪除操作。計(jì)數(shù)布魯姆過濾器廣泛應(yīng)用于很多領(lǐng)域中，如：重復(fù)檢測(cè)[24]、高速緩存系統(tǒng)[25]、網(wǎng)絡(luò)測(cè)量[26]等。

在介紹使用計(jì)數(shù)布魯姆過濾器減運(yùn)算進(jìn)行集合調(diào)和的新方法之前，首先探討一下計(jì)數(shù)布魯姆過濾器減運(yùn)算的相關(guān)性質(zhì)。

3.2 計(jì)數(shù)布魯姆過濾器減運(yùn)算

定義1 (同源計(jì)數(shù)布魯姆過濾器) 對(duì)于全集U中的任意子集SA、SB，其計(jì)數(shù)布魯姆過濾器表示分別為CBF(SA)、CBF(SB)，若它們使用的k個(gè)散列函數(shù)為同一組散列函數(shù)，計(jì)數(shù)器向量長(zhǎng)度m相同，且計(jì)數(shù)器長(zhǎng)度r相等，則稱CBF(SA)、CBF(SB)為同源計(jì)數(shù)布魯姆過濾器。下文討論的均為同源計(jì)數(shù)布魯姆過濾器。

定義 2 (計(jì)數(shù)布魯姆過濾器的減運(yùn)算)如圖 2所示，對(duì)于計(jì)數(shù)布魯姆過濾器CBF(U)，CBF(SA)與CBF(SB)，令 CBF(U)i，CBF(SA)i，CBF(SB)i分別為它們的第i個(gè)計(jì)數(shù)器，CBF(SB)與CBF(SA)減運(yùn)算定義如下：

圖2 計(jì)數(shù)布魯姆過濾器減運(yùn)算

定義3 (計(jì)數(shù)布魯姆過濾器的大小關(guān)系) 2計(jì)數(shù)布魯姆過濾器CBF(SA)與CBF(SB)，若?i∈{1，…，m}，都有 CBF(SA)i≥CBF(SB)i，則稱 CBF(SA)大于等于 CBF(SB)，記為 CBF(SA)≥CBF(SB)；若?i ∈{1，…，m}，都有 CBF(SA)i=CBF(SB)i，則稱CBF(SA)等于 CBF(SB)，記為 CBF(SA)=CBF(SB)；若?i∈{1，…，m}，都有CBF(SA)i≤CBF(SB)i則稱 CBF(SA)小于等于 CBF(SB)，記為 CBF(SA)≤CBF(SB)。

引理1 對(duì)于全集中的任意子集SA、SB，其計(jì)數(shù)布魯姆過濾器表示分別為：CBF(SA)、CBF(SB)，若SA?SB，則必有CBF(SA)≤CBF(SB)。

證明 不失一般性，假設(shè)SA∩SB中元素先同時(shí)插入 CBF(SA)與 CBF(SB)中，此時(shí) CBF(SA)i=CBF(SB)i，i=1,…,m；而后差集SB-SA中元素插入CBF(SB)中，因 SA?SB，SB-SA為空集或非空集，則CBF(SA)i≤CBF(SB)i，i=1,…,m，即 CBF(SA)≤CBF(SB)。引理得證。

定理 1 對(duì)于全集 U 中的任意子集 SA、SB，CBF(SA)、CBF(SB)分別為它們的計(jì)數(shù)布魯姆過濾器表示，則 C BF( SB) - CBF( SA)≥ CBF( SB-SA)。

證明 若 C BF( SB-SA)i=Ci，1≤i≤m，因(SB-SA) ?SB，(SB- SA) ?，則據(jù)引理 1有：CBF( SB)i≥Ci且CBF()i≥Ci，1≤i≤m，又由計(jì)數(shù)布魯姆過濾器的構(gòu)造過程可知：CBF()i=CBF( U )i-CBF( SA)i)，從而可得：min(C BF( SB)i,(C BF( U )i-CBF( SA)i))≥ Ci, 1 ≤ i≤ m ,即(C BF( SB)-CBF( SA) )i≥ Ci, 1≤i≤ m ? 若 C BF( SB- SA)i= Ci，則必有(C BF( SB)- CBF( SA) )i≥ Ci，1≤i≤m。

因此，(C BF( SB) - CBF( SA))≥ CBF( SB-SA)。定理得證。

推論1 使用CBF減運(yùn)算 C BF( SB) - CBF( SA)查詢SB中的差集SB-SA元素時(shí)能找出所有SB-SA元素，即CBF減運(yùn)算 C BF( SB) - C BF( SA)查詢差集時(shí)不存在假陰性誤判。

證明 設(shè) Q1、Q2分別為使用 C BF( SB)-CBF( SA)、 C BF( SB- SA)查詢到的數(shù)據(jù)集合，由定理1可知，Q1包含Q2，又由于使用 C BF( SB- SA)查詢 SB-SA時(shí)無假陰性但存在假陽性，即 Q2包含SB-SA，從而可得，Q1包含SB-SA。也就是說，使用CBF( SB) - C BF( SA)查詢到的數(shù)據(jù)集合包含所有SB-SA元素，推論得證。

3.3 基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和

本文提出的基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和方法分為如下幾個(gè)步驟。

Step1 節(jié)點(diǎn)A構(gòu)造CBF(SA)，并將之傳送給節(jié)點(diǎn)B。

Step2 節(jié)點(diǎn)B進(jìn)行CBF減運(yùn)算，得到過濾器CBF(SB)-CBF(SA)。

Step3 節(jié)點(diǎn) B使用 CBF(SB)-CBF(SA)查詢 SB中元素是否屬于SB-SA，獲得全部SB-SA元素及少量交集SA∩SB元素，并返回給節(jié)點(diǎn)A。

Step4 節(jié)點(diǎn)A將Step3中節(jié)點(diǎn)B返回的結(jié)果集與SA合并，得到完整的SA∪SB。

算法的Step 3中，節(jié)點(diǎn)B找出的結(jié)果集中包含SB-SA中全部元素，也包含少量SA∩SB中元素(其數(shù)量取決于CBF()的假陽性概率，參見定理3)，交集元素的少量冗余并不影響算法接下來的集合并運(yùn)算(即Step 4)的結(jié)果。本文將這一方法稱為基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和(CBFSR, counting Bloom filter based set reconciliation)。

首先定義調(diào)和率和冗余率，將二者作為評(píng)估調(diào)和算法性能的2個(gè)指標(biāo)，然后在此基礎(chǔ)上對(duì)CBFSR算法的性能進(jìn)行理論分析。

定義4 (調(diào)和率)集合調(diào)和過程中，設(shè) B返回給A的元素集合為Ssub，Ssub中SB-SA元素個(gè)數(shù)設(shè)為Srecon，Srecon與差集規(guī)模|SB-SA|的比率，稱調(diào)和率(reconciliation ratio)。其計(jì)算公式為：

定義5 (冗余率)集合調(diào)和過程中，B返回給A的集合 Ssub中 SB∩SA元素個(gè)數(shù)設(shè)為 Sredun，Sredun與差集規(guī)模|SB-SA|的比率，稱冗余率(redundancy ratio)。其計(jì)算公式為：

定理2 CBFSR法調(diào)和過程中，節(jié)點(diǎn)B在使用CBF(SB)-CBF(SA)查詢 SB中元素是否屬于 SB-SA時(shí)能找出所有SB-SA元素，其調(diào)和率為100%。

證明 1)若 x ∈ SB- SA，則CBF( SB)hj(x)≥1,j=1,…,k;2)x∈SB-SA→x∈ U ∩ x?SA→(C BF( U )hj(x)-CBF( SA)hj(x))≥ 1, j = 1 ,… ,k。

由1)、2)及定義2得：

min(C BF( SB)hj(x),(C BF( U )hj(x)-CBF( SA)hj(x)))≥1, j = 1 ,… ,k即(C BF( SB) - CBF( SA) )hj(x)≥ 1, j=1,… ,k 。也就是說，只要元素 x屬于 SB-SA，則CBF(SB)-CBF(SA)中對(duì)應(yīng)x的所有計(jì)數(shù)器一定非0，從而判定x屬于SB-SA，不會(huì)被判為不屬于SB-SA。CBFSR法中節(jié)點(diǎn)B能找出所有SB-SA元素返回給節(jié)點(diǎn)A，其調(diào)和率為100%。定理得證。

定理 3 CBFSR法調(diào)和過程中，在使用CBF(SB)-CBF(SA)查詢 SB中元素是否屬于差集SB-SA時(shí)，會(huì)有少量不在 SB-SA中的元素(即少量 SA∩SB元素)被誤判為屬于SB-SA，即使用CBF(SB)- CBF(SA)進(jìn)行差集查詢時(shí)存在假陽性誤判，SA∩SB中元素被誤判為差集SB-SA元素的概率為CBFSR法的冗余率為100%。

證明

1) 若 x ∈SA∩SB，則必有：CBF( SB)hj(x)≥1,j = 1 ,… ,k ，此時(shí)只要CBF()hj(x)≥1, j = 1,… ,k，則必有min(C BF( SB)hj(x),(C BF( U )hj(x)-CBF( SA)hj(x)))≥1, j = 1 ,… ,k,即(C BF( SB) - CBF( SA) )hj(x)≥1,j=1,… ,k 。也就是說，使用CBF(SB)-CBF(SA)查詢SA∩SB中元素是否屬于SB-SA時(shí)存在假陽性，其假陽性誤判概率fp與CBF()的假陽性概率相同，等于即查詢過程的假陽性誤判概率取決于與|SB-SA|、|SA∩SB|無關(guān)。

2)由1)可知，SA∩SB中有 fp|SA∩SB|個(gè)元素在 Ssub中，從而 CBFSR法的冗余率為定理得證。

4 性能分析與實(shí)驗(yàn)比較

4.1 性能分析

將本文的CBFSR算法與已有的5個(gè)調(diào)和算法進(jìn)行性能的對(duì)比分析，用于比較的5個(gè)算法如下。

算法 1 使用比特向量布魯姆過濾器的近似集合調(diào)和算法，本文將其稱為BFSR(Bloom filter based set reconciliation)[18]法，其具體過程如下：節(jié)點(diǎn) A傳遞比特向量布魯姆過濾器表示的集合(BF(SA))給節(jié)點(diǎn)B，節(jié)點(diǎn)B據(jù)此查詢SB中元素y對(duì)應(yīng)的k個(gè)散列位置在BF(SA)中是否全為1，若是，則判定y屬于SB∩SA，否則，判定y不屬于SB∩SA。由于這一交集查詢過程中存在少量假陽性，節(jié)點(diǎn)B僅能找出SB-SA大部分元素。最后，節(jié)點(diǎn)B返回這部分SB-SA元素給節(jié)點(diǎn)A，執(zhí)行集合并運(yùn)算SA∪(SB-SA)，得到SA∪SB的大部分元素，完成近似集合調(diào)和。

算法2 使用近似調(diào)和樹的近似集合調(diào)和算法，本文稱其為ART法，該算法中近似調(diào)和樹的構(gòu)造較為復(fù)雜，由于篇幅所限，算法具體步驟參見文獻(xiàn)[19]。

算法 3 Difference Digest法[13]，Difference Digest結(jié)構(gòu)由Strata Estimator和IBF 2部分組成。節(jié)點(diǎn)A首先發(fā)送其構(gòu)造的Strata Estimator給對(duì)方節(jié)點(diǎn)B，B使用該 Strata Estimator估算出 d，構(gòu)造出合適的IBF(B)返回給A，A使用IBF減運(yùn)算計(jì)算出IBF(A)-IBF(B)，并對(duì)IBF(A) -IBF(B)進(jìn)行譯碼得到SB-SA和SA-SB。

算法4 CPISync法，即2.1節(jié)介紹的特征多項(xiàng)式插值法，是一種精確集合調(diào)和算法，算法具體步驟參見2.1節(jié)介紹和文獻(xiàn)[1]。

算法5 改進(jìn)的CPISync法，是特征多項(xiàng)式插值法的一種改進(jìn)算法，參見2.1節(jié)介紹和文獻(xiàn)[14]。

表 1列出了上述 5種集合調(diào)和方法和本文CBFSR算法的性能分析結(jié)果。其中，節(jié)點(diǎn)間的傳輸消息比特?cái)?shù)僅列出了節(jié)點(diǎn)A傳送給節(jié)點(diǎn)B的消息比特?cái)?shù)；對(duì)于節(jié)點(diǎn) B返回給節(jié)點(diǎn) A的消息比特?cái)?shù)，CBFSR法為O(|SB-SA|+|SA∩SB|)，Difference Digest法為 O(|SA-SB|+|SB-SA|)，其他調(diào)和方法均為O(|SB-SA|)，各方法差別不大。

由于CBF用r位計(jì)數(shù)器代替BF的二進(jìn)制位，CBFSR法調(diào)和過程中 A節(jié)點(diǎn)需傳送給 B節(jié)點(diǎn)O(rm)bit信息，BFSR法僅需傳送O(m)bit消息，其中 m為計(jì)數(shù)器向量大小或比特向量大小。設(shè)法中，當(dāng)m/n值確定時(shí)，為保證SA∩SB中元素被誤判為SB-SA中元素的可能性最小，需取k=ln2(m/n)。例，若m/n=6，則k取值4時(shí)，的假陽性誤判概率值 fp近似最小，計(jì)算得其fp=5.61%。若r=4，CBFSR法中節(jié)點(diǎn)A需傳送給節(jié)點(diǎn)B的消息比特?cái)?shù)等于4m，由B返還A的元素集合中包含全部SB-SA元素，也包含大約5.61%的SA∩SB元素，即調(diào)和率為 100%，冗余率為而BFSR法A節(jié)點(diǎn)需傳送給B節(jié)點(diǎn)mbit消息，但約有的 SB-SA中元素被遺漏，若 u=2|SA|=2n，則大約 5.61%的差集元素被遺漏，即調(diào)和率為94.39%。

表1 各集合調(diào)和方法性能分析

CBFSR法可以找出SB-SA中所有元素，調(diào)和率為100%；由于CBF可支持刪除操作，因此CBFSR法適用于更新頻繁的系統(tǒng)環(huán)境；與BFSR法比較，CBFSR法多一次CBF減運(yùn)算，需要r(如r=4)倍于BFSR法的傳輸消息比特?cái)?shù)及節(jié)點(diǎn)在首次與源節(jié)點(diǎn)或?qū)Φ裙?jié)點(diǎn)建立聯(lián)系時(shí)需得到CBF(U)。

ART法調(diào)和率取決于校正系數(shù)和分支系數(shù)，達(dá)不到100%；而CBFSR法調(diào)和率始終為100%，但傳輸消息比特?cái)?shù)是ART法的r倍。

Difference Digest法與本文提出的CBFSR法都借助于布魯姆過濾器減運(yùn)算來完成調(diào)和，但Difference Digest法存在一定的調(diào)和失敗率，盡管該概率較小，在使用適當(dāng)參數(shù)配置的條件下不超過O(d-k)[13]，而CBFSR法則能確保調(diào)和成功。

與調(diào)和率同樣為 100%的特征多項(xiàng)式調(diào)和法(CPISync法和改進(jìn)的CPISync法)相比，CBFSR法具有僅需單輪消息交換、計(jì)算簡(jiǎn)單的優(yōu)點(diǎn)。

4.2 實(shí)驗(yàn)比較

在分布式網(wǎng)絡(luò)系統(tǒng)中，為實(shí)現(xiàn)集合調(diào)和，精確集合調(diào)和法中的CPISync法和改進(jìn)的CPISync法通常需要多輪消息交換，網(wǎng)絡(luò)延時(shí)較高，本文實(shí)驗(yàn)不考慮此類需多輪消息交換的算法。BFSR法、ART法等近似集合調(diào)和法與 CBFSR法一樣，只需單輪消息交換，模擬實(shí)驗(yàn)中考察了BFSR法、ART法、CBFSR法3種調(diào)和算法，在調(diào)和率、冗余率等方面對(duì)它們進(jìn)行比較。

實(shí)驗(yàn)中全集規(guī)模u=20 000，子集規(guī)模|SA|= |SB|=10 000，散列函數(shù)個(gè)數(shù)k=6，CBF或BF向量大小m=80 000，|SB-SA|取值范圍為[100，9 000]。實(shí)驗(yàn)結(jié)果取100次實(shí)驗(yàn)的數(shù)據(jù)平均值。

ART法中校正系數(shù)c取0或2，分支系數(shù)b取2或4。b=2時(shí)的近似調(diào)和樹稱二叉調(diào)和樹，b=4的近似調(diào)和樹則稱四叉調(diào)和樹。

由圖 3可見，CBFSR法的調(diào)和率始終為100%，與|SB-SA|、u、k、m 等參數(shù)設(shè)置無關(guān)。BFSR法的調(diào)和率取決于 k、m 及|SA|的值，與|SB-SA|的取值無關(guān)，實(shí)驗(yàn)結(jié)果非常集中地位于期望值97.84%附近。在4種不同參數(shù)設(shè)置的調(diào)和樹中，校正系數(shù)為0的二叉調(diào)和樹的調(diào)和率最低，約為71.71%。校正系數(shù)為2的四叉調(diào)和樹的調(diào)和率最高，約為97.71%，與BFSR法的調(diào)和率極為接近。由本文實(shí)驗(yàn)結(jié)果可看出，ART法的調(diào)和率與|SB-SA|的取值無關(guān)，取決于校正系數(shù)和分支系數(shù)，校正系數(shù)和分支系數(shù)越大，ART法的調(diào)和率越高，選取足夠大的校正系數(shù)和分支系數(shù)，可使ART法的調(diào)和率趨近于1。

圖3 調(diào)和率

BFSR法、ART法等近似集合調(diào)和方法不存在冗余率，只有 CBFSR法存在冗余，當(dāng)全集規(guī)模與子集規(guī)模取值確定時(shí)，其冗余率隨差集規(guī)模|SB-SA|不同而不同，其變化趨勢(shì)如圖 4所示。冗余率與|SB-SA|成反比，差集越大，冗余率越小。本實(shí)驗(yàn)中，當(dāng)|SB-SA|達(dá)9 000時(shí)，冗余率僅為0.24%。但冗余率的大小除與|SB-SA|有關(guān)外，還取決于k、m、u和|SA|，當(dāng)其他參數(shù)相同，而u值較大、|SA|較小時(shí)，冗余率會(huì)隨之增加。當(dāng)冗余率較大時(shí)，會(huì)造成較多的帶寬浪費(fèi)，而當(dāng)u和|SA|值相差不大時(shí)，則冗余率小，從而帶寬浪費(fèi)較小。

圖4 基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和冗余率

根據(jù)定理 3，CBFSR法調(diào)和過程中，交集(SA∩SB)中元素被誤判為 SB-SA元素的概率與的規(guī)模(u-|SA|)有關(guān)，其期望值為在前述實(shí)驗(yàn)設(shè)置中，誤判概率期望值為2.16%。圖5中的直線為SA∩SB元素用CBF(SB)-CBF(SA)查詢的假陽性期望值，曲線為差集規(guī)模取不同值時(shí)的誤判實(shí)測(cè)值。由圖5可見，實(shí)測(cè)值非常一致地集中于期望值附近，說明定理3的分析是正確的。

圖5 CBFSR法交集元素被判為SB-SA元素的概率

由上述算法分析及模擬實(shí)驗(yàn)結(jié)果可得出基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和法在應(yīng)用前需事先獲得 CBF(U)，這一操作可以在節(jié)點(diǎn)首次加入網(wǎng)絡(luò)時(shí)完成，節(jié)點(diǎn)與遠(yuǎn)程節(jié)點(diǎn)在調(diào)和時(shí)(可能是多次調(diào)和)不再需要此操作，從而該方法以較小的冗余率、傳輸消息數(shù)倍于BFSR等近似集合調(diào)和法為代價(jià)，使得節(jié)點(diǎn)間僅需單輪消息交換即能實(shí)現(xiàn)調(diào)和率達(dá)100%，是一種簡(jiǎn)單、可靠的調(diào)和方法。

5 結(jié)束語

本文首先通過理論分析和模擬實(shí)驗(yàn)證明：計(jì)數(shù)布魯姆過濾器的減運(yùn)算能支持集合的差集查詢。利用這一結(jié)論，設(shè)計(jì)了基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和方法，數(shù)據(jù)集合用CBF表示，利用CBF減運(yùn)算得到的新過濾器 CBF(SB)-CBF(SA)找出 SB中屬于SB-SA的元素，完成集合并運(yùn)算 SA∪(SB-SA)，得到SA∪SB，實(shí)現(xiàn)集合調(diào)和。研究結(jié)果表明，基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和法兼具已有集合調(diào)和方法的優(yōu)點(diǎn)，其算法簡(jiǎn)單，節(jié)點(diǎn)間僅需一次消息交換就能找出所有差集元素，實(shí)現(xiàn)精確集合調(diào)和，支持集合元素的動(dòng)態(tài)刪除，適合于更新頻繁的系統(tǒng)環(huán)境。

接下來的工作重點(diǎn)是將本文提出的基于計(jì)數(shù)布魯姆過濾器的集合調(diào)和法更進(jìn)一步應(yīng)用于實(shí)際分布式系統(tǒng)，如分布式數(shù)據(jù)庫與文件系統(tǒng)、閑談協(xié)議、移動(dòng)數(shù)據(jù)庫同步等系統(tǒng)，并優(yōu)化其性能。

[1] MINSKY Y, TRACHTENBERG A, ZIPPEL R. Set reconciliation with nearly optimal communication complexity[J]. IEEE Information Theory, 2003, 49(9): 2213-2218.

[2] DECANDIA G, HASTORUN D, JAMPANI M, et al. Dynamo:amazon's highly available key-value store[A]. Proceedings of the 21st ACM SIGOPS Symposium on Operating Systems Principles[C]. New York, NY, USA, 2007. 205-220.

[3] 付波, 李建平, 文曉陽. 基于集合調(diào)和的遠(yuǎn)程口令恢復(fù)方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2009, 26(6): 2113-2116.FU B, LI J P, WEN X Y. Remote password recovery using set reconciliation[J]. Application Research of Computers, 2009, 26(6):2113-2116.

[4] ELKOUSS D, MARTINEZ J, LANCHO D, et al. Rate compatible protocol for information reconciliation: an application to QKD[A].Proceedings of the Information Theory Workshop (ITW)[C]. 2010.145-149.

[5] GUO K, HAYDEN M, VAN RENESSE R, et al. GSGC: An Efficient Gossip-Style Garbage Collection Scheme for Scalable Reliable Multicast[R]. Cornell University, 1997.

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

[7] VAN RENESSE R. Scalable and secure resource location[A].Proceedings of the International Conference on System Sciences[C].2000. 1530-1605.

[8] Data domain[EB/OL]. http://www.datadomain.com.

[9] ZHU B, LI K, PATTERSON H. Avoiding the disk bottleneck in the data domain deduplication file system[A]. Proceedings of the 6th USENIX Conference on File and Storage Technologies[C]. San Jose,California, 2008. 1-14.

[10] KULKARNI P, DOUGLIS F, LAVOIE J, et al. Redundancy elimination within large collections of files[A]. Proceedings of the Annual Conference on USENIX Annual Technical Conference[C].Boston, MA, 2004.

[11] BOLOSKY W J, CORBIN S, GOEBEL D, et al. Single instance storage in Windows 2000[A]. Proceedings of the 4th Conference on USENIX Windows Systems Symposium[C]. Seattle, Washington, 2000.

[12] BYERS J W, LUBY M, MITZENMACHER M. Accessing multiple mirror sites in parallel: using Tornado codes to speed up downloads[A]. Proceedings of the IEEE INFOCOM 1999[C]. New York, NY , USA 1999. 275-283.

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

[14] MINSKY Y, TRACHTENBERG A. Practical Set Reconciliation[R].BUECE 2002-01. Boston University, 2002.

[15] MINSKY Y, TRACHTENBERG A. Efficient Reconciliation of Unordered Databases[R]. TR1999-1778. Cornell University, 1999.

[16] AGARWAL S, CHAUHAN V, TRACHTENBERG A. Bandwidth efficient string reconciliation using puzzles[J]. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(11): 1217-1225.

[17] TIAN X M, ZHANG D F, XIE K, et al. Exact set reconciliation based on Bloom filters[A]. Proceedings of the International Conference on Computer Science and Network Technology[C]. Harbin, China, 2011.2001-2009.

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

[19] BYERS J, CONSIDINE J, MITZENMACHER M. Fast Approximate Reconciliation of Set Differences[R]. BU Computer Science TR 2002-19.Boston University, 2002.

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

[21] EPPSTEIN D, GOODRICH M T. Straggler identification in round-trip data streams via newton's identities and invertible Bloom filters[J]. IEEE Transaction on Knowledge and Data Engineering, 2011, 23(2): 297-306.

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

[23] FAN L, CAO P, ALMEIDA J, et al. Summary cache: a scalable wide-area web cache sharing protocol[J]. IEEE/ACM Transactions on Networking(TON), 2000, 8(3): 281-293.

[24] WEI J, JIANG H, ZHOU K, et al. Detecting duplicates over sliding windows with ram-efficient detached counting Bloom filter arrays[A].Proceedings of the 6th IEEE International Conference on Networking,Architecture and Storage[C]. 2011. 382-391.

[25] AHMADI M, WONG S. A Cache architecture for counting Bloom filters:theory and application[J]. Journal of Electrical and Computer Engineering,2011, (1): 1-10.

[26] 吳樺, 龔儉, 楊望. 一種基于雙重Counter Bloom Filter的長(zhǎng)流識(shí)別算法[J]. 軟件學(xué)報(bào), 2010, 21(5): 1115-1126.WU H, GONG J,YANG W. Algorithm based on double counter Bloom filter for large flows identification[J]. Journal of Software, 2010,21(5):1115-1126.