ブルームフィルタ徹底解説

キャッシュを扱う人ならたいてい避けて通れない問題があります。リクエストされた key がキャッシュにもデータベースにも存在しないのに、クエリが毎回データベースまで突き抜けてしまうという問題です。この種のリクエストを防ぐには、まず「この key がそもそも存在するのか」を高速に判定できなければなりません。ブルームフィルタはまさにそのために生まれました。

背景の紹介

redis キャッシュのシナリオでは、誰かがまったく存在しない key を大量にリクエストしてくると、キャッシュは永遠にヒットせず、負荷がすべてデータベースに集中します。これがよく言われるキャッシュ貫通（キャッシュペネトレーション）です。この種のリクエストを遮断する最も素朴な発想は、正当な key をすべて集合に保存しておき、クエリの前に判定することです。しかし key の数が多くなると、HashSet のような構造で全量の key を保存するのはメモリコスト的に受け入れがたくなります。ブルームフィルタは極めて小さな空間と引き換えに「誤差はあり得るが十分に速い」存在判定を提供するもので、まさにこのニーズにぴったりはまります。

ブルームフィルタ（Bloom Filter）は 1970 年に Bloom によって提案されたもので、実際には非常に長いバイナリベクトルと一連のランダム写像関数で構成されています。ブルームフィルタの利用シーンは一般に redis のキャッシュ貫通の防止であり、ブルームフィルタを使えば空間を大きく節約でき、要素の存在有無をすばやく特定できます。

ブルームフィルタは key をハッシュしてビットマップ（Bitmap、実体は bit 配列）内の対応するインデックスを特定します。この配列の各位置は 0 と 1 の 2 つの状態しか持たず、各位置は 1 ビット（bit）しか占有しません。0 は要素が存在しないこと、1 は要素が存在することを表します。

具体的には、要素を書き込むとき、k 個の異なるハッシュ関数でそれぞれ key を計算して k 個のインデックスを得て、ビットマップ内のこれら k 個の位置をすべて 1 にします。クエリのときも同じ流れをたどります。k 個の位置のうちどれか 1 つでも 0 なら、この key は一度も書き込まれていないことを意味します。k 個の位置がすべて 1 のときに限り、「存在する可能性がある」と判定します。プロセス全体はハッシュ計算とビット演算だけで、時間計算量は O(k) であり、格納済みの要素数には依存しません。これがクエリの速さの理由でもあります。

注意：2 つの異なる key をハッシュした結果、対応するインデックスが一部重複することがあります。これによりメモリ使用量を削減できますが、ハッシュ衝突が発生する確率もあり、本来存在しない key をハッシュした結果、ビットマップ上でたまたますべて 1 になっているケースが起こり得ます。

以上の現象から、ブルームフィルタの観点で 2 つの大きな特徴を導き出せます。

1、ブルームフィルタがある要素は存在すると判定した場合、その要素は存在する可能性がある。

2、ブルームフィルタがある要素は存在しないと判定した場合、その要素は確実に存在しない。

この 2 つの特徴が使い方を決めます。確実に存在しないリクエストを外側で遮断する「前段フィルタ」に適している一方、「存在する」という結論を鵜呑みにしてはいけません。存在すると判定された後も、キャッシュまたはデータベースでの二次確認が必要です。

なぜならブルームフィルタには常に誤判定率が存在するからです。ハッシュ衝突を 100% 回避することは不可能です。ブルームフィルタではこの誤判定率を偽陽性確率、すなわち False Positive Probability、略して fpp と呼びます。

誤判定率の大きさは主に 3 つの要因で決まります。ビットマップの長さ m、ハッシュ関数の個数 k、そしてすでに書き込まれた要素数 n です。書き込まれる要素が多いほどビットマップ内で 1 になったビットが増え、未知の key の k 個の位置が「たまたますべて 1」になる確率も高くなります。そのためブルームフィルタは通常、作成時に想定要素数と期待する fpp の指定を求め、実装側（Guava の BloomFilter など）が適切な m と k を逆算します。

