僕が好きなトリックがあるんだ。メンバーシップチェックをたくさんやる小さいセットに対して、64ビットのブルームフィルターをトリビアルなハッシュ関数で追加するってやつ。これ、バカみたいに聞こえるかもしれないけど、コストがすごく小さいから、賭けみたいに使えるんだよね。もしうまくいかなかったら、挿入やメンバーシップチェックに10nsくらい追加されるだけだけど、うまくいったらものすごく作業を節約できるんだ。

このアーティクルは、僕みたいな人に向けて書かれてるね。名前は聞いたことあったけど、言及されるたびに調べようと思ってたんだ。あなたの記事を見て、やっと調べてみたら、探してた完璧なイントロだったよ :)

Eli Benderskyからの別のブルームフィルターに関する投稿もすごく良かったので、興味がある人は読んでみてね： https://eli.thegreenplace.net/2025/bloom-filters/

ブルームフィルターの別のビジュアライゼーションはこのページの最後にあるよ： https://www.chrislaux.com/hashtable.html

僕はCassandraのリードスパイクをデバッグしているときにブルームフィルターにハマったんだ。キーが存在しないときでもたくさんのsstableルックアップがあって、最初は意味が分からなかったけど、各sstableにブルームフィルターがあってディスクをスキップするためのものだと気づいたんだ。でもデフォルトの偽陽性率が0.1くらい高すぎて、うちのケースには合わなかった。ほとんどのリードはキャッシュミスだったから、その偽陽性が厄介で、0.01に変更したら、少しメモリを使ったけど無駄なリードが減って、p99のリードレイテンシが16-18%も改善されたよ。

過去にブルームフィルターを使ったことはあったけど、どう機能するかはよく理解してなかったんだ。ある日、Wikipediaの記事を参考にして32ビットのMurmurHash関数を使って実装してみたら、すごく簡単だったんだ。C++を使ってるなら、std::vector（C++23からはstd::bitsetも）を使うと、ビットを効率的に保存するのがもっと簡単になるよ。

2009年に大学のためにCUDAでブルームフィルターを書いたんだ。僕の指導教官は元Nvidiaの人だった。その後、キャリアの中でGPUプログラミングは全くやらなかったけど、もし別の選択をしていたら、1億ドルくらい稼げたかもしれないな。

最近、ログメッセージのアンチスパム機能にブルームフィルターを使ったんだ。ロガーではメッセージをハッシュ化してフィルターに入れた。エントリーがあればメッセージは出力しなかったんだ。それから数秒ごとにフィルターを繰り返し処理して、すべてのビットをクリアしてた。フィルターのビットを原子的にクリアする心配がいらなくて、メッセージが入ってきてビットがクリアされてたら、再度ログされるのに十分だったから、うまくいったよ。以前の実装は見たメッセージのカウントを保持していて、Nで飽和しちゃってたから、特定のメッセージが繰り返しログされると、フィルターがクリアされる速度でしか見れなかったんだ。ブルームフィルターについて知ってからしばらく経って、実際に役立つ使い方を見つけられて満足だったよ。

作者へのメモ -- インタラクティブな部分が大好き。ポイントを強調するために一つ提案があるんだけど、ハッシュ衝突がある2つの文字列の例をユーザーに示して、一つをボックスに入力させて、もう一つを別のボックスでテストさせるといいと思う。それで「セットに入ってるかも！」って答えが出る理由がわかるはず。

ブームフィルターを重ねて使えば、木をクエリするみたいにハッシュ化できるよ。