基于Bloom Filter 的Left 算法的應用研究

劉文君 曹 偉 王 鍵

（江陰職業技術學院，江蘇 江陰 214405）

1. 引言

布隆過濾器已經得到深入研究，普遍認為bloom filter 的優勢在于快捷和空間利用率高，缺點是存在一定的識別錯誤率[1]。本文嘗試結合d-left 算法，對原有布隆過濾器進行優化改進，解決一般哈希表存在的最壞訪問時間的問題。在實現方面可以按照設計需要折中考慮存儲器利用率、加入失敗概率等因素，具有很好的靈活性和可擴展性，以期提高空間效率。

2. 基于Bloom Filter的Left算法概述

2.1 Left Counting Bloom Filter 算法的格式

若d=2 時，2-left Hashing 指的是將一個哈希表分成長度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個哈希函數，h1和h2。在存儲一個新的key 時，同時用兩個哈希函數進行計算，得出兩個地址h1[key]和h2[key]。這時需要檢查T1中的h1[key] 位置和T2中的h2[key]位置，哪一個位置已經存儲的（有碰撞的）key 比較多，然后將新key 存儲在負載少的位置。如果兩邊一樣多，比如兩個位置都為空或者都存儲了一個key，就把新key 存儲在左邊的T1子表中，2-left 也由此而來。在查找一個key 時，必須進行兩次Hash，同時查找兩個位置[2]。

Left Hashing 是對前者的擴展。2-left Hashing 固定了對應的子表的個數是2，d-left Hashing 更加靈活，子表的個數是一個變量d，同時也意味著哈希函數的個數是d。在d-left Hashing 中，整個哈希表被分成d 個從左到右依次相鄰的子表，每個子表對應一個相互獨立的哈希函數。在加入新key 時，這個key 被d 個哈希函數同時計算，產生d 個相互獨立的位置，然后將key 加入到負載最輕的位置（bucket）中。如果負載最輕的位置有多個，就把key 加入到最左邊的負載最輕的子表中。同樣地，如果要查找一個key，需要同時查找d 個位置。

2.2 Left Counting Bloom Filter 算法的空間分配

哈希函數的輸出值（Hash value）通常有兩種用途：一種用作地址，比如在哈希表中要存儲一個元素，首先要針對這個元素生成一個隨機地址；另一種用作fingerprint（或者叫digital summary），比如將密碼字符串Hash成一個fingerprint，驗證時進行核對。d-Left hashing 的存儲信息的方式是將以上兩種用途結合了起來：一個Hash value 分作兩部分，一部分用作存儲地址，另一部分用作fingerprint。

使用一個哈希函數，將其Hash value 分作兩部分，高位部分用作隨機地址，低位部分留作fingerprint。若用這一個哈希函數存儲一個集合，則在基于Perfect Hashing 的方法中，第一步用的哈希函數是Perfect Hash Function，即一個集合的n 個元素會映射到n 個bucket中，沒有碰撞。由于Perfect Hash Function 不能應對變動的集合，并且對大多數應用來說開銷太大，所以上述所說的一個哈希函數并不是Perfect Hash Function。由此可知碰撞會產生，并且各個bucket 的負載并不均衡，實際上單個哈希函數Hash value 的分布服從泊松（Poisson）分布[2]。

從一個Hash value 同時用作地址和fingerprint 出發，構造一個簡潔的存儲方式來存儲一個集合的fingerprints 基本可行，但遇到了負載不均衡的問題。為此提出使用d-left Hashing 來了解決哈希表的負載平衡問題。在沒有d-left Hashing 的情況下，同一個Hash value 高位用作地址低位用作fingerprint，這就意味著同一個地址對應著多個fingerprint。一個地址對應一個bucket，因此一個bucket 需要存儲多個fingerprint。由于單個哈希函數的Hash value 分布不均，各個bucket 的負載也不均衡。如果每個bucket 能存儲的fingerprint 數量固定，為了不溢出必須按最壞的情況來分配bucket 的容量，這就造成了不小的浪費。

使用d-left Hashing 之后，fingerprint 的分布相對比較均衡，因此大大減少了空間的浪費。原來即使分配很大的哈希表，由于按最壞情況分配bucket 容量，仍然很難縮小bucket 的容量，并且哈希表中大量空間閑置。而使用d-left Hashing 可以讓存儲的信息分布均勻，更加緊湊，從而用更小的空間存儲同樣多的信息。在前文Perfect Hashing 章節中提到過，d-left CBF 可以比CBF節省至少一倍的空間，就是因為CBF 負載不均衡，很多空間都被浪費掉了。

因此，d-left CBF 的主要思路就是利用d-left Hashing 的方法存儲fingerprint。

2.3 Left Counting Bloom Filter 算法的調用方法

首先使用一個d-left 哈希表，表中每個bucket 可以容納若干個（固定數量的）cell，每個cell 的位數固定，包括一個fingerprint 和一個counter。包含一個fingerprint還要包含一個counter 是為了處理碰撞（collision）。在dleft 哈希表的d 個子表中，每個子表都要處理碰撞的情況。在某一個子表出現碰撞時，會發現已經有同樣的fingerprint 被存儲到同一位置，因此，有了counter 只需把counter 的值加1 即可。