fpp を抑えるには、ビットマップの長さを増やすか、ハッシュ回数を増やして衝突確率を下げることができますが、ビットマップの拡大にはより多くのメモリ空間が必要で、ハッシュ回数の増加にはより多くの CPU リソースが必要です。リソースコストの見積もりをきちんと行い、適切な方式を選ぶ必要があります。これは本質的に、空間・CPU・正確性の三者間のトレードオフであり、タダの昼食はありません。

対応する key を削除するには？

ここまで見てきたように、ブルームフィルタで要素の存在を判定するのは、対応するインデックス位置が 1 かどうかで判断するものです。しかし要素を削除したいとき、1 をそのまま 0 に変えることはできません。その位置には他の要素が存在している可能性があるからです。**したがって元のブルームフィルタは削除操作をサポートできません。**削除をサポートしたい場合はどうすればよいのでしょうか。最も簡単な方法はカウンターを追加することです。つまりビット配列の各位置について、存在しなければ 0、存在するなら要素の個数を具体的な数値として保存し、単に 1 を保存するだけにはしません。ここで問題になるのは、本来なら 1 を保存するのに 1 ビットで足りたところ、たとえば 2 という具体的な数値を保存するには 2 ビット必要になることです。そのためカウンター付きのブルームフィルタはより大きな空間を占有します。

この改良版は一般にカウンティングブルームフィルタ（Counting Bloom Filter）と呼ばれます。書き込み時は k 個の位置のカウンターをそれぞれ 1 増やし、削除時はそれぞれ 1 減らします。カウンターが 0 になったときに初めて、その位置が本当に空になったことを意味します。代価は空間の膨張（各位置が 1 bit から数 bit になる）に加えて、もう 1 つ隠れたリスクがあります。一度も書き込まれていない要素を誤って削除すると、カウンターが誤って減らされ、本来存在する要素を「消してしまう」可能性があり、偽陰性を引き起こします。したがって削除操作は、書き込み済みと確認できた要素に対してのみ実行すべきです。

業務上、削除の必要性が高くないなら、もっと手軽な方法もあります。削除はせず、定期的に最新の全量データで新しいブルームフィルタを再構築し、古いものと置き換えるのです。再構築中は旧フィルタがサービスを継続し、切り替えはアトミックに行えます。多くのキャッシュ貫通対策のシーンで使われているのがまさにこの考え方です。

ハマりどころと注意点

1）容量は十分に見積もること。ブルームフィルタは作成後にビットマップの長さが固定され、書き込まれる要素が想定規模を超えると fpp が著しく悪化します。しかもオンラインで拡張することはできず、再構築するしかありません。

2）「存在する」は本当に存在することを意味しない。誤判定で通過した key は依然としてデータベースに到達します。ブルームフィルタは貫通を大幅に減らせるだけで、100% なくすことはできません。データベース側のセーフティネット（空値のキャッシュなど）は依然として必要です。

3）ハッシュ関数は書き込み側と一致させること。複数のサービスが 1 つのブルームフィルタを共有する場合（redis に置く場合など）、各側のハッシュ実装とパラメータは完全に同一でなければなりません。そうでなければ判定結果は誤ったものになります。

まとめ

ブルームフィルタは 1 つのビットマップと k 個のハッシュ関数によって、極めて小さな空間占有と O(k) のクエリで存在判定を実現します。その代価は、偽陽性が存在すること、そして元の構造では削除をサポートしないことです。「存在しないと言えば確実に存在しない、存在すると言えば可能性があるにすぎない」という 2 つの判定特性が、前段フィルタとしての適性を決めており、典型的なシーンがキャッシュ貫通の防止です。削除が必要ならカウンティングブルームフィルタに切り替えるか、いっそ定期再構築の道を選べばよいでしょう。そして容量の見積もりと fpp の設定については、メモリ・CPU・正確性の間で、自分の業務に合わせてそろばんを弾く必要があります。