5分でブルームフィルタを理解する。10億レベルのデータフィルタリングアルゴリズムは、知っておく価値があります。

[[339720]]

この記事はWeChatの公開アカウント「Uncle Who Knows a Little Code」から転載したもので、著者はUncle Who Knows a Little Codeです。この記事を転載する場合は、Uncle Who Knows Codeの公式アカウントまでご連絡ください。

Bloom フィルターについて正式に説明する前に、次のビジネスシナリオを見てみましょう。

Redis は、ソフトウェアアーキテクチャでよく使用されるコンポーネントです。最も一般的な使用方法は、データベースへの負荷を軽減するために、ホットデータを Redis にキャッシュすることです。クエリプロセス中に最も一般的な使用方法は、Redis をクエリすることです。データが見つかった場合は、直接返されます。Redis に存在しない場合は、データベースのクエリを続行します。

この方法により、データベースアクセスの回数を減らすことができますが、「データがキャッシュにないときにデータベースをクエリする」ことは、同時実行性の高い環境では依然としてリスクを伴います。たとえば、要求されたデータの 90% がキャッシュにない場合、これらの要求はすべてデータベースに送られ、キャッシュ侵入が発生します。

では、この問題を解決する方法はあるのでしょうか? これは、「特定のデータが確実に存在しない」ことを判断できるブルームフィルターを使用することで解決できます。

01. ブルームフィルタの概念

ブルームフィルタは、「ブルーム」という人物によって提案されました。それ自体は非常に長いバイナリベクトル (配列として想像してください) と一連のランダムマッピング関数 (複数のハッシュ関数として想像してください) です。バイナリベクトルには 0 または 1 が格納されます (ブルームフィルタについて学習する前に、まず BitMap アルゴリズムを理解すると理解しやすくなります)。

例えば、顧客の携帯電話番号を条件として顧客情報を照会したい場合、通常は携帯電話番号をキャッシュのキーとして設定します。長さ 16 の Bloom フィルターを設定してみましょう。

ブルームフィルタは 0 に初期化されます。

13800000000 に対して hash1()、hash2()、hash3() 演算を実行し、5、9、12 の 3 つの結果を取得します。対応する位置を 1 に設定します。

18900000000 に対して hash1()、hash2()、hash3() 演算を実行し、2、8、12 の 3 つの結果を取得します。対応する位置を 1 に設定します。これで、2、5、8、9、12 はすべて 1 になり、残りの要素は 0 になります。

電話番号が存在するかどうかを確認したい場合はどうすればいいでしょうか?

13700000000 に対してそれぞれ hash1()、hash2()、hash3() 演算を実行し、1、9、13 の 3 つの結果を取得します。次に、1 番目、9 番目、13 番目のビットの値が 0 か 1 かを判定します。すべて 1 でない場合は、13700000000 がこの Bloom フィルター上にないことを意味し、これにより、「特定のデータが確実に存在しない」ことが確認されます。

もちろん、ブルームフィルタには問題があることもわかります。つまり、データが存在することを保証できないということです。たとえば、18000000000 に対して hash1()、hash2()、hash3() 演算を実行すると、結果は 5、8、9 となり、たまたま 1 になります。しかし、実際にはこのデータは存在しないため、ブルームフィルタには一定の誤判定率があります。

また、計算後に複数のデータが同一の位置にマッピングされる可能性があるため（138と189の計算結果はともに12）、ビットごとにカウンターを追加しない限り、ブルームフィルターを削除することは困難です。削除する場合は、カウンターが0になるまでカウンターから1を減算し、ブルームフィルターの対応する位置を0に変更する必要があります。

02. 機能概要

ある要素が確実に存在しないと判断することは可能ですが、ある要素が確実に存在すると判断することは不可能です。

バイナリベクトルが長いほど、マッピング関数の数が多くなり、誤判定率が低くなります。誤判定率が事前に判定できれば、ブルームフィルタの長さも推測できます。

要素は追加できますが、削除することはできません (カウンターが増加しない限り)。

