再ハッシュ: ブルームフィルタアルゴリズムの実装原理を理解する

[[385658]]

この記事では、広く使用されているアルゴリズムである「ブルーム フィルター アルゴリズム」について再度説明します。

ブルーム フィルタの主な概念は次のとおりです。

• 導入
• アルゴリズム
• パラメータ
• 利点と欠点

ブルームフィルタの紹介

ブルーム フィルタは、「スペース効率の高い確率的データ構造」です (百科事典の元のテキストは、スペース効率の高い確率的データ構造です)。このデータ構造は、1970 年に Burton Howard Bloom によって提案されました。「その機能は、要素がセットのメンバーであるかどうかをテストすることです。」ブルーム フィルタには、誤検出が発生する可能性があります。つまり、ブルーム フィルタを使用すると、「セット内に存在する可能性がある」または「セット内に確実に存在しない」結果が返される可能性があります。

ブルームフィルタアルゴリズムの説明

複雑なシナリオの Web クローラーでは、クロールされた Web ページの URL 依存関係がループを形成する場合があります。たとえば、URL-1 のページに URL-2 が表示され、次に URL-2 のページに URL-1 が表示されます。このとき、過去に訪問された URL を記録して判別するソリューションが必要です。この時点で、次のような解決策が考えられます。

• 解決策1: MySQLテーブルにURLに基​​づいて一意のインデックスを作成したり、RedisのSETデータ型を使用したりして、アクセスしたURLをデータベースに保存する
• 解決策2: HashSet（実際にはHashSetに限定されず、リンクリスト、ツリー、ハッシュテーブル、その他のデータ構造でも要件を満たすことができます）を使用して、アクセスしたURLを保存します。
• 解決策3: 解決策1と解決策2に基づいて最適化し、URLダイジェストを保存し、MD5やSHA-nなどのダイジェストアルゴリズムを使用してURL文字列のダイジェストを生成します。
• 解決策 4: ハッシュ関数を使用して対応する URL を処理してハッシュ コードを生成し、マッピング関数を使用してハッシュ コードを固定容量の BitSet 内のビットにマッピングします。

方式 1、2、3 の場合、過去にアクセスされた URL データの量が膨大になると、膨大な量のストレージ容量 (ディスクまたはメモリ) が消費されます。方式 4 の場合、URL が 100 億個あると、競合の確率を 1% に下げるためには、BitSet の容量を 1 兆に設定する必要があります。

したがって、上記の 4 つのソリューションにはすべて明らかな欠点があり、ブルーム フィルタ アルゴリズムの基本的な考え方はソリューション 4 と似ています。最大の違いは、ソリューション 4 では 1 つのハッシュ関数の使用のみに言及しているのに対し、ブルーム フィルタでは k (k >= 1) 個の独立した効率的で競合の少ないハッシュ関数が使用されることです。

初期化されたブルーム フィルターは、すべてのビットが 0 に設定された長さ m のビット配列であり、これは Redis のビット配列、ビット セット、またはビット マップの概念です。次に、k 個の異なるハッシュ関数を導入する必要があります。新しい要素がこれらの k 個のハッシュ関数によって処理された後、ビット配列内の m ビットのうちの k ビットにマッピングされ、マッピングにヒットしたこれらの k ビットが 1 に設定され、均一なランダム分布が得られます。通常、k は必要な偽陽性率に依存する小さな定数ですが、ブルーム フィルタの容量 m はハッシュ関数 k の数と追加する必要がある要素の数と正の相関関係にあります。

追加する必要があるすべての要素がブルーム フィルターに追加されると、ビット配列内の多くのビットが 1 に設定されます。このとき、ブルームフィルタに要素が存在するかどうかを判定する必要がある場合は、k 個のハッシュ関数を使用してビット配列の k 個の添え字を取得し、ビット配列の添え字に対応するビットが 1 であるかどうかを判定するだけで済みます。これらの k 個の添字が配置されているビットに 0 が少なくとも 1 つある場合、判定対象の要素はブルーム フィルターによって表されるセット内に存在してはなりません。これらの k 個の添字が配置されているビットがすべて 1 である場合、判定対象の要素はブルーム フィルターによって表されるセット内に「存在する可能性がある」か、単に誤検知である可能性があります。エラー率の分析については、以下の「ブルーム フィルターの関連パラメーター」セクションを参照してください。誤検知の状況は以下の図に示されています。

