0%

结合 Guava 源码解读布隆过滤器

介绍

BloomFilter(布隆过滤器)是一种可以高效地判断元素是否在某个集合中的算法。

在很多日常场景中,都大量存在着布隆过滤器的应用。例如:检查单词是否拼写正确、网络爬虫的 URL 去重、黑名单检验,微博中昵称不能重复的检测等。

在工业界中,Google 著名的分布式数据库 BigTable 也用了布隆过滤器来查找不存在的行或列,以减少磁盘查找的 IO 次数;Google Chrome 浏览器使用 BloomFilter 来判断一个网站是否为恶意网站。

对于以上场景,可能很多人会说,用 HashSet 甚至简单的链表、数组做存储,然后判断是否存在不就可以了吗?

当然,对于少量数据来说,HashSet 是很好的选择。但是对于海量数据来说,BloomFilter 相比于其他数据结构在空间效率和时间效率方面都有着明显的优势。

但是,布隆过滤器具有一定的误判率,有可能会将本不存在的元素判定为存在。因此,对于那些需要 “零错误” 的应用场景,布隆过滤器将不太适用。具体的原因将会在第二部分中介绍。

同时其他章节的安排如下:

  • 在本文的第二部分,本文将会介绍 BloomFilter 的基本算法思想;
  • 第三部分将会基于 Google 开源库 Guava 来讲解 BloomFilter 的具体实现;
  • 在第四部分中,将会介绍一些开源的 BloomFilter 的扩展,以解决目前 BloomFilter 的不足。

算法讲述

布隆过滤器是基于 Hash 来实现的,在学习 BloomFilter 之前,也需要对 Hash 的原理有基本的了解。个人认为,BloomFilter 的总体思想实际上和 bitmap 很像,但是比 bitmap 更节省空间,误判率也更低。

BloomFilter 的整体思想并不复杂,主要是使用 k 个 Hash 函数将元素映射到位向量的 k 个位置上面,并将这 k 个位置全部置为 1。当查找某元素是否存在时,查找该元素所对应的 k 位是否全部为 1 即可说明该元素是否存在。

算法流程

BloomFilter 的整体算法流程可总结为如下步骤:

  1. BloomFilter 初始化为 m 位长度的位向量,每一位均初始化为 0
    step-1
  2. 使用 k 个相互独立的 Hash 函数,每个 Hash 函数将元素映射到 {1…m} 的范围内,并将对应的位置为 1。
    step-2
    如上图所示,元素 x 分别被三个 Hash 函数映射到了三个位置 8、1、14,并将这三个位置从 0 变为 1。
  3. 若检查一个元素 y 是否存在,首先第一步使用 k 个 Hash 函数将元素 y 映射到 k 位。分别检测每一位是否为 0。若某一位为 0,则元素 y 一定不存在,若全部为 1,则有可能存在。

空间复杂度
BloomFilter 使用位向量来表示元素,而不存储本身,这样极大压缩了元素的存储空间。其空间复杂度为 O(m),m 是位向量的长度。而 m 与插入总数量 n 的关系如公式 (1)(1) 所示

m=nlnp(ln2)2(1)m=-{\frac {n\ln p}{(\ln 2)^{2}}} \tag{1}

我们可以利用这个公式来算一下需要抓取 100 万个 URL 时 BloomFilter 所占据的空间。

假设要求误判率为 1%,因此该公式可转化为 m=9.6nm=9.6*n。故此时 BloomFilter 位向量的大小为 100w9.6=960wbit100w*9.6 = 960w bit,约 1.1M 内存空间。
只需要 1.1M 的内存空间,就可满足 100 万个 url 的去重需求,这个空间复杂度之低不可谓不惊人。
实际上,哪怕是 1 亿个 URL,也仅需 100M 左右的内存空间即可满足 BloomFilter 的空间需求,这对于绝大部分爬虫的体量来说,是完全可行的。

时间复杂度
时间复杂度方面 BloomFilter 的时间复杂度仅与 Hash 函数的个数 k 有关,即 O(k)O(k)

误判率

为什么说,在查找元素时,即使某个元素所映射的 k 位全部位 1,依然无法确定它一定存在?

