Yebangyu's Blog

Fond of Concurrency Programming and Machine Learning

深入解析Bloom Filter(上)

本文将介绍:

  • Bloom Filter和它的变形与拓展
  • Bloom Filter的使用场景
  • Bloom Filter的详细数学分析

提出问题

Google的爬虫每天需要抓取大量的网页。于是就有一个问题:每当爬虫分析出一个url的时候,是抓呢,还是不抓呢?如何知道这个url已经爬过了?

这个问题,归纳抽象后可以定义为:

给定一个集合S(注意,这里的集合是传统意义上的集合:元素彼此不同。本文不考虑multiset),给定一个元素e,需要判断$e\in S$ 是否成立。(学术界一般称为membership问题)

分析问题

都有哪些方案可以解决这个问题?

一种简单的想法是把url存储在一个哈希表中,每次去表里look up下判断是否存在。假如每个url占用40B,那么10亿条url将占用大概30多GB的内存!Can this be more space efficient ?

解决问题

我们可不可以不存url本身?这样子所需空间就会大大减少了。于是我们想到一个很经典的做法:bitmap(位图)。将集合S中的url哈希到bitmap上,给定一个url,只需要将它hash,得到它在bitmap的下标,检查该位置是否为1即可。

这样做空间是省了,可是也产生了一个问题:由于冲突(碰撞),不是集合S中的元素也可能被哈希到值为1的位置上,导致误报。

给定一个元素e,如果实际上$e\notin S$ 而被判为 $e\in S$,那么我们称e是false positive(伪正例。顺便说一句,false positive等的分析在machine learning的classification任务里评价model时非常重要)。

如何降低false positive的概率呢?Bloom Filter的想法是使用多个独立的哈希函数。

Standard Bloom Filter

在传统的Bloom Filter中,我们有:

集合S:其大小为m。也就是说,集合中有m个不同元素。

可用内存B:B被当成位数组bitmap来使用,大小为n。(有n个bit)。

哈希函数:有k个独立的、均匀分布的哈希函数。

Bloom Filter的做法是:初始时,所有比特位都初始化为0。对于集合中的每个元素,利用k个哈希函数,对它哈希得到k个位置,将bitmap中的对应的k个位置置为1。

给定一个元素e,为了判断它是否是集合中的元素,也利用该k个函数得到k个位置,检查该k个位置是否都为1,如果是,认为$e\in S$,否则认为$e\notin S$。

不难看出,如果$e\in S$,那么Bloom Filter肯定会正确判断出$e\in S$,但是它还是可能产生false positive。那么,如何分析false positive的概率呢?

false positive发生时,表示哈希该元素后得到的k个位置都为1。这个概率大概为:

$P\approx p_1^k$

其中$p_1$代表某位为1的概率,它等于:

$p_1 = 1 - p_0$

对于$p_0$,表示某个特定的比特位为0。什么时候该位才为0呢?也就是说m个元素各自经过k次哈希得到km个对象,没有一个对象定位到了该位置。某个对象定位到该位置的概率为$\frac{1}{n}$,因此我们可以得到:

$p_0 = (1 - \frac{1}{n})^{mk}$

分析$p_0$。在实际应用中,n一般很大,根据重要极限公式,我们有:

$p_0 = (1 - \frac{1}{n})^{mk} = (1-\frac{1}{n})^{-n{\frac{mk}{-n}}} \approx e^{-\frac{mk}{n}} $

代入到最上面的那个式子,我们不难得到:

$P \approx ({1 - e^{-\frac{mk}{n}}})^{k}$

当k为何值时,P取得最小,false positive possibility最低呢?

令 $f(k) = ({1 - e^{-\frac{mk}{n}}})^{k}$

$ln(f(k)) = kln({1 - e^{-\frac{mk}{n}}})$

$\frac{f\prime(k)}{f(k)} = ln({1 - e^{-\frac{mk}{n}}}) + k(\frac{1}{1 - e^{- \frac{mk}{n}}})(- e^{-\frac{mk}{n}})(\frac{-m}{n})$

