劉文君 曹 偉 王 鍵

（江陰職業(yè)技術(shù)學(xué)院，江蘇 江陰 214405）

1. 引言

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

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

2.1 Left Counting Bloom Filter 算法的格式

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

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

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

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

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

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

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

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

2.3 Left Counting Bloom Filter 算法的調(diào)用方法

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

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

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

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

針對該缺陷，特別提出對應(yīng)的優(yōu)化補救辦法來改進d-Left CBF。

3. 對于Left算法下的BloomFilter的優(yōu)化改進

3.1 基于Bloom Filter 的Left 算法的優(yōu)化改進

根據(jù)前面的描述并分析，不難發(fā)現(xiàn)出現(xiàn)該缺陷的有三個前提：

(1) x 和y 的fingerprint 相同；

(2) 位置選擇有重合；

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

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

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

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

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

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

3.2 Left Counting Bloom Filter 的優(yōu)化與標(biāo)準(zhǔn)CBF 的比較

若將d-Left CBF 與標(biāo)準(zhǔn)的CBF 進行比較，假設(shè)要表示的集合有m 個元素，構(gòu)造d-left CBF 的各個參數(shù)如下：

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

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

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

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

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

若false positive 概率相同，假設(shè)標(biāo)準(zhǔn)CBF 使用9 個4 位的counter（每個元素36 位），6 個獨立的哈希函數(shù)，得到的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 節(jié)省至少一倍的存儲空間。

4. 仿真測試

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

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

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

?

仔細觀察表中數(shù)據(jù)，不難發(fā)現(xiàn)仿真結(jié)果已經(jīng)非常接近預(yù)期。

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

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

5. 小結(jié)

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

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

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

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

[2]譚興曄，張勇，雷振明.基于d-left算法的硬件哈希表研究與實現(xiàn)[J].計算機應(yīng)用研究，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]劉衛(wèi)江，白磊，景泉.基于Sample_CBF技術(shù)的長流識別實現(xiàn)[J].計算機工程，2007，33(20)：116-118.