王鹏
【摘要】 介绍布隆过滤器（Bloom Filter）的相关算法原理和使用说明，并阐述其在BSS领域中应用。通过与Redis缓存技术相结合，利用布隆过滤器（Boom Filter）的高效匹配、低存储等优势，提高BSS中排重效率，减少BSS对硬件扩容的需求。同时，阐述BSS排重中关于位数组的划分，以及针对布隆过滤器（Bloom Filter）对数据存在一定误判率的不足，并提出相应的应对措施。
【关键词】 布隆过滤器 排重 哈希算法 BSS Redis
一、引 言
判断一个元素已经存在某个集合里，一般的做法是：将集合中所有的元素保存起来，然后通过比较的方式来确定是否为重复元素。例如，常用于存储集合元素的数据结构有：链表、树、哈希表（hash table）等。但是，随着数据量的不断增长，所需的存储空间呈线性增长，检索的效率面临着严峻的考验。在BSS系统中，需要从检索效率、空间存储以及准确性等多个方面考虑排重机制，从而保障系统性能及稳定性。在众多的排重技术中，布隆过滤器（Bloom Filter）是其中最优秀的排重技术之一。它的主要优势在于：快速的检索以及极低的存储需求，主要缺点在于：存在一定的误判率，需要从应用角度，设计适中的位数组以及多重哈希判断来降低误判率。同时，针对误判元素进行特殊处理，以满足系统需要。
二、Bloom Filter概述
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
布隆过滤器（Bloom Filter）是一种空间效率极高的随机数据结构，采用位向量的方式表示一个集合，并结合哈希（hash）函数映射到集合中。布隆过滤器（Bloom Filter）的这种高效算法有一定的代价：判断一个元素是否属于某个集合时，有可能把不属于这个集合的元素误认为属于这个集合。因此，布隆过滤器（Bloom Filter）不适合“零误判”的应用场合。而是在能够容忍低误判率的应用场合下，布隆过滤器（Bloom Filter）通过极低的误判，节省极大的存储空间。
三、Bloom Filter原理布隆过滤器（Bloom Filter）是一个包含N位的位数组，每一位初始为0（如图1）。
二位數组集合N={x1，x2，x3，… …，xn}存放N个位元素，布隆过滤器（Bloom Filter）使用K个相互独立的哈希（hash）函数，将待处理的数据分别压缩成K个散列值，然后采用取模算法，将K个散列值分别映射到集合{1，2，3，…，n}的范围内。即（图二）对于一个待处理数据x1，x2，通过3个独立的哈希（hash）函数fk（h）分别计算出相应的散列值fk（x），并将计算出来的3个散列值fk（x）对N进行取模运算得到位数组下标，对相应下标的位进行置1操作。当在检索一个元素时，同样需要经过K个哈希（hash）函数计算出来的位数组下标，并挨个确认是否置为1。如果全为1，则被检索的元素可能已经存在；如果K个里面有任何一个不为1，则被检索的元素一定不存在当前集合中。
在布隆过滤器中，由于无论哈希（hash）函数设计的多么精密，都会有冲突现象，即2个不同的元素通过同一个哈希（hash）函数的处理结果可能映射到同一个位置。所以，为了减少冲突发生的概率，布隆过滤器（Bloom Filter）通过K个独立的哈希（hash）函数来进行映射操作，但是无法百分百避免。如果在不考虑位数组大小的前提下，随着K值增长（即独立哈希（hash）函数的增多），冲突的概率会不断降低，即误判率会不断降低。但是，随着K值增大，也会引起大量哈希（hash）计算占用过高的CPU计算，导致整体的效率降低。
四、Bloom Filter排重应用
在BSS系统中传统的排重算法，是将原数据X（待排重元素）作为自变量，通过特定的哈希（hash）函数映射成相应的散列值。表达为：f（x）=H（X）。将计算出来的f（x），到存储哈希表（hash table）的文件（或数据库）中查找，如果匹配上则认为可能是重复数据，然后进行下一步完全排重判断；如果匹配不上，认为不是重复数据，则将此数据写入存储哈希表（hash table）的文件（或数据库）中供后续数据排重使用。传统的排重中，为了能够快速的查找到散列值，将计算后的散列值按照一定的规则进行分片，例如：按照时间、地域等多个维度进行分片。同时，按照访问的热度，将热数据放到内存中，提高匹配效率。虽然，以上多种优化措施在一定程度上提高了目前的排重效率，能够有效的处理日常的话单排重。但是，随着用户的不断发展，历史排重文件所占的空间不断增加，在普通存储设备上即使采用高效的哈希（hash）算法也很难提高效率。例如，采取目前MD5（Message-Digest Algorithm 5）算法将待排重数据计算成一个128bit大小的大整数，100亿数据量大约需要占用约149GB空间。由于需要完全匹配排重，所以需要将原数据也一同保留下来，以便在发生哈希（hash）冲突时，使用原数据进行完全比对。单条原数据的空间本身占用就比较大，那么100亿记录的空间占用会更大。
采用布隆过滤器（Bloom Filter）来代替目前传统的数据结构，在效率和空间上都有所改变。但是，在使用布隆过滤器（Bloom Filter）时，需要考虑多个因素：（1）考虑如何分配大小最优的位数组以及最优的K值（独立哈希函数的个数）；（2）考虑位数组集合存储问题，以便最快的检索；（3）解决由于布隆过滤器（Bloom Filter）自身的误判率问题，以便完全匹配重复数据。
使用布隆过滤器（Bloom Filter）在分配位数组大小以及K值（独立哈希函数的个数）时，都会影响到最终的误判率以及排重的处理效率。假设位数组的大小为N，独立的哈希函数个数为K，那么在已经插入x个元素后的误判率为： 。其中当K=1时， x/N与误判率f（x）的关系：随着N的不断增加，误判率不断降低。N的大小设定，需要取决于待排重总量的大小。所以，一定要对当前需要排重的数据量有一个初步的预估，从而计算出合理的N值。当x/N=1时，K值与误判率f（x）的关系：随着K值的不断增加，误判率不断降低。 K值的大小设定，需要考虑对CPU消耗影响，过高的K值会影响应用的整体效率。
在确定位数组大小后，需要考虑存储方式，可以通过多种存储方式存储，例如：一块连续的私有内存、链表以及容器等存储方式。如果对于少量的数据，应用可以通过分配私有内存的方式，分配一定大小的连续内存空间，即可满足；如果对于大量数据，例如100亿数据量，当x/N=1时大约就需要1.16GB容量。这个数量级的操作，放到私有内存有重多限制，例如：内存分配问题、数据共享问题、应用启动加载问题等。大量数据可以考虑以共享内存的形式存放位数组。但是，需要考虑数据的持久性、容灾备份、并发访问以及快速查找等因素。尤其考虑到位数组的特殊性：以比特位（bit）的形式存储。结合当前开源的产品：内存库、缓存以及消息中间件，最终选取了Redis。Redis不仅具备事务、磁盘持久化、复制等功能，最主要的是提供BitMap这种可以直接用于位操作的数据类型。将需要排重的数据信息通过布隆过滤器（Bloom Filter）生成相应位数组的位置下标，然后使用BitMap中的setbit（置位）/getbit（获取位）进行相应的写/读操作。
在BSS的话单排重中，由于整个月的话单都需要排重，而且单省整月的话单量大约在270亿条左右。如果只用一个BitMap来存放整月的数据，则会带来效率的下降。从系统的业务角度出发，将数据按照话单开始日期进行分片，BitMap从而也按照开始日期进行存储，不同的BitMap存放不同开始时间的话单排重信息。即，每月可以拆成30个BitMap。但是，即使拆成30个BitMap，还有有新的问题：并发处理话单时，多个应用程序同时处理同一个用户的同一条记录，存在竞争的关系。为了解决这个问题，可以采取多种方案，例如：在进行事物操作时加锁，避免并发带来的数据异常；或者，将话单记录按照用户进行划分，同一个用户在一个应用进程下处理。如果，按照用户进行划分后，原来的30个BitMap可以根据用户的不同再次分解。即，按照日期加进程的方式进行划分BitMap。这样一个BitMap存储的数据量会变得较低，有利于检索效率的提升。
布隆过滤器（Bloom Filter）由于存在一定的误判率，但是BSS的排重对重单是零容忍。针对误判用户再采取完全匹配的方式到文件系统（或数据库）进行检索匹配，判断是否重复数据。由于检索文件系统（或数据库）效率比Redis差了很多倍，所以尽可能通过适当增加BitMap的大小以及最优的K值，来保障最小的誤判率。从而使绝大多数话单记录通过操作Redis里的BitMap实现排重，只有少部分的误判记录查询文件系统（或数据库）。
五、结论
布隆过滤器（Bloom Filter）优点在于：检索效率快、存储空间占用低；缺点在于：无法删除、存在误判。利用存储空间低的优势，可以部署在低配置的主机实现大量数据的排重操作。同时，可以与目前开源的多种工具相结合使用，比如：与Redis+Hadoop相结合，实现大数据的快速排重。
参 考 文 献
[1] 刘威；郭渊博；黄鹏 基于Bloom filter的多模式匹配引擎评论推荐[期刊论文]-电子学报 2010（05）.
[2]A.Broder；M.Mitzenmacher Network applications of bloom filters：A survey 2005（04）
