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

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > Ruby > 如何实现一个 Bloom Filter

如何实现一个 Bloom Filter

 2011/10/31 8:30:17  night_stalker  http://night-stalker.iteye.com  我要评论(0)
  • 摘要:BloomFilter是使用较小的内存和CPU来快速检验一个元素是否存在于某个巨大的集合中的数据结构。场景假设你有一大堆服务器,每个服务器都有个哈希表存着很多key和value。你知道一个key,想把这个key对应的value取出来。如果每次都对每个服务器都进行查询,消耗就有点大。最好就是把key都缓存起来放到一个索引服务器上,在索引服务器就知道该查询哪台机器了。但这里就出现了另外一个问题:索引服务器的内存放不下所有key。怎么办?BloomFilter应运而生
  • 标签:实现 一个
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
  • 查看图片附件
发表评论
用户名: 匿名