コミュニティ 学ぶ ツールライブラリ レジャー
検索
日本語
ホームページ > データベース > Redis > 本文

Redis のブルーム フィルターの詳細な分析

青灯夜游
リリース： 2022-01-07 09:35:08
転載
2849 人が閲覧しました

キャッシュの侵入を回避するにはどうすればよいですか?次の記事では、キャッシュの侵入を回避するための Redis の強力なツールである Bloom Filter (ブルーム フィルター) について説明します。

Redis のブルーム フィルターの詳細な分析

概要

ブルーム フィルター (ブルーム フィルター) は、1970 年に Burton Howard Bloom によって発明され、1970 年に提案されたデータ構造です。 。これは実際には長いバイナリ ベクトルと一連のランダム マッピング関数です。 [関連する推奨事項: Redis ビデオ チュートリアル ]

ブルーム フィルターを使用すると、要素がコレクション内にあるかどうかを効率的に取得できます。このアルゴリズムの利点は、スペース効率とクエリ時間が通常のアルゴリズムよりもはるかに優れていることですが、欠点は、一定の誤認識率があり、削除が難しいことです (通常はサポートされておらず、追加の実装が必要です)。

偽陽性率とは、その要素がセットに確実に含まれていないと判断できる、要素がセットに含まれている可能性があると判断できるが、判断できないことを意味します。要素がセット内に存在する必要があることを示します。

ブルーム フィルターが効率的である理由は、要素がセットに確実に含まれていないこと、または要素がセットに含まれている可能性があることを確認できる確率的なデータ構造であるためです。このようなことが可能な理由は、一定の誤認識率があり、その要素がセット内に存在することを 100% 確信することは不可能であるためです。

質問の紹介

日常の業務では、要素がセット内にあるかどうかを判断する必要がよくあります。たとえば、次のシナリオは次のとおりです。

  • IP ブラックリスト データベースがある場合、指定された IP がブラックリストに含まれているかどうかを確認します。
  • 電子メールを受信するときに、電子メール アドレスがスパムかどうかを判断するにはどうすればよいですか?
  • ワープロ ソフトウェアで、英単語のスペルが正しいかどうかを確認しますか?

この種の問題に遭遇すると、通常、私たちの直感は、セットのようなデータ構造を使用して実装する必要があると判断します。たとえば、最初に IP ブラックリスト データベース内のすべての IP をセットに保存し、次に指定した IP がセット内に存在するかどうかを確認します。存在する場合は、その IP がブラックリストにヒットすることを意味します。

コードを使用して、IP ブラックリスト ライブラリの保存とチェックをシミュレートします。 

public class IPBlackList {

	public static void main(String[] args) {
		Set<String> set = new HashSet<>();
		set.add("192.168.1.1");
		set.add("192.168.1.2");
		set.add("192.168.1.4");
		System.out.println(set.contains("192.168.1.1"));
		System.out.println(set.contains("192.168.1.2"));
		System.out.println(set.contains("192.168.1.3"));
		System.out.println(set.contains("192.168.1.4"));
	}
}
ログイン後にコピー

コレクションの内部は通常、ハッシュ テーブルを使用して実装されます。利点は、クエリが非常に効率的であることですが、欠点は、より多くのストレージ領域を消費することです。

一般に、データの量が比較的少ない場合、ストレージとしてコレクションを使用します。スペースを時間と交換すると、占有スペースを減らしながらクエリの効率を向上させることができます。

ただし、保存するデータ量が比較的多い場合には、大量のスペースを消費することが問題になります。これらのデータは通常、クエリ効率を高めるためにプロセス メモリに保存されるためです。マシンのメモリは通常限られているため、できるだけ効率的に使用する必要があります。

一方、ハッシュ テーブルは、スペースと効率の点でバランスを取る必要があります。同じ数の要素を格納する場合、ハッシュ テーブルの容量が小さい場合、競合の可能性が高くなり、競合の解決に多くの時間がかかるため、パフォーマンスに影響します。