ブルームフィルタに追加される要素数が多く、ブルームフィルタの容量が適切に設定されていない（小さすぎる）場合、k ハッシュ関数を介して複数の要素が同じ k ビット（上図の添え字 1、3、9 が配置されているビットなど）にマッピングされやすくなります。このとき、これらの k ビットが特定のどの要素からマッピングされているかを正確に判断することはできません。実際、極端な考え方をすることができます。ブルーム フィルターの容量が 24 でハッシュ関数が 1 つしかないと仮定すると、最大 25 個の異なる要素が追加された場合、マッピング結果が同じ位置になる 2 つの異なる要素が存在する必要があります。

ブルームフィルタ関連のパラメータ

アルゴリズムの説明セクションで述べたように、ブルーム フィルタには次のパラメータがあります。

ビット配列容量mを初期化する

ハッシュ関数の数 k

偽陽性率 ε (数学記号イプシロン、偽陽性率を表す)

ブルームフィルタに追加する必要がある要素の数n

記事の長さを考慮して、ここではこれらの値の関係を推測するのではなく、結果と関係式を直接整理します。

偽陽性率εの推定値は[1 - e^(-kn/m)]^kである。

ハッシュ関数の最適数kの推定値：与えられたmとnに対して、k = m/n * ln2のとき、誤判定率εは最も低くなる。

k = m/n * ln2、m >= n * log2(e) * log2(1/ε)のとき、初期ビット容量mの値を計算します。

以下は、参考文献から引用した m/n、k、および偽陽性率の関係を示す図です。

ここで、表内の最大のパラメータに必要なスペース制限を推測できます。n が 10 億、m/n = 32 と仮定すると、m は 320 億、k は 24 です。このときのエラー率は 2.17e-07 (0.000000217) で、3814.69727m のスペースが必要です。一般的なルールは次のとおりです。

k が固定されている場合、m/n が大きいほど誤判定率は小さくなります。

m/n が固定されている場合、k が大きいほど誤判定率が高くなります。

通常、k は固定する必要がありますが、n の正確な値を決定することはできません。成長傾向を評価し、より大きな m 値を事前に計算して誤判定率を下げるのが最善です。もちろん、m 値が大きすぎるとスペースが過剰に消費される問題も考慮する必要があります。

パラメータの関係式が導出されたので、関係式に基づいてパラメータジェネレーターを記述できます。

 java.math.BigDecimal をインポートします。
 java.math.RoundingMode をインポートします。 
 
パブリッククラス BloomFilterParamGenerator { 
 
パブリックBigDecimal偽陽性率( int m, int n, int k) {
ダブル  temp = Math.pow(1 - Math.exp(Math.floorDiv(-k * n, m)), k);
 BigDecimal.valueOf( temp ).setScale(10, RoundingMode.FLOOR);を返します。
    } 
 
パブリックBigDecimal kForMinFalsePositiveRate( int m, int n) {
        BigDecimal k = BigDecimal.valueOf(Math.floorDiv(m, n) * Math.log(2));
 k.setScale(10, RoundingMode.FLOOR)を返します。
    } 
 
パブリックBigDecimal bestM( int n, double falsePositiveRate) {
ダブル  temp = log2(Math.exp(1) + Math.floor(1 / falsePositiveRate));
 BigDecimal.valueOf(n).multiply(BigDecimal.valueOf( temp )).setScale(10, RoundingMode.FLOOR);を返します。
    } 
 
公共 ダブルlog2(ダブルx) {
 Math.log(x) / Math.log(2)を返します。
    } 
 
公共 静的void main(String[] args) {
        BloomFilterParamGenerator ジェネレータ = 新しい BloomFilterParamGenerator();
        システム.out.println (generator.falsePositiveRate(2, 1, 2)); // 0.3995764008
        システム.out.println (generator.kForMinFalsePositiveRate(32, 1)); // 22.1807097779
        システム.out.println (generator.bestM(1, 0.3995764009)); // 2.2382615950
    }
 }

ここでの計算は厳密な繰り上がりや切り捨てを考慮していないため、実際の結果はこれと異なる場合があります。あくまでも参考例として提供されています。

