特徴

　Wikipediaより引用。

空間効率の良い確立的データ構造であり、要素が集合のメンバーであるかどうかのテストに使われる。偽陽性（False Positive）による誤検出の可能性があるが、偽陰性（False Negative）はない。要素を集合に追加することができるが、削除することはできない（Counting filter を使えば削除できる）。集合に要素が追加されればされるほど、偽陽性の可能性が高くなる。

　つまり、特定の要素（例えば名前）が集合（名簿）に含まれているかどうかを調べるために使われる。ただ、毎回名簿情報をサーバに投げているとデータ量が多くなってしまうので、ある程度簡略化したものだ。

実装

　実装を簡単に説明すると

0で初期化されたmビット配列を用意
特定の値をk個のハッシュ関数でmまでの値に変換する
2で計算したビット目を立てる

　※既に立てようとしているビット目が立っていても気にしないで立てておく。

　利用する場合は、特定の値を同じk個のハッシュ関数で求められたビット目が すべて 立っているかどうか確認する。すべて立っていれば、その値がブルームフィルタに含まれている 可能性 がある。ここで可能性があると書いているのは、アルゴリズム上、確実に入っていることを保証するわけではないからだ。ブルームフィルタは特徴として、偽陽性の可能性はあるが偽陰性はない。

　つまり、ブルームフィルタに登録されている値が本当は含まれているのに、含まれていないと判定されることは無いが、登録されていない値が含まれていると誤判定することはあるということだ。

なぜ使われているのか

　勝手な想像ではあるが、H2Oではキャッシュがクライアント含まれている場合は無駄なのでサーバープッシュでコンテンツを送りたくない。だが、HTMLに含まれている静的コンテンツ（cssやjs等）が100個とかあった場合に、それの内容をハッシュ化した（ファイル名だけだと内容が更新されている場合があるので）値を毎回送受信するのも効率が良くない。なのでブルームフィルタ（ビット列）はソート済整数列として表現出来るのでそのブルームフィルタだけを送受信すれば効率的だ。先程も記述した通り、クライアントがキャッシュを持っているのに、持っていないと判定されることは無いので、無駄なコンテンツを送ることはない。ただ、キャッシュを持っていない物を、持っていると判定されることがあるのでその場合はサーバプッシュでは送られず、通常通りのリクエスト・レスポンスによって配信される。

　キャッシュという特性上、「あればラッキー」ぐらいな感覚なので、誤判定されてサーバプッシュされなくても（今までと同じなので）マイナスにはならないという考えだろう。

　このブルームフィルタをCookieでブラウザに食わせてやりとりを行うようだ。その為にCookie値のバイト数分もったい無いと感じるかもしれないが、HTTP/2にはHPACKという仕様があり、前回と同じヘッダ項目は送らなくても良くなっている。このCASPER(cache-aware server pusher)はCookieという枯れた技術を利用することで、あらゆるブラウザに対応し、HTTP/2の仕様もうまく利用したとても良い実装だと感じた。