LASSIC Media らしくメディア
ブルームフィルタとは｜高速な存在判定の仕組み
大量のデータを扱うシステムでは、「この値はすでに登録済みか」「このIDは処理済みか」といった存在確認を、何度も繰り返すことになります。素直に毎回データベースやストレージへ問い合わせると、件数が増えるほど負荷が積み上がり、応答が遅くなりがちです。この問い合わせを手前でふるいにかけ、多くのケースを軽くさばく工夫のひとつが、ブルームフィルタです。
この記事では、発注担当者やプロジェクトマネージャーに向けて、ブルームフィルタとは何か、どんな性質を理解して使うのかを、実装コードには立ち入らずに整理します。仕組みの直感、誤検知という独特のふるまい、向いている場面、そして設計・発注のレビューで確認したい点まで、順にかみくだいていきましょう。
目次
この記事のポイント
- ブルームフィルタとは、ある要素が集合に含まれるかを、少ないメモリで手早く判定できる確率的なデータ構造です。
- 「含まれていない」という判定は見逃しがなく信頼できる一方、「含まれている」という判定にはまれに誤検知（偽陽性）が混じる、という非対称な性質を持ちます。
- 誤検知率はビット配列の大きさとハッシュ関数の数で調整でき、基本の方式では要素を削除できないため、想定件数と許容誤検知率を見積もって使うのが勘所です。
ブルームフィルタとは
ブルームフィルタとは、ある要素が集合に含まれているかどうかを、少ないメモリで手早く判定できる確率的なデータ構造です。1970年にBurton H. Bloomが考案したもので、要素そのものを保存せずに「含まれていそうか」を見分けられる点に特徴があります。
いちばん理解しておきたいのは、判定結果の非対称な性質です。ブルームフィルタが「含まれていない」と答えたときは、その要素は集合の中には存在しません。一方で「含まれている」と答えたときは、本当に存在する場合と、実際には存在しないのに存在すると誤って答える場合（偽陽性、false positive）とが混じります。つまり、見逃し（偽陰性、false negative）はない代わりに、空振り（偽陽性）がまれに起きる、という設計です。
この「否定は確実、肯定はほぼ確からしい」という割り切りが、ブルームフィルタの本質になります。厳密さを一部ゆるめる代わりに、メモリの消費を大きく切り詰め、判定を高速に済ませているわけです。誤りが許されない用途にはそのままでは向きませんが、「まず粗くふるいにかけ、疑わしいものだけを本体で確認する」という前段のフィルタとしては、たいへん相性が良い道具といえます。
なぜ使うのか：存在確認の負荷を手前で減らす
ブルームフィルタが活きるのは、存在確認そのものにコストがかかる場面です。たとえば数千万件のデータを持つデータベースに対して、「このキーは登録済みか」を1件ずつ問い合わせると、ディスクの読み込みやネットワーク往復が積み重なり、件数が伸びるほど処理が重くなります。
ここでブルームフィルタを手前に置くと、多くの問い合わせを本体に届く前でさばけます。フィルタが「含まれていない」と即座に答えたものは、存在しないと分かるため、本体への問い合わせを省けます。「含まれている」と答えたものだけを本体で確かめれば、重い問い合わせの回数をぐっと減らせるのです。
Redisの公式ドキュメントでも、ユーザー名がすでに使われているかの確認や、ユーザーがその広告をすでに見たかの判定といった用途が挙げられています。いずれも「否定の答えでその先の重い処理を止められる」ことが値打ちになる場面です。要素を丸ごと持たずビット列だけで判定するため、同じ件数を集合として保持する場合に比べ、必要なメモリをかなり小さく抑えられます。
仕組み：ビット配列と複数のハッシュ関数
ブルームフィルタの土台は、すべてが0で初期化された長いビット配列と、複数のハッシュ関数の組み合わせです。ハッシュ関数は、入力された値を配列上のどこかの位置へ対応づける計算だと考えてください。
要素を登録するときは、その要素を複数（k個）のハッシュ関数にかけ、得られたk個の位置のビットをそれぞれ1に立てます。存在を確かめるときは、同じようにk個の位置を計算し、そのすべてが1かどうかを見るわけです。ひとつでも0があれば、その要素は登録されていないと判断できます。すべて1のときは「登録されている可能性が高い」と判断する、という流れです。
ここから、非対称な性質が自然に導かれます。ある要素のk個の位置に0がひとつでもあれば、その要素は一度も登録されていないと言い切れます。ところが「すべて1」は、別々の要素が立てたビットがたまたま重なっても成立してしまうのです。これが偽陽性の正体になります。下の表に、2つの判定結果とその意味を整理します。
| 判定結果 | 意味 | とるべき行動 |
|---|---|---|
| 「含まれていない」 | その要素は集合内に存在しない（見逃しは起きない） | 本体への問い合わせを省ける |
| 「含まれている」 | 存在する可能性が高いが、まれに偽陽性が混じる | 本体に問い合わせて最終確認する |
誤検知率とサイズの関係、削除の制約
偽陽性がどのくらいの割合で起きるかは、設計時にコントロールできます。ビット配列を大きくとるほど、またハッシュ関数の数を適切に選ぶほど、偽陽性の割合は下がっていきます。逆にビット配列に対して登録件数が増えすぎると、1に立つビットが密になり、偽陽性が起きやすくなるのです。
Redisの公式ドキュメントでは、目標とする誤検知率と想定件数から必要なサイズが自動で見積もられ、たとえば誤検知率0.1%なら1件あたり約14.4ビット、0.01%なら約19.2ビットが目安と示されています。同じ件数を集合として持つ場合に比べ、要素の中身を持たないぶん、必要なメモリは小さく収まります。
もうひとつ知っておきたい制約が、要素の削除です。基本のブルームフィルタでは、いったん立てたビットを単純に0へ戻せません。そのビットが他の要素と共有されているかもしれず、消すと別の要素まで「含まれていない」と誤ってしまうためです。削除が必要な場合は、各位置をカウンタで持つカウンティングブルームフィルタなどの拡張で対応します。想定件数が読みにくいときは、あらかじめ大きめに見積もるか、自動で拡張する実装を選ぶといった判断が要るでしょう。
どこで使われているか
ブルームフィルタは、「否定の答えで重い処理を省ける」という性質が活きる場所で幅広く使われています。データベースの世界では、ディスク上のデータを探しにいく前段に置き、存在しないキーへの無駄な読み込みを避ける使い方が代表的でしょう。PostgreSQLには、複数の列の任意の組み合わせで等価検索するケースに向く、ブルームフィルタを用いた索引の拡張（bloom）も用意されています。
キャッシュの前段に置いて、キャッシュにも本体にも無いキーへの問い合わせ（キャッシュのすり抜け）を抑える使い方もあります。ほかにも、大量URLの重複判定、分散システムでのデータ配置の絞り込み、迷惑メール判定の下ごしらえなど、応用は多彩です。先に触れたユーザー名の重複チェックや広告の表示済み判定も、代表的な例といえるでしょう。
共通しているのは、「たまに空振りしても、後段の確認で吸収できる」という条件です。逆に、判定を最終結論としてそのまま使い、誤りが許されない場面には向きません。この向き不向きの線引きが、導入を考えるうえでの出発点になります。
発注・設計でおさえる点
発注担当者やプロジェクトマネージャーの立場では、実装の細部よりも、使いどころの妥当性を確認できると役立ちます。まず押さえたいのは、その処理が「偽陽性を後段で吸収できる用途か」という点です。フィルタが空振りしても本体で最終確認する流れになっていれば、誤検知は実害につながりません。
次に、想定する登録件数と、許容できる誤検知率をあらかじめ見積もっておくことです。この2つが決まれば、必要なメモリの大きさが定まります。件数が将来伸びる見込みがあるなら、自動で拡張する実装か、初めから大きめのサイズを取る設計かを相談しておくとよいでしょう。あわせて、要素の削除が必要になる運用かどうかも、早い段階で開発会社と確認しておきたいポイントになります。
ブルームフィルタは、あくまで本体の存在確認を軽くするための補助的な仕組みです。何を確定的な答えとして扱い、何を確率に委ねるのかという役割分担を、設計レビューの場で言葉にしておくと、後々の認識のずれを防げます。
まとめ
- ブルームフィルタは、要素が集合に含まれるかを少ないメモリで手早く判定する確率的なデータ構造である。
- 「含まれていない」は言い切れて見逃しがなく、「含まれている」にはまれに偽陽性（空振り）が混じるという非対称な性質を持つ。
- ビット配列と複数のハッシュ関数で成り立ち、位置がすべて1なら「たぶん有る」、ひとつでも0なら「まちがいなく無い」と判断する。
- 誤検知率はビット配列の大きさとハッシュ関数の数で調整でき、基本の方式では要素の削除ができない。
- 存在確認の前段フィルタとして幅広く使われ、偽陽性を後段で吸収できる用途かどうかが導入判断の要になる。
よくある質問
ブルームフィルタは判定を間違えることがあるのですか。
「含まれている」という判定については、まれに間違えます。実際には登録していない要素を、登録済みと答えてしまう偽陽性が起こり得るためです。ただし「含まれていない」という判定は間違えません。見逃し（偽陰性）は原理的に起きないので、否定の答えは信頼できるものとして扱えます。
なぜ少ないメモリで判定できるのですか。
要素そのものを保存せず、ハッシュ関数で決めた位置のビットを立てるだけだからです。値の中身を持たないため、同じ件数を集合として保持する場合に比べ、必要なメモリを小さく抑えられます。そのぶん、判定はビットを見るだけで済み、速く処理できます。
一度登録した要素を削除できますか。
基本のブルームフィルタでは削除できません。立てたビットが他の要素と共有されている場合があり、単純に0へ戻すと別の要素まで誤って「含まれていない」と判定してしまうためです。削除が要るなら、各位置をカウンタで管理するカウンティングブルームフィルタなどの拡張を検討することになります。
どんな場面に向いていますか。
まず粗くふるいにかけ、疑わしいものだけを本体で確認する、という前段フィルタの用途に向いています。存在しないキーへの重い問い合わせを省きたい場面が典型です。逆に、判定をそのまま最終結論として使い、誤りが許されない用途には向きません。偽陽性を後段の確認で吸収できるかどうかが、向き不向きの分かれ目になります。
著者：テレリモ総研編集部 鈴木 亮佑
LASSICでは、国内ニアショア開発体制を活かし、データ構造やアルゴリズムの選定からシステムの設計・実装、公開済みシステムの見直しまでを一貫して支援する体制です。要件定義の段階から実装、テスト、リリース後の運用・保守まで、工程を分けずに任せられる点も強みでしょう。性能とメモリのバランス設計でお困りの際も、ご相談いただけます。
ご不明な点はお問い合わせフォームからもご連絡いただけます。
出典
- Wikipedia（日本語版）「ブルームフィルタ」
- PostgreSQL Documentation「bloom — bloom filter index access method」
- Redis Documentation「Bloom filter」
