Bloom filter の解説 : 効果的な local read / write set の探索

はじめに

これは自作 DBMS Advent Calendar 2020 (https://adventar.org/calendars/5548) 向けの記事になります。内容としてはでかい集合の中に特定の要素が存在するかどうかの効果的な検証として bloom fileter を考えてみましょうというものになります。bloom filter、偽陽性（充填率）抑制のためのパーティション分割・フィルター増設を解説します。

トランザクショナルシステムにおけるデータ探索の課題

non-deterministic トランザクショナルシステムを実装する人にとって、効果的な local read / write set の探索というのは一つの課題になりえると思います。
例えば repeatable read のプロパティを課す場合、同一キーに対して複数回 read query が発行されることを考慮しなければいけません。
一回目と二回目の read で異なる結果を返してはまずいので、「既に同一キーに対して read したか？」ということを local read set へチェックしにいかなければいけません。
異なる例として、 read-own-write のプロパティを課す場合、「既に同一キーに対して write したか？」ということを local write set へチェックしにいかなければいけません。
もし local set size が（バッチのようなトランザクションによって）大きいものである場合、探索コストも大きくなることが考えられます。bloom fileter で存在するかどうかをぱっと事前検証してみるのはいかがでしょうか？

bloom filter ってなに？

ハッシュです。
とある bit set に対して要素を挿入するたびに要素をハッシュに通した結果に即すように bit set の bit を上げます。
存在を検証するときは、要素をハッシュに通した結果に即す位置のビットが上がっているかどうかで検証します。

例

bloom filter を１バイト変数とします。
一バイトは八ビットありますので、初期状態は下記です。

bloom filter bit index	0	1	2	3	4	5	6	7
value	0	0	0	0	0	0	0	0

Set = {}

ハッシュ関数は 8 の剰余とします。
２という整数を挿入したとき、８の剰余を取ると 2 ですので、 bit index 2 のビットを上げます。

bloom filter bit index	0	1	2	3	4	5	6	7
value	0	0	1	0	0	0	0	0

Set = {2}

同様に、 11 という整数を挿入したとき、8 の剰余を取ると 3 ですので、下記のテーブルのようになります。

bloom filter bit index	0	1	2	3	4	5	6	7
value	0	0	1	1	0	0	0	0

Set = {2, 11}

このような状態において、5 という整数が集合に含まれているか？という検証は 5 の 8 による剰余を取った bit index 5 の位置のビットが上がっているかどうかを確認します。
ビットは下がっていますし、集合にも含まれていませんね？
このようにして bloom filter は運用されます。

偽陽性

bloom filter bit index	0	1	2	3	4	5	6	7
value	0	0	1	1	0	0	0	0

Set = {2, 11}

上記テーブルに対して、整数 3 の存在検証を行ったとき、8 の剰余を取ると 3 ですので、 bit index 3 の位置を見に行くのですが、既にビットが上がっているので要素が既に存在するかのように思えますが、集合には含まれていません。
これが偽陽性です。
ビットがたくさん立っていれば立っているほど、偽陽性は高いです。

フィルターサイズによる偽陽性抑制

上述の例において、フィルターサイズを 16 取ってハッシュを 16 の剰余としたとき、 Set = {2, 11} で上がっているビットは 2, 11 になりますので、 3 が入る余地が生まれます。
従って、フィルターサイズを大きくすると、偽陽性を抑制することができます。

bloom filter bit index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
value	0	0	1	0	0	0	0	0	0	0	0	1	0	0	0	0

Set = {2, 11}

partition による偽陽性抑制

bloom filter をパーティション分割することによって充填率を上昇させる代わりに偽陽性を抑制することができます。
それぞれのパーティションごとにハッシュ関数を持たせて、要素挿入時はパーティションごとにハッシュを通した結果を反映させます。
存在検証時は全てのパーティションにハッシュ関数の結果が既に反映されている状態であれば、存在しうると判定します。

要素の集合を {2, 11} とし、フィルターの上位 5 bits (index 0 - 4) は 5 の剰余関数、下位 3 bits (index 5 - 7) は 3 の剰余関数とすると、フィルターの状態は下記のようになります。

bloom filter bit index	0	1	2	3	4	5	6	7
partition number	1	1	1	1	1	2	2	2
value	0	1	1	0	0	0	0	1
raised by	0	{11}	{2}	0	0	0	0	{2, 11}

Set = {2, 11}

3 を挿入したいとき、5 の剰余は 3 (bit index 3), 3 の剰余は 0 (bit index 5) になりますので、3 を挿入するとテーブルは下記のようになります。

bloom filter bit index	0	1	2	3	4	5	6	7
partition number	1	1	1	1	1	2	2	2
value	0	1	1	1	0	1	0	1
raised by	0	{11}	{2}	{3}	0	{3}	0	{2, 11}

Set = {2, 3, 11}

フィルター増加による偽陽性抑制

要素をたくさん挿入すればするほど、ビットがたくさん立つことによって充填率が上昇し、その結果偽陽性も上昇していきます。
フィルターの数を増やすことで、それを抑制することができます。
フィルターの充填率が一定を超えた場合、新しいフィルターを増設し、以降はそこにハッシュ関数の結果を反映させていきます。
存在検証は古いフィルターから順に行っていきます。

例

bloom filter bit index	0	1	2
value	1	1	1
raised by	{a}	{a, b}	{b}

Set = {a, b}

例として、要素 a, b を順に挿入した結果のブルームフィルターを上記テーブルとします。
要素 a は index {0, 1} を上げるものとし、 b は index {1, 2} を上げるものとします。
ここに、ハッシュの結果 bit index {0, 2} を上げることになる要素 c の存在を検証すると、偽陽になります。
ブルームフィルターで何が困るかと言えば、要素挿入による作用の和集合の部分集合に入れてない要素の挿入によって発生する作用が完全一致することだと思います。
これを避けるために、充填率が一定以上になったときにフィルターを増設することを検討します。

要素 a のみが挿入されたフィルター状態を下記テーブルとします。

bloom filter bit index	0	1	2
value	1	1	0
raised by	{a}	{a}	{}

Set = {a}

次に、フィルターの充填率が一定を超えたとみなし、要素 b の挿入は新しいフィルターに適用するとしたテーブルが下記になります。

bloom filter bit index	0	1	2
filter[0] value	1	1	0
raised by	{a}	{a}	{}
filter[1] value	0	1	1
raised by	{}	{b}	{b}

Set = {a, b}

ハッシュの結果 bit index {0, 2} を上げることになる要素 c の存在を検証する場合、 filter [0] を見ますと、bit index {2} が上がっていません。
filter [1] を見ますと bit index {0} が上がっていません。
従って、（偽陽なく）適切に存在していないことが検証できました。

まとめ

• bloom filter は存在検証に使う。
• たくさんの要素を登録すると、充填率上昇に伴って、存在検証における偽陽性が上昇する。
• 偽陽性を抑えるテクニックに、パーティション分割、フィルター増加が有効である。

余談

• ハッシュ関数の結果はなるべくばらけるように考慮すると偽陽性抑制に効果的です。