在沒有應用d-left Hashing 的情況下，使用一個哈希函數，把它的Hash value 分成兩段，高位作存儲地址，低位作fingerprint。現在要應用d-left Hashing，有d 個存儲地址需要生成，仍然用一個哈希函數，但把它的Hash value 分成d+1 段：高位的d 段分別用作d 個存儲地址，每個子表對應一個，剩下的低位部分作為fingerprint。

在添加一個key 時，先對它作一次Hash，得到d 個存儲位置和一個fingerprint，然后判斷d 個位置中的負載情況，并在負載最輕的幾個位置中選擇最左邊的插入。如果選擇的位置已經存儲了相同的fingerprint，就把那個cell 的counter 加1。在刪除一個key 時，同樣地作一次Hash，然后在d 個存儲位置查找相應的fingerprint，如果找到就將這個cell 置空或者將相應的counter 減1。

到此為止d-left CBF 的構造基本完成。但實際上，上面的構造過程中有一個缺陷，這個缺陷會在從集合中刪除元素時出現。

針對該缺陷，特別提出對應的優化補救辦法來改進d-Left CBF。

3. 對于Left算法下的BloomFilter的優化改進

3.1 基于Bloom Filter 的Left 算法的優化改進

根據前面的描述并分析，不難發現出現該缺陷的有三個前提：

(1) x 和y 的fingerprint 相同；

(2) 位置選擇有重合；

(3) x 不選擇重合位置，y 選擇重合位置；

其中fingerprint 相同無法避免，因為碰撞總會出現，cell 中的counter 也是為此而設置的。元素是否選擇重合位置也無法控制，因為這要根據當時的負載情況而定。所以能夠彌補這個缺陷，只能從位置重合入手。即在不考慮碰撞的前提下，使得不同元素的d 個位置選擇完全沒有重合[3]。

為此提出的解決方案是：將Hashing 的整個操作分成兩個階段。第一階段，用一個哈希函數H 計算要插入元素x 的Hash value，記做fx；第二階段，為了獲得d 個存儲位置，另外引入d 個隨機置換（random permutation）。令

其中b 是bucket index，表示存儲位置；r 是remainder，表示要存儲的fingerprint。然后令d 個置換為：

其中Pi(fx)對應著x 在第i 個子表的存儲位置和fingerprint。因為置換意味著一一對應，因此不同元素的Hash value 作置換之后的值仍然不同。這樣就達到了前面提到的讓不同元素的d 個位置選擇完全沒有重合的目標[3]。

引入隨機置換避免了位置重合之后，還需要在插入元素之前完成一項工作。每次插入一個元素時，先要在它的d 個位置選擇中檢查是否已經存有相同的fingerprint，如果有，就把相應cell 的counter 加1。由于不同元素的存儲位置不會重合，因此只有在碰撞的情況下才會出現兩個相同fingerprint 能存入同一組存儲位置的情況。而一旦在插入之前作了檢測，再作刪除操作時就永遠不會發現d 個位置中有兩個完全相同的fingerprint。至此，刪除元素時的缺陷問題已經完全解決。

3.2 Left Counting Bloom Filter 的優化與標準CBF 的比較

若將d-Left CBF 與標準的CBF 進行比較，假設要表示的集合有m 個元素，構造d-left CBF 的各個參數如下：

Left 哈希表包含4 個子表；每個子表包含m/24 個bucket，使得bucket 的平均負載是6 個元素；子表中每個bucket 可以容納8 個cell，8 個就能以很高的概率保證不會溢出；cell 中每個counter 包含2 位，可以容納4 個相同的fingerprint；且fingerprint 設置必須為表示空的狀態即全0。

假設用r 位表示fingerprint，那么false positive 的概率就是24×2-r。其中兩個fingerprint 完全相同的概率為(1/2)r，又因d-left hashing 使得查找時有4 個選擇（有4個子表），每個選擇對應一個bucket，一個bucket 平均負載是6，所以需乘以24。整個d-left CBF 所需的所有位數為4m(r+2)/3。其中r+2 表示一個cell 的位數，m 是集合元素個數，一個bucket 能容納8 個cell，但平均負載是6 個，所以乘以4/3 就得到全部的位數。

再與標準CBF 進行比較。假設對于m 個元素的集合，CBF 使用cm 個counter，每個counter 使用4 位，哈希函數的個數k 使用最優值cln2，得到false positive 的概率為（2-ln2）c，總共使用4cm 位。如果令c=(r+2)/3，則兩種方法使用的位數相同，比較false positive 概率會發現當r≥7 時，

（2-ln2）（r+2）/3＞24×2-r

而且使用的位數越多，兩個false positive 概率的差距就越大。當r = 14 時，c = 16/3，雖然兩個結構使用的位數相同，但CBF 比d-left CBF 的false positive 概率大100 倍以上。

