论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2010-12-23 10:33 |只看该作者 |倒序浏览

如何实现一个 Bloom Filter

Bloom Filter 是使用较小的内存和 CPU 来快速检验一个元素是否存在于某个巨大的集合中的数据结构。

场景
假设你有一大堆服务器，每个服务器都有个哈希表存着很多 key 和 value。
你知道一个 key，想把这个 key 对应的 value 取出来。
如果每次都对每个服务器都进行查询，消耗就有点大。
最好就是把 key 都缓存起来放到一个索引服务器上，在索引服务器就知道该查询哪台机器了。但这里就出现了另外一个问题：索引服务器的内存放不下所有 key。怎么办？Bloom Filter 应运而生。

原理

如何用比较小的内存来表示“元素在集合中”？
容易想到把所有元素的 hash code 用某种运算合并在一起，譬如说 bit or 运算。
假设已知在集合中的元素的 hash code 为 x1, x2, x3, x4, ...，那么：
Pseudo代码

let sx = x1 | x2 | x3 | x4 | ...
如果 x & sx == x，则 x 很可能在集合中，否则一定不在集合中

复制代码

但是几个 hash code bit or 在一起，很快就会变成全 1 了。如何去改进？最好合并 hash code 的运算的结果位数多一些，多到不会很快地变成全 1，hash code 非 0 位要少一些，少到每添加一个对合并运算的结果没多大影响：譬如只添加 1 位。

所以将上面的方法改一改：
伪代码

let sx = (1<<x1) | (1<<x2) | (1<<x3) | (1<<x4) | ...
如果 (1<<x) & sx == (1<<x)，则 x 很可能在集合中，否则一定不在集合中

复制代码

一个哈希函数可能不太够准确，再加几个就更好了。
假设已知元素对于哈希函数 y 和 z 还有 hash code y1, y2, y3, ... 和 z1, z2, z3, ...，那么
伪代码

let sx = ((1<<x1) | (1<<y1) | (1<<z1)) | ((1<<x2) | (1<<y2) | (1<<z2)) | ...
如果 ((1<<x) | (1<<y) | (1<<z)) & sx == ((1<<x) | (1<<y) | (1<<z))，那么 x 很可能在集合中，非则一定不再集合中

复制代码

这就是 Bloom Filter。上面的 sx 称为 Bloom Set，长短可定制(m 位)，哈希函数的个数也可定制(k 个)。Bloom Filter 的检验结果中可能包含所谓的 "false positive" 项（想想hiv阳性却没有得aids的……）。"false positive rate" (错误阳性检测率？) 就是表现 Bloom Filter 效能的参数，当选择合适的 k 和足够大的 m 时（比集合总元素个数多10倍之类的），就能把误判率无限的降低，甚至低到比 "宇宙射线 bug" 的几率还低。不过一般没必要太使劲 …… 就像开头举的例子，偶尔误判个一两个，几乎没增加查询量，由于有进一步的校验（误判的结果就是到子服务器查询找不到），结果依然完全正确。

用 Ruby 实现一个 Bloom Filter
新的问题又来了： k 个哈希函数怎么找？有很多方法地！
下面用偷懒的方法：由于需要的哈希函数的值域很小(0...m)，用一个结果值域很大的（例如SHA512）的就能拆出很多小哈希函数来，而且拆出来的哈希函数数量已经足够支持百亿的数据量了…… （如果不够再加上 SHA384, SHA1, MD5）

Bloom Set 可以用 boolean 数组实现，也可以用大整数（Bignum），还可以用字符串。下面为了效率考虑，用整数数组。每元素只有 16 位是有用的，保证它在 Fixnum 范围而不会变成 Bignum，对空间稍微有点浪费 (x2) 但能忍受 ……

另外为了方便切割哈希函数，将 m 放大到比它大的最小的 2 的 x 次幂。把 SHA512 的结果，每 x 位取出来转成一个哈希值，我们的哈希函数族就搞定了 ……
Ruby代码