挿入クエリのストレージスペースと時間の複雑さの点で大きな利点があります。

この記事の冒頭のビジネスシナリオに戻ると、キャッシュ侵入を防ぐために、ブルームフィルターを使用して、確実に存在しないデータをフィルター処理できます。誤って判断されたリクエストはデータベースに配置されますが、侵入の数は大幅に削減されます。

03. ブルームフィルタを手書きする

コードを書くことが目的ではなく、コーディングのプロセスは理解を深めることです。

まず、ビットマップを定義する必要があります。JDK には、対応するデータ構造クラス java.util.BitSet が既に存在します。

 //ブルームフィルターを設定する
プライベートint DEFAULT_SIZE = 1 << 30; 
 
プライベート BitSet ビットセット;

マッピング関数のセットも必要です。ここでは、加法ハッシュ関数を使用して、6 つの異なるハッシュ関数に対応する 6 つの素数を設定できます。

 //長さ6の素数配列を定義し、ランダムマッピング用の6つのハッシュ関数を生成できる
プライベートint []シード = {3, 7, 13, 31, 37, 61}; 
 
プライベートHashFunction[] functions = new HashFunction[seeds.length];

コンストラクターで初期化し、BitSet の長さを設定し、マッピング関数を生成します。

 /**
 * 初期化
*/
パブリックブルームフィルタ() {
  ビットセット = 新しい BitSet(DEFAULT_SIZE); 
 
 ( int i = 0; i < seeds.length; i++) {
      functions[i] = 新しいHashFunction(DEFAULT_SIZE、seeds[i]);
  }
 }

要素を追加するときは、入力パラメータに対して 6 つのハッシュ操作を実行し、結果に対応する位置を 1 に変更します (BitSet に対応する位置は true に変更されます)。

 /**
 * 要素を追加し、ハッシュ演算の結果を取得し、対応する位置を1（ true ）に変更します。
 * @パラメータ値
*/
パブリックvoid add (文字列値) {
  値 != null の場合{
 (HashFunction f: 関数)の場合{
    bitset.set (f.hash(値), true );
      }
  }
 }

Bloom マネージャーに要素が存在するかどうかを判断するには、入力パラメータに対して 6 つのハッシュ演算を実行し、結果の対応する位置が 0 か 1 (真か偽か) かどうかを確認する必要があります。ビットの 1 つが 0 の場合、データが確実に存在しないことを意味します。すべてが 1 の場合、データが存在する可能性がある (高い確率で存在する) ことを意味します。

 /**
 * 要素がブルームフィルタ内にあるかどうかを判定する
* @パラメータ値
* @戻る 
 */
パブリックブール値には（文字列値）が含まれます{
  値 == nullの場合
戻る 間違い;
  } 
 
 (HashFunction f: 関数)の場合{
    if(!bitset.get(f.hash(値))){
      //位置が1（ true ）でない場合は存在しないことを意味し、直接falseを返します 
戻る 間違い;
    }
  } 
 
戻る 真実;
 }

04. Guava の BloomFilter

Bloom マネージャーの実装に役立つオープンソースフレームワークはすでに多数存在します。たとえば、すぐに使用できる Bloom フィルターを備えた Google 製の Guava ツールライブラリなどです。

パブリッククラスBloomFilterTest {
公共 静的void main(String[] args){
整数 サイズ= 1000000;
    //ブルームフィルター
    BloomFilter< Integer > bloomFilter = BloomFilter.create ( Funnels.integerFunnel(),サイズ, 0.001); 
     
 ( int i = 0; i <サイズ; i++) {
            ブルームフィルタを put(i);
        } 
     
    リスト<整数> リスト = 新しい ArrayList<整数>(1000);
 ( int i =サイズ+ 1; i <サイズ+ 10000; i++) {
            if (bloomFilter.mightContain(i)) {
                リストに追加します(i);
            }
        }
        System.out.println ( "誤判定数:" +list.size ( ));
  }
 }