程序世界的算法都要在时间, 资源占用甚至正确率等多种因素间进行平衡. 同样的问题, 所属的量级或场景不同, 所用算法也会不同, 其中也会涉及很多的 trade-off.
If there's one rule in programming, it's this: there will always be trade-offs.
你是否真的存在
今天我们就来探讨如何判断一个值是否存在于已有的集合问题. 这类问题在很多场景下都会遇到, 比如说防止缓存击穿, 爬虫重复 URL 检测, 字典纠缠和 CDN 代理缓存等.
我们以网络爬虫为例. 网络间的链接错综复杂, 爬虫程序在网络间 "爬行" 很可能会形成 "环". 为了避免形成 "环", 程序需要知道已经访问过网站的 URL. 当程序又遇到一个网站, 根据它的 URL, 怎么判断是否已经访问过呢?
第一个想法就是将已有 URL 放置在 HashSet 中, 然后利用 HashSet 的特性进行判断. 它只花费 O(1)的时间. 但是, 该方法消耗的内存空间很大, 就算只有 1 亿个 URL, 每个 URL 只算 50 个字符, 就需要大约 5GB 内存.
如何减少内存占用呢? URL 可能太长, 我们使用 MD5 等单向哈希处理后再存到 HashSet 中吧, 处理后的字段只有 128Bit, 这样可以节省大量的空间. 我们的网络爬虫程序又可以继续执行了.
但是好景不长, 网络世界浩瀚如海, URL 的数量急速增加, 以 128bit 的大小进行存储也要占据大量的内存.
这种情况下, 我们还可以使用 BitSet, 使用哈希函数将 URL 处理为 1bit, 存储在 BitSet 中. 但是, 哈希函数发生冲突的概率比较高, 若要降低冲突概率到 1%, 就要将 BitSet 的长度设置为 URL 个数的 100 倍.
但是冲突无法避免, 这就带来了误判. 理想中的算法总是又准确又快捷, 但是现实中往往是 "一地鸡毛". 我们真的需要 100% 的正确率吗? 如果需要, 时间和空间的开销无法避免; 如果能够忍受低概率的错误, 就有极大地降低时间和空间的开销的方法.
所以, 一切都要 trade-off. 布隆过滤器 (Bloom Filter) 就是一种具有较低错误率, 但是极大节约空间消耗的算法.
布隆过滤器
Bloom Filter 是一种空间效率很高的随机数据结构, 它利用位数组很简洁地表示一个集合, 并能判断一个元素是否属于这个集合. Bloom Filter 的这种高效是有一定代价的: 在判断一个元素是否属于某个集合时, 有可能会把不属于这个集合的元素误认为属于这个集合(false positive). 因此, Bloom Filter 不适合那些 "零错误" 的应用场合. 而在能容忍低错误率的应用场合下, Bloom Filter 通过极少的错误换取了存储空间的极大节省.
A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom filter has a 100% recall rate. In other words, a query returns either "possibly in set" or "definitely not in set".
上述描述引自维基百科, 特点总结为如下:
空间效率高的概率型数据结构, 用来检查一个元素是否在一个集合中.
对于一个元素检测是否存在的调用, BloomFilter 会告诉调用者两个结果之一: 可能存在或者一定不存在.
布隆过滤器的使用场景很多, 除了上文说的网络爬虫, 还有处理缓存击穿和避免磁盘读取等. Goole Bigtable,Apache HBase 和 PostgreSQL 等都使用了布隆过滤器.
我们就以下面这个例子具体描述使用 BloomFilter 的场景, 以及在此场景下, BloomFilter 的优势和劣势.
一组元素存在于磁盘中, 数据量特别大, 应用程序希望在元素不存在的时候尽量不读磁盘, 此时, 可以在内存中构建这些磁盘数据的 BloomFilter, 对于一次读数据的情况, 分为以下几种情况:
我们知道 HashMap 或者 Set 等数据结构也可以支持上述场景, 这里我们就具体比较一下二者的优劣, 并给出具体的数据.
精确度量十分重要, 对于算法的性能, 我们不能只是简单的感官上比较, 要进行具体的计算和性能测试. 找到不同算法之间的平衡点, 根据平衡点和现实情况来决定使用哪种算法. 就像 Redis 一样, 它对象在不同情况下使用不同的数据结构, 比如说列表对象的内置结构可以为 ziplist 或者 linkedlist, 在不同的场景下使用不同的数据结构.
请求的元素不在磁盘中, 如果 BloomFilter 返回不存在, 那么应用不需要走读盘逻辑, 假设此概率为 P1. 如果 BloomFilter 返回可能存在, 那么属于误判情况, 假设此概率为 P2. 请求的元素在磁盘中, BloomFilter 返回存在, 假设此概率为 P3.
如果使用 HashMap 等数据结构, 情况如下:
请求的数据不在磁盘中, 应用不走读盘逻辑, 此概率为 P1+P2
请求的元素在磁盘中, 应用走读盘逻辑, 此概率为 P3
假设应用不读盘逻辑的开销为 C1, 走读盘逻辑的开销为 C2, 那么, BloomFilter 和 hashmap 的开销分别为
- Cost(BloomFilter) = P1 C1 + (P2 + P3) C2
- Cost(HashMap) = (P1 + P2) C1 + P3 C2;
- Delta = Cost(BloomFilter) - Cost(HashMap) = P2 * (C2 - C1)
因此, BloomFilter 相当于以增加 P2 * (C2 - C1)的时间开销, 来获得相对于 HashMap 而言更少的空间开销.
既然 P2 是影响 BloomFilter 性能开销的主要因素, 那么 BloomFilter 设计时如何降低概率 P2(即误判率 false positive probability)呢?, 接下来的 BloomFilter 的原理将回答这个问题.
原理解析
初始状态下, 布隆过滤器是一个包含 m 位的位数组, 每一位都置为 0.
为了表达 S={x1, x2,...,xn}这样一个 n 个元素的集合, Bloom Filter 使用 k 个相互独立的哈希函数, 它们分别将集合中的每个元素映射到 {1,...,m} 的范围中. 对任意一个元素 x, 第 i 个哈希函数映射的位置 hi(x)就会被置为 1(1≤i≤k). 注意, 如果一个位置多次被置为 1, 那么只有第一次会起作用, 后面几次将没有任何效果. 在下图中, k=3, 且有两个哈希函数选中同一个位置(从左边数第五位).
在判断 y 是否属于这个集合时, 我们对 y 应用 k 次哈希函数, 如果所有 hi(y)的位置都是 1(1≤i≤k), 那么我们就认为 y 是集合中的元素, 否则就认为 y 不是集合中的元素. 下图中 y1 就不是集合中的元素. y2 则可能属于这个集合, 或者刚好是一个误判.
下面我们来看一下具体的例子, 哈希函数的数量为 3, 首先加入 1,10 两个元素. 通过下面两个图, 我们可以清晰看到 1,10 两个元素被三个不同的韩系函数映射到不同的 bit 上, 然后判断 3 是否在集合中, 3 映射的 3 个 bit 都没有值, 所以判断绝对不在集合中.
关于误判率, 实际的使用中, 期望能给定一个误判率期望和将要插入的元素数量, 能计算出分配多少的存储空间较合适. 这涉及很多最优数值计算问题, 比如说错误率估计, 最优的哈希函数个数和位数组的大小等, 相关公式计算感兴趣的同学可以自行百度, 重温一下大学的计算微积分时光.
- /** guava 实现的以 CAS 方式设置每个 bit 位的 bit 数组 */
- private final LockFreeBitArray bits;
- /** hash 函数的个数 */
- private final int numHashFunctions;
- /** guava 中将对象转换为 byte 的通道 */
- private final Funnel<? super T> funnel;
- /**
- * 将 byte 转换为 n 个 bit 的策略, 也是 bloomfilter hash 映射的具体实现
- */
- private final Strategy strategy;
- interface Strategy extends java.io.Serializable {
- /** 设置元素 */
- <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits);
- /** 判断元素是否存在 */
- <T> boolean mightContain(
- T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits);
- .....
- }
- enum BloomFilterStrategies implements BloomFilter.Strategy {
- MURMUR128_MITZ_32() {//....}
- MURMUR128_MITZ_64() {//....}
- }
- public <T> boolean put(
- T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits) {
- long bitSize = bits.bitSize();
- // 先利用 murmur3 hash 对输入的 funnel 计算得到 128 位的哈希值, funnel 现将 object 转换为 byte 数组,
- // 然后在使用哈希函数转换为 long
- long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
- // 根据 hash 值的高低位算出 hash1 和 hash2
- int hash1 = (int) hash64;
- int hash2 = (int) (hash64>>> 32);
- boolean bitsChanged = false;
- // 循环体内采用了 2 个函数模拟其他函数的思想, 相当于每次累加 hash2
- for (int i = 1; i <= numHashFunctions; i++) {
- int combinedHash = hash1 + (i * hash2);
- // 如果是负数就变为正数
- if (combinedHash <0) {
- combinedHash = ~combinedHash;
- }
- // 通过基于 bitSize 取模的方式获取 bit 数组中的索引, 然后调用 set 函数设置.
- bitsChanged |= bits.set(combinedHash % bitSize);
- }
- return bitsChanged;
- }
- public <T> boolean mightContain(
- T object, Funnel<? super T> funnel, int numHashFunctions, BitArray bits) {
- long bitSize = bits.bitSize();
- long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
- int hash1 = (int) hash64;
- int hash2 = (int) (hash64>>> 32);
- for (int i = 1; i <= numHashFunctions; i++) {
- int combinedHash = hash1 + (i * hash2);
- // Flip all the bits if it's negative (guaranteed positive number)
- if (combinedHash <0) {
- combinedHash = ~combinedHash;
- }
- // 和 put 的区别就在这里, 从 set 转换为 get, 来判断是否存在
- if (!bits.get(combinedHash % bitSize)) {
- return false;
- }
- }
- return true;
- }
- 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;
- // 经典的 CAS 自旋重试机制
- do {
- oldValue = data.get(longIndex);
- newValue = oldValue | mask;
- if (oldValue == newValue) {
- return false;
- }
- } while (!data.compareAndSet(longIndex, oldValue, newValue));
- bitCount.increment();
- return true;
- }
- http://oserror.com/backend/bloomfilter/
- https://en.wikipedia.org/wiki/Bloom_filter
- https://juejin.im/post/5c9442ae5188252d77392241
来源: https://yq.aliyun.com/articles/700552