ブルームフィルタを例で理解する

 (llimllib.github.io)
2 ポイント 投稿者 GN⁺ 2025-07-01 | 1件のコメント | WhatsAppで共有
  • ブルームフィルタは、メモリ効率よく集合内の要素の存在有無を高速に確認できる確率的データ構造である
  • 要素が集合に確実に存在しないか、存在するかもしれないかだけを示し、偽陽性の確率が存在する
  • 基本構造ではビットベクタと複数のハッシュ関数を用い、各要素に対応するビットを 1 に設定する
  • フィルタサイズとハッシュ関数の数によって誤差率と性能が決まり、用途に合わせて調整できる
  • 推奨されるハッシュ関数や最適な設定方法、空間効率、実際の適用事例なども紹介されている

ブルームフィルタとは何か

  • ブルームフィルタは、特定の要素が集合に存在するかどうかを高速かつメモリ効率よく判定するためのデータ構造である
  • この効率性のために、ブルームフィルタは確率的データ構造となっており、検査結果は「集合に確実に存在しない」または「集合に存在するかもしれない」に分かれる
  • ブルームフィルタの中核となる構造はビットベクタである
  • 要素を追加するときは、各要素を複数回ハッシュして、そのインデックスのビットを 1 に設定する
  • 各ハッシュ関数で得られたインデックスに対応するビットがすべて 1 の場合は「存在するかもしれない」と判定し、そうでなければ「確実に存在しない」と扱う

動作原理の例

  • 複数のハッシュ関数（例: Fnv, Murmur）を通して、要素を複数のビットインデックスにマッピングする
  • 要素を追加するときは、計算されたインデックスのビットを 1 に変更する
  • 特定の要素の存在有無を調べる際、同じハッシュ関数で得られる対応インデックスがすべて 1 であれば「存在するかもしれない」とみなす
  • もしひとつでも対応するビットが 0 なら、「集合に存在しない」と確実に判断できる
  • このため、**偽陽性（フォールス・ポジティブ）**の可能性が生じる

高度なトピック

注意: 著者は実際に大規模サービスへブルームフィルタを適用した経験はない

ハッシュ関数の選択

  • 独立性があり、一様分布を持つハッシュ関数が推奨される
  • 暗号学的ハッシュ関数（sha1 など）は遅いため適していない
  • 高速で単純なハッシュ関数の例としては、Murmur、xxHash、Fnv、HashMix などがある
  • 実例では、md5 から murmur に変更した際に 800% 以上の速度向上を経験した

ブルームフィルタのサイズ決定

  • フィルタサイズ(m) が大きいほど偽陽性率は低下する
  • 偽陽性率は通常 (1-e^(-kn/m))^k で近似できる
  • 期待要素数(n)、フィルタサイズ(m)、ハッシュ関数の数(k)を適切に決める必要がある

ハッシュ関数の数は？

  • ハッシュ関数の数が多いほど速度は遅くなり、フィルタもより早く埋まる
  • 少なすぎると偽陽性率が高くなる
  • 理想的な k は (m/n)ln(2) で計算される
  • 設計時は次の手順で進める:
    • 期待要素数 n を見積もる
    • ビット数 m を決める
    • 最適な k を算出する
    • 望む誤差率が出るか確認し、だめなら m を調整する

性能と空間効率

  • ブルームフィルタでの要素追加/存在確認は O(k) の時間計算量を持つ
  • 空間効率は、許容できる誤差率と要素範囲に応じて決まる
  • 要素範囲をおおまかにでも予測できない場合は、ハッシュテーブルや拡張型ブルームフィルタのほうが適していることがある

活用事例

  • 詳しい活用例は Wikipedia を参照
  • C. Titus Brown は、ブルームフィルタのバイオインフォマティクスへの適用事例を示している

参考資料

関連記事