ブルーム フィルター (ブルーム フィルター) の登場により、この問題は非常にうまく解決できます。一方で、より少ないメモリでデータを保存できる一方で、非常に効率的なクエリ パフォーマンスを実現できます。

基本原則

  • まず、バイナリ ベクトルを作成し、すべてのビットを 0 に設定します

  • 次に、K 個のハッシュ関数を選択します要素を K 回ハッシュし、ベクトルのビット インデックスを計算するために使用されます。

要素の追加

要素をセットに追加するとき、K 個のハッシュ関数が要素にそれぞれ適用され、添え字として K 個の値が生成されます。そして、ベクトルの対応するビットを 1 に設定します。

要素のチェック

要素がセット内に存在するかどうかを確認したい場合は、同じハッシュ法を使用して K 個の添字を生成し、対応するビットがセット内に存在するかどうかを確認します。ベクトルはすべて 1 です。

すべてが 1 の場合、その要素はセット内にある可能性が高く、それ以外の場合 (1 つ以上のビットが 0 である限り) 要素は間違いなくセット内にありません。

デモ

  • 以下に示すように、15 ビットの容量と 2 つのハッシュ関数を使用するブルーム フィルターがあると仮定します。

|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |0|||||||||||||||||

  • 文字列 a を追加し、2 回ハッシュして、次のマークを取得します。 4 と 10、4 と 10 に対応するビットを 0 から 1 までマークします。

|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1|||||1|||||||||

  • 別の文字列 b を追加し、2 回ハッシュ化します。 添え字が取得されます11 として、11 に対応するビットは 0 から 1 でマークされます。

|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1||||||1|1|||||||

  • 別の文字列 c を追加し、2 回ハッシュして添字 11 と 12 を取得し、対応するビットを 0 から 1 までマークします。

|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1|||||1|1|1||||||

  • 最後に文字列 sam、2 添え字 0 を追加します。および 7 は 2 番目のハッシュを通じて取得され、対応するビットには 0 から 1 のマークが付けられます。

|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |1||||1|||1|||1|1|1|||||||

上記では、4 つの文字列を追加しました。各文字列は 2 回追加されました。ハッシュでは、対応する 2 ビットは 1 としてマークされ、最終的には 8 ビットではなく 6 ビットが 1 としてマークされます。

これは、異なる要素をハッシュすることによって取得された位置が重複する可能性があることを示しています。要素が多ければ多いほど、重複する可能性が高くなります。 2 つの要素が重なった位置にある場合、どちらかの要素がセットに含まれなければならないと判断できません。

要素がセット内に存在するかどうかを確認したい場合は、同じ方法で要素を 2 回ハッシュし、得られた 2 つの添字のブルーム フィルター内の対応するビットを検索するだけです。対応する 2 ビットがすべて 1 ではない場合、その要素はセット内に存在しません。対応する 2 ビットがすべて 1 の場合、その要素がセット内に存在するか、存在しない可能性があることを意味します。

たとえば、文字列 b がセット内に存在し、ハッシュ化によって得られた 2 つの添字が両方とも 11 であるかどうかを確認します。 11 に対応するビットが 1 であることを確認します。ただし、これは b がセット内になければならないという意味ではありません。これは、文字列 c のハッシュされた添え字にも 11 が含まれているためです。文字列 c がセット内に存在する可能性がありますが、b は存在しません。これにより、誤認が発生します。偽とも呼ばれます。ポジティブ。

文字列 foo をもう一度確認します。ハッシュによって取得された添え字はそれぞれ 8 と 13 で、対応するビットはすべて 0 です。したがって、文字列 foo はセットに含まれていません。

数学的原理

ブルーム フィルターの背後にある数学的原理は次のとおりです。

2 つの完全に乱数が衝突する確率は非常に小さいため、次のような用途に使用できます。非常に小さい 誤認識率が低い条件下では、少ないスペースに大量の情報が格納されます。

誤認識率

