关于布隆过滤器在bss中应用

《关于布隆过滤器在bss中应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、关于布隆过滤器在BSS中应用【摘要】介绍布隆过滤器(BloomFilter)的相关算法原理和使用说明，并阐述其在BSS领域中应用。通过与Redis缓存技术相结合，利用布隆过滤器(BoomFilter)的高效匹配、低存储等优势，提高BSS屮排重效率，减少BSS对硬件扩容的需求。同时，阐述BSS排重中关于位数组的划分，以及针对布隆过滤器(BloomFilter)对数据存在一定误判率的不足，并提出相应的应对措施。【关键词】布隆过滤器排重哈希算法BSSRedis一、引言判断一个元素已经存在某个集合里，一般的

2、做法是：将集合中所有的元素保存起来，然后通过比较的方式来确定足否为重复元素。例如，常川于存储集合元素的数据结构有：链表、树、哈希表(hashtable)等。但是，随着数据量的不断增长，所需的存储空间呈线性增长，检索的效率面临着严峻的考验。在BSS系统中，需要从检索效率、空间存储以及准确性等多个方面考虑排重机制，从而保障系统性能及稳定性。在众多的排重技术中，布隆过滤器(BloomFilter)是其中最优秀的排重技术之一。仑的主要优势在于.•快速的检索以及极低的存储需求，主要缺点在于：存在一定的误判率，

3、需要从应用角度，设计适屮的位数组以及多重哈希判断来降低误判率。同时，针对误判元素进行特殊处理，以满足系统需要。二、BloomFilter概述布隆过滤器(BloomFilter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和査询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。布隆过滤器(BloomFilter)是一种空间效率极高的随机数裾结构，采用位向量的方式表示一个集合，并结合哈希(has

4、h)函数映射到集合中。布隆过滤器(BloomFilter)的这种高效算法有一定的代价：判断一个元素是否属于某个集合时，有可能把不属于这个集合的元素误认为属于这个集合。因此，布隆过滤器(BloomFilter)不适合“零误判”的应用场合。而是在能够容忍低误判率的应用场合下，布隆过滤器(BloomFilter)通过极低的误判，节省极大的存储空间。三、BloomFilter原理布隆过滤器(BloomFiIter)是一个包含N位的位数组，每一位初始为0(如图1)。二位?底榧?合N={xl,x2,x3,:n｝

5、存放N个位元素，布隆过滤器(BloomFilter)使用K个相互独立的哈希(hash)函数，将待处理的数据分别压缩成K个散列值，然后采用取模算法，将K个散列值分别映射到集合｛1，2,3,…，n｝的范围内。即(图二)对于一个待处理数据xl，x2，通过3个独立的哈希(hash)函数fk(h)分别计算出相应的散列值fk(x),并将计算出来的3个散列值fk(x)对N进行取模运算得到位数组下标，对相应下标的位进行置1操作。当在检索一个元素时，同样需要经过K个哈希(hash)函数计算出来的位数组下标，并挨个确认

6、是否置为1。如果全为1，则被检索的元素可能己经存在；如果K个里面有任何一个不为1，则被检索的元素一定不存在当前集合中。在布隆过滤器中，由于无论哈希(hash)函数设计的多么精密，都会有冲突现象，即2个不同的元素通过同一个哈希(hash)函数的处理结果可能映射到同一个位置。所以，为了减少冲突发生的概率，布隆过滤器(BloomFilter)通过K个独立的哈希(hash)函数来进行映射操作，但是无法百分百避免。如果在不考虑位数组大小的前提下，随着K值增长(即独立哈希(hash)函数的增多)，冲突的概率会不

7、断降低，即误判率会不断降低。但是，随着K值增大，也会引起大量哈希(hash)计算占用过高的CPU计算，导致整体的效率降低。四、BloomFilter排重应用在BSS系统中传统的排重算法，是将原数据X(待排重元素)作为自变量，通过特定的哈希(hash)函数映射成相应的散列值。表达为：f(x)=H(X)。将计算出来的f(X)，到存储哈希表(hashtable)的文件(或数据库)中查找，如果匹配上则认为可能是重复数据，然后进行下一步完全排重判断；如果匹配不上，认为不是重复数据，则将此数据写入存储哈希表(h

8、ashtabic)的文件(或数据库)中供后续数据排重使用。传统的排重中，为了能够快速的查找到散列值，将计算后的散列值按照一定的规则进行分片，例如：按照时间、地域等多个维度进行分片。同时，按照访问的热度，将热数据放到内存中，提高匹配效率。虽然，以上多种优化措施在一定程度上提高了冃前的排重效率，能够有效的处理H常的话单排重。但是，随着用户的不断发展，历史排重文件所占的空间不断增加，在普通存储设备上即使采用高效的哈希(hash)算法也很难提高效率。例如，采取目前MD5(Me