若false positive 概率相同，假設標準CBF 使用9 個4 位的counter（每個元素36 位），6 個獨立的哈希函數，得到的false positive 概率為0.01327。d-left CBF 使用11位的fingerprint（每個元素52/3 位），得到的false positive概率為0.01172。計算可得，（52/3）÷36= 0.48，即d-left CBF 只使用了CBF 不到一半的空間，就得到了比CBF更低的錯誤率。

因此由于d-left CBF 負載均衡，可比負載不均衡的CBF 節省至少一倍的存儲空間。

4. 仿真測試

通過仿真測試，比較d-left CBF 和標準CBF。首先，確定一張哈希表，包含4 個子表，每個子表包含2048 個bucket，子表中每個bucket 容納8 個cell，可處理4×2048×8=216 個元素，假設預期的目標負載值為3×214=49152，那么49152÷（4?2048）=6，即平均每個bucket 負載6 個。正如前面章節介紹，如果bucket 的過載非常小，可以被忽略不計，在本例中，每個元素的過載量大約是接近10-27，完全可以忽略。其次，設置剩下部分的每個cell，所使用的計數器的位數，本次仿真中設置cell 中有14 位用于存放fingerprints，已知假設用r 位表示fingerprint，那么false positive 的概率就是24×2-r=24×2-14≈0.001465。

在這個表構造中，將Hashing 的整個操作分成兩個階段。第一步用了一個（Perfect）哈希函數生成了這個元素的存儲地址，第二步用另一個哈希函數生成這個元素的fingerprint，然后將fingerprint 存儲到第一步生成的地址中。另外引入d 個隨機線性置換（random linear permutation），因為置換意味著一一對應，因此能保證不同元素的Hash value 做置換之后的值仍然不同。

當這些都構建完畢以后，重復上文所述測試10000次，在每次試驗中，均按照之前對d-left CBF 的預計，將總共的負載設置為3×214=49152，從而保證每個bucket的平均負載為6 個元素。在所有的隨機插入和刪除操作后，溢出沒有出現，檢查bucker 的負載和對照bucket 的分布，可以獲得下表結果。

?

仔細觀察表中數據，不難發現仿真結果已經非常接近預期。

同樣通過10000 次試驗，獲得標準CBF 的false positive 概率在0.108 ～0.205 之間，其平均值大約低于0.1529，非常接近的預期。注意這個值高于d-left CBF 的false positive 概率，約0.86 左右。所以通過本次仿真測試，獲得d-left CBF 比CBF 使用更少的存儲空間，卻能得到比CBF 更低的運算錯誤率，也就是具有更高的效率。

比較d-left CBF 與原先標準的CBF，首先從理論著手進行推導，當這兩種CBF 使用的hash 表位數相同，CBF 的false positive 概率高于d-left CBF 的false positive 概率，而且隨著使用的位數越多，兩個false positive概率的差距就越大。反之，若false positive 概率相同，dleft CBF 只使用了CBF 不到一半的hash 表位數，換個說法就是節約了一半的空間。其次通過仿真試驗，構建一個虛擬網絡環境，對網段內節點進行測試，完成動態刪減和自動更新的操作，實踐結果證明了的理論推導是正確的，空間確實被節約了一半左右。

5. 小結

對d-left CBF 而言，其主要的思路就是將d-left Hashing 加入到計數型Bloom Filter 中，利用d-left Hashing 的方法存儲計數型Bloom Filter 中的fingerprint，從而用更小的空間存儲同樣多的信息。

對于當前網絡而言，隨時變化的節點信息，是一個巨大的信息量，而如何有效地存儲管理這些信息更是一個難題。對于標準的BF 而言，雖然處理速度非常快捷，但是功能過于簡單，特別是不具有刪除操作，當節點出現損壞，需要從集合表中刪除該節點信息時，這個漏洞就顯而易見了。對于標準的CBF 而言，雖然增加的刪除操作，但卻付出了存儲空間成倍增長的代價。d-left CBF就是為了改進標準的CBF 臃腫的結構而提出的。

因此，確信將d-left Hashing 加入到CBF 中，利用d-left Hashing 的方法存儲CBF 中的fingerprint，確實能用更小的空間存儲同樣多的信息，同時還能保留原有CBF 的刪除操作功能，實現對網絡中隨時變化的節點信息的動態管理。在實踐中，將這種哈希表結構應用到千兆以太網接入網關上實現流量統計和過濾，收到了很好的效果。值得在今后的網絡管理中使用。

[1]肖明忠，代亞非.Bloom Filter及其應用綜述[J].計算機科學，2004，(04)：180-183.

[2]譚興曄，張勇，雷振明.基于d-left算法的硬件哈希表研究與實現[J].計算機應用研究，2005，(10)：52-55.

[3]C.Rijmen，V.klavos.N.The NIST Cryptographic Workshop on Hash Functions Rechberger[J]，Security&Privacy Magazine，IEEE Volume 4，Issue1，Jan-Feb.2006：54-56.

[4]AndreiB，M ichaelM.Net work applications of bloom filters：a survey[J].InternetMath，2003，1(4)：485-509.

[5]劉衛江，白磊，景泉.基于Sample_CBF技術的長流識別實現[J].計算機工程，2007，33(20)：116-118.