Fork me on GitHub

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://vearne.cc

1. 前言

笔者早几年的工作经历和爬虫相关,为防止重复抓取URL, 要对每个需要抓取的URL进行判重,由于每天待抓取的URL数量都在好几亿条。因此去重服务的压力很大,当时相关的小伙伴就曾经调研过布隆过滤器。
本文笔者将结合Google Guava的BloomFilter(com.google.common.hash.BloomFilter),谈谈布隆过滤器的实现,以及它的一些特点。

2. 布隆过滤器简介

An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the m array positions, generating a uniform random distribution.

布隆过滤器由一个m位的bitArray以及k个hash函数组成。mk的具体值可以由布隆过滤器中预期存储的数据量n,以及可能出现假阳性概率p决定。

待存储的数据经过1个hash函数作用,并会将bitArray中的某一位置成1
k个hash函数最多会将bitArray中k位置成1

image_1di9k1gnl1av11i301jnm1bq114qbm.png-13.4kB

如上图所示,假定k=2
hash_func1将bitArray[3]=1
hash_func2将bitArray[8]=1

如果想判断数值1990是否在布隆过滤器中,只需要重新执行hash_func1和hash_func2,如果第3位和第8位都是1,那么1990可能在布隆过滤器中(存在假阳性的可能),反之第3位和第8位有1位为0,则1990一定不在布隆过滤器中。

可以换一个角度来解释布隆过滤器,每个hash函数都在尝试提取数据值的一部分特征。存储数据的过程(置1),实际是在标记,布隆过滤器中至少包含一个元素满足特定的特征。如果有一个特征不满足,那么该数据一定不在布隆过滤器中。

举个例子满足以下特征的就是哺乳动物

  • 身体表面有毛
  • 用肺呼吸
  • 体温恒定
  • 哺乳
  • 胎生

有一个特征不满足,肯定不是哺乳动物
从这里我们能够想到,布隆过滤器准确性很大程度上依赖于hash函数的选取,只有hash选择的合适才能够提取出数据值的特征。

3. Google Guava的BloomFilter

首先来看看BloomFilter 使用示例

package guava;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class TestBloomFilter {

    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) {
        // (m / n) * log(2), but avoid truncation due to division!
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }

    public static void main(String args[])
    {
        int n = 10000;
        float p = 0.01f;
        long m = optimalNumOfBits(n, p);
        System.out.println("optimalNumOfBits:" + m);
        System.out.println("optimalNumOfHashFunctions:" + optimalNumOfHashFunctions(n, m));

        BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(), n, p);
        for(int i=0;i<n*5;i++){
            filter.put(i*2);
        }
        int success = 0;
        int failed = 0;
        for(int i=2000;i<3000;i++){
            if (filter.mightContain(i) && i%2 ==0){
                success++;
            }
            if (filter.mightContain(i) && i%2 !=0){
                failed++;
            }
        }
        System.out.println(1- (success + 0.0)/(success + failed));
    }
}
create(Funnel<? super T> funnel, int expectedInsertions, double fpp)

创建空的BloomFilter
funnel: 数据类型
原生BloomFilter已经支持了int,String等数据类型,其它也可以通过实现Funnel接口来满足
expectedInsertions: 预期将存入的数据量, 相当于n
fpp: 能够承受的假阳性的概率

  • 预期存储的数据量n越大,bitArray的位数m越大, hash函数的个数k越大
  • fpp 越小,bitArray的位数越大

3.1 空间开销

我们来做个简单的定量分析

n p m k false positive probability(%)
10k 0.01 95850 约为11KB 7 1.38
100k 0.01 958505 约为119KB 7 0.39
100M 0.01 958505842 约为120MB 7 0.99

HashMap假定HashMap的装载系数为0.75,同样存储10k个数据,数据为int类型,则

10000 * 4 / 0.75 /1000 约需要53KB的空间

可见相比与HashMap, BloomFilter节约了将近80%的空间开销。当然BloomFilter有假阳性问题,但这个问题在很多场景下是可以接受的。
另外我们能看到k几乎没有变化,可认为是常数。因此写入和判重的时间复杂度是O(1)

3.2 特点2

Guava的BloomFilter的只能存数据,无法删除一个数据。
并且如果BloomFilter的数量超过expectedInsertions, 则假阳性的概率会上升
expectedInsertions:10k
fpp: 0.01

realInsertions false positive probability(%)
10k 1.38
20k 16.0
30k 31.5
40k 40.5

超过3倍expectedInsertions, BloomFilter几乎已经没法用了

4. 源码分析

在Google Guava的BloomFilter的实现中比较重要的有

预估bitArray的位数`m`
optimalNumOfBits()
预估hash函数的个数`k`
optimalNumOfHashFunctions()
写入数据
put()
判断是否包含
mightContain()

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

这里比较有意思的是
1)MURMUR128_MITZ_64使用的Murmur哈希,它与其它流行的哈希函数相比,对于规律性较强的key,MurmurHash的随机分布特征表现更良好。在前文笔者提到布隆过滤器准确性很大程度上依赖于hash函数的选取,所以这里选择了MurmurHash是有原因的。
2) k个hash函数其实是由2个hash函数演变来的

hash_func_i(x) = (hash_func1(x) + i * hash_func2(x) ) % m
1 <= i <= k

5. 总结

布隆过滤器和hyperloglog一样都是从概率方法上对集合数据结构进行的空间优化,前者用来判重,后者用来计数。他们在使用场景上,都一定局限性。但对于特定场景,空间和时间复杂度都非常的低,可以达到四两拨千斤的效果。

后记

2022年8月24日
n、p、m、k对布隆过滤器的计算影响可以看这个链接here

参考资料

  1. wikipedia-Bloom filter
  2. wikipedia-布隆过滤器
  3. Google Guava之BloomFilter源码分析及基于Redis的重构
  4. Murmur哈希

微信公众号

1 对 “聊聊布隆过滤器”的想法;

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据