SKYSEA Client Viewは、大量のログを保存します。
もともとこのログの検索は、素直に文字列検索する仕組みになっていましたが、どうしても検索に時間がかかるため、高速化することが求められていました。 この記事では、検索の高速化を実現した仕組みについて説明していきます。
一般的な検索高速化の手法と、その問題
一般的に、検索処理を高速化するのに使われるのは転置インデックスです。これを使ったシステムとしては、Elasticsearchが有名です。 これは検索対象のデータの切片から検索対象のドキュメント自体へのインデックスを構築する仕組みで、非常に高速に検索を行えます。
ただ、この方式をとると、ストレージ容量が大きく消費されてしまうという問題があります。
SKYSEA Client Viewはオンプレミスで使っていただくケースがとても多く、ストレージの容量はお客様の投資コストに直接響きます。そのため、転置インデックスを採用するのはためらわれました。
そこで注目したのが、ブルームフィルターというデータ構造です。
確率的データ構造
ブルームフィルターは、確率的データ構造（probabilistic data structures）と呼ばれる種類のデータ構造の一つです。確率的データ構造には、代表的なものとして
- ブルームフィルター（集合の中にデータが含まれているか）
- HyperLogLog（集合中のユニークなデータの数）
- Count-Min Sketch（ストリーム中の要素の発生頻度）
などがあり、いずれも大量のデータからある程度の誤差を伴いながら、きわめて高い効率（演算負荷やメモリ使用量）で目的を果たすことができます。 こういったデータ構造には様々なバリエーションが提唱されており、多くの論文があります。
ブルームフィルター
ブルームフィルターは、データの集合の中にあるアイテムが含まれているかどうかを調べることができるデータ構造です。 通常、この処理をするにはデータの集合をそのまま保持して、同じアイテムがあるかを何らかの方法で調べることになりますが、 ブルームフィルターにはオリジナルのデータの集合を保持する必要がなく、小さなサイズのブルームフィルターに大量のデータを登録できます。 そして、アイテムがその集合中に含まれるかどうかをきわめて軽量に調べることができます。
ただしもちろんそこには制限があります。アイテムが集合に含まれていないという判定は100%正しいのですが、
アイテムが集合に含まれていると判定された場合には、ある程度の確率で実は含まれていなかった、というケースが出てきます（擬陽性）。
これがどの程度の確率になるかは、フィルターのサイズや収容するアイテム数によります（詳しい数式を知りたい場合は「ブルームフィルター」で検索すれば調べられます）。
ブルームフィルターの構築
では簡単な例を見てみましょう。たとえば「リンゴ、ミカン、パイナップル」という集合の中に「ミカン」は入っているかどうかを調べるという例を考えてみます。
１．十分な長さの配列を用意する。
簡単に24ビットの配列を使うものとしましょう。この配列がブルームフィルターそのものです。最初にすべてのビットは落としておきます。
□□□□□□□□□□□□□□□□□□□□□□□□
２．「リンゴ、ミカン、パイナップル」を１つずつブルームフィルターに追加していきます。
各要素をハッシュ関数にかけて得られた値のビットを立てることで追加します。（だいぶ簡略化しています）
リンゴ→ハッシュ関数→0008
□□□■□□□□□□□□□□□□□□□□□□□□
ミカン→ハッシュ値→0800
□□□□□□□□□□□■□□□□□□□□□□□□
パイナップル→ハッシュ値ー＞0x010000
□□□□□□□□□□□□□□□□■□□□□□□□
こうして得られたビット配列のORをとったものが 「リンゴ、ミカン、パイナップル」を含んだブルームフィルターです。
□□□■□□□□□□□■□□□□■□□□□□□□
このビット配列（ブルームフィルター）を使って要素の有無を判定します。
3. それでは、得られたブルームフィルターにある要素があるかないか判定します。
Q1. リンゴはあるか？
「リンゴ」のハッシュ値を計算します。
リンゴ→ハッシュ値＝0008
リンゴをあらわすビット配列
□□□■□□□□□□□□□□□□□□□□□□□□
「リンゴとミカンとパイナップルを含む配列」（さっき作ったブルームフィルター）
□□□■□□□□□□□■□□□□■□□□□□□□
両者の配列を比較してみると、「リンゴとミカンとパイナップルを含むビット配列」 は、「リンゴをあらわすビット配列」を含んでいることがわかります。
結果として、このブルームフィルターは、（おそらく）リンゴを含んでいることになります。
Q2. オレンジはあるか？
オレンジ→ハッシュ値＝0x100000
「オレンジをあらわすハッシュ値」
□□□□□□□□□□□□□□□□□□□□■□□□
「リンゴとミカンとパイナップルを含む配列」
□□□■□□□□□□■□□□□□■□□□□□□□
リンゴと同じように比較すると、「リンゴとミカンとパイナップルを含む配列」は、「オレンジをあらわすハッシュ値」 を含んでいないことがわかります。 すなわち、このブルームフィルターには「オレンジ」は絶対に含まれていません。
4. 誤判定のパターン
仮にキウイフルーツのハッシュが0808だったとしましょう。ビットパターンはこうなります。
□□□■□□□□□□■□□□□□□□□□□□□□
これを「リンゴとミカンとパイナップルを含む配列」（さっき作ったブルームフィルター）と比較してみると、
□□□■□□□□□□■□□□□□■□□□□□□□
「含まれている」という判定になってしまいます。これが擬陽性のパターンです。
以上の様子から、ブルームフィルターのビット長を長くしてやれば、擬陽性の確率は下がっていくことが直感的にわかると思います。
どうやって製品で活用するか
さて、こういった面白い特徴を持つブルームフィルターですが、実際の製品で利用する上ではいろいろ工夫が必要になります。 次回の記事では、実際の利用に際しての工夫などを書いていこうと思います。
