Redis のブルーム フィルターと PHP の使用方法

Redis は、キャッシュ、メッセージ キュー、分散ロックなどのシナリオで広く使用されているオープン ソースのメモリ内データベースです。中でもブルームフィルターは、セット内に要素が存在するかどうかを判定するために使用できる効率的なデータ構造であり、Redis で広く使用されています。この記事では、Redis でのブルーム フィルターの実装原理と使用法、および PHP でのブルーム フィルターのサポートについて紹介します。

1. ブルーム フィルターの実装原理

ブルーム フィルターは、複数のハッシュ関数とバイナリ ベクトル集合の判定を使用して実装される、非常にシンプルかつ効率的なデータ構造です。要素がセットに追加されると、その要素は複数のハッシュ関数に渡され、それぞれが一意のハッシュ値 (通常は数値) を生成し、その後バイナリに変換されます。ベクトル内の対応する位置は 1 に設定されます。要素がセット内に存在するかどうかを判断する必要がある場合、要素をこれらのハッシュ関数に渡し、複数のハッシュ値を生成し、これらのハッシュ値に対応するバイナリ ベクトルの位置がすべて 1 であるかどうかをクエリします。がすべて 1 の場合、この要素はセットに含まれる可能性があると考えられます。そうでない場合は、この要素はセットに確実に含まれていないと判断できます。なお、ハッシュ関数の特性上、ブルームフィルタには一定の偽陽性率が発生しますが、この偽陽性率はハッシュ関数の数とバイナリベクトルのサイズを設定することで調整できます。

2. Redis でブルーム フィルターを使用する方法

Redis でブルーム フィルターを実装するコマンドは、それぞれ BF.ADD、BF.EXISTS、BF.MADD、BF.MEXISTS です。ブルーム フィルタに要素を追加し、ブルーム フィルタに単一の要素が存在するかどうかを判断し、ブルーム フィルタに複数の要素を追加し、ブルーム フィルタに複数の要素が存在するかどうかを判断します。これを使用する場合は、まず BF.RESERVE コマンドで作成できるブルーム フィルターを作成する必要があります。ブルーム フィルターの名前、ハッシュ関数の数、バイナリ ベクトルのサイズ、および偽陽性率。たとえば、ハッシュ関数の数が 10、バイナリ ベクトルのサイズが 10000、偽陽性率が 1% である test という名前のブルーム フィルターを作成するには、次のコマンドを使用できます。

BF.RESERVE test 10 10000 0.01

Thenこのブルーム フィルターに要素を追加したり、要素がコレクションに存在するかどうかを判断したりできます。具体的な使用法は次のとおりです:

1. ブルーム フィルターに要素を追加します

BF.ADD test element1

このコマンドは、要素 element1 を test という名前のブルーム フィルターに追加します。

2. ブルーム フィルターに単一の要素が存在するかどうかを確認する

BF.EXISTS test element1

このコマンドは、test という名前のブルーム フィルターに要素 element1 が存在するかどうかを確認します。1 が返された場合は、存在する可能性があることを意味します。 0 が返された場合は、間違いなく存在しないことを意味します。

3. ブルーム フィルターに複数の要素を追加する

BF.MADD test element1 element2 element3

このコマンドは、要素 element1、element2、element3 を test という名前のブルーム フィルターに追加します。

4. ブルーム フィルターに複数の要素が存在するかどうかを確認する

BF.MEXISTS test element1 element2 element3

このコマンドは、返された結果のいずれかが、 test という名前のブルーム フィルターに要素 element1、element2、および element3 が存在するかどうかを確認します。が 0 の場合、少なくとも 1 つの要素がブルーム フィルターに存在してはいけないことを意味します。

3. PHP でのブルーム フィルターのサポート

PHP でのブルーム フィルターのサポートは、redis 拡張機能を通じて実装されています。使用する前に、redis 拡張機能がインストールされていることを確認する必要があります。具体的な使用方法については、次のコード例を参照してください。

$redis = new Redis();
$redis->connect('127.0.0.1', 6379);
// 创建布隆过滤器，哈希函数个数为10，二进制向量大小为10000，误判率为1%
$redis->rawCommand('BF.RESERVE', 'test', 10, 10000, 0.01);
// 将元素element1加入到布隆过滤器中
$redis->rawCommand('BF.ADD', 'test', 'element1');
// 判断元素element1是否存在于布隆过滤器中
$result = $redis->rawCommand('BF.EXISTS', 'test', 'element1');
if ($result) {
    echo 'element1可能存在于布隆过滤器中';
} else {
    echo 'element1一定不存在于布隆过滤器中';
}
// 将元素element2和element3加入到布隆过滤器中
$redis->rawCommand('BF.MADD', 'test', 'element2', 'element3');
// 判断元素element1、element2和element3是否存在于布隆过滤器中
$result = $redis->rawCommand('BF.MEXISTS', 'test', 'element1', 'element2', 'element3');
if (in_array(0, $result)) {
    echo '其中至少一个元素一定不存在于布隆过滤器中';
} else {
    echo '所有元素可能存在于布隆过滤器中';
}

上記の PHP コード例を通じて、Redis でブルーム フィルターを使用できます。

概要:

実際の応用シーンでは、ブルームフィルターは高速な検索と効率的な保存という特徴があるため、キャッシュ侵入防止やスパム対策などの分野で広く使われています。 Redis では、BF.ADD、BF.EXISTS、BF.MADD、BF.MEXISTS コマンドのサポートにより、ブルーム フィルター関連の操作を簡単に実装できます。もちろん、PHP に Redis 拡張機能をインストールすることで、ブルーム フィルターの使用を簡単に実装することもできます。

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