誤認識率(FPP、偽陽性確率)は以下のように計算されます。

ブルーム フィルターのサイズが m ビット、n 要素が保存され、ハッシュ関数の k 倍が使用されて計算されると仮定します。ストレージの場所。

  • 要素を 1 つ追加すると、任意のビットが 1 になる確率は 1/m、任意のビットが 0 になる確率は 1-1/m# になります。 ##;
    • 1 つの要素を追加して k 個のハッシュを実行すると、任意のビットが 0 になる確率は
  • (1-1/m)^k となり、任意のビットが 1 になる確率は次のようになります。は 1-(1-1/m)^k;
    • n 個の要素を追加すると、任意のビットが 0 になる確率は
  • (1-1 /m)^ になります。 kn、任意のビットが 1 である確率は 1-(1-1/m)^kn;
    • 新しい要素が追加された場合、すでにブルーム フィルターで
  • n 要素があり、任意のビットがすでに 1 である確率は上記と同じで、確率は 1-(1-1/m)^kn です。したがって、すべての k ビットが 1 である確率は (1-(1-1/m)^kn)^k となり、これが新しく挿入された要素の誤認識率になります。

n の値が比較的大きい場合、$(1-(1-1/m)^{kn})^k$ は # にほぼ等しくなります。 ##$ (1-e^{-kn/m})^k$ブルーム フィルター サイズ

m

が 16 ビット、k が 8 であると仮定します。 、記憶要素 n が 1 の場合、誤認 (偽陽性) の確率は 10,000 分の 5 (5/10000) です。 この時点では、

m/n=16

、実際、これは 1 つの要素が格納するために 16 ビットのスペースを使用することを意味します。 したがって、

k

が同じ場合、m/n は 16/1、32/2、64/4 などでも同じ誤認識率になります。 。 ウェブサイト

ブルーム フィルター - 数学

はブルーム フィルターの誤認識率テーブルを提供します。これにより、さまざまな m、n# # を簡単にチェックして対処できます。 #, k 特定の値における誤認識率。 誤認識率を解決する

誤認識率を解決する一般的な方法には次のようなものがあります。

ホワイトリスト

  • # バックトラック確認

    • ホワイトリスト

誤認識率を解決する一般的な方法は、データを誤認した可能性のある人を保存するためのより小さなホワイトリストを確立することです。 。

スパム フィルタリングを例に挙げます。電子メールの受信時にスパムをフィルターで除外するスパム ライブラリがあるとします。

現時点では、まずこのスパム ライブラリをブルーム フィルターに保存し、電子メールを受信するときに、まずブルーム フィルターを通じてほとんどの通常の電子メールを効率的に除外できます。

ヒットした (おそらく) スパム メールの数が少ない場合、その一部は通常のメールである可能性があります。

再创建一个白名单库，当在布隆过滤器中判断可能为垃圾邮件时，通过查询白名单来确认是否为正常邮件。

对于没在白名单中的邮件，默认会被移动到垃圾箱。通过人工识别的方式，当发现垃圾箱中存在正常邮件的时候，将其移入白名单。

回源确认

很多时候，使用布隆过滤器是为了低成本，高效率的拦截掉大量数据不在集合中的场景。例如

  • Google Bigtable，Apache HBase以及Apache Cassandra和PostgreSQL 使用 Bloom 过滤器来减少对不存在的行或列的磁盘查找。避免进行昂贵的磁盘查找，可大大提高数据库查询操作的性能。
  • 在谷歌浏览器用于使用布隆过滤器来识别恶意URL的网页浏览器。首先会针对本地 Bloom 过滤器检查所有 URL，只有在 Bloom 过滤器返回肯定结果的情况下，才对执行的 URL 进行全面检查（如果该结果也返回肯定结果，则用户会发出警告）。
  • 拦截掉大量非IP黑名单请求，对于少量可能在黑名单中的IP，再查询一次黑名单库。

