布隆过滤器

布隆过滤器是一种由位数组和多个哈希函数组成概率数据结构，返回两种后果 可能存在 和 肯定不存在。

布隆过滤器里的一个元素由多个状态值独特确定。位数组存储状态值，哈希函数计算状态值的地位。

依据它的算法构造，有如下特色：

  • 应用无限位数组示意大于它长度的元素数量，因为一个位的状态值能够同时标识多个元素。
  • 不能删除元素。因为一个位的状态值可能同时标识着多个元素。
  • 增加元素永远不会失败。只是随着增加元素增多，误判率会回升。
  • 如果判断元素不存在，那么它肯定不存在。

比方上面，X,Y,Z 别离由 3个状态值独特确定元素是否存在，状态值的地位通过3个哈希函数别离计算。

数学关系

误判概率

对于误判概率，因为每个位的状态值可能同时标识多个元素，所以它存在肯定的误判概率。如果位数组满，当判断元素是否存在时，它会始终返回true，对于不存在的元素来说，它的误判率就是100%。

那么，误判概率和哪些因素无关，已增加元素的数量，布隆过滤器长度（位数组大小），哈希函数数量。

依据维基百科推理误判概率 \( P_{fp} \)有如下关系：

$${ P_{fp} =\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{{-\frac {kn}{m}}}\right)^{k}}$$

  • $m$ 是位数组的大小；
  • $n$ 是曾经增加元素的数量；
  • $k$ 是哈希函数数量；
  • $e$ 数学常数，约等于2.718281828。

由此能够失去，当增加元素数量为0时，误报率为0；当位数组全都为1时，误报率为100%。

不同数量哈希函数下，$ P_{fp}$ 和 $ n$ 的关系如下图：

依据误判概率公式能够做一些事

  • 估算最佳布隆过滤器长度。
  • 估算最佳哈希函数数量。

最佳布隆过滤器长度

当 \(n \) 增加元素和 \( P_{fp} \)误报概率确定时，\( m \) 等于：

$${\displaystyle m=-{\frac {n\ln P_{fp}}{(\ln 2)^{2}}} \approx -1.44\cdot n\log _{2}P_{fp}}$$

最佳哈希函数数量

当 \( n \) 和 \(P_{fp} \) 确定时，\( k \) 等于：

$${\displaystyle k=-{\frac {\ln P_{fp} }{\ln 2}}=-\log _{2}P_{fp} }$$

当 \( n \) 和 \( m \) 确定时，\( k \) 等于：

$${\displaystyle k={\frac {m}{n}}\ln 2}$$

实现布隆过滤器

应用布隆过滤器前，咱们个别会评估两个因素。

  • 预期增加元素的最大数量。
  • 业务对谬误的容忍水平。比方1000个容许错一个，那么误判概率应该在千分之一内。

很多布隆过滤工具都提供了预期增加数量和误判概率配置参数，它们会依据配置的参数计算出最佳的长度和哈希函数数量。

Java中有一些不错的布隆过滤工具包。

  • Guava 中 BloomFilter。
  • redisson 中 RedissonBloomFilter 能够redis 中应用。

看下 Guava 中 BloomFilter 的简略实现，创立前先计算出位数组长度和哈希函数数量。

 static <T> BloomFilter<T> create(      Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {    /**     * expectedInsertions：预期增加数量     * fpp：误判概率     */    long numBits = optimalNumOfBits(expectedInsertions, fpp);    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);    try {      return new BloomFilter<T>(new BitArray(numBits), numHashFunctions, funnel, strategy);    } catch (IllegalArgumentException e) {      throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);    }  }

依据最佳布隆过滤器长度公式，计算最佳位数组长度。

static long optimalNumOfBits(long n, double p) {    if (p == 0) {      p = Double.MIN_VALUE;    }    return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));  }

依据最佳哈希函数数量公式，计算最佳哈希函数数量。

static int optimalNumOfHashFunctions(long n, long m) {    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));  }

在redisson 中 RedissonBloomFilter 计算方法也是统一。

    private int optimalNumOfHashFunctions(long n, long m) {        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));      }    private long optimalNumOfBits(long n, double p) {        if (p == 0) {            p = Double.MIN_VALUE;        }        return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));    }

内存占用

构想一个手机号去重场景，每个手机号占用22 Byte，估算逻辑内存如下。

expectedHashSetfpp=0.0001fpp=0.0000001
100万18.28MB2.29MB4MB
1000万182.82MB22.85MB40MB
1亿1.78G228.53MB400MB
注：理论物理内存占用大于逻辑内存。

误判概率 \( p \) 和已增加的元素 \( n \)，位数组长度 \( m \)，哈希函数数量 \( k \) 关系如下：

利用场景

  1. 弱明码检测；
  2. 垃圾邮件地址过滤。
  3. 浏览器检测钓鱼网站；
  4. 缓存穿透。

弱明码检测

保护一个哈希过弱明码列表。当用户注册或更新明码时，应用布隆过滤器查看新密码，检测到提醒用户。

垃圾邮件地址过滤

保护一个哈希过垃圾邮件地址列表。当用户接管邮件，应用布隆过滤器检测，检测到标识为垃圾邮件。

浏览器检测钓鱼网站

应用布隆过滤器来查找钓鱼网站数据库中是否存在某个网站的 URL。

缓存穿透

缓存穿透是指查问一个基本不存在的数据，缓存层和数据库都不会命中。当缓存未命中时，查询数据库

  1. 数据库不命中，空后果不会写回缓存并返回空后果。
  2. 数据库命中，查问后果写回缓存并返回后果。

一个典型的攻打，模仿大量申请查问不存在的数据，所有申请落到数据库，造成数据库宕机。

其中一种解决方案，将存在的缓存放入布隆过滤器，在申请前进行校验过滤。

小结

对于千万亿级别的数据来说，应用布隆过滤器具备肯定劣势，另外依据业务场景正当评估预期增加数量和误判概率是要害。

参考

https://en.wikipedia.org/wiki...

https://hur.st/bloomfilter