布隆过滤器详解

小灰灰 2020-11-15 03:23 661阅读 0赞

## 什么是布隆过滤器 ##

本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

实现原理  
HashMap 的问题  
讲述布隆过滤器的原理之前，我们先思考一下，通常你判断某个元素是否存在用的是什么？应该蛮多人回答 HashMap 吧，确实可以将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇高。但是 HashMap 的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，那 HashMap 占据的内存大小就变得很可观了。

还比如说你的数据集存储在远程服务器上，本地服务接受输入，而数据集非常大不可能一次性读进内存构建 HashMap 的时候，也会存在问题。

## 布隆过滤器数据结构 ##

BF是由一个长度为m比特的位数组（bit array）与k个哈希函数（hash function）组成的数据结构。位数组均初始化为0，所有哈希函数都可以分别把输入数据尽量均匀地散列。可以认为是这个这样：  
![在这里插入图片描述][format_png]如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置 1，例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7，则上图转变为：  
![在这里插入图片描述][format_png 1]  
Ok，我们现在再存一个值 “tencent”，如果哈希函数返回 3、4、8 的话，图继续变为：  
![在这里插入图片描述][format_png 2]  
值得注意的是，4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位，因此它被覆盖了。现在我们如果想查询 “dianping” 这个值是否存在，哈希函数返回了 1、5、8三个值，结果我们发现 5 这个 bit 位上的值为 0，说明没有任何一个值映射到这个 bit 位上，因此我们可以很确定地说 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话，那么哈希函数必然会返回 1、4、7，然后我们检查发现这三个 bit 位上的值均为 1，那么我们可以说 “baidu” 存在了么？答案是不可以，只能是 “baidu” 这个值可能存在。

这是为什么呢？答案跟简单，因为随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个值 “taobao” 即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ，那么程序还是会判断 “taobao” 这个值存在。

## 优缺点与用途 ##

**BF的优点是显而易见的：**

*  不需要存储数据本身，只用比特表示，因此空间占用相对于传统方式有巨大的优势，并且能够保密数据；
 *  时间效率也较高，插入和查询的时间复杂度均为O(k)； 哈希函数之间相互独立，可以在硬件指令层面并行计算。

**它的缺点也同样明显：**

*  存在假阳性的概率，不适用于任何要求100%准确率的情境；
 *  只能插入和查询元素，不能删除元素，这与产生假阳性的原因是相同的。我们可以简单地想到通过计数（即将一个比特扩展为计数值）来记录元素数，但仍然无法保证删除的元素一定在集合中。

## 不能删除 ##

目前我们知道布隆过滤器可以支持 add 和 isExist 操作，那么 delete 操作可以么，答案是不可以，例如上图中的 bit 位 4 被两个值共同覆盖的话，一旦你删除其中一个值例如 “tencent” 而将其置位 0，那么下次判断另一个值例如 “baidu” 是否存在的话，会直接返回 false，而实际上你并没有删除它。

如何解决这个问题，答案是计数删除。但是计数删除需要存储一个数值，而不是原先的 bit 位，会增大占用的内存大小。这样的话，增加一个值就是将对应索引槽上存储的值加一，删除则是减一，判断是否存在则是看值是否大于0。

## 如何选择哈希函数个数和布隆过滤器长度 ##

很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

![在这里插入图片描述][format_png 3]

k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率。  
假阳性率的最终公式位：  
![在这里插入图片描述][format_png 4]  
所以，在哈希函数的个数k一定的情况下：

*  位数组长度m越大，假阳性率越低；
 *  已插入元素的个数n越大，假阳性率越高。

## 哈希策略 ##

在BloomFilterStrategies枚举中定义了两种哈希策略，都基于著名的MurmurHash算法，分别是MURMUR128\_MITZ\_32和MURMUR128\_MITZ\_64。前者是一个简化版，所以我们来看看后者的实现方法。