require "digest/sha2"
# traditional BF
class BloomFilter
attr_reader :m, :k, :filter
# m: least filter size in bit
# k: num of hash functions
def initialize m, k
# unify m to 2 ** x
x = Math.log(m, 2).ceil
m = 2 ** x
raise "m or k too large" if x * k > 512
@m, @k = m, k
@unpack_template = "b#{x}" * @k
# each represents 16 bits
@filter = Array.new (m >> 4), 0
end
# add x to set
def add x
hashes x do |(i, j)|
@filter[i] |= (1 << j)
end
end
# if x in set
def test x
hashes x do |(i, j)|
return false if @filter[i][j] == 0
end
true
end
private
def hashes x, &p
h = Digest::SHA512.digest(x).unpack @unpack_template
h.each do |s|
p[s.to_i(2).divmod 16]
end
end
end
if __FILE__ == $PROGRAM_NAME
bf = BloomFilter.new 10_000_000, 7
bf.add 'word'
bf.add 'pres'
p bf.test 'word' # true
p bf.test 'xof*' # false
p bf.test 'pres' # true
end

复制代码

下面简称 Bloom Filter 为 BF ……

变种：计数 BF - CBF
上面的 BF 只能往集合中加元素，不能删元素：将一个 bit 置为 0 会影响到其它元素。容易想到扩展成可以做删除操作的简单方法：

方法 1:
维护两个 filter：add_filter 和 del_filter。
添加时往 add_filter 里添加，删除时往 del_filter 中添加。
查找时先检查 add_filter，如果找到，就检查 del_filter，如果 del_filter 中没有，就返回 true。

此方法的缺点是：不能重新加上被删除的元素 ……

方法 2:
原版每个 bit 只有 1 和 0，扩展这个 bit 变成整数，每次添加增加 1，每次删除减少 1。缺点是空间消耗变大了很多。如果 key 比较小，还不如直接保存 key 本身。

下面代码（Counting Bloom Filter）目的在于阐述这个 idea，为了实现简单，空间占用是上面的 16 倍（实际应用中一般有 3-4 bit 就够了）。另外用 OpenSSL 的 BN (bignum) 类：将 2 进制数据直接转换为大整数：BN.new(data, 2)，BN 的除法相当于 Ruby 整数的 divmod 方法，返回的是 [quotient, remainder]。
Ruby代码

require "digest/sha2"
require "openssl"
class CBF
attr_reader :m, :k, :filter
# m: least filter size in bit
# k: num of hash functions
def initialize m, k
raise "m or k too large" if (m ** k) >= (1<<512)
@m, @k = m, k
@filter = Array.new m, 0
end
# add x to set
def add x
hashes x do |i|
@filter[i] += 1
end
end
# remove x from set
# NOTE if x was not added before, will cause false negative error
def del x
if (test x)
hashes x do |i|
@filter[i] -= 1
end
end
end
# if x in set
def test x
hashes x do |i|
return false if @filter[i] == 0
end
true
end
private
def hashes x, &p
n = OpenSSL::BN.new Digest::SHA512.digest(x), 2
@k.times do
n, d = n / @m
p[d]
end
end
end
if __FILE__ == $PROGRAM_NAME
bf = CBF.new 10_000_000, 7
bf.add 'word'
bf.add 'pres'
p bf.test 'word' # true
bf.del 'word'
p bf.test 'word' # false
end

复制代码

可删除BF - DlBF
Deletable BF (DlBF) 作为一种折中方案，当删除次数不太多时，可以解决 90% 以上删除元素导致的撞车。

简单原理是：
分配 r 位作为冲突区域标记，剩下的 m 位分成 r 个区域，每区域 m / r 位，r 个冲突标记位和 r 个区域一一对应。
当一个区域的一个位添加超过 1 次时，相应这个区域的冲突标记就设为 1。
标记为 1 的区域不能进行删除操作，标记为 0 的区域可以删除。