d-LeftCBF技術在P2P中的研究.pdf

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

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

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

4、置。
　　 了解了2-left Hashing，d-left Hashing就很好理解，它只是對前者的擴展。2-leftHashing固定了子表的個數(shù)是2，d-left Hashing更加靈活，子表的個數(shù)是一個變量d，同時也意味著哈希函數(shù)的個數(shù)是d。在d-left Hashing中，整個哈希表被分成d個從左到右依次相鄰的子表，每個子表對應一個相互獨立的哈希函數(shù)。在加入新key時，這個key被d個哈希函數(shù)同時計算，產(chǎn)生d個相互獨立

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

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

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