2.3 布隆过滤器

1.案例

如何高效判断元素w是否存在于集合A之中？首先想到的答案是，把集合A中的元素一个个放到哈希表中，然后在哈希表中查一下w即可。这样确实可以解决小数据量场景下元素存在性判定，但如果A中元素数量巨大，甚至数据量远远超过机器内存空间，该如何解决问题呢？

实现一个基于磁盘和内存的哈希索引当然可以解决这个问题。而另一种低成本的方式就是借助布隆过滤器（Bloom Filter）来实现。

布隆过滤器由一个长度为N的01数组array组成。首先将数组array每个元素初始设为0。对集合A中的每个元素w，做K次哈希，第i次哈希值对N取模得到一个index(i)，即index(i)=HASH_i(w)%N，将array数组中的array[index(i)]置为1。最终array变成一个某些元素为1的01数组。

下面举个例子，如图2-9所示，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=010001000000010000。

对元素y，HASH_0(y)%N=4，HASH_1(y)%N=11，HASH_2(y)%N=16。因此array=010011000001010010。

对元素z，HASH_0(z)%N=3，HASH_1(y)%N=5，HASH_2(y)%N=11。因此array=010111000001010010。

最终得到的布隆过滤器串为：010111000001010010。

此时，对于元素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，给出的存在性结果为两种：

•w可能存在于集合A中。

•w肯定不在集合A中。

在论文中证明，当N取K*|A|/ln2时（其中|A|表示集合A元素个数），能保证最佳的误判率，所谓误判率也就是过滤器判定元素可能在集合中但实际不在集合中的占比。

举例来说，若集合有20个元素，K取3时，则设计一个N=3×20/ln2=87二进制串来保存布隆过滤器比较合适。

2.算法实现

布隆过滤器的代码实现很短，如下所示：

        public class BloomFilter {
          private int k;
          private int bitsPerKey;
          private int bitLen;
          private byte[] result;
          public BloomFilter(int k, int bitsPerKey) {
            this.k=k;
            this.bitsPerKey=bitsPerKey;
          }
          public byte[] generate(byte[][] keys) {
            assert keys !=null;
            bitLen=keys.length ＊ bitsPerKey;
            bitLen=((bitLen+7) / 8) << 3; //align the bitLen.
            bitLen=bitLen < 64 ? 64 : bitLen;
            result=new byte[bitLen >> 3]; //each byte have 8 bit.
            for (int i=0; i < keys.length; i++) {
              assert keys[i] !=null;
              int h=Bytes.hash(keys[i]);
              for (int t=0; t < k; t++) {
                int idx=(h % bitLen+bitLen) % bitLen;
                result[idx / 8] |=(1 << (idx % 8));
                int delta=(h >> 17) | (h << 15);
                h +=delta;
              }
            }
            return result;
          }
          public boolean contains(byte[] key) {
            assert result !=null;
            int h=Bytes.hash(key);
            for (int t=0; t < k; t++) {   //Hash k times
              int idx=(h % bitLen+bitLen) % bitLen;
              if ((result[idx / 8] & (1 << (idx % 8)))==0) {
                return false;
              }
              int delta=(h >> 17) | (h << 15);
              h +=delta;
            }
            return true;
          }
        }

有两个地方说明一下：

•在构造方法BloomFilter(int k, int bitsPerKey)中，k表示每个Key哈希的次数，bitsPerkey表示每个Key占用的二进制bit数，若有x个Key，则N=x*bitsPerKey。

•在实现中，对Key做k次哈希时，算出第一次哈希值h之后，可借助h位运算来实现二次哈希，甚至三次哈希。这样性能会比较好。

3.案例解答

有了布隆过滤器这样一个存在性判断之后，我们回到最开始提到的案例。把集合A的元素按照顺序分成若干个块，每块不超过64KB，每块内的多个元素都算出一个布隆过滤器串，多个块的布隆过滤器组成索引数据。为了判断元素w是否存在于集合A中，先对w计算每一个块的布隆过滤器串的存在性结果，若结果为肯定不存在，则继续判断w是否可能存在于下一个数据块中。若结果为可能存在，则读取对应的数据块，判断w是否在数据块中，若存在则表示w存在于集合A中；若不存在则继续判断w是否在下一个数据块中。

这样就解决了这个问题。读者可以思考一下：在64KB的数据块中，平均每个Key占用1000字节，且在做3次哈希的情况下，需要占用多少字节的空间来存储布隆过滤器的二进制？

4. HBase与布隆过滤器

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

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

• NONE：关闭布隆过滤器功能。

• ROW：按照rowkey来计算布隆过滤器的二进制串并存储。Get查询的时候，必须带rowkey，所以用户可以在建表时默认把布隆过滤器设置为ROW类型。

• ROWCOL：按照rowkey+family+qualif ier这3个字段拼出byte[]来计算布隆过滤器值并存储。如果在查询的时候，Get能指定rowkey、family、qualif ier这3个字段，则肯定可以通过布隆过滤器提升性能。但是如果在查询的时候，Get中缺少rowkey、family、qualif ier中任何一个字段，则无法通过布隆过滤器提升性能，因为计算布隆过滤器的Key不确定。

注意，一般意义上的Scan操作，HBase都没法使用布隆过滤器来提升扫描数据性能。原因很好理解，同样是因为布隆过滤器的Key值不确定，所以没法计算出哈希值对比。但是，在某些特定场景下，Scan操作同样可以借助布隆过滤器提升性能。

对于ROWCOL类型的布隆过滤器来说，如果在Scan操作中明确指定需要扫某些列，如下所示：

          Scan scan=new Scan()
            .addColumn(FAMILY0, QUALIFIER0)
            .addColumn(FAMILY1, QUALIFIER1)

那么在Scan过程中，碰到KV数据从一行换到新的一行时，是没法走ROWCOL类型布隆过滤器的，因为新一行的key值不确定；但是，如果在同一行数据内切换列时，则能通过ROWCOL类型布隆过滤器进行优化，因为rowkey确定，同时column也已知，也就是说，布隆过滤器中的Key确定，所以可以通过ROWCOL优化性能，详见HBASE-4465。

另外，在HBASE-20636中，腾讯团队介绍了一种很神奇的设计。他们的游戏业务rowkey是这样设计的：

          rowkey=<userid>#<other-f ield>

也就是用userid和其他字段拼接生成rowkey。而且业务大部分的请求都按照某个指定用户的userid来扫描这个用户下的所有数据，即按照userid来做前缀扫描。基于这个请求特点，可以把rowkey中固定长度的前缀计算布隆过滤器，这样按照userid来前缀扫描时（前缀固定，所以计算布隆过滤器的Key值也就固定），同样可以借助布隆过滤器优化性能，HBASE-20636中提到有一倍以上的性能提升。另外，对于Get请求，同样可以借助这种前缀布隆过滤器提升性能。因此，这种设计对Get和基于前缀扫描的Scan都非常友好。

这个功能已经在HBase 2.x版本上实现，感兴趣的读者可以尝试。