关于java:5分钟掌握布隆过滤器

布隆过滤器

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

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

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

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

比方上面，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，估算逻辑内存如下。

注：理论物理内存占用大于逻辑内存。

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

利用场景

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

弱明码检测

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

垃圾邮件地址过滤

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

浏览器检测钓鱼网站

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

缓存穿透

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

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

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

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

小结

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

参考

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

https://hur.st/bloomfilter