IT 技書の森

ブルームフィルタ

要素が集合に含まれるかを高速に判定する確率的データ構造で、偽陽性はあるが偽陰性はない

データ構造アルゴリズム

ブルームフィルタとは

ブルームフィルタ (Bloom Filter) は、要素が集合に含まれるかを高速に判定する確率的データ構造である。「含まれない」は 100% 正確だが、「含まれる」は偽陽性 (false positive) の可能性がある。1970 年に Burton Bloom が発明。

仕組み

ビット配列: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

"apple" を追加:
  hash1("apple") = 2, hash2("apple") = 5, hash3("apple") = 8
  [0, 0, 1, 0, 0, 1, 0, 0, 1, 0]

"banana" を追加:
  hash1("banana") = 1, hash2("banana") = 5, hash3("banana") = 7
  [0, 1, 1, 0, 0, 1, 0, 1, 1, 0]

"cherry" を検索:
  hash1("cherry") = 2, hash2("cherry") = 4, hash3("cherry") = 8
  位置 4 が 0 → 確実に含まれない ✅

"grape" を検索:
  hash1("grape") = 1, hash2("grape") = 5, hash3("grape") = 8
  全て 1 → 含まれるかもしれない (偽陽性の可能性)

特徴

ブルームフィルタは「含まれる」と判定しても実際には含まれない偽陽性が発生するが、「含まれない」と判定した場合は確実に含まれない (偽陰性は発生しない)。要素そのものを保存せずビット配列のみで管理するため空間効率が極めて高く、判定の時間計算量は O(k) (k はハッシュ関数の数) だ。ただし要素の削除はできない (Counting Bloom Filter で対応可能)。

ユースケース

ユースケース 説明
キャッシュの事前チェック DB に問い合わせる前にブルームフィルタで存在チェック
スパムフィルタ 既知のスパム URL のチェック
LSM-Tree (DynamoDB) SSTable に目的のキーが含まれるか事前判定
重複排除 大量データの重複チェック

DynamoDB (LSM-Tree) での活用

読み取りリクエスト: key = "user:123"

1. MemTable を検索 → なし
2. SSTable-1 のブルームフィルタ → 「含まれない」→ スキップ
3. SSTable-2 のブルームフィルタ → 「含まれるかも」→ 読み取り
→ 不要なディスク I/O を削減

パラメータの設計

パラメータ 影響
ビット配列のサイズ (m) 大きいほど偽陽性率が低下
ハッシュ関数の数 (k) 最適値は m/n × ln(2)
要素数 (n) 多いほど偽陽性率が上昇

偽陽性率 1% で 100 万要素を格納する場合、約 1.2 MB のメモリで実現できる。

Cuckoo Filter (改良版)

観点 Bloom Filter Cuckoo Filter
削除 不可 可能
空間効率 良い より良い
検索速度 高速 高速

現場での応用を知るには関連書籍も役立つ。

関連用語