ブルームフィルタと確率的データ構造
数バイトの配列だけで巨大な集合の「ない」を確実に言い切る仕組みが分かります。偽陽性率の計算式と、LSM-Tree の読み取りを速くする実応用まで一気に押さえられます。
- 1.ブルームフィルタはビット配列と複数のハッシュ関数だけで集合の所属判定を行う省メモリ構造。要素の追加は対応する k 個のビットを 1 にし、判定は k ビットすべてが 1 かを見る。
- 2.偽陰性は決して起きず（あると言ったら必ずある）、偽陽性のみ起きる（ないものをあると誤判定しうる）。偽陽性率は配列長 m・要素数 n・ハッシュ数 k で決まり、最適な k はおよそ (m/n)×0.693。
- 3.LSM-Tree では各 SSTable にブルームフィルタを付け、存在しないキーの検索でディスク読み取りをほぼ排除する。確実な「ない」が、無駄な I/O を消す決め手になる。
「ない」を確実に、省メモリで言い切る
巨大な集合に対して「この要素は含まれるか」を判定したい場面は無数にあります。素直にやるならハッシュセットを持てばよいのですが、要素そのものを保持するためメモリを食います。1000万件のキーを抱えると、それだけで数百MB級になりかねません。
ブルームフィルタ（Bloom filter） は、要素を一切保存せずに所属判定を行う 確率的データ構造 です。代償として誤判定を許しますが、その誤りは一方向にしか起きません。すなわち、
- 偽陰性（false negative）は起きない: 「含まれない」と答えたら、本当に含まれない。
- 偽陽性（false positive）は起きうる: 「含まれる」と答えても、実際には無いことがある。
この非対称性こそがブルームフィルタの価値です。「ない」が確実なので、本体（ディスクや遠隔ストア）への問い合わせを 安全に省略 できます。フィルタが「あるかも」と言ったときだけ実体を確認すればよい、という使い方になります。
構造と操作：ビット配列 + k 個のハッシュ
部品は2つだけです。長さ m の ビット配列（最初は全ビット 0）と、独立な k 個のハッシュ関数 h1,h2,...,hk です。各ハッシュは要素を 0 から m-1 の位置へ写します。
| 操作 | 手順 | 計算量 |
|---|---|---|
| 追加（insert） | 要素 x について k 個の位置 h1(x)..hk(x) を求め、その m ビット配列の該当ビットを全て 1 にする | O(k) |
| 判定（query） | x の k 個の位置を求め、全て 1 なら「あるかも」、1つでも 0 なら「確実にない」 | O(k) |
なぜ偽陰性が起きないかは、この手順から直ちに分かります。要素を追加したときに立てた k ビットは二度と 0 に戻らない（削除しない限り）ので、本当に入っている要素を判定すれば必ず k ビットすべてが 1 のままです。逆に偽陽性は、別の要素たちが立てたビットがたまたま k 箇所すべて重なってしまうと起きます。
m=12, k=3 のビット配列
index: 0 1 2 3 4 5 6 7 8 9 10 11
0 1 0 1 0 0 1 0 1 1 0 0
"apple" を追加: h1=1, h2=6, h3=9 → index 1,6,9 を 1 に
"apple" を判定: index 1,6,9 が全て 1 → 「あるかも」
"grape" を判定: h1=3, h2=8, h3=9 → index 3,8,9 が全て 1
→ "grape" は入れていないのに「あるかも」（＝偽陽性）
独立な k 個のハッシュ関数を本当に用意する必要はありません。実装では2つの良いハッシュ値 a, b から gi(x) = a + i*b (mod m) のように k 個を合成する double hashing が定番です。Kirsch と Mitzenmacher が、この方式でも偽陽性率がほぼ悪化しないことを示しました。計算コストを抑えつつ十分なばらつきが得られます。
偽陽性率の数理
偽陽性率がどう決まるかを式で追います。要素を n 個追加した後を考えます。1回のハッシュであるビットが立つ確率は 1/m、立たない確率は 1 - 1/m。k 個のハッシュで n 個を入れたので、特定のビットが最後まで 0 のままである確率はおよそ
P(あるビットが 0) = (1 - 1/m)^(k*n) ≈ e^(-k*n/m)
逆に、そのビットが 1 になっている確率は 1 - e^(-k*n/m)。偽陽性は、判定対象の k 箇所が すべて 1 のときに起こるので、偽陽性率 f は近似的に
f ≈ (1 - e^(-k*n/m))^k
ここから読み取れるのは、m/n（要素1個あたりのビット数）を増やすほど f は下がる こと、そして k には最適値があることです。f を k について最小化すると、最適なハッシュ数は
k_opt = (m/n) * ln 2 ≈ 0.693 * (m/n)
このとき各ビットが 0 か 1 になる確率がちょうど半々になり、配列の情報量が最大に使われます。最適 k を入れたときの偽陽性率は f ≈ (0.6185)^(m/n) と簡潔に書け、要素あたりのビット数だけで決まります。
| m/n（1要素あたりビット数） | 最適 k（四捨五入） | 偽陽性率 f（最適 k 時） |
|---|---|---|
| 8 bit | 6 | 約 2.1% |
| 10 bit | 7 | 約 0.82% |
| 12 bit | 8 | 約 0.31% |
| 16 bit | 11 | 約 0.046% |
実務でよく使われる「1要素あたり10ビット・ハッシュ7個」という設定が、偽陽性率1%弱という手頃な点だと分かります。重要なのは、保存している要素数 n が同じでも、要素1個あたり10ビット程度しか使わない ことです。キー本体がどれだけ大きくても、フィルタの大きさは件数だけで決まります。
ハッシュ関数を増やすと「1個でも 0 があれば確実にない」と言える機会が増える一方、追加時に立てるビットも増えて配列が早く埋まります。埋まりすぎると逆に偽陽性が増えるため、k_opt ≈ 0.693*(m/n) という最適点が存在します。m/n を固定したまま k だけ増やしても改善しないのはこのためです。
なぜ素朴な削除ができないのか
ブルームフィルタは 要素の削除が原理的に難しい です。ある要素のビットを 0 に戻すと、そのビットを共有していた別の要素まで「ない」と誤判定してしまい、偽陰性が発生します。偽陰性ゼロという最大の長所が壊れるため、標準のブルームフィルタは削除を許しません。
削除が必要なら派生構造を使います。
| 構造 | 違い | 用途 |
|---|---|---|
| Counting Bloom filter | 各位置を1ビットではなく小さなカウンタにし、追加で+1・削除で-1する | 削除が必要な集合 |
| Cuckoo filter | 要素の指紋（fingerprint）を格納し、削除も範囲も扱いやすい | 削除あり・低偽陽性 |
| Quotient filter | 指紋を商と剰余に分けて配列に詰める、キャッシュ効率が良い | リサイズ・マージ重視 |
これらは「ビット配列＋ハッシュで集合を圧縮する」という発想を共有する確率的データ構造の仲間です。なお要素の 概数を数える HyperLogLog や、頻度を見積もる Count-Min Sketch も、同じく「正確さを少し諦めて省メモリを得る」確率的データ構造の系譜にあります。
LSM-Tree での読み高速化への応用
ブルームフィルタが最も効くのが LSM-Tree のような 追記型ストレージ です。LSM では更新を直接書き換えず、不変な SSTable として次々に書き出すため、あるキーの最新値がどのファイルにあるか分かりません。読み取りは新しい SSTable から古い SSTable へ順にたどる必要があり、存在しないキーの検索では全 SSTable を読みかねない という弱点があります。
そこで各 SSTable に、そのファイルが持つキー集合のブルームフィルタを添えます。読み取り時はまずフィルタに問い合わせ、
- フィルタが「ない」と答えたら、その SSTable は ディスクを読まずに飛ばす（偽陰性が無いので安全）。
- 「あるかも」のときだけ実際にブロックを読みに行く（偽陽性なら空振りするが、それは稀）。
これにより、存在しないキーの検索コストが「全ファイル走査」から「フィルタ参照だけ」へ激減します。RocksDB・LevelDB・Cassandra・HBase などはいずれもこの仕組みを内蔵しています。フィルタは要素あたり10ビット程度と小さいので、SSTable ごとに持ってもメモリにブロックキャッシュと共存させられます。
ブルームフィルタが価値を出すのは 偽陽性のコストより本体アクセスのコストがずっと高い場合です。LSM ではディスク I/O を1回省けるので割が合います。逆に、存在するキーばかりを引くワークロードでは毎回「あるかも」になり、フィルタ参照のぶんだけ無駄になります。点検索（point lookup）でこそ効き、範囲検索には直接は効かない点も押さえておきましょう。
このため、点検索が1経路で安定して速い B+Tree 系インデックスとは対照的に、LSM は フィルタで「読まないファイル」を切り捨てて はじめて読み取りが実用的になります。ハッシュを使ってキーを位置へ写す発想は、ノードへキーを割り当てる コンシステントハッシュ法 とも通じますが、ブルームフィルタの狙いはあくまで「集合の所属を省メモリで近似する」ことにあります。
偽陰性は起きず偽陽性のみ起きること、その理由（立てたビットは戻さない／別要素のビットが偶然重なる）を即答できるように。偽陽性率 f ≈ (1 - e^(-kn/m))^k、最適ハッシュ数 k ≈ 0.693*(m/n)、素朴な削除ができない理由、そして LSM-Tree で存在しないキーの I/O を省く応用がセットで問われます。
まとめ
ブルームフィルタは、ビット配列と k 個のハッシュだけで集合の所属を判定する確率的データ構造です。追加は k ビットを 1 にし、判定は k ビットが全て 1 かを見るだけ。偽陰性ゼロ・偽陽性のみ という非対称性により、「ない」を確実に言い切って本体アクセスを安全に省けます。偽陽性率は要素あたりビット数 m/n でほぼ決まり、最適ハッシュ数は 0.693*(m/n)。削除が要るなら Counting / Cuckoo などの派生を使います。最大の応用が LSM-Tree で、各 SSTable のフィルタが存在しないキーのディスク読み取りを消し、読み取り増幅を抑える決め手になります。
データベース Article
ブルームフィルタと確率的データ構造を実務で読む
TL;DRは入口です。実際に選ぶ・使う段階では、何を解決するか、何と比較するか、導入後にどこで詰まるかまで見る必要があります。
解決すること
ブルームフィルタ
比較で見る軸
難易度: advanced / カテゴリ: データベース / タグ数: 5
導入後に効く点
偽陰性は決して起きず（あると言ったら必ずある）、偽陽性のみ起きる（ないものをあると誤判定しうる）。偽陽性率は配列長 m・要素数 n・ハッシュ数 k で決まり、最適な k はおよそ (m/n)×0.693。
先に潰すリスク
用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。
- 難易度
- advanced
- カテゴリ
- データベース
- タグ数
- 5
判断チェックリスト
- 自社の用途が「ブルームフィルタ / 確率的データ構造」に近いか確認する。
- 強みである「ブルームフィルタはビット配列と複数のハッシュ関数だけで集合の所属判定を行う省メモリ構造。要素の追加は対応する k 個のビットを 1 にし、判定は k ビットすべてが 1 かを見る。」が本当に評価軸になるか確認する。
- 注意点の「用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。」を運用で吸収できるか確認する。
- 公開値や仕様値は、対象プラン・対象機種・対象リージョンまで確認する。
- 既存システム、ID、ネットワーク、監視、バックアップとの接続方法を先に洗い出す。
- 小さく試してから、本番移行、権限設計、障害時手順、コスト監視を決める。