这是布隆过滤器非常典型的应用场景，先过滤掉大部分请求，然后只处理少量不明确的请求。

这个方法，和白名单库的区别是，不需要再另外建立一套库来处理，而是使用本来就已经存在的数据和逻辑。

例如 Google Bigtable 查询数据行本来就是需要查的，只不过使用布隆过滤器拦截掉了大部分不必要的请求。而 IP 是否为黑名单也是需要查询的，同样是先使用布隆过滤器来拦截掉大部分IP。

而上面垃圾邮件的处理，对于可能为垃圾邮件的情况，不是通过完整的垃圾邮件库再查询一次进行确认，而是用增加白名单来进行判断的方式。因为通常来说，白名单库会更小，便于缓存。

这里所说的回源，实际上是对可能被误识别的请求，最后要回到数据源头或逻辑确认一次。

Guava中的布隆容器的实现

Guava 中就提供了一种 Bloom Filter 的实现。

guava包引入

要使用 Bloom Filter，需要引入 guava 包

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>23.0</version>
</dependency>
ログイン後にコピー

误判率测试

下面对布隆容器的误判率进行测试，分2步

  • 往过滤器中放一百万个数，然后去验证这一百万个数是否能通过过滤器

  • 另外找一万个数，去检验漏网之鱼的数量

/**
 * 测试布隆过滤器(可用于redis缓存穿透)
 * 
 * @author 敖丙
 */
public class TestBloomFilter {

    private static int total = 1000000;
    private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total);
//    private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total, 0.001);

    public static void main(String[] args) {
        // 初始化1000000条数据到过滤器中
        for (int i = 0; i < total; i++) {
            bf.put(i);
        }

        // 匹配已在过滤器中的值，是否有匹配不上的
        for (int i = 0; i < total; i++) {
            if (!bf.mightContain(i)) {
                System.out.println("有坏人逃脱了~~~");
            }
        }

        // 匹配不在过滤器中的10000个值，有多少匹配出来
        int count = 0;
        for (int i = total; i < total + 10000; i++) {
            if (bf.mightContain(i)) {
                count++;
            }
        }
        System.out.println("误伤的数量：" + count);
    }

}
ログイン後にコピー

运行结果

误伤的数量：320
ログイン後にコピー

运行结果表示，遍历这一百万个在过滤器中的数时，都被识别出来了。一万个不在过滤器中的数，误伤了320个，错误率是0.03左右。

Bloom Filter 源码分析

public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions) {
        return create(funnel, (long) expectedInsertions);
    }  

    public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
        return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
    }

    public static <T> BloomFilter<T> create(
          Funnel<? super T> funnel, long expectedInsertions, double fpp) {
        return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);
    }

    static <T> BloomFilter<T> create(
      Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
     ......
    }
ログイン後にコピー

Bloom Filter 一共四个 create 方法，不过最终都是走向第4个。看一下每个参数的含义

  • funnel：数据类型(一般是调用Funnels工具类中的)

  • expectedInsertions：期望插入的值的个数

  • fpp： 错误率(默认值为0.03)

  • strategy： 哈希算法 Bloom Filter的应用

更多编程相关知识，请访问：编程视频！！

以上がRedis のブルーム フィルターの詳細な分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

関連ラベル：
redis ブルームフィルター
ソース：juejin.cn
前の記事：Redis の特殊なデータ型についての深い理解: カーディナリティ統計、ビットマップ、地理的位置 次の記事：Redis における AOF の潜在的な障害点について話しましょう (概要)
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
最新の問題
Symfony Redis は、env ファイルで定義されたホスト (デフォルトは localhost) に接続できません キャッシュメカニズムとして Redis を使用した新しい Symfony セットアップがあります。デフォルトのローカルホストではなく、特定のホストに接続したいと考えています。運用環...
から 2024-04-06 10:53:02
0
1
375
関連トピック
詳細>
人気のおすすめ
人気のチュートリアル
詳細>
関連するチュートリアル
人気のおすすめ
最新のコース
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート