Bloom Filter - 布隆过滤器

简介

布隆过滤器（英语：Bloom Filter）是1970年由布隆（Burton Howard Bloom）提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

原理

通常判断某个元素是否存在用什么？

HashMap 确实可以将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率很高。但是 HashMap 的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，那 HashMap 占据的内存大小就变得很可观了。

一个 email 地址需要占用十六个字节。

HashMap：一亿个地址大约要 1.6GB， 即十六亿字节的内存

Bloom Filter：一亿个地址，千分之一误报率，大约需要171MB

布隆过滤器

布隆过滤器主要做用就是查询一个数据，在不在这个二进制的集合中，过程如下：

• 经过K个哈希函数计算该数据，对应计算出的K个hash值
• 经过hash值找到对应的二进制的数组下标
• 判断：若是存在一处位置的二进制数据是0，那么该数据不存在。若是都是1，该数据存在集合中。

举个栗子：

假设有3个hash函数，key1 通过3个hash函数生成hash值对数组长度取模得到下标分别为1、5、7，key1 通过3个hash函数生成hash值对数组长度取模得到下标分别为2、4、7。

当我们查询key3时，假设下标为1，4，5发现三个位置都为1，那么key3一定存在么？不一定，key3可能存在。因为随着增加的值越来越多，被置为1的位置越来越多，具有一定概率的误判性。（不同值计算出来的hash值有可能相同，hash值不同，原值一定不同）

公式

m代表bit位的数量（字节数组长度）， n代表插入的元素个数，k代表hash函数个数，p代表误报率

计算hash函数数量

当m/n=10的时候我们需要的k元素数量为7，也就是7个哈希函数才能实现一个比较低的误报率。

计算需要字节数

下图是布隆过滤器误报率 p 与位数组大小 m 和集合中插入元素个数 n 的关系图，假定 Hash 函数个数选取最优数目

在线布隆计算器：https://hur.st/bloomfilter/

假定插入元素个数n=1亿，误报率为千分之一，则预计字节数组大小为171MB，hash函数个数为10

优点

1. 因为存储的是二进制数据，因此占用的空间很小
2. 它的插入和查询速度是很是快的，时间复杂度是O(K)
3. 保密性很好，由于自己不存储任何原始数据，只有二进制数据

缺点

1. 存在一定误报率
2. 需要预估插入数据量，超过则误报率大大提升
3. 不能删除（Counting Bloom filter 计数过滤器提供了一种在Bloom过滤器上实现删除操作而无需重新创建过滤器的方法）

应用

• 公司Dmp数据营销项目使用布隆过滤器来判断是否推送过广告。
• 公司Pwc爬虫使用布隆过滤器来判断是否爬取过url。
• Google Bigtable、Apache HBase和Apache Cassandra和PostgreSQL 使用布隆过滤器来减少对不存在的行或列的磁盘查找。避免昂贵的磁盘查找可显着提高数据库查询操作的性能。
• Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。
• Microsoft Bing搜索引擎对其搜索索引BitFunnel使用多级分层布隆过滤器。
• Redis 缓存穿透

Bloom filter used to speed up answers in a key-value storage system. Values are stored on a disk which has slow access times. Bloom filter decisions are much faster. However some unnecessary disk accesses are made when the filter reports a positive (in order to weed out the false positives). Overall answer speed is better with the Bloom filter than without the Bloom filter. Use of a Bloom filter for this purpose, however, does increase memory usage

在很多Key-Value系统中使用了布隆过滤器来加快查询过程，Value 保存在访问时间较慢的磁盘中，布隆过滤器可以快速判断某个Key对应的Value是否存在，然而某些误报会导致磁盘访问磁盘。总体来说，使用Bloom过滤比不使用Bloom过滤的应答速度更快，但是是引入布隆过滤器会带来一定的内存消耗

Guava实现布隆过滤器

/**
 * 预计要插入多少数据
 */
private static int size = 1000000;

/**
 * 期望的误判率
 */
private static double fpp = 0.001;

/**
 * 布隆过滤器
 */
private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);

public static void main(String[] args) {
    // 插入10万样本数据
    for (int i = 0; i < size; i++) {
        bloomFilter.put(i);
    }

    // 用另外十万测试数据，测试误判率
    int count = 0;
    for (int i = size; i < size + 100000; i++) {
        if (bloomFilter.mightContain(i)) {
            count++;
            System.out.println(i + "误判了");
        }
    }
    System.out.println("总共的误判数:" + count);
}

1097387误判了
1097421误判了
1098501误判了
.
.
.
总共的误判数:114

创建过滤器

• funnel：数据类型(通常是调用Funnels工具类中的)
• expectedInsertions：指望插入的值的个数
• fpp：误判率(默认值为0.03)
• strategy：哈希算法

static <T> BloomFilter<T> create(
    Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
  checkNotNull(funnel);
  checkArgument(
      expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions);
  checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);
  checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);
  checkNotNull(strategy);

  if (expectedInsertions == 0) {
    expectedInsertions = 1;
  }
  /*
   * TODO(user): Put a warning in the javadoc about tiny fpp values, since the resulting size
   * is proportional to -log(p), but there is not much of a point after all, e.g.
   * optimalM(1000, 0.0000000000000001) = 76680 which is less than 10kb. Who cares!
   */
  // 计算需要的字节数
  long numBits = optimalNumOfBits(expectedInsertions, fpp);
  // 计算需要的hash函数数量
  int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
  try {
    return new BloomFilter<T>(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy);
  } catch (IllegalArgumentException e) {
    throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
  }
}

插入

@CanIgnoreReturnValue
public boolean put(T object) {
  return strategy.put(object, funnel, numHashFunctions, bits);
}

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;
}

判断是否可能包含元素

/**
 * Returns {@code true} if the element <i>might</i> have been put in this Bloom filter, {@code
 * false} if this is <i>definitely</i> not the case.
 */
public boolean mightContain(T object) {
  return strategy.mightContain(object, funnel, numHashFunctions, bits);
}

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;
}

参考文献

1. https://en.wikipedia.org/wiki/Bloom_filter
2. https://www.cnblogs.com/liyulong1982/p/6013002.html