Bloom Filter 実装の高速化

ruby

前回まで
http://d.hatena.ne.jp/valdzone/20070625#1182768956
http://d.hatena.ne.jp/valdzone/20070624#1182681301

どうにもこうにもBloomFilter が遅いので、Cによる拡張ライブラリを作ってみた。ソースコードはこちらより（完全無保証です）。
思っていた以上に楽にライブラリを作る事ができた。拡張ライブラリのプログラミング自体がCで書いているにも関わらず Ruby の世界になっているというのがとても面白い。そして実際に走らせてみると当社比で約400倍速度が向上した（この数値はもちろんパラメタ、環境、状態に依存）。

% ruby extconf.rb
creating Makefile
% make
% make install

この拡張ライブラリ(sbloomfilter)は以下のようにして使うことができる。(下記は examples に入っている）

  • sbf.rb　
#!/usr/bin/env ruby
require 'sbloomfilter'

def main
  bf = BloomFilter.new(100000000, 4, 1)
  num = 0
  while line = ARGF.gets
    data = line.chop
    if bf.new_entry?(data)
      num += 1
      bf.insert(data)
    end
  end 
  print "#distinct elements = #{num}\n"
end

main

BloomFilter クラスの第一引数は最大エントリーの数（いわゆるm）、第二引数はハッシュ関数の数（いわゆるk）、第三引数はハッシュ関数（ここではCRC32）にあたえる種（初期値）になっている。
これの当て馬は下記の Ruby + BitSet による実装である。

  • bf.rb
#!/usr/bin/env ruby
require './bloomfilter.rb'

def main
  bf = BloomFilter.new(1000000, 4, 0)
  num = 0
  while line = ARGF.gets
    data = line.chop
    if bf.new?(data)
      num += 1
      bf.insert(data)
    end
  end 
  print "#distinct elements = #{num}\n"
end

main
  • bloomfilter.rb
require 'bitset'
require 'zlib'

class BloomFilter

  def initialize(max_entries, num_hashes, seed)
    @num_hashes = num_hashes
    @size = max_entries.to_i       
    @bitmap = BitSet.new(@size)
    @mask = BitSet.new(@size)
    @seed = seed
  end

  def insert(key)
    mask = make_mask(key)
    @bitmap |= mask
  end

  def new?(key)
    mask = make_mask(key)
    return ((@bitmap & mask) != mask);
  end

  def make_mask(key)
    @mask.clear
    0.upto(@num_hashes.to_i - 1) do |i| 
      hash = Zlib.crc32(key, i + @seed)
      @mask.set(hash % @size, 1)
    end
    return @mask
  end
end
  • 性能評価結果

同じメモリ量、入力データ、ハッシュ関数という条件で拡張ライブラリ版と元の Ruby + BitSet 版を比較してみた。

% time ruby sbf.rb /usr/share/dict/words
#element = 234331
ruby sbf.rb /usr/share/dict/words  0.77s user 0.04s system 79% cpu 1.020 total
% time ruby bf.rb /usr/share/dict/words 
#element = 222827
ruby bf.rb /usr/share/dict/words  306.34s user 85.99s system 95% cpu 6:51.00 total

当社比 = 411 / 1.02 ≒ 400 となった（環境によっては1000倍くらいになるケースもある）。ちなみに正解は

%cat /usr/share/dict/words|sort | uniq |wc -l
  234936

であった。

高速化がうまくいった（というか元の実装が遅すぎた）ポイントは、元のコード(RAAの実装も同じ）でフィルタにクエリを投げるところで、すべてのハッシュをかけたマスクをつくってからフィルタと論理積をとっていたところの無駄をなくしたこと。どうせハッシュを1回ずつかけるのならすべてのハッシュをかけてから比較するのではなく、一度でもヒットしなければループをぬければ良い。あとRAAの実装ではハッシュでヒットしたビットの比較をするのにすべてのビットをひとつづつ比較するというとんでもない無駄をしていたので、m が大きいほど遅くなるという問題があった(BitSet が generic な実装なので仕方がないのだけど)。これもクエリに対応するビットのみ比較することで大幅に速度を向上できた。Bloom Filter は色々と拡張や一般化がされているので、それらもいずれ近いうちに実装してみる予定。

あと元のRAAの実装では、想定する最大エントリー数nと所望のエラー率(false positive rate）からm と k の組を逆算しているのだけど、n/m が十分に小さいようにメモリを確保するという富豪アプローチでいけば m = 100,000,000, k = 4 などのようにしておけば簡単なので、そのような設定方法にしている（単に面倒だったという理由もある）。この場合、n/m が 1/10 になっても FPR は 0.01 程度になる（簡単な確率計算で算出できる。例えばこの表を参照）。m=100,000,000とすると純粋に Bloom Filter に使うメモリ量は 12MB となるが、今時の計算機ならこのくらい余裕のはず。もっと条件が厳しいデータストリーミングに対してハードウェア実装をやるとかいう場合にはもう少し真面目に考える必要がある。あと乱数種が変えられるようにしているのはバグがないかを確かめる目的でエラーが実際に統計的にそうなるかを調べるために用意したのだけど、まだ確認はしていない。

あとは Ruby の VM 実装の問題も大きいのだろうけど、このあたりはまだよくわからない。今後色々と試してみようと思う。いずれにしても当面はCでかけるところはそのようにしておくのが良さそうだ。であれば全部Cで書けばいいかというとそうでもない。DBMS等も含めて他のライブラリを柔軟かつ簡単に使える点やRuby のノーテーションが使えるというメリットが大きい。

追記：
そういえば単純に Ruby のハッシュクラスを使う方法との比較を忘れていたので、sort, uniq コマンドとの比較も合わせて下記に記しておこう。

% time ruby hash-distinct.rb /usr/share/dict/words    [~]
#element = 234936
ruby hash-distinct.rb /usr/share/dict/words  1.07s user 0.09s system 95% cpu 1.208 total

% time cat /usr/share/dict/words |sort |uniq |wc -l   [~]
  234936
cat /usr/share/dict/words  0.00s user 0.01s system 4% cpu 0.177 total
sort  0.24s user 0.07s system 71% cpu 0.439 total
uniq  0.06s user 0.01s system 14% cpu 0.435 total
wc -l  0.03s user 0.01s system 9% cpu 0.434 total

どちらと比較しても早い模様 :-)