ブルームフィルタの長所と短所

ブルームフィルタの利点:

• ブルーム フィルタは、他のデータ構造と比較して、時間と空間の面で大きな利点があります。メモリの消費量が少なく、要素のクエリと挿入にかかる時間の計算量は O(k) です。
• ブルームフィルタに要素が存在しないシナリオを正確に判断できる
• ハッシュ関数は独立して設計できる
• ブルーム フィルター自体はストレージ要素を必要とせず、特定のデータが機密情報であったり、厳密に機密扱いされるシナリオに適しています。

ブルームフィルタの欠点:

• ブルームフィルタでは要素が存在するかどうかを正確に判断することは不可能であり、誤判定率があります。kとmを固定した場合、要素を追加すればするほど誤判定率が高くなります。
• すべての要素が保存されるわけではないため、正確なクエリや正確な統計のシナリオには適していません。
• ネイティブブルームフィルターは要素を安全に削除できない

読者の皆さんに簡単な質問です。ネイティブのブルーム フィルタはなぜ要素を安全に削除できないのでしょうか? (False Positive については前回の紹介を参照してください)

ブルームフィルタアルゴリズムの実装

有名な Java ツール ライブラリ Guava には、ブルーム フィルタ実装のベータ バージョンが付属しています。ここでは、ソース コードの実装のアイデアと上記のアルゴリズムの説明を参照して、ブルーム フィルタを実装します。まずハッシュ関数の設計について考えてみましょう。より簡単な方法は、JavaBean の hashCode() メソッドの設計を参照することです。

 // 次のメソッドはjava.util.Arrays#hashCodeから来ています
公共 静的  intハッシュコード(オブジェクト a[]) {
    (a == null )の場合
0を返します。
 int結果 = 1;
 for (オブジェクト要素: a)
        結果 = 31 * 結果 + (要素 == null ? 0 : element.hashCode());
結果を返します。
 }

上記の方法の 31 は入力シードとして使用できます。各ハッシュ関数は独立したシードを設計し、このシード値は素数を使用して文字列内の各文字を重ね合わせて、比較的独立した計算結果を実現します。

 java.util.Objects をインポートします。 
 
パブリッククラスHashFunction { 
 
    /**
     * ブルームフィルター容量
     */
    プライベート最終int m; 
 
    /**
     * 種子
     */
    プライベート最終intシード; 
 
パブリックハッシュ関数( int m, intシード) {
        m = m;
        this.seed = シード;
    } 
 
公共  intハッシュ(文字列要素) {
        if (Objects.isNull(要素)) {
 0を返します。
        }
 int結果 = 1;
 int len ​​= 要素.length();
 ( int i = 0; i < len; i++)の場合{
            結果 = シード * 結果 + 要素.charAt(i);
        }
        // ここで計算結果がmを超えないようにします
(m - 1) & 結果を返します。
    }
 }

次に、ブルーム フィルターを実装します。

パブリッククラスBloomFilter { 
 
    プライベート静的最終int [] K_SEED_ARRAY = {5、7、11、13、31、37、61、67}; 
 
    プライベート静的最終int MAX_K = K_SEED_ARRAY.length; 
 
    プライベート最終int m; 
 
    プライベート最終int k; 
 
    プライベート最終 BitSet bitSet; 
 
    プライベート最終HashFunction[] hashFunctions; 
 
パブリックブルームフィルタ( int m, int k) {
        k = k;
        (k <= 0 && k > MAX_K) の場合 {
            新しい IllegalArgumentException をスローします ( "k = " + k);
        }
        m = m;
        bitSet を新規作成します。
        ハッシュ関数 = 新しいハッシュ関数[k];
 ( int i = 0; i < k; i++) {
            ハッシュ関数[i] = 新しいハッシュ関数(m、K_SEED_ARRAY[i]);
        }
    } 
 
パブリックvoid addElement(文字列要素) {
 (ハッシュ関数ハッシュ関数 : ハッシュ関数) {
            bitSet.set (hashFunction.hash(要素), true );
        }
    } 
 
パブリックブール値(文字列要素)を含む{
        if (Objects.isNull(要素)) {
戻る 間違い;
        }
        ブール値の結果 = true ;
 (ハッシュ関数ハッシュ関数 : ハッシュ関数) {
            結果 = 結果 && bitSet.get(hashFunction.hash(要素));
        }
結果を返します。
    } 
 
公共 整数m(){
 mを返します。
    } 
 
公共 整数k(){
 kを返します。
    } 
 
公共 静的void main(String[] args) {
        ブルームフィルタ bf = 新しいブルームフィルタ(24, 3);
        bf.addElement( "throwable" );
        bf.addElement( "throwx" );
        System.out.println (bf.contains ( " throwable" ) ); // true  
    }
 }