1件のコメント

 
GN⁺ 2025-07-01
Hacker News のコメント
  • こういう記事は自分みたいな人にぴったりだと感じる。名前は聞いたことがあったけれど、そのたびに調べようと思って先延ばしにしていた。今回この記事を見てようやく調べてみたら、まさに自分が求めていた入門記事という感じだった
    • iBooks の検索機能を実装するために Bloom filter を初めて知ったことを思い出した。もう 10 年以上前の話
    • Bloom filter は本当に面白い。問題を解いていて Bloom filter が必要になる場面が来ると本当にわくわくするけれど、ドメインによってはそういう状況が少なくて残念
  • 著者への提案が一つある。インタラクティブな部分はとても良かった。Bloom filter の特性をもっとよく理解させるために、2 つの文字列がハッシュ衝突を起こす例を出して、片方を入力してみてから、もう片方を 2 つ目の入力欄に入れてみるようにするとよいと思う。そうすれば「集合に入っていると断言はできないが、たぶん入っているかもしれない(maybe)」という独特の結果ロジックがなぜ生まれるのかを簡単に理解できる
    • 例として、"bloom" と "demonstrators "（末尾の空白を含む）が fnv: 7、murmur: 12 で衝突する
  • 2009 年の大学時代に CUDA で Bloom filter を実装したことがある。指導教授は元 Nvidia 出身だった。けれどキャリアでは GPU プログラミングとはまったく関係のない道に進んだ。別の選択をしていれば 1 億ドル稼げていたかもしれない、と思うことがある
    • 1970 年に出たコンピュータ科学のアイデアだから、それは無理だっただろうと思う。GPGPU 関連のアイデアはすでに十分研究されていた感じがする。自分も 10 年前に GPU で Hashcash を実装したけれど、今となっては価値はほぼゼロに近い
    • 大学の卒業プロジェクトで機械学習アルゴリズムを CUDA に移植したあと、大したことではないと思って組み込みプログラミングへ進路を変えた
    • 自分も似たような経験がある。2009 年に GeForce 8 と CUDA v1(!) で GPU 最適化されたバイオインフォマティクス・ツールキットを、おそらく初めて作った。ただの好奇心で作ったあと完全に別の道へ進み、大金を稼ぐチャンスを逃した
    • ビットコインを買っていればもっと大金を稼げていたはずだ、という冗談まじりの話
  • 自分の好きなトリックがある。要素数が少ないかもしれず、membership check を頻繁に行う小さな set に対して、64 ビットの Bloom filter をとても単純なハッシュ関数と一緒に入れておく方法だ。ばかげて見えるけれど、コストがあまりに低いので一種の賭けのように試せる。うまくいかなくても membership check や insert に 10ns くらい追加されるだけだが、はまると非常に大きな作業量を減らせる
    • Chromium でもあちこちでこうしたトリックが使われている。記事では Safe Browsing にしか触れていないが、Blink レイヤーでは rapidhash とこうしたマイクロフィルタを積極的に使っている。たとえば querySelector()、CSS バケットでのハッシュルックアップの事前フィルタ、アクセシビリティのための Aria 属性探索での rapid reject などだ。32 ビット、64 ビットの小さな filter でも実際によく機能する。より大きな Bloom filter も適切に活用していて、自分もこうした機能を直接追加した
  • 最近、ログメッセージのアンチスパム機能に Bloom filter を使ったことがある。ログメッセージをハッシュして filter に入れ、すでに filter にあれば出力しない。定期的に filter のビットを全部クリアする。ビット全体をアトミックにクリアする必要はなく、メッセージが入ってくる途中で一部のビットが消えてもログが再び出るだけだ。以前はメッセージごとのカウントを別に保持していたが、この方式のほうがずっと効率的だった。実際にこの用途へ Bloom filter を適用して満足度が高かった
  • Bloom filter の可視化の例として、このページ の最後の部分に良い資料がある
  • Eli Bendersky が書いた別の Bloom filter 入門記事もおすすめ。もっと詳しく知りたければ こちら を参照
  • Bloom filter、set、ハッシュテーブルを理解するのに必要な概念のほぼ 95% は重なっていると思う。set は key だけを気にするハッシュテーブルで、Bloom filter はハッシュの衝突特性を積極的に利用する set だ。意図的に衝突しやすくしたハッシュ関数を使う。ある特定の key が入ったことがあるなら必ず一致する。しかし同じハッシュ値を作る別の key が存在する可能性がある。だからこれはバグではなく、意図された特性だ
    • 自分も Bloom filter を、ハッシュテーブルからデータそのものを抜いてバケットだけを追跡する方式のように考えることが多い。こういうマインドセットの人が自分だけではないと分かってうれしい
    • Bloom filter が衝突を減らすために複数のハッシュ関数を使う、という点がもう少し補足されるとよいと思う。たとえば 3 つのハッシュ関数がすべて一致して初めて set にあると判断する。この構造のおかげで false positive の確率は下げられる一方、false negative は決して起きない
    • Bloom filter を理解できたなら、ランダム射影や Locality Sensitive Hashes の一部実装もすぐ理解できるようになる
  • Cassandra の read spike をデバッグしていたとき、Bloom filter にどっぷりはまったことがある。存在しない key なのに sstable 参照が多すぎて不思議だった。sstable ごとに付いている Bloom filter の意味をあとから理解した。デフォルトの false positive 率が 0.1 で、自分たちの状況には高すぎた。ほとんどが cache miss で、false positive のせいで無意味な参照が多すぎた。率を 0.01 に下げたところ、メモリ使用量は少し増えたが無駄な read が大きく減り、p99 read latency が 16〜18% も改善した
  • Bloom filter が本当に好きだ。技術の話をするときに必ず伝える三つの重要概念は、Bloom filter、Random Weight Hashing（Rendezvous Hashing、Highest Random Weight Hashing）、そして Cumulative flow diagram だ。この三つの概念は複雑な分散システムの運用に不可欠だと思う
    • 分散ハッシュテーブルの構造も同じくらい重要なテーマだと思う。たとえば circle、chord、CAN、kademlia などさまざまなアーキテクチャ