bloom filter

从 mm 的 blog 介绍的东西开始补 engineering 方面的东西,bloom filter 算是第一个。基础部分可以参考 wikipedia 的介绍

bloom filter 诞生的原因之一是为了减少不必要的数据库查询,可以认为是 hash table 的一种扩展。我们知道 hash table 一般都是作为 in-memory 的一张表(假定大小为 N),我们通过 hash function 将存入表内的 key 映射到 [0, N) 这个区间的整数里面,这样在没有 collision 的情况下,我们只需要 O(1) 时间便能确定某个 key 是否在这个表中,为此 hash table 可以用来实现 STL 的 set 和 map 这类容器(见 unordered_set 和 unordered_map)。

相应的通过 BST 实现 set/map 也是常见的一种选择,但是这时判定某个 key 是否在表中的时间复杂度变为了 O(\log N),但是 tree 结构的好处是不一定需要将整个树放在内存里面,通过 B+ tree 这类结构,我们可以极大的减少 disk IO 请求,这也就是现代数据库实现的基本数据结构。这样一旦数据量超过了 memory 可以容纳的限制,数据库/B+ tree 就成了不二的选择。

在某些 internet 应用中,频繁的对数据库进行查询会占用大量的系统开销,特别 NoSQL 类型数据库的普及应用表明,多数应用仅仅也只需要 key/value pair 类型的查询,而这里面的 query 类型主要就是根据 key 判断存不存在对应的数据,bloom filter 的一个重要的应用场景就是减少对数据库不必要的查询开销,它能大量减少 negative query(指 query 的 key 不在数据库中)导致的开销。

bloom filter 的目标既然是上面所说的,其想法其实和 hash table 非常类似,这里如果我们有 N 大小的 hash table 就能解决问题了,但是往往我们内存不够,为此,我们换用一个大小为 M > N 的 bit table(这样应该也有 M / (8s) < N 其中 s 是一个 record 的大小),同时,为了避免一个 hash function 导致的 collision 概率较大,我们使用 k 个能将 key 独立的均匀映射到 [0, M) 的 hash function,为此这个 hash table 会有如下的操作限制:

  • 加入一个 key,我们将 k 个 hash function 作用在 key 上,将对应表位设为 1(默认值为 0)
  • 不能删除 key
  • 查询某个 key,如果 k 个 hash function 计算出来对应位置上均为 1,则认为 key 存在;否则认为 key 不存在

容易证明,bloom filter 认为不存在的 key(negative query)一定是 negative query,而认为是 positive 的可能是 false positive。那么设计一个合理的 bloom filter 的问题就是如何能让 false positive rate 足够低,memory 满足要求情况下,hash function 尽可能少。那么这其实是一个数学问题。

一个近似估算的策略是这样想的:任意取表中一个 bit,其不被设为 1 的概率是多少呢?我们知道取定一个 hash function,加入一个 key,这位被设为 0 的概率是 1 - \frac{1}{M},而我们现在有 k 个 hash function,因此加入此 key 后这个 bit 为 0 的概率是 (1 - \frac{1}{M})^k,当我们加入了 N 个 key 后,这个 bit 仍然是 o 的概率就会大大的降低,为 (1 - \frac{1}{M})^{kN},相反为 1 的概率就是 1 - (1 - \frac{1}{M})^{kN}。这时我们看看出现 false positive 的概率是多少:也就是说 k 次均取 1 的概率,为 (1 - (1 - \frac{1}{M})^{kN})^k。如果我们把这个当成 k 的函数(已知 set 大小和 memory 的上限,最优的 hash function 个数是?),我们可以如下估计:

  • 我们知道 (1 + \frac{1}{n})^n 单调递增,而 (1 - \frac{1}{n})^{-n} 单调递减,极限都是 e,自然对数的底。
  • 那么 (1 - \frac{1}{M})^{kN} > e^{-\frac{kN}{M}}
  • 这样一来 (1 - (1 - \frac{1}{M})^{kN})^k < (1 - e^{-kN/M})^k,这样我们获得了这个 false positive rate 的上界,将其当作 k 的函数优化
  • 我们可以取对数,变成 J(k) = k \log (1 - e^{-kN/M}),于是 \frac{\mathrm{d} J}{\mathrm{d} k} = \log (1 - e^{-kN / M}) + \frac{kNe^{-kN/M}}{M(1 - e^{-kN/M})},啊 shit 这个方程大概是不容易搞解析解的?但是似乎令 k = \frac{M}{N}\log 2,导数为 \frac{\mathrm{d} J}{\mathrm{d} k} |_{k = \frac{M}{N}\log 2} = -\log 2 + \log 2 = 0
  • 于是我们得到 k = \frac{M}{N} \log 2 \approx 0.7 M / N
  • 这时的false positive rate 的 upper bound 约为 2^{-k} \approx 0.6185^{M/N}
  • 实际操作中更常见的问题是给定一个 false positive rate,记为 p,以及 N,我们需要多大的 bloom filter?我们可以将 k = \frac{M}{N}\log 2 代入 false positive rate,这样就得到了关于 M 的方程 \log p = -\frac{M}{N}/\log^2 2

变种

除了使用 bit table 计算 0-1 以外,还可以使用 count table,即每个位置初始记为 0,每添加一个 key,对应位置均加一。这样一来就允许删除某个已有的 key,将对应位置减一即可。但是原先使用 bloom filter 有 N < M < 8sN 的限制,这时每个位置变成 count 就会对内存有较大的影响,通常这个 count 只能消耗 2-3 个 bit。当然对较小的数据来说,似乎直接用 hash table 就行了,何必用什么 bloom filter + DB 呢?不过也许 s 很大也难说吧?

扩展阅读:

样例

boost 的候选库里面提供了一个 bloom filter 的实现,我们主要基于它来谈谈使用。如果需要源代码可以

svn co http://svn.boost.org/svn/boost/sandbox/bloom_filter/trunk bloom_filter

它需要使用 boost.hash 提供的 hash function,实现的 bloom filter 包括简单的(basic_bloom_filter)和复杂一些的例如 counting_bloom_filter。基本的操作包括 insert、probably_contains 和 remove(仅对 counting bloom filter 有),另外还支持一些并和交之类的操作(如果将 bloom filter 当作是 bit set,那么这就对应于或和与运算)。

#include <boost/bloom_filter/basic_bloom_filter.hpp>
#include <iostream>

using namespace boost::bloom_filters;
using namespace std;

static const size_t INSERT_MAX = 5000;
static const size_t CONTAINS_MAX = 10000;
static const size_t NUM_BITS = 8192;

int
main (int, char**) {
  basic_bloom_filter<int, NUM_BITS> bloom;
  size_t collisions = 0;

  for (size_t i = 0; i < INSERT_MAX; ++i)
    bloom.insert (i) ;

  for (size_t i = INSERT_MAX; i < CONTAINS_MAX; ++i)
    if (bloom.probably_contains(i)) ++collisions ;

  cout << "collisions: " << collisions << endl;

  return 0 ;
}

——————
And the servant put his hand under the thigh of Abraham his master, and sware to him concerning that matter.

Advertisements
bloom filter

一个有关“bloom filter”的想法

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s