jiaji's blog

Guava BloomFilter

BloomFilter简介

BloomFilter是一个可以快速判断一个元素是否在一个集合中的组件,它的设计也比较容易理解:构建的时候,一个元素经过几个hash函数hash后,命中一个bit数组的不同的位点,并把位点置为1。在判断的时候,也要执行同样的hash函数,只要有一个没有命中则这个元素一定不存在;否则有可能存在。只会有一种“误判”的情况:元素不在集合中,但被判断为在集合中。

因为构建时候多个元素经过hash可能命中同样的位点,这样会影响判断时候的准确率。可以想象一下,bit数组越大,hash函数散列效果越好,这样“冲突”的概率越小,判断的正确率越高。但是,扩大bit数组会占用更多内存,hash函数计算复杂度和数量会影响计算速度。所以如何平衡正确率与bit数组长度、hash函数的个数呢?有一个公式:

假设m是bit数组的bit的数量(长度),k是hash函数的数量,n是在构造时元素的数量,p为判断时的错误率。则当它们满足下边两个公式时,有近似最优解。

  1. m = -n * lnp / (ln2)^2

  2. k = m / n * ln2

具体的推导过程可以看下这里。

Guava中的实现

Guava中有一个BloomFilter的实现,下面来分析具体的实现方法:

初始化

Guava的BloomFilter提供一个静态的创建方法,支持三个参数:

  1. Funnel<? super T> 转为PrimitiveSink的对象的类型,推荐使用enum。Funnels中支持一些基础类型,也可以自己实现。
  2. expectedInsertions 预估的构造时元素的数量,即公式中的n。
  3. fpp 错误率,即公式中的p,范围为0-1.0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
checkNotNull(funnel);
checkArgument(
expectedInsertions >= 0, "Expected insertions (%s) must be >= 0", expectedInsertions);
checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);
checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);
checkNotNull(strategy);
if (expectedInsertions == 0) {
expectedInsertions = 1;
}
//根据公式1. 计算bit数组的bit的数m
long numBits = optimalNumOfBits(expectedInsertions, fpp);
//根据公式2. 计算hash函数(执行hash次数)的数量k
int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
try {
//生成bit数组,绑定hash策略(默认为MURMUR128_MITZ_64)
return new BloomFilter<T>(new BitArray(numBits), numHashFunctions, funnel, strategy);
} catch (IllegalArgumentException e) {
throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
}
}

构建

调用BloomFilter实例的put方法来添加元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public <T> boolean put(
T object, Funnel<? super T> funnel, int numHashFunctions, BitArray 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
//这里先和Long最大值与去掉符号位,模bit数组长度来定位,然后尝试将这位置1。最后加上Hashing.murmur3_128()结果的高8位后循环执行刚才过程。
bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);
combinedHash += hash2;
}
//判断bit数组是否发生了变化,在上边循环中有一位被置为1则说明有变化,添加元素成功,返回true;否则可能之前已经添加过,或者和别的元素hash结果冲突,返回false;
return bitsChanged;
}

可见Guava中BloomFilter的实现并不是真正用了多种hash函数,而是通过加法和取模实现再hash。

判断

判断过程和添加过程类似,当有一个应该为1的位为0,则这个元素肯定不在集合中,直接返回false。因为有一定误判率p,所以函数名为mightContain:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public <T> boolean mightContain(
T object, Funnel<? super T> funnel, int numHashFunctions, BitArray 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;
}

在工程中的应用

去重

BloomFilter常用在爬虫系统中的url去重,可以节省大量内存空间。

性能优化

BloomFilter可以挡在系统的最前边,进行流量有效性的判断和过滤。如果判断不是此系统的业务则直接丢弃,减轻服务压力。理想情况下,流量经过的组件的顺序是这样的:BloomFilter->本地缓存->远端缓存->db,中间每个环节都可以命中并返回,减轻对后边的压力。

关键词过滤

BloomFilter可以支持keyword filter。英文文章有自然的空格字符分词,所以可以直接将敏感词库建立BloomFilter,对文章进行过滤。但是中文就有点尴尬了,只能使用多模式匹配(AC自动机、 Wu-Manber等)的精确算法来进行过滤了。

分布式系统

对于分布式系统来说,每台机器上都会有自己的BloomFilter。每个BloomFilter都有自己的版本号,它们需要定时去一个统一的数据源(db或者文件)中load数据,并拿远端的版本号和自己本地版本号进行对比:如果相同则直接跳过,如果不同则需要拿远端数据进行增量构建;同时还需要定时在系统负载低时进行全量构建,保障所有机器上BloomFilter的有效性和正确性。