1概要

この記事では、

Guava

ライブラリーからのBloomフィルター構成を調べます。ブルームフィルタは、与えられた要素が集合に含まれるかどうかにかかわらず** の問題に答えるために使用できる、メモリ効率の良い、確率的なデータ構造です。

  • ブルームフィルタには

    偽陰性はありません

    ので、それが

    false

    を返すとき、要素が集合にないことを100%確信できます。

しかし、ブルームフィルタ

は誤検出

を返す可能性があるため、

true

を返すと、要素がセット内にある可能性が高いですが、100%確実というわけではありません。

ブルームフィルタがどのように機能するかをより詳細に分析するには、https://llimllib.github.io/bloomfilter-tutorial/[このチュートリアル]を参照してください。


2 Mavenの依存関係

GuavaのBloomフィルタの実装を使用しますので、

guava

依存関係を追加しましょう。

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>22.0</version>
</dependency>

最新版はhttps://search.maven.org/classic/#search%7Cgav%7C1%7Cg%3A%22com.google.guava%22%20AND%20a%3A%22guava%22[Maven Centralにあります]。


3ブルームフィルターを使用する理由

ブルームフィルタは、スペース効率が良く高速に設計されています。それを使用するとき、私たちは受け入れることができる偽陽性の応答の確率を指定することができます** そして、その構成によれば、ブルームフィルタはそれができる限り少ないメモリを占有するでしょう。

このスペース効率のおかげで、

ブルームフィルタは膨大な数の要素に対しても

メモリに簡単に収まります** 。 CassandraやOracleなどの一部のデータベースでは、特定のIDの要求があった場合など、ディスクやキャッシュに移動する前の最初のチェックとしてこのフィルタを使用します。

IDが存在しないことをフィルタが返した場合、データベースはそれ以降の要求処理を中止してクライアントに戻ることができます。それ以外の場合は、ディスクに移動し、ディスク上に見つかった場合は要素を返します。


4ブルームフィルタを作成する

最大500のInteger__に対してブルームフィルタを作成し、1パーセント(0.01)の誤検出確率を許容できるとします。

これを実現するには、

Guava

ライブラリの

BloomFilter

クラスを使用できます。フィルタに挿入されると予想される要素数と必要な誤検出確率を渡す必要があります。

BloomFilter<Integer> filter = BloomFilter.create(
  Funnels.integerFunnel(),
  500,
  0.01);

それでは、フィルタにいくつか数値を追加しましょう。

filter.put(1);
filter.put(2);
filter.put(3);

3つの要素だけを追加し、最大挿入数は500になるように定義したので、Bloomフィルタ

は非常に正確な結果

を生成するはずです。

mightContain()

メソッドを使ってテストしましょう。

assertThat(filter.mightContain(1)).isTrue();
assertThat(filter.mightContain(2)).isTrue();
assertThat(filter.mightContain(3)).isTrue();

assertThat(filter.mightContain(100)).isFalse();

名前が示すように、メソッドが

true

を返したときに特定の要素が実際にフィルタ内にあることを100%保証することはできません。

この例で

mightContain()



true

を返すと、要素がフィルタ内にあることを99%確信でき、結果が偽陽性である確率が1パーセントになります。フィルタが

false

を返すとき、要素が存在しないことを100%確信できます。


5過飽和ブルームフィルタ

ブルームフィルタを設計するときには、

予想される要素数

に対してかなり正確な値を提供することが重要です。

さもなければ、私達のフィルターは望まれるよりはるかに高い率で偽陽性を返します。例を見てみましょう。

1%の期待誤検出確率と5に等しいいくつかの要素を持つフィルターを作成したと仮定しますが、その後100,000要素を挿入します。

BloomFilter<Integer> filter = BloomFilter.create(
  Funnels.integerFunnel(),
  5,
  0.01);

IntStream.range(0, 100__000).forEach(filter::put);

予想される要素数が非常に少ないので、フィルタは非常に小さなメモリを占有します。

ただし、予想よりも多くの項目を追加すると、** フィルタが飽和しすぎて、誤検出の結果が返される可能性がはるかに高くなります。

assertThat(filter.mightContain(1)).isTrue();
assertThat(filter.mightContain(2)).isTrue();
assertThat(filter.mightContain(3)).isTrue();
assertThat(filter.mightContain(1__000__000)).isTrue();


mightContatin()

メソッドは、以前フィルタに挿入されていなかった値に対しても

true

を返しました。


6. 結論

このクイックチュートリアルでは、

Guava

実装を使用して、ブルームフィルタのデータ構造の確率的な性質を調べました。


GitHubプロジェクト

に、これらすべての例とコードスニペットの実装があります。

これはMavenプロジェクトなので、そのままインポートして実行するのは簡単なはずです。