d-LeftCBF技術(shù)在P2P中的研究.pdf

1、本文分析了布隆濾波器技術(shù)在時(shí)下流行的分布式系統(tǒng)--P2P系統(tǒng)中的應(yīng)用，著重介紹基于d-left算法的的計(jì)數(shù)型布隆濾波器技術(shù)，d-left CBF利用d-left hashing的方法存儲(chǔ)fingerprint。將hash value分為兩部分，分別用于存儲(chǔ)隨機(jī)地址和fingerprint，從而提高工作效率，并支持節(jié)點(diǎn)動(dòng)態(tài)刪除操作，應(yīng)用于節(jié)點(diǎn)異常活躍的P2P系統(tǒng)中。
　　 在當(dāng)前各種P2P技術(shù)中，搜索技術(shù)是最有價(jià)值、最亟待解決的問(wèn)

2、題，其中分布式哈希表(hashing)將是對(duì)等網(wǎng)搜索的重要方向。Hashing通過(guò)使用哈希表來(lái)實(shí)現(xiàn)存儲(chǔ)和查詢，對(duì)于P2P搜索而言，其優(yōu)點(diǎn)是快速準(zhǔn)確，缺點(diǎn)是浪費(fèi)存儲(chǔ)空間。本文提出的d-left方法，是基于Bloom Filter技術(shù)，利用d-left Hashing的方法存儲(chǔ)fmgerprint，從而實(shí)現(xiàn)空間利用效率的提高。
　　 d-left中的d是多個(gè)的意思。為了更加簡(jiǎn)單的說(shuō)明這個(gè)“d”，本文以d=2，既2-left算法應(yīng)用到

3、哈希表的實(shí)現(xiàn)方法為例，分析其結(jié)構(gòu)和性能。2-left Hashing指的是將一個(gè)哈希表分成長(zhǎng)度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個(gè)哈希函數(shù)，h1和h2。在存儲(chǔ)一個(gè)新的key時(shí)，同時(shí)用兩個(gè)哈希函數(shù)進(jìn)行計(jì)算，得出兩個(gè)地址h1[key]和h2[key]。如果兩邊一樣多，如兩個(gè)位置都為空或者都存儲(chǔ)了一個(gè)key，就把新key存儲(chǔ)在左邊的T1子表中，2-left也由此而來(lái)。在查找一個(gè)key時(shí)，必須進(jìn)行兩次Hash，同時(shí)查找兩個(gè)位

4、置。
　　 了解了2-left Hashing，d-left Hashing就很好理解，它只是對(duì)前者的擴(kuò)展。2-leftHashing固定了子表的個(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ú)立

5、的位置，然后將key加入到負(fù)載最輕的位置(bucket)中。如果負(fù)載最輕的位置有多個(gè)，就把key加入到最左邊的負(fù)載最輕的子表中。同樣地，如果要查找一個(gè)key，需要同時(shí)查找d個(gè)位置。
　　 d-Left計(jì)數(shù)型布隆濾波器與標(biāo)準(zhǔn)的布隆濾波器比較，若false positive概率相同，假設(shè)標(biāo)準(zhǔn)CBF使用9個(gè)4位的counter(每個(gè)元素36位)，6個(gè)獨(dú)立的哈希函數(shù)，得到的false positive概率為0.01327。d-left

6、CBF使用11位的fingerprint(每個(gè)元素52/3位)，得到的false positive概率為0.01172。計(jì)算可得，52/3÷36=0.48，即d-left CBF只使用了CBF不到一半的空間，就得到了比CBF更低的錯(cuò)誤率。因此在保證false positive概率接近的同時(shí)，由于d-left CBF負(fù)載均衡，可比負(fù)載不均衡的CBF節(jié)省至少一倍的存儲(chǔ)空間。
　　 較之布隆濾波器的其它變種，d-left計(jì)數(shù)型布隆濾波

7、器有其特殊性。雖然d-left計(jì)數(shù)型布隆濾波器沒(méi)有標(biāo)準(zhǔn)布隆濾波器快捷，也沒(méi)有標(biāo)準(zhǔn)計(jì)數(shù)型布隆濾波器高效，但d-left結(jié)合了兩者的優(yōu)點(diǎn)，綜合性能較強(qiáng)。既彌補(bǔ)了標(biāo)準(zhǔn)布隆濾波器的只能對(duì)靜態(tài)網(wǎng)絡(luò)進(jìn)行快捷管理，查找和插入，不能刪除操作的先天缺陷；也避免了標(biāo)準(zhǔn)計(jì)數(shù)型布隆濾波器過(guò)度占用空間的臃腫。能夠較好的解決負(fù)載均衡、減少網(wǎng)絡(luò)瀏覽等熱點(diǎn)問(wèn)題。
　　 當(dāng)然d-left計(jì)數(shù)型布隆濾波器不是沒(méi)有缺點(diǎn)，無(wú)法與標(biāo)準(zhǔn)布隆濾波器或標(biāo)準(zhǔn)計(jì)數(shù)型布隆濾波器結(jié)合