Bloom Filter 是使用较小的
内存和 CPU 来快速检验一个元素是否存在于某个巨大的集合中的数据结构。
场景
假设你有一大堆服务器,每个服务器都有个哈希表存着很多 key 和 value。
你知道一个 key,想把这个 key 对应的 value 取出来。
如果每次都对每个服务器都进行查询,消耗就有点大。
最好就是把 key 都
缓存起来放到一个索引服务器上,在索引服务器就知道该查询哪台机器了。但这里就出现了另外一个问题:索引服务器的内存放不下所有 key。怎么办?Bloom Filter 应运而生。
原理
如何用比较小的内存来表示“元素在集合中”?
容易想到把所有元素的
hash code 用某种运算合并在一起,譬如说 bit or 运算。
假设已知在集合中的元素的 hash code 为 x1, x2, x3, x4, ...,那么:
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 位取出来转成一个哈希值,我们的哈希函数族就搞定了 ……
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 会影响到其它元素。容易想到扩展成可以做
caozuo.html" target="_blank">删除操作的简单方法:
方法 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]。
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 的区域可以删除。
缺点是:随着添加删除次数的增加,设为 1 的标记越来越多,可以删除的位越来越少,最后就不能行了 …… 但是 m 和 r 都比较大的时候,这种效应的产生会慢到可以忽略的程度。
代码如下(还没有完整测试,不保证一定正确……)
require "digest/sha2"
require "openssl"
class DlBF
# abstract some bit operations
class Bitset
def initialize sz
@data = Array.new ((sz >> 4) + 1), 0
end
def add x
q, r = x.divmod 16
@data[q] |= (1<<r)
end
def del x
q, r = x.divmod 16
@data[q] -= (@data[q] & (1<<r))
end
def test x
q, r = x.divmod 16
@data[q][r] == 1
end
end
attr_reader :m, :k, :r, :filter
# m: least filter size in bit
# k: num of hash functions
# r: divide m into r regions
def initialize m, k, r
raise "m or k too large" if (m ** k) >= (1<<512)
@m, @k, @r = m, k, r
@locker = Bitset.new r
@filter = Bitset.new m
end
# add x to set
def add x
# uniq
is = {}
hashes x do |i|
is[i] = 1
end
is.each do |i, _|
if (@filter.test i)
# mark region as not deletable
@locker.add i % @r
else
@filter.add i
end
end
end
# remove x from set
def del x
hashes x do |i|
unless (@locker.test i % @r)
@filter.del i
end
end
end
# if x in set
def test x
hashes x do |i|
return false unless @filter.test i
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.to_i]
end
end
end
if __FILE__ == $PROGRAM_NAME
bf = DlBF.new 1000, 7, 4
%w[mode blue brown blow fox word para graph].each do |s|
bf.add s
end
p bf.test 'word'
bf.del 'word'
p bf.test 'word'
end
EDIT - 实现扩展性也可以很简单??
既然一个 BF 在 key 太多的时候错误率会升高,那么就定好这个 BF 的大小,当 key 数目到达一定程度时,把新的 key 放到新的 BF 中去。例如 mneme 就是这样做的:
http://www.igvita.com/2011/03/24/mneme-scalable-duplicate-filtering-service
- 大小: 18.5 KB