论文部分内容阅读
本文分析了布隆滤波器技术在时下流行的分布式系统——P2P系统中的应用,着重介绍基于d-left算法的的计数型布隆滤波器技术,d-left CBF利用d-left hashing的方法存储fingerprint。将hash value分为两部分,分别用于存储随机地址和fingerprint,从而提高工作效率,并支持节点动态删除操作,应用于节点异常活跃的P2P系统中。在当前各种P2P技术中,搜索技术是最有价值、最亟待解决的问题,其中分布式哈希表(hashing)将是对等网搜索的重要方向。Hashing通过使用哈希表来实现存储和查询,对于P2P搜索而言,其优点是快速准确,缺点是浪费存储空间。本文提出的d-left方法,是基于Bloom Filter技术,利用d-left Hashing的方法存储fingerprint,从而实现空间利用效率的提高。d-left中的d是多个的意思。为了更加简单的说明这个“d”,本文以d=2,既2-left算法应用到哈希表的实现方法为例,分析其结构和性能。2-left Hashing指的是将一个哈希表分成长度相等的两半,分别叫做T1和T2,给T1和T2分别配备一个哈希函数,h1和h2。在存储一个新的key时,同时用两个哈希函数进行计算,得出两个地址h1[key]和h2[key]。如果两边一样多,如两个位置都为空或者都存储了一个key,就把新key存储在左边的T1子表中,2-left也由此而来。在查找一个key时,必须进行两次Hash,同时查找两个位置。了解了2-left Hashing,d-left Hashing就很好理解,它只是对前者的扩展。2-leftHashing固定了子表的个数是2,d-left Hashing更加灵活,子表的个数是一个变量d,同时也意味着哈希函数的个数是d。在d-left Hashing中,整个哈希表被分成d个从左到右依次相邻的子表,每个子表对应一个相互独立的哈希函数。在加入新key时,这个key被d个哈希函数同时计算,产生d个相互独立的位置,然后将key加入到负载最轻的位置(bucket)中。如果负载最轻的位置有多个,就把key加入到最左边的负载最轻的子表中。同样地,如果要查找一个key,需要同时查找d个位置。d-Left计数型布隆滤波器与标准的布隆滤波器比较,若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更低的错误率。因此在保证false positive概率接近的同时,由于d-left CBF负载均衡,可比负载不均衡的CBF节省至少一倍的存储空间。较之布隆滤波器的其它变种,d-left计数型布隆滤波器有其特殊性。虽然d-left计数型布隆滤波器没有标准布隆滤波器快捷,也没有标准计数型布隆滤波器高效,但d-left结合了两者的优点,综合性能较强。既弥补了标准布隆滤波器的只能对静态网络进行快捷管理,查找和插入,不能删除操作的先天缺陷;也避免了标准计数型布隆滤波器过度占用空间的臃肿。能够较好的解决负载均衡、减少网络浏览等热点问题。当然d-left计数型布隆滤波器不是没有缺点,无法与标准布隆滤波器或标准计数型布隆滤波器结合使用和结构过于复杂等,这些都有待更深入的研究。同样,本文提出的基于d-left计数型布隆滤波器技术在P2P中的研究,只是P2P技术的很小一部份,但基于d-left计数型布隆滤波器的构建思路独辟蹊径,却的确值得期待,希望今后有更多的观察研究。