$f\prime(k) = f(k)(ln({1 - e^{-\frac{mk}{n}}}) + k(\frac{1}{1 - e^{- \frac{mk}{n}}})(- e^{-\frac{mk}{n}})(\frac{-m}{n}))$

看起来够复杂了,然而别怕!!!

令$f\prime(k) = 0$ , 我们有(注意到$f(k) > 0$ 恒成立):

$ln({1 - e^{-\frac{mk}{n}}}) + k(\frac{1}{1 - e^{- \frac{mk}{n}}})(- e^{- \frac{mk}{n}})(\frac{-m}{n}) = 0$

作代换,令$\lambda = e^{-\frac{mk}{n}}$ 则 $k = \frac{-nln\lambda}{m}$,代入上式,得到

$(1-\lambda)ln(1-\lambda) = \lambda ln\lambda$

因此$\lambda = \frac{1}{2}$ , $k = \frac{n}{m}ln2$

也就是说,当n和m固定时,选择$k = \frac{n}{m}ln2$ 附近的一个整数,将使false positive possibility最小。

工程实现时,我们需要k个哈希函数或者哈希函数值。如何构造和获得k个独立的哈希函数呢?这篇论文 提出,只需要两个独立的哈希函数hf1和hf2即可,也就是通过如下方式获得k个哈希函数值:

hash value = hf1(key) + i*hf2(key)

其中i=0、1、2…k-1

Counting Bloom Filter

除了存在false positive这个问题之外,传统的Bloom Filter还有一个不足:无法支持删除操作(想想看,是不是这样的)。而Counting Bloom Filter(CBF)就是用来解决这个问题的。

在CBF中,维护的不是单纯的标示0或者1的比特位,而是计数器counter。对于集合中的每个元素,利用k个哈希函数,对它哈希得到k个位置,将对应的k个位置上的k个counter都加1。删除时,只需要把k个counter都减1即可。

那么,这个counter应该占用几位呢?分配太多,浪费空间;分配太少,容易溢出。通过下面的分析,我们可以知道,实际使用时,4位足矣。

考察(是考察,不是考查。这两个词有什么区别?)某个位置,该位置的计数器counter的值$\xi$

$P(\xi = c) \approx \binom{mk}{c} {(\frac{1}{n})}^{c}({1-\frac{1}{n}})^{mk-c} = B(km,\frac{1}{n})$

这个式子有点点复杂,然而回忆下概率论里的知识:若二项分布B(n,p)里n很大,p很小时,二项分布的极限近似分布是泊松分布$P(\lambda=k) = \frac{\lambda^k}{k!}{e}^{-\lambda}$,其中$\lambda=np$,因此:

$P(\xi = c) \approx \binom{mk}{c} {(\frac{1}{n})}^{c}({1-\frac{1}{n}})^{mk-c} \approx \frac{({\frac{km}{n}})^{c}}{c!}{e}^{-{\frac{km}{n}}}$

令$k = \frac{n}{m}ln2$,代入,我们得到

$P(\xi >16) \approx \frac{(ln2)^{16}}{16!} * \frac{1}{2} < \frac{1}{16!} = \frac{1}{20922789888000}$

也就是说,选择4位来存counter在实际情况中已经足矣,发生溢出的概率极小。

本文小结

总结下,Bloom Filter可以用在什么地方,或者说,在什么场景下,你应该想到这种技术:

1,回答是或者不是的问题。你需要判断一个元素是否属于某个集合,仅仅这样。你不应该要求更多。如果你想获得该元素对应的value或者还有其他payload,那么bloom filter不适合你,你需要哈希表。

2,允许false positive。也就是说,发生false positive不应该是致命的。比如说,搜索引擎的爬虫里,如果url不是set的元素,却被bloom filter过滤了,那么顶多就是不抓它而已,没啥特别大的损失。

3,空间敏感。作为一种概率数据结构,Bloom Filter不存储原始数据(比如说url),这也是它为什么space efficient的本质原因。

有了Standard Bloom Filter和Counting Bloom Filter,似乎可以满足绝大多数需求了,然而,这里面还是有问题。什么问题?请看下集