布隆过滤器

2024-01-19 17:14:46

布隆过滤器是一位名叫Bloom的人提出的一种用于检索元素是否存在给定的大集合中的数据结构，这种数据结构由二进制向量（或者说位数组）和一系列随机映射函数（哈希函数）两部分组成。它只需占用极小的空间，便可以给出“可能存在”和“肯定不存在”的存在性判断。

布隆过滤器由一个长度为N的0-1数组array组成，每个元素只占用1bit。首先将数组array每个元素初始设置为0。

假设此时有一个集合A，我们要检索某些元素是否存在于集合A之中。那么布隆过滤器的处理过程就是，首先对集合A中的每个元素w，做K次哈希，第i次哈希值对N取模得到一个index(i)，即

index(i) = HASH_i(w) % N，

将array数组中的array[index(i)]置为1。最终array变成一个某些元素为1的01数组。

下面举个例子，集合A = {x,y,z}，N=18，K=3

初始化：

array = 000000000000000000

对于元素x，HASH_0(x) % N = 1，HASH_1(x) % N = 5，HASH_2(x) % N = 13，所以此时array等于：

array = 010001000000010000

对于元素y，HASH_0(y) % N = 4，HASH_1(y) % N = 11，HASH_2(y) % N = 16，所以此时array等于：

array = 010011000001010010

对于元素z，HASH_0(z) % N = 3，HASH_1(z) % N = 5，HASH_2(z) % N = 11，所以此时array等于：

array = 010101000001010000

所以最终的布隆过滤器串为：010101000001010000

此时，对于元素w，K次的哈希值分别为：

HASH_0(w) % N = 4，
HASH_1(w) % N = 13，
HASH_2(w) % N = 15

可以发现布隆串的第15位为0，因此可以确认w肯定不在集合A中。因为如果w在集合A中，那么布隆串的第15位必为1。

如果有另外一个元素t，K次的哈希值为：

HASH_0(t) % N = 5，
HASH_1(t) % N = 11，
HASH_2(t) % N = 13

我们发现布隆串的第5、11、13位都为1，但是却没法肯定t一定在集合A中。所以布隆过滤器串对于任意给定的元素w，给出的存在性结果为两种：

在论文BloomFilterSurvey中证明，当N（布隆串的长度）取

K * |A| / ln2      |A|表示集合A中的元素个数

时，能保证最佳的误判率，所谓误判率也就是过滤器判断元素可能在集合中但是实际不在集合中的占比。

由于布隆过滤器只需占用极小的空间就可以给出”可能存在“和”不存在“的存在性判断，所以可以提前过滤掉很多不必要的数据块，从而节省大量的磁盘IO。HBase的Get操作就是通过运用低成本高效率的布隆过滤器来过滤大量无效数据块的，从而节省了大量磁盘IO。

在HBase1.x版本中，用户可以对某些列设置不同类型的布隆过滤器，共有3种类型：

NONE：关闭布隆过滤器功能。
ROW：按照rowkey来计算布隆过滤器的二进制串并存储。Get查询的时候，必须带rowKey，所以用户可以在建表时默认把布隆过滤器设置为ROW类型。
ROWCOL：按照rowkey+family+qualifier这三个字段拼出byte[]来计算布隆过滤器值并存储。如果在查询的时候，Get能指定rowkey、family、qualifier这三个字段，则肯定可以通过布隆过滤器提升性能。但是如果在查询的时候，Get中缺少rowkey、family、qualifier中任何一个字段，则无法通过布隆过滤器提升性能，因为计算布隆过滤器的key不确定。

注意，一般意义上的Scan操作，HBase都没法使用布隆过滤器来提升扫描数据性能，因为布隆过滤器的key值不确定，所以没法计算哈希值进行对比。

码农公寓