1. 概要

この記事では、GuavaライブラリのBloomfilterコンストラクトについて説明します。 ブルームフィルターは、メモリ効率の高い確率的なデータ構造であり、特定の要素がセットにあるかどうかの質問に答えるために使用できます。

ブルームフィルターにはフォールスネガティブがないため、 false を返すと、要素がセットに含まれていないことを100% c確認できます。

ただし、ブルームフィルターは誤検知を返す可能性があるため、 true を返す場合、要素がセットに含まれている可能性が高くなりますが、100% sになることはできません。 ure。

ブルームフィルターがどのように機能するかについてのより詳細な分析については、このチュートリアルを実行できます。

2. Mavenの依存関係

ブルームフィルターのGuavaの実装を使用するので、guava依存関係を追加しましょう。

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre</version>
</dependency>

最新バージョンはMavenCentralにあります。

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

ブルームフィルターはスペース効率が高く高速になるように設計されています。 これを使用する場合、受け入れ可能な誤検知応答の確率を指定でき、その構成に従って、ブルームフィルターは可能な限り少ないメモリを占有します。

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

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

4. ブルームフィルターの作成

最大500整数のブルームフィルターを作成し、誤検知の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になると定義したため、ブルームフィルターは非常に正確な結果を生成するはずです。 mightContain()メソッドを使用してテストしてみましょう。

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

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

名前が示すように、メソッドが true を返すときに、特定の要素が実際にフィルター内にあることを100% s確実にすることはできません。

この例でmightContain() true を返す場合、要素がフィルター内にあることを99 % c確認でき、結果が1%の確率で発生します。誤検知。 フィルタがfalseを返す場合、要素が存在しないことを100% c確認できます。

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

ブルームフィルターを設計するときは、予想される要素数に対して適度に正確な値を提供することが重要です。 それ以外の場合、フィルターは必要以上に高い割合で誤検知を返します。 例を見てみましょう。

望ましい誤検知の確率が1%で、いくつかの要素が5に等しいと予想されるフィルターを作成したが、100,000個の要素を挿入したとします。

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

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

予想される要素の数が非常に少ないため、フィルターはほとんどメモリを占有しません。

ただし、予想よりも多くのアイテムを追加すると、フィルターが過飽和になり、誤検知の結果が必要な1パーセントよりもはるかに高くなる可能性があります。

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プロジェクトなので、そのままインポートして実行するのは簡単です。