版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | http://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一样都是从概率方法上对集合数据结构进行的空间优化,前者用来判重,后者用来计数。他们在使用场景上,都一定局限性。但对于特定场景,空间和时间复杂度都非常的低,可以达到四两拨千斤的效果。

参考资料

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

如果我的文章对你有帮助,你可以给我打赏以促使我拿出更多的时间和精力来分享我的经验和思考总结。

微信支付码

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

发表评论

电子邮件地址不会被公开。

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