MURMUR128_MITZ_64() { 
        @Override
        public <T> boolean put(
            T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) { 
          long bitSize = bits.bitSize();
          byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
          long hash1 = lowerEight(bytes);
          long hash2 = upperEight(bytes);
    
          boolean bitsChanged = false;
          long combinedHash = hash1;
          for (int i = 0; i < numHashFunctions; i++) { 
            // Make the combined hash positive and indexable
            bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);
            combinedHash += hash2;
          }
          return bitsChanged;
        }
    
        @Override
        public <T> boolean mightContain(
            T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) { 
          long bitSize = bits.bitSize();
          byte[] bytes = Hashing.murmur3_128().hashObject(object, funnel).getBytesInternal();
          long hash1 = lowerEight(bytes);
          long hash2 = upperEight(bytes);
    
          long combinedHash = hash1;
          for (int i = 0; i < numHashFunctions; i++) { 
            // Make the combined hash positive and indexable
            if (!bits.get((combinedHash & Long.MAX_VALUE) % bitSize)) { 
              return false;
            }
            combinedHash += hash2;
          }
          return true;
        }
    
        private /* static */ long lowerEight(byte[] bytes) { 
          return Longs.fromBytes(
              bytes[7], bytes[6], bytes[5], bytes[4], bytes[3], bytes[2], bytes[1], bytes[0]);
        }
    
        private /* static */ long upperEight(byte[] bytes) { 
          return Longs.fromBytes(
              bytes[15], bytes[14], bytes[13], bytes[12], bytes[11], bytes[10], bytes[9], bytes[8]);
        }
      };

其中put()方法负责向布隆过滤器中插入元素，mightContain()方法负责判断元素是否存在。以put()方法为例讲解一下流程吧。

1.  使用MurmurHash算法对funnel的输入数据进行散列，得到128bit（16B）的字节数组。
2.  取低8字节作为第一个哈希值hash1，取高8字节作为第二个哈希值hash2。
3.  进行k次循环，每次循环都用hash1与hash2的复合哈希做散列，然后对m取模，将位数组中的对应比特设为1。

这里需要注意两点：

*  在循环中实际上应用了双重哈希（double hashing）的思想，即可以用两个哈希函数来模拟k个，其中i为步长：

![在这里插入图片描述][format_png 5]

*  哈希值有可能为负数，而负数是不能在位数组中定位的。所以哈希值需要与Long.MAX\_VALUE做bitwise AND，直接将其最高位（符号位）置为0，就变成正数了。

## 位数组具体实现 ##

static final class LockFreeBitArray { 
        private static final int LONG_ADDRESSABLE_BITS = 6;
        final AtomicLongArray data;
        private final LongAddable bitCount;
    
        LockFreeBitArray(long bits) { 
          this(new long[Ints.checkedCast(LongMath.divide(bits, 64, RoundingMode.CEILING))]);
        }
    
        // Used by serialization
        LockFreeBitArray(long[] data) { 
          checkArgument(data.length > 0, "data length is zero!");
          this.data = new AtomicLongArray(data);
          this.bitCount = LongAddables.create();
          long bitCount = 0;
          for (long value : data) { 
            bitCount += Long.bitCount(value);
          }
          this.bitCount.add(bitCount);
        }
    
        /** Returns true if the bit changed value. */
        boolean set(long bitIndex) { 
          if (get(bitIndex)) { 
            return false;
          }
    
          int longIndex = (int) (bitIndex >>> LONG_ADDRESSABLE_BITS);
          long mask = 1L << bitIndex; // only cares about low 6 bits of bitIndex
    
          long oldValue;
          long newValue;
          do { 
            oldValue = data.get(longIndex);
            newValue = oldValue | mask;
            if (oldValue == newValue) { 
              return false;
            }
          } while (!data.compareAndSet(longIndex, oldValue, newValue));
    
          // We turned the bit on, so increment bitCount.
          bitCount.increment();
          return true;
        }
    
        boolean get(long bitIndex) { 
          return (data.get((int) (bitIndex >>> 6)) & (1L << bitIndex)) != 0;
        }
        // ....
    }

看官应该能明白为什么它要叫做“LockFree”BitArray了，因为它是采用原子类型AtomicLongArray作为位数组的存储的。另外还有一个Guava中特有的LongAddable类型的计数器，用来统计置为1的比特数。作者：LittleMagic

## 大Value的拆分 ##

Redis 因其支持 setbit 和 getbit 操作，且纯内存性能高等特点，因此天然就可以作为布隆过滤器来使用。但是布隆过滤器的不当使用极易产生大 Value，增加 Redis 阻塞风险，因此生成环境中建议对体积庞大的布隆过滤器进行拆分。  
拆分的形式方法多种多样，但是本质是不要将 Hash(Key) 之后的请求分散在多个节点的多个小 bitmap 上，而是应该拆分成多个小 bitmap 之后，对一个 Key 的所有哈希函数都落在这一个小 bitmap 上。

[format_png]: /images/1605410607746.jpg
[format_png 1]: /images/1605410584384.jpg
[format_png 2]: /images/1605410560314.jpg
[format_png 3]: /images/1605410536149.jpg
[format_png 4]: /images/1605410513480.png
[format_png 5]: /images/1605410487712.png