ここでのハッシュ アルゴリズムと制限された k 値は、複雑なシナリオに対処するには不十分です。これらは、ブルーム フィルターの実装方法を説明するためにのみ使用されます。一般に、ネイティブのブルーム フィルター アルゴリズムは比較的単純です。複雑な本番環境のシナリオでは、Guava の Bloom フィルター API、Redis の Bloom フィルター プラグイン、Redisson (Redis アドバンス クライアント) の Bloom フィルター API などの既製のライブラリを使用できます。

ブルームフィルタの応用

主なものは次のとおりです:

• Guava の API
• RedissonのAPI
• 使用シナリオ

Guava での Bloom フィルタ API の使用

Guava 依存関係を導入します。

 <依存関係>
    <groupId>com.google.guava</groupId>
    <artifactId>グアバ</artifactId>
    <バージョン>30.1-jre</バージョン>
 </依存関係>

ブルームフィルタの使用:

 com.google.common.hash.BloomFilter をインポートします。
 com.google.common.hash.Funnels をインポートします。 
 
 java.nio.charset.StandardCharsets をインポートします。 
 
パブリッククラス GuavaBloomFilter { 
 
    @SuppressWarnings( "不安定な API 使用法" )
公共 静的void main(String[] args) {
        BloomFilter<CharSequence> bloomFilter = BloomFilter.create (Funnels.stringFunnel(StandardCharsets.US_ASCII), 10000, 0.0444D);
        bloomFilter.put( "throwable" );
        bloomFilter.put( "throwx" );
        システム.out .println(bloomFilter.mightContain( "throwable" ));
        システム.out.println (bloomFilter.mightContain( "throwx" ));
    }
 }

