如何实现一个 Bloom Filter_Ruby_编程开发_程序员俱乐部

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

• 查看图片附件