ブルームフィルターとは何ですか? Redis で使用するにはどうすればよいですか?

ブルーム フィルターは魔法のようなデータ構造です。この記事では、ブルーム フィルターについて深く理解し、Redis でブルーム フィルターを使用する方法を紹介します。

「ブルーム フィルター」とは

ブルーム フィルターは魔法のデータ構造であり、ブルーム フィルターを使用して、要素はコレクション 内にあります。非常に一般的に使用される関数は、重複を削除するです。クローラーに共通の要件: ターゲット Web サイトの URL は何千もあり、クローラーが特定の URL を優先したかどうかを判断するにはどうすればよいですか?簡単に言うと、クローラーは URL を収集するたびに、その URL をデータベースに保存し、新しい URL が来るたびにデータベースにアクセスして、以前にアクセスされたことがあるかどうかをクエリします。 [関連する推奨事項: Redis ビデオ チュートリアル ]

select id from table where url = 'https://jaychen.cc'

しかし、クローラーがクロールする URL が増えるにつれて、各リクエストの前にデータベースに 1 回アクセスする必要があり、この種の文字列の SQL クエリの効率が低下します。高くありません。データベースに加えて、Redis のセット構造を使用することでもこの要件を満たすことができ、そのパフォーマンスはデータベースよりも優れています。しかし、Redis にはメモリを大量に消費するという問題もあります。このとき、ブルーム フィルターは非常に水平に表示されます。この質問に答えましょう。

データベースや Redis と比較して、ブルーム フィルターを使用すると、パフォーマンスとメモリ使用量の問題を効果的に回避できます。

ブルーム フィルターは本質的に ビット配列 です。ビット配列とは、配列の各要素が 1 ビットのみを占有することを意味します。各要素は 0 または 1 のみです。このように、10000 要素のビット配列を適用する場合、必要なスペースは 10000 / 8 = 1250 B だけです。ビット配列に加えて、ブルーム フィルターには K 個のハッシュ関数もあります。ブルーム フィルターに要素が追加されると、次の操作が実行されます。

• K 個のハッシュ関数を使用して要素値を K 回計算し、K 個のハッシュ値を取得します。
• 取得したハッシュ値に従って、ビット配列内の対応する添え字の値を 1 に設定します。

たとえば、ブルーム フィルターに 3 つのハッシュ関数、f1、f2、f3 とビット配列 arr があるとします。次に、ブルーム フィルターに https://jaychen.cc を挿入する必要があります。

• 値に対して 3 つのハッシュ計算を実行して、3 つの値 n1、n2、n3 を取得します。 。
• ビット配列の 3 つの要素 arr[n1]、arr[n2]、arr[3] を 1 に設定します。

値がブルームフィルターに含まれているかどうかを判定したい場合は、要素に対して再度ハッシュ計算を実行し、値を取得した後、ビット配列の各要素が 1 であるかどうかを判定します。値がすべて 1 の場合は、その値がブルーム フィルターに含まれていることを意味し、1 以外の値がある場合は、その要素がブルーム フィルターに含まれていないことを意味します。

文章が理解できない場合は、以下のソウルペインターの絵の説明をご覧ください。

上記の説明では、必ず問題が発生します。より多くの要素が挿入されると、ビット配列内のより多くの位置が 1 に設定されます。要素がブルーム フィルターに含まれていない場合、ハッシュ計算の後、取得された値がクエリされます。おそらくこれらの場所も 1 に設定されています。このようなブルー​​ムフィルタに存在しないオブジェクトも、ブルームフィルタに含まれると誤判定される可能性がある。ただし、ブルーム フィルターが要素がブルーム フィルター内にないと判断した場合、この値はブルーム フィルター内にあってはなりません。簡単に言うと、

• ブルームフィルターが特定の要素が存在すると言っている場合、それは誤って判断される可能性があります。
• ブルーム フィルターは、要素が存在しないと判断するため、要素は存在しないはずです。

このブルームフィルタの欠陥は、上記のクローラの要件に組み込まれており、未訪問のURLでも訪問済みと誤判定される可能性がありますが、訪問済みのURLであれば、必ず訪問済みと判断されます。誤って訪問していないと判断されないようにする必要があります。

Redis のブルーム フィルター

redis はバージョン 4.0 でモジュール機能を追加しました。ブルーム フィルターはモジュールの形式で Redis に追加できます。 4.0 以降では、module をロードすることで Redis でブルーム フィルターを使用できます。しかし、これは最も簡単な方法ではなく、Docker を使用して Redis でブルーム フィルターを直接体験することもできます。

> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
> docker exec -it bloomfilter redis-cli

redis ブルーム フィルターには主に 2 つのコマンドがあります:

• bf.add ブルーム フィルターに要素を追加します: bf. add urls https:/ /ジェイチェン.cc。
• bf.exists 要素がフィルター内にあるかどうかを判断します: bf.exists urls https://jaychen.cc。

上記の通り、Bloom フィルターには誤判定が存在しますが、ブルーム フィルターの精度を決定する redis の値は

の 2 つです。

• error_rate：允许布隆过滤器的错误率，这个值越低过滤器的位数组的大小越大，占用空间也就越大。
• initial_size：布隆过滤器可以储存的元素个数，当实际存储的元素个数超过这个值之后，过滤器的准确率会下降。

redis 中有一个命令可以来设置这两个值：

bf.reserve urls 0.01 100

三个参数的含义：

• 第一个值是过滤器的名字。
• 第二个值为 error_rate 的值。
• 第三个值为 initial_size 的值。

使用这个命令要注意一点：执行这个命令之前过滤器的名字应该不存在，如果执行之前就存在会报错：(error) ERR item exists

更多编程相关知识，请访问：编程入门！！

以上がブルームフィルターとは何ですか? Redis で使用するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。