这是因为当插入的元素很多的情况下,某个元素即使之前不存在,但是它所映射的 k 位已经被之前其他的元素置为 1 了,这样就会出现误判,BloomFilter 会认为它已经存在了。

但是这个概率是非常小的。根据维基百科的推导公式来说,误判率的大小 p 满足以下公式 (2)(2):

lnp=mn(ln2)2(2)\ln p = -{\frac {m}{n}}\left(\ln 2\right)^{2} \tag{2}

其中 m 为位向量的长度,n 为要插入元素的总数。当误判率为 1% 时,mn=9.6\frac mn=9.6 即每个元素仅需要 9.6 个字节存储即可

Hash 函数的个数 k,与误判率大小 p 的关系为公式 (3)(3) 所示

k=lnpln2(3)k = {-{\ln p} \over {\ln 2}} \tag{3}

当误判率大小为 0.1 时,k 为 3。当误判率大小为 0.01 时,k 为 7

而,k 与位向量的长度 m 和插入元素的总数 n 的关系为公式 (4)(4) 所示

k=mnln2(4)k = {\frac {m}{n}}\ln 2 \tag{4}

缺点

删除元素

BloomFilter 由于并不存储元素,而是用位的 01 来表示元素是否存在,并且很有可能一个位时被多个元素同时使用。所以无法通过将某元素对应的位置为 0 来删除元素。

幸运的是,目前学术界和工业界都有很多方法扩展已解决以上问题。具体可以参考本文第三部分 [BloomFilter 的优化和扩展](#BloomFilter 的优化和扩展)

Guava’s BloomFilter 源码剖析

Guava 是 Google 主导开发的基于 Java 6 开发的一个开源工具包, 其中便包含了 一个 BloomFilter 的实现。Guava’s BloomFilter 也是一个完全可工程化的 BloomFilter 的最佳实现范本,本文基于 Guava 19.0 的源码进行解读。

使用介绍

在讲解 Guava BloomFilter 的源码之前,还是要用一个简单的例子来说明下 Guava 中 BloomFilter 的使用,以便更好地理解 Guava。具体代码在 这里

在这个例子中,我们定义了一个 Person 类, 来表示一个人的姓名信息。代码如下

1
2
3
4
5
6
class Person{
private String firstName;
private String lastName;
//getter..
//setter..
}

在这个例子中,我们会将 Person 对象传递给 BloomFilter,当该对象的 firstName+lastName 在 BloomFilter 中存在时,会提示已存在,不将其加入 BloomFilter 中。

但是对于 BloomFilter 来说,它无法主动地知道如何把一个自定义类的对象转化为 hash 值,也许有人会说,重写类的 hashcode 方法不就行了吗?

事实上还真不行,因为这和 BloomFilter 的概念冲突了,BloomFilter 简单来说是通过计算出 k 个不同的 hash 值来定位元素,重写了 hashcode 那么这个计算 k 个 hash 的过程将毫无意义。

Guava 通过将自定义对象分解为普通类型,对普通类型进行 Hash 值的计算,来将对象存入 BloomFilter 中。

这里 Guava 引入了一个叫做 Funnel 的类,Funnel 类定义了如何把一个具体的对象类型分解为原生字段值,从而将值分解为 Byte 以供后面 BloomFilter 进行 hash 运算。通过使用这个类,我们可以自己定义一个属于自己类的 Funnel。如下代码

1
2
3
4
5
6
7
8
9
enum PersonFunnel implements Funnel<Person> {
INSTANCE;

@Override
public void funnel(Person person, PrimitiveSink into) {
into.putString(person.getFirstName(), Charset.defaultCharset())
.putString(person.getLastName(), Charset.defaultCharset());
}
}

此外,Guava 预定义了一些原生类型的 Funnel,如 String、Long、Integer。具体代码可以在 这里看到。当我们的 BloomFilter 存储的是这些原生类型时,不用再额外自行写 Funnel,直接使用 Guava 预定义的这些即可。

以下是整个代码调用的流程

1
2
3
4
5
6
7
8
9
10
11
12
class BloomFilterSample{
public static void main(String[] args) {
// 创建一个 BloomFilter,其预计插入的个数为 10,误判率大约为 0.01
BloomFilter<Person> bloomFilter = BloomFilter.create(PersonFunnel.INSTANCE, 10, 0.01);
// 查询 new Person("chen", "yahui") 是否存在
System.out.println(bloomFilter.mightContain(new Person("chen", "yahui"))); //false
// 将 new Person("chen", "yahui") 对象放入 BloomFilter 中
bloomFilter.put(new Person("chen","yahui"));
// 再次查询 new Person("chen", "yahui") 是否存在
System.out.println(bloomFilter.mightContain(new Person("chen", "yahui"))); //true
}
}

源码解读

初始化 BloomFilter

在例子中,我们通过调用 BloomFilter.create 工厂方法来生成一个 BloomFilter

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<T> BloomFilter<T> create(Funnel<? super T> funnel,
long expectedInsertions, // 预期会插入多少元素
double fpp, // 自定义误判率
Strategy strategy //Hash 策略
) {
if (expectedInsertions == 0) {
expectedInsertions = 1;
}
...
// 根据插入的数量和误判率来得出位向量应有的长度, 这里使用的算法就是公式 2
long numBits = optimalNumOfBits(expectedInsertions, fpp);
// 根据插入的数量和位向量的长度来得出应该用多少个 Hash 函数,这里使用的算法是公式 4
int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
return new BloomFilter<T>(new BitArray(numBits), numHashFunctions, funnel, strategy);
}

整个创建流程非常清晰,如果看懂了本文的算法描述部分,应该不难理解该段代码。整个初始化流程的目的主要有两个:根据参数计算出位向量的长度以及 Hash 函数的个数

  1. 根据预期插入的数量 expectedInsertions 和自定义的误判率 fpp 来得到位向量的长度 numBits,其中 optimalNumOfBits 的实现如下
1
2
3
4
5
6
7
// 根据插入的数量和误判率来得出位向量应有的长度
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)));
}

