解读BloomFilter算法

介绍

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的关系如公式$\eqref{eq:mn}$所示
\begin{equation}
m=-{\frac {n\ln p}{(\ln 2)^{2}}} \label{eq:mn}
\end{equation}

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

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

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

误判率

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

这是因为当插入的元素很多的情况下,某个元素即使之前不存在,但是它所映射的k位已经被之前其他的元素置为1了,这样就会出现误判,BloomFilter会认为它已经存在了。但是这个概率是非常小的。根据维基百科的推导公式来说,误判率的大小p满足以下公式$\eqref{eq:p}$
\begin{equation}
\ln p = -{\frac {m}{n}}\left(\ln 2\right)^{2} \label{eq:p}
\end{equation}
其中m为位向量的长度,n为要插入元素的总数。当误判率为1%时,$\frac mn=9.6$即每个元素仅需要9.6个字节存储即可

Hash函数的个数k,与误判率大小p的关系为公式$\eqref{eq:k1}$ 所示
\begin{equation}
k = {-{\ln p} \over {\ln 2}} \label{eq:k1}
\end{equation}
当误判率大小为0.1时,k为3。当误判率大小为0.01时,k为7

与位向量的长度m和插入元素的总数n的关系为公式$\eqref{eq:k2}$ 所示
\begin{equation}
k = {\frac {m}{n}}\ln 2 \label{eq:k2}
\end{equation}

缺点

删除元素

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

幸运的是,目前学术界和工业界都有很多方法扩展已解决以上问题。具体可以参考本文第三部分 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引入了一个叫做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的源码,其实就是对公式$\eqref{eq:mn}$的实现

  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也对应了我们算法中公式$\eqref{eq:k2}$

  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位,$2^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值的运算,完美地解决了这个问题。
\begin{equation}
g_i(x)=h_1(x)+ih_2(x)+i^2 mod m \label{eq:gxhash}
\end{equation}

上述公式中$g_i(x)$为第i个hash函数。其中0 < 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是对公式$\eqref{eq:gxhash}$的一个实现的体现。首先根据MurMurHash计算出某个对象的64位hash值,将其分为两段,后32位为hash1,前32位为hash2。
将hash1看错公式$\eqref{eq:gxhash}$中的h1(x)计算后的结果,hash2看做是h2(x)计算后的结果,同时省去公式中的$i^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的数量,使得布隆过滤器可以支持删除操作。
但是这样会数倍地增加布隆过滤器的存储空间。

参考

坚持原创技术分享,您的支持将鼓励我继续创作!