BloomFilterを構築するための最も多くのパラメータを持つ静的ファクトリメソッドはBloomFilterです。作成(ファネル（funnel、long expectedInsertions、double fpp、BloomFilter.Strategy strategy）の場合、パラメータは次のとおりです。

• Funnel: 主にあらゆるタイプのデータをHashCodeに変換します。これは、多数の組み込み実装を備えたトップレベルのインターフェースです。Funnelsを参照してください。
• expectedInsertions: 挿入される予定の要素の数
• fpp: 推測は偽陽性率、誤判定率、パーセンテージではなく小数、デフォルト値 0.03
• 戦略: マッピング戦略。現在は MURMUR128_MITZ_32 と MURMUR128_MITZ_64 のみ (デフォルトの戦略)

上記の表またはパラメータ ジェネレーターのガイダンスを参照して、実際のシナリオに基づいてパラメータをカスタマイズできます。

Redisson での Bloom Filter API の使用

高度な Redis クライアント Redisson は、Redis ビットマップ データ構造に基づいてカプセル化されており、複雑な実装ロジックが隠蔽されており、すぐに使用できます。 Redisson 依存関係を導入します。

 <依存関係>
    <グループID>org.redisson</グループID>
    <artifactId>redisson</artifactId>
    <バージョン>3.15.1</バージョン>
 </依存関係>

Redisson で Bloom フィルタ API を使用する:

 org.redisson.Redisson をインポートします。
 org.redisson.api.RBloomFilter をインポートします。
 org.redisson.api.RedissonClient をインポートします。
 org.redisson.config.Config をインポートします。 
 
パブリッククラスRedissonBloomFilter { 
 
公共 静的void main(String[] args) {
        設定 config = new Config();
        config.useSingleServer()
                .setアドレス( "redis://127.0.0.1:6379" );
        RedissonClient の設定を変更します。
        RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter( "ipBlockList" );
        // 最初のパラメータexpectedInsertionsは挿入される要素の数を表し、2番目のパラメータfalseProbabilityは小数点で表される予想される偽陽性率を表します。
        ブルームフィルタの初期化(100000L, 0.03D)
        bloomFilter.add ( "127.0.0.1" );
        bloomFilter.add ( "192.168.1.1" );
        System.out.println (bloomFilter.contains ( " 192.168.1.1" ) ); // true  
        System.out.println (bloomFilter.contains ( " 192.168.1.2" ) ); // false  
    }
 }

Redisson が提供するブルーム フィルタ インターフェイス RBloomFilter は非常にシンプルです。

よく使用されるメソッドには、tryInit() (初期化)、add() (要素の追加)、contains() (要素が存在するかどうかの判断) などがあります。 Guava のインメモリ Bloom フィルター実装と比較して、Redisson は Redis に基づく「分散 Bloom フィルター」を提供し、分散クラスターでの Bloom フィルターの使用に対応できます。

ブルームフィルタの使用シナリオ

実際、ブルーム フィルタの使用シナリオは、百科事典の図で説明できます。

上記の図に基づいたいくつかのシナリオを以下に示します。

• ウェブサイトクローラーアプリケーションでの URL の重複排除 (ブルームフィルターに存在しない URL は、クロールされていない URL である必要があります)
• ファイアウォール アプリケーションでの IP ブラックリスト判定 (IP ブラックリストに限定されず、ブルーム フィルタは一般的なブラックリスト判定シナリオで使用でき、ブルーム フィルタに存在しない IP はホワイトリストに含まれている必要があります)
• キャッシュ侵入を回避するために使用されます（ブルームフィルタに存在しないキーは、後続のキャッシュに存在してはなりません）

ブルームフィルタのバリエーション

ブルーム フィルタにはさまざまなバリエーションがあり、主にブルーム フィルタ アルゴリズムの欠陥や欠点を解決するために使用されています。一般的なバリエーションは次のとおりです。

ここでは、Counting Bloom Filter (CBF) バリアントを選択して少し拡張します。ネイティブ ブルーム フィルタの基本的なデータ構造はビット ベクトルです。CBF はネイティブ ブルーム フィルタの基本的なデータ構造を拡張します。基礎となる配列の各要素は、4 ビット カウンターを使用して、配列の特定のインデックスに要素を追加するときに成功したマッピングの頻度を格納します。新しい要素を挿入すると、k 個のハッシュ関数を介して k 個の特定のカウンターにマッピングされ、これらのヒット カウンターの値は 1 ずつ増加します。要素を削除すると、k 個のハッシュ関数を介して k 個の特定のカウンターにマッピングされ、これらのカウンターの値は 1 ずつ減少します。 CBF を使用して要素がセット内にあるかどうかを判断する場合:

• 要素は、k 個のハッシュ関数を通じて k 個の特定のカウンターにマッピングされます。すべてのカウンターの値が 0 の場合、その要素はセット内に存在してはなりません。
• 要素はk個のハッシュ関数を通じてk個の特定のカウンターにマッピングされます。少なくとも1つのカウンターの値が0より大きい場合、その要素はセットに含まれる可能性があります。
  

概要 Bloom フィルターの基本的な機能は、「存在しない場合は存在しないはずです。存在する場合は存在しない可能性があります。」という一文で要約できます。

Bloom フィルターを使用して要素がセットに属しているかどうかを判断する場合、一定の誤判定率が発生します。つまり、ある集合に属さない要素を、その集合に属すると誤って判断する可能性があります。この誤りをFalse Positiveと呼びますが、ある集合に属する要素が、その集合に属さないと誤って判断されることはありません（False Positive、「偽陽性」に対して、ある集合に属する要素が、その集合に属さないと誤って判断されることをFalse Negative、「偽陰性」と呼びます）。 False Positive、つまりエラー率または誤判定率の導入は、ブルーム フィルタの設計においてスペース効率のバランスをとる鍵となります。

参考文献:

• ブルームフィルタ
• Guava関連のソースコード
• ブルームフィルタ - 数学

（記事終了 c-1-w ea-20210306）

この記事はWeChatの公開アカウント「Throwable」から転載したもので、以下のQRコードからフォローできます。この記事の転載についてはThrowable公式アカウントまでご連絡ください。