可以很明显看出,optimalNumOfBits 的源码,其实就是对公式 (1)(1) 的实现
2. 根据插入的数量 expectedInsertions 和位向量的长度 numBits 来得出应该用多少个 Hash 函数,其中 optimalNumOfHashFunctions 的实现如下

1
2
3
4
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)));
}

同样,optimalNumOfHashFunctions 也对应了我们算法中公式 (4)(4)
3. 根据 numBits 生成 BitArray。
BitArray 是 Guava 中位向量的表示,具体的实现细节,将会在下一节中讲述。

位向量的表示

本节主要讲述了 Guava 中位向量的表示,此部分对于 BloomFilter 的整体算法流程的理解关联性并不是特别强。读者如对此部分不感兴趣,可直接跳过此节。

位向量是 BloomFilter 的存储表示,所有的数据都在 BloomFilter 中存储。如何更高效地表示位向量也是一个优质的 BloomFilter 代码重要考量标准。
在 Guava 中,自定义了 BitArray 类, 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class BitArray {
final long[] data;
long bitCount;

BitArray(long bits) {
// 对于长度为 m 的位向量来说,对应的 long 数组的长度应为 m/64 向上取整。
this(new long[Ints.checkedCast(LongMath.divide(bits, 64, RoundingMode.CEILING))]);
}

boolean set(long index) {
if (!get(index)) {
data[(int) (index >>> 6)] |= (1L << index);
bitCount++;
return true;
}
return false;
}

boolean get(long index) {
return (data[(int) (index >>> 6)] & (1L << index)) != 0;
}
}

在 BitArray 中,使用 long 数组来表示位向量,一个数组元素对应位向量的 64 位,所以对于长度为 m 的位向量来说,对应的 long 数组的长度应为 m/64 向上取整。

1
new long[Ints.checkedCast(LongMath.divide(bits, 64, RoundingMode.CEILING))]

在 BloomFilter 算法讲解部分,我们可以看到,对于位向量的常用操作主要有两个,将位向量某一位置为 1 以及查看位向量某一位是否为 1。分别对应源码中的 set 操作和 get 操作。
本文只讲下 get 方法的源码部分,set 方法与 get 方法类似,不再累述。

