劉文君 曹 偉 王 鍵

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

1. 引言

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

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

2.1 Left Counting Bloom Filter 算法的格式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1) x 和y 的fingerprint 相同；

(2) 位置選擇有重合；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

因此由于d-left CBF 負(fù)載均衡，可比負(fù)載不均衡的CBF 節(jié)省至少一倍的存儲(chǔ)空間。

4. 仿真測(cè)試

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

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

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

?

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

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

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

5. 小結(jié)

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

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

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

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

[2]譚興曄，張勇，雷振明.基于d-left算法的硬件哈希表研究與實(shí)現(xiàn)[J].計(jì)算機(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ù)的長流識(shí)別實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2007，33(20)：116-118.