針對動態集的矩陣型Ｂｌｏｏｍ ｆｉｌｔｅｒ表示與查找
2008-12-31 00:00:00肖明忠王佳聰閔博楠
計算機應用研究 2008年7期
摘 要：提出一種針對動態集合的矩陣型Bloom filter表示與查找法（matrix Bloom filter，MBF），它使用一個s×m位矩陣對數據集合進行哈希表示與查找，較同類算法SBF和DBF，能繼承Bloom filter算法常數查找開銷的基本精髓。
關鍵詞：Bloom過濾器；動態集；拆分型Bloom filter；動態性Bloom filter；矩陣型Bloom filter
中圖分類號：TP391 文獻標志碼：A
文章編號：1001-3695(2008)07-2001-03
Matrix Bloom filter on dynamic set
XIAO Mingzhong，WANG Jiacong，MIN Bonan
(Networking Laboratory，School of Electronic Engineering Computer Science， Peking University， Beijing 100871， China)
Abstract:This paper presented matrix Bloom filter (MBF)， which used as×m bit matrix for data represent and query.Compared to SBF and DBF， it more accurately represented the essential characteristics of Bloom filter for its constant query time.
Key words:Bloom filter；dynamic set；split Bloom filter(SBF)；dynamic Bloom filter(DBF)；MBF
0 引言
表示和查找信息是大多數計算機應用程序的核心，這兩個過程是密切相關的。例如，采用順序表表示信息則可以使用折半查找；采用哈希表組織信息則可以使用哈希查找。表示就是以計算機能處理的方式把信息組織成為可計算的實體；查找就是確定一個具有特定值的元素是不是一個特定集合的成員[1]。
Bloom filter使用一個位串對數據集合進行哈希表示與查找，其基本精髓體現在壓縮表示和常數查找開銷，近年來在大規模分布式系統中得到了廣泛應用[2]。如圖1所示的P2P文件共享系統結構模型中，Bloom filter扮演了一個很重要的角色。
每個對等用戶都有很多的文件要共享，在節點之間互相傳遞共享的文件元數據信息將會消耗掉大量的時間和帶寬。利用Bloom filter，每個節點都可以將它所擁有的資源表示成一個位串，然后再將這些位串發送給附近的超級節點。這樣，每個超級節點就收集有附近節點的共享信息。
假設節點P5想要查找在對等網絡中哪個節點上的文件f，它首先將這個請求發送給超級節點2。超級節點2在自己所收集的Bloom filter串集合中進行查找，如果在超級節點2沒有找到文件f，這個查詢請求就會被以flooding方式轉發給其他所有超級節點處理，直到查詢包TTL值為零或是在某個超級節點找到目標文件f的位置。
Bloom filter的主要改進型包括壓縮型Bloom filter[3]、計數型Bloom filter[4]、空間碼Bloom filter[5]以及光譜型Bloom filter[6]，所有這些表示與查找算法都是針對靜態集合設計。然而在實際的應用系統中，只有很少的系統使用靜態集，絕大多數的應用處理的是動態數據集合。動態型Bloom filter（DBF）[7]和拆分型Bloom filter（SBF）[8]可以支持動態集合的表示和查找，但是它們均違背了Bloom filter查找常數開銷的基本精髓。
1)相關工作
（1）Bloom filter[9]
Bloom filter使用長為m的位串V表達數據集合A={a1，a2，…，an}。在初始的時候，位串的所有位都是0。設有k個具有均勻分布特性的哈希函數h1，h2，…，hk，且x∈A，hi(x)∈{1，2，…，m}。對每一個集合A中的元素x，利用k個哈希函數將位串的第hi(x)位置為1。最后，數據集合A被壓縮表示成一個Bloom filter位串。查找某個元素是否屬于該集合時，只需使用這些哈希函數作用該元素，查看位串相應的位是否為1即可。
上述表示法由于哈希函數的沖突性，會導致某個元數不屬于集合A，而被誤稱屬于的可能性，簡稱誤稱率。假設hash函數是均勻隨機分布的，一個元素被誤稱的概率可作如下定義： 令p表示位串中的某位在對n個集合元素表示結束時仍為0的概率，顯然p=(1-1/m)nk≈e-nk/m。式（1）中的PerrBF(m，k，n)就是表示算法的誤稱率。
PerrBF(m，k，n)=(1-p)k≈(1-e-kn/m)k(1)
（2）動態型Bloom filter
DBF的基本思想是把一個動態集合A表示成一個s×m的位矩陣，這個位矩陣是由s個標準的Bloom filter位串組成。s的初始值為1，但是它可以隨著集合元素的持續增長而不斷增大，如圖2所示。
在初始化時，s被設置成1，所以Bloom filter 1就是當前的活躍Bloom filter位串。在每次向Bloom filter位串中加入元素時，檢查當前的活躍Bloom filter位串中的元素是否達到了設定的上限值n0。如果沒有，就把元素表示到當前活躍的Bloom filter位串中。如果達到了上限值，則首先把當前的活躍Bloom filter位串設置成不活躍，然后創建一個新的Bloom filter位串來作為當前的活躍Bloom filter位串，把s的值加1。然后用同樣的方法把元素表示到當前的活躍Bloom filter位串中。易知，DBF中只有最后一個Bloom filter位串永遠是活躍的，這意味著它的元素個數沒有達到n0，且它之前的所有Bloom filter位串都被設置成不活躍。
(3)拆分型 Bloom filter
SBF使用不變的s×m的位矩陣來表示一個集合。這里s是一個常量，必須按照對集合尺寸的最大值的估計預先確定好。這種估計可能是基于集合尺寸增長的歷史記錄或者其他的一些因素，其工作原理如圖3所示。在每次添加表示元素前，隨機選擇一個Bloom filter位串，然后按照傳統Bloom filter算法進行表示。假設所選擇方法是完美隨機的，則所有的Bloom filter位串中表示的元素個數都應該是相同的，其值為n/s。
2)本文貢獻
盡管DBF和SBF都聲稱它們使用s×m的位矩陣來表示一個動態集合A，但是實際上它們不是真正的矩陣表示法。因為矩陣必須是二維的，有行向量和列向量。基于這種基本的定義，DBF和SBF所使用的不過是s個m位的Bloom filter位串，而不是一個s×m的位矩陣。此外，這兩種表示法在查找一個集合元素時，都需要遍歷s個Bloom filter位串，所以它們查找一個元素的平均時間復雜度為O(k(s+1)/2)。s是由集合中元素的個數n決定的，所以平均時間復雜度近似為O（n），而不是一個常數。這偏離了傳統Bloom filter表示法O（k）常數查找開銷的基本精神。
本文設計了一種新的Bloom filter——矩陣型Bloom filter，用來表示一個動態集合。它使用s×m的位矩陣，而不是s個m位的Bloom filter串。并且，MBF可以把平均時間復雜度限制在常數時間開銷。
1 矩陣型Bloom filter
MBF的基本思想是將動態集合A表示成一個s×m的位矩陣，這個位矩陣擁有s行和m列。這里s是一個常量，必須按照對集合尺寸的最大值的估計而預先確定好。
為了達到平均時間復雜度為O（k）這個目標，本文設計了一種方法來快速地定位元素所要加入的行。當執行查詢的時候，檢查一行中的k個位是否都被置成了1需要花費的時間為O（k），因此，定位該行所需要的時間必須為一個常數。使用哈希函數來完成這項任務，在每個元素添加之前，MBF會使用一個哈希函數來指定該元素所要加入的行。
為了構建一個MBF，必須首先按照應用的需要確定m和每一行的誤稱率，而且還要計算hash函數的個數k以及每一行所能容納的最大的元素個數n0。
1)算法設計
算法1 將一個元素添加到MBF中
addElement(object element)
bitMatrix MBF_addElement(bitMatrix MBF，object ele)
{
if(MBF == 1){
MBF=new bitMatrix();
}
int row=h1(ele);
for(int i=2; i<=k+1; i++){
MBF[row][hi(ele)]=1;
}
return MBF;
}
算法2 將集合A中的所有元素添加到MBF中
represent (set A， int s， int m)
bitMatrix MBF_represent(set A， int s， int m)
{
bitMatrix MBF=new bitMatrix(s，m);
for(int j=1;j<=n;j++){
MBF=MBF_addElement(MBF， A[j]);
}
return MBF;
}
在每個元素添加之前，需要確認這個元素應該被添加到哪一行中，所以使用第一個hash函數h1來做這項工作。h1是一個特殊的hash函數，不同于在MBF中用到的其他hash函數。因為MBF有s行，h1的hash范圍為{1，…，s}；而其他hash函數的范圍為{1，…，m}，因為MBF有m列。因此，在構建MBF前，hash函數的個數k不是真正用在MBF中的個數。實際上，將要使用k+1個hash函數，其中h1是被特別定義的。當要添加一個元素到MBF中時，首先使用hash函數h1來決定行，參見算法1中的語句：row=h1(ele)；然后在這一矩陣行中，使用其余的hash函數h2到 hk+1，對于2≤i≤k+1，將hi(ele)位置為1。假設哈希函數h1是完美隨機的，這樣，每一行中的元素個數應該是相同的，均為n/s。其工作原理如圖4所示。
一旦一個動態集合A被表示成了MBF，可以通過算法3來檢查一個元素x是否是集合A的一個元素。
算法3 query(bitMatrix MBF，object ele)
boolean MBF_Query(bitMatrix MBF，object ele)
{
int i=2;
int row=h1(ele);
while(MBF[row][hi(ele)]==1 i<=k+1);
i++;
if(i≤k+1)
return 1;
else return true;
}
這個算法的主要過程如下：對于元素x，首先利用hash函數h1計算這個元素可能被添加到哪一行中;然后在這一行中，對于2≤i≤k+1，檢查是不是所有的hi(x)位都被置為1。如果不是，可以確定x不是集合A的一個元素；否則，可以以一定的誤稱率認為x是集合A的一個元素。
2)算法分析
從平均時間復雜度和誤稱率的角度來對算法進行理論分析。為了計算平均時間復雜度，本文把元素的添加過程分為兩步：a)使用特殊定義的哈希函數h1來決定元素應該被添加到哪一行，這會花費O（1）的時間；b)使用其余的k個哈希函數把元素對應的位置映射為1，這會花費O（k）的時間。因此，添加一個元素到MBF中的平均時間復雜度為O（k）。從MBF中查詢一個元素的平均時間復雜度，其計算過程和添加一個元素類似。因此，查詢過程的平均時間復雜度也是O（k），是一個常數時間。
通過以上的分析可以看到，MBF在查找的平均時間復雜度上比起DBF和SBF要好。下面討論MBF的誤稱率。
如果一個元素x不是動態集合A的一個成員，但在MBF中查詢時，MBF卻返回“yes”，則誤稱便發生了。這個概率可以用下面的方法來計算。首先假設hash函數是完全隨機的，那么在每一行中，所添加進的元素的個數均為n/s。對于1≤i≤s，MBF的第i行的行誤稱率為PBFerr(m，k，n/s)，則MBF中所有的Bloom filter矩陣行都不誤稱的概率為
(1-PBFerr(m，k，n/s))s
因此，至少有一個Bloom filter矩陣行誤稱的概率（也就是整個MBF的誤稱率）為
PMBFerr(m，k，n)=1-（1-PBFerr(m，k，n/s))s=1-(1-e-kn/ms)k)s(2)
2 比較研究
下面將比較MBF和傳統的Bloom filter的性能，平均時間復雜度和誤稱率是性能的兩個重要量度。
對MBF來說，添加和查詢算法的平均時間復雜度均為O（k），對傳統的Bloom filter來說，平均時間復雜度也都為O（k）。因此，MBF在平均時間復雜度上并不比傳統的Bloom filter有優勢；但是在誤稱率上，它們的表現是不同的。
本文用傳統的Bloom filter和MBF來表示同一個動態集合A。對于傳統的Bloom filter，誤稱率可以被如下計算：
PerrBF(m，n，k)=(1-e-kn/ms)k
在MBF中，誤稱率為
PerrMBF(m，n，k)=1-(1-(e-kn/ms)k)s
在MBF和傳統的Bloom filter中用到的哈希函數的個數設定為5，MBF中的行誤稱率與傳統的Bloom filter相同。比較結果如圖5所示。
從圖5中可以看到，為了表示同一個動態集合A，MBF可以獲得更好的誤稱率；并且，MBF的行數越多，誤稱率越低。同時，相比于傳統的Bloom filter，MBF可以更好地支持集合大小n的增長。誠然，MBF使用s倍的空間開銷。
下面將把MBF應用在一個流行的P2P文件共享應用Maze系統[10]中。內容控制是Maze系統的一項重要功能，用于實現系統范圍內非法共享內容的過濾。中心服務器維持著一個被禁止共享文件的列表，每一個用戶在登入系統時會從中心服務器獲得這個禁止列表。禁止列表是一個動態集合，可能有成千上萬項，每一項包含有被禁止文件的屬性，如MD5值、文件大小等。從中心服務器發送這個禁止列表到各個用戶會花費掉很多時間和帶寬，并且，維護這個巨大的禁止列表也會占用很多空間。因此，使用Bloom filter會使情況好很多。
在接下來的實驗中把禁止列表表示成一個MBF，然后同未使用MBF時比較系統的性能。
首先需要確定MBF中每一行的長度m。在這個實驗中會使用到五個MBF：m=2n， m=3n， m=5n， m=10n以及 m=30n。在MBF中所使用到的哈希函數的個數為5，設定的最大誤稱率為10-4。帶寬的消耗如圖6所示。
用戶向中心服務器請求禁止列表時的延遲情況如圖7所示。這里的延遲是指，從用戶向服務器發出請求，直到該用戶得到禁止列表的總的時間。
比起直接交換原始禁止共享列表來說，MBF可以很好地節省帶寬消耗和縮小獲取列表的延遲。
3 結束語
Bloom filter使用一個位串對靜態數據集合進行壓縮表示并支持哈希查找操作，近年來在大規模P2P系統中得到了廣泛應用。DBF和SBF使用多個Bloom filter位串來實現動態集合的表示與查找，但它們均違背了Bloom filter常數查找開銷的精髓。本文提出了MBF用來表示動態集合，其在哈希表示的同時也完全能做到哈希查找。通過對MBF算法進行的分析證明了其在平均時間復雜性和誤稱率方面的良好特點，并被實際用于指導Maze系統非法共享內容過濾功能的設計。
參考文獻：
［1］
SHAFFER C A.Data structures and algorithm analysis[M].[S.l.]:Prentice Hall，1997.
[2]肖明忠，代亞非.Bloom filter及其應用綜述[J].計算機科學，2004，31(4):180184.
[3]MITZENMACHER M.Compressed Bloom filters[C]//Proc of Annual ACM Symposium on Principles of Distributed Computing.New York:ACM Press，2001:144150.
[4]FAN Li，CAO Pei，ALMEIDA J，et al.Summary cache:a scalable widearea Web cache sharing protocol[J].IEEE/ACM Trans on Networking，2000，8(3):281-293.
[5]KUMAR A，XU Jun，WANG Jia，et al.Spacecode Bloom filter for efficient perflow traffic measurement[C]//Proc of the 23rd Annual Joint Conference on IEEE Computer and Communications Societies.Hong Kong:IEEE Press，2004:17621773.
[6]COHEN S，MATIAS Y.Spectral Bloom filters[C]//Proc of ACM SIGMOD International Conference on Management of Data.New York:ACM Press，2003:241-252.
[7]GUO D，WU Jie，CHEN Honghui，et al.Theory and network application of dynamic Bloom filters[C]//Proc of the 25th IEEE International Conference on Computer Communications Proceedings.2006:112.
[8]肖明忠，代亞非，李曉明.拆分型Bloom filter[J].電子學報，2004，32(2):241-245.
[9]BLOOM B.Space/time tradeoffs in hash coding allowable errors[J].Communications of the ACM，1970，13(7):422-426.
[10]Maze系統[EB/OL].http://maze.pku.edu.cn.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”