get 方法大致可以分为两部分

  1. data[(int) (index >>> 6)] 定位到元素
    上面讲到 long 数组的每一个元素都包含位向量其中的 64 位,如果想要找出某个位的 bit,那么首先第一步就是定位到该 bit 所在的元素编号。我们一般的做法是 index/64
    而源码中使用了 index >>> 6, 逻辑右移 6 位,26=642^6=64, 其效果与除以 64 相同。采用位运算的速度比普通的除法要快很多。
  2. … & (1L << index) 获取位的状态
    源码中直接将要查看的 bit 以及同一数组元素块的 64 位 bits 一起取出,将 1L 左移 index 位后求且运算,最终即可得出该位的值。

k 个 hash 函数的选取

在 Hash 函数的选取方面,一个很重要的问题就是如何选取多个 Hash 函数?

我们在对元素进行映射的时候,Hash 函数的个数 k 的选取,最少也得为 3 个,最多可能多达十几个甚至更多,而目前世界上可商用的高质量的开源的 Hash 方法,远远达不到 BloomFilter 的需求。
在论文 《Bloom Filters in Probabilistic Verification》 中提出了一种算法,把原本需要几十个 hash 函数的 bloom filter 转化成了两个 hash 值的运算,完美地解决了这个问题。

gi(x)=h1(x)+ih2(x)+i2modm(5)g_i(x)=h_1(x)+ih_2(x)+i^2 mod m \tag{5}

上述公式中 gi(x)g_i(x) 为第 i 个 hash 函数。其中 0<i<k0 < i < k。也就是说使用 hash1() 和 hash2() 对一次输入求出两个不同的 hash 值,然后将这两个 hash 值代入公式,求出 k 个 hash 值。
整体的计算流程如下:

1
2
3
4
5
6
7
8
9
// 准备阶段
h1 = hash1(input), h2 = hash2(input)

// 求出 k 个 hash 值
g0(x) = h1 第 0 个 hash 函数求出的 hash 值
g1(x) = h1+h2+11 个 hash 函数求出的 hash 值
g2(x) = h1+2*h2+42 个 hash 函数求出的 hash 值
...
gk-1(x) = h1+(k-1)*h2+(k-1)^2 第 k-1 个 hash 函数求出的 hash 值

在哈佛大学 2006 年的一篇论文《Less hashing, same performance: building a better bloom filter》中,对此方法的有效性进行了验证,证明了此种方法不会对 BloomFilter 的效率有所恶化。

Guava 实现了两种策略 MURMUR128_MITZ_32 和 MURMUR128_MITZ_64,其所有的实现类为 BloomFilterStrategies
本文针对 Guava 的 BloomFilter 所采用的 MURMUR128_MITZ_32 策略进行讲解,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 public <T> boolean put(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);

boolean bitsChanged = false;
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;
}
bitsChanged |= bits.set(combinedHash % bitSize);
}
return bitsChanged;
}
}

MURMUR128_MITZ_32 是对公式 (5)(5) 的一个实现的体现。首先根据 MurMurHash 计算出某个对象的 64 位 hash 值,将其分为两段,后 32 位为 hash1,前 32 位为 hash2。
将 hash1 看成公式 (5)(5) 中的 h1(x) 计算后的结果,hash2 看做是 h2(x) 计算后的结果,同时省去公式中的 i2i^2,将 hash1 和 hash2 代入公式计算。

在 Hash 函数选取方面,Guava 采用了 MurmurHash3 算法。MurmurHash 算法是 2008 年提出的一种 Hash 算法,运算简单高效,而且随机性强。目前最新的版本为 MurmurHash3。

MurmurHash3 能够产生出 32-bit 或 128-bit 两种哈希值。在 MURMUR128_MITZ_32 和 MURMUR128_MITZ_64 都选择使用了 128-bit 的结果。二者不同的是,MURMUR128_MITZ_32 仅使用 128-bit 的前 64 位。而 MURMUR128_MITZ_64 完全使用了 128 位的结果。

BloomFilter 的优化和扩展

Counting BloomFilter

上文提到布隆过滤器无法支持元素的删除操作, Counting BloomFilter 通过存储位元素每一位的置为 1 的数量,使得布隆过滤器可以支持删除操作。
但是这样会数倍地增加布隆过滤器的存储空间。

参考

cyhone wechat