ブルームフィルタ（Bloom filter）は、要素が集合に含まれるかを小さなビット配列で調べる確率的データ構造です。
答えが「存在しない」なら確実に存在せず、「存在するかもしれない」なら本体を確認します。 高価なディスク読み取りや外部問い合わせを省く前段として使われます。
ビット配列と複数のハッシュ
長さmのビット配列をすべて0で始めます。要素を追加する時はk個のハッシュ関数で位置を求め、対応するビットを1にします。
add("ada")
hash1 -> 2
hash2 -> 7
hash3 -> 11
bit[2], bit[7], bit[11] = 1
検索時も同じ位置を調べます。一つでも0なら、その要素は追加されていません。すべて1なら、追加済みの可能性があります。
偽陽性が起きる理由
別の要素が偶然同じビットを1にすると、追加していない要素でもすべての位置が1になることがあります。これが偽陽性（false positive）です。
「存在しない」 -> 確実に存在しない
「存在するかも」 -> 存在する場合と、偽陽性の場合がある
標準的なブルームフィルタでは、同じハッシュ手順を使い、追加後にビットを勝手に消さない限り、追加済み要素を「存在しない」と答える偽陰性は起きません。ビットを直接0へ戻すと、同じ位置を共有する別要素まで消したことになるため、この性質が壊れます。
容量と偽陽性率
理想化した独立なハッシュを仮定すると、n個の要素、mビット、k個のハッシュで、偽陽性率pは次の式で近似できます。
p ≈ (1 - e^(-kn/m))^k
mを大きくすると偽陽性は減り、予定以上のnを追加すると増えます。mとnが決まった時の最適なハッシュ数の目安は次です。
k ≈ (m / n) ln 2
式は設計の目安で、実測値の保証ではありません。ハッシュの品質、入力の偏り、実装方法も影響します。導入前に次を決めます。
- 最大で何要素を入れるか
- 何%の偽陽性を許せるか
- 偽陽性で発生する本体確認のコストはいくらか
- 容量を超えた時に再構築できるか
容量設計の例
100万件を入れ、偽陽性率を1%以下にしたいとします。理想化した式では、必要なビット数とハッシュ数を次のように見積もれます。
m = -n ln(p) / (ln 2)^2
k = (m / n) ln 2
この条件では、1要素あたりおよそ9.6ビット、ハッシュ数は約7が目安です。ただし、これは「どの実装でも1%を保証する性能値」ではありません。実装が採用する丸め、ハッシュ生成、最大件数に合わせ、ライブラリの計算結果と実データで確認します。
予定件数を大きく超えて追加すると、0のビットが減って偽陽性が急に増えます。最大件数を監視し、上限前に新しいフィルタを作る、期間や区画ごとに分ける、拡張可能な方式を採用する、といった更新手順が必要です。
最小のTypeScript例
次は仕組みを確認するための小さな実装です。文字列ハッシュは教材用で、暗号用途や本番の品質を保証するものではありません。
class BloomFilter {
private readonly bits: Uint8Array;
constructor(
private readonly size: number,
private readonly seeds: number[],
) {
this.bits = new Uint8Array(size);
}
private hash(value: string, seed: number): number {
let result = seed;
for (const char of value) {
result = Math.imul(result ^ char.charCodeAt(0), 16777619);
}
return (result >>> 0) % this.size;
}
add(value: string): void {
for (const seed of this.seeds) {
this.bits[this.hash(value, seed)] = 1;
}
}
mightContain(value: string): boolean {
return this.seeds.every((seed) => this.bits[this.hash(value, seed)] === 1);
}
}
const filter = new BloomFilter(128, [17, 31, 53]);
filter.add("ada");
console.log(filter.mightContain("ada"));
console.log(filter.mightContain("grace"));
この例は読みやすさのため1ビットをUint8Arrayの1要素で表しており、実際には1要素あたり1byteを使います。本来のメモリ効率が必要な実装では、1byte内の各bitを利用するライブラリを使います。
メソッド名をcontainsではなくmightContainにすると、確率的な結果であることを利用側へ伝えられます。
使い方
データベースでは、あるファイルや区画にキーが絶対にないと分かれば、その読み取りを省けます。キャッシュでも「登録なし」を高速に除外できます。ただし、ブルームフィルタだけで認可、課金、重複禁止を確定してはいけません。偽陽性を許せない判断は必ず本体データで確認します。
次の条件では別の構造も検討します。
- 要素の削除が頻繁に必要
- すべての要素を列挙したい
- 値や件数も保存したい
- 偽陽性を一件も許容できない
削除対応のCounting Bloom Filterなどもありますが、カウンタ分のメモリとオーバーフロー管理が増えます。標準形で要件を満たせない理由が明確になってから選びます。
保存・共有するときの注意
フィルタをファイルや別サービスへ渡すなら、ビット配列だけでなく次も同じ形式で保存します。
- ビット数
mとハッシュ数k - 使用したハッシュ方式とseed
- 文字列の正規化・文字コード
- 想定要素数と作成時点
- データ形式のversion
追加時と検索時で大文字小文字、Unicode正規化、seedが違えば、追加済み要素を見つけられず、偽陰性がないという前提を壊します。複数プロセスから同じフィルタを更新する場合は、ビット更新の原子性と配布順序も確認します。
効果を測る
ブルームフィルタの価値は、判定自体の速さだけでは決まりません。通過後に行う本体確認をどれだけ減らせたかを測ります。
- 問い合わせ総数
- 「確実にない」と除外した数
mightContain後に本体で見つからなかった偽陽性数- 本体I/Oの削減量
- フィルタ作成・更新の時間とメモリ
対象データの多くが実在するなら、除外できる問い合わせが少なく、フィルタ管理のコストが上回る場合があります。 本体確認の遅延も合わせて比較します。
ハッシュ関数の作り方
k個の完全に別のハッシュ実装を用意すると、計算と保守の負担が増えます。実用ライブラリでは、二つのハッシュ値から複数の位置を導くdouble hashingなどが使われます。独自実装より、要素数と誤り率を指定できる検証済みライブラリを優先します。
暗号学的ハッシュが必須という意味ではありません。必要なのは、対象入力で位置が十分に分散し、攻撃者が入力を制御できる場合の計算量攻撃も含めて要件を満たすことです。公開APIの前段へ置くなら、意図的に衝突を作られる可能性も評価します。
また、ハッシュ計算前の入力表現を固定します。数値42、文字列"42"、JSONのキー順が違うオブジェクトを同一と扱うかは、フィルタの外で決めます。
更新方法を設計する
標準的なブルームフィルタは追加に向きます。削除や件数の減少があるデータでは、次の方法を選びます。
- 一定期間ごとに本体データから再構築する
- 日付やpartitionごとにフィルタを分け、古い単位を丸ごと捨てる
- カウンタを持つCounting Bloom Filterを使う
- 削除を扱いやすい別の近似membership filterを検討する
再構築中に新旧フィルタをどう切り替えるかも重要です。新しいフィルタの作成開始後に追加された要素が抜けないよう、更新ログを後から反映するか、短い二重書き期間を設けます。
複数フィルタへ分ける
データを日付やSSTableのような変更しない単位へ分けると、各単位のフィルタも不変にできます。問い合わせ時は対象になり得る単位のフィルタを調べ、「確実にない」単位の本体読み取りを省きます。
単位を細かくしすぎると、フィルタ数と問い合わせ回数が増えます。大きすぎると再構築コストが増え、古いデータを捨てにくくなります。データの保存・compact単位と合わせて決めます。
複数のフィルタを直列に確認する場合、各フィルタの偽陽性率が同じでも、全体で余分な本体確認が起きる割合は変わります。単体の誤り率だけでなく、実際のqueryが通過するフィルタ数で測定します。
テストする性質
本体データから既知の存在要素と非存在要素を用意し、次を確認します。
- 追加済み要素で
mightContainが必ずtrueになる - 非存在要素の偽陽性率が設計範囲にある
- 最大予定件数を入れた後も範囲内か
- 保存・読み込み後に結果が変わらないか
- 異なるプロセスでも同じ位置を計算するか
少数の手作業データだけでは偽陽性率を評価できません。実際のキー分布に近い十分なサンプルを使います。
セキュリティ判断には使わない
ブルームフィルタは近似membership queryの最適化です。アクセス許可リスト、使用済みtoken、課金済みIDの最終判定をフィルタだけで行うと、偽陽性が権限や状態の誤判定につながります。
セキュリティ用途で前段の除外に使う場合も、肯定結果は信頼できる本体データで確認します。また、外部から大量の任意入力を送れるAPIでは、ハッシュ計算自体の負荷、情報推測、フィルタを飽和させる入力も考慮します。
よくある誤解
- 「ある」と確定できる：答えは「あるかもしれない」です。
- 偽陰性はどんな実装でもない：ビット削除、状態破損、異なるハッシュ設定で性質を壊せます。
- 要素数が増えても精度は同じ：設計数を超えると1のビットが増え、偽陽性率が上がります。
- ハッシュ数は多いほどよい：計算量が増え、ビットが埋まりすぎるため最適値があります。
まとめ
ブルームフィルタは「存在しない」を小さなメモリで確定し、高価な本体確認を減らします。「存在するかも」は必ず本体で確認します。要素数、許容する偽陽性率、再構築方法を先に決めることが、導入の中心です。
