Redis で HyperLogLog データ型を使用する方法-Redis-php.cn

Redis で HyperLogLog データ型を使用する方法

PHPz

リリース： 2023-05-29 09:29:12

転載

957 人が閲覧しました

1. HyperLogLog の原理

Redis HyperLogLog は、確率アルゴリズムである HyperLogLog アルゴリズムを使用してカーディナリティを推定します。 HyperLogLog は、一連のハッシュ関数と長さ m のビット配列を使用して、セット内の固有の要素の数を推定できます。

HyperLogLog アルゴリズムでは、各要素がハッシュされ、ハッシュ値をバイナリに変換した後、バイナリ文字列プレフィックス内の 1 の数に従って各要素がスコア付けされます。たとえば、要素のハッシュ値が 01110100011 の場合、プレフィックス内の 1 の数は 3 であるため、HyperLogLog アルゴリズムでは、この要素のスコアは 3 になります。

すべての要素のスコアを数えた後、各スコアの逆数 (1 / 2^n) を計算し、これらの逆数を加算して逆数を計算すると、カーディナリティの推定値が得られます。これが HyperLogLog です。アルゴリズムの結果。

HyperLogLog アルゴリズムは、ビット配列の長さ m のサイズをトレードオフにして、データ構造が占有するメモリと推定値 (つまり推定誤差) の精度を犠牲にして、次の間の結果を取得します。データが占めるスペースと誤差の少なさ、完璧なバランス。

つまり、HyperLogLog アルゴリズムの中心となるアイデアはハッシュ関数とビット演算に基づいており、ハッシュ値をビットストリームに変換し、先頭の 0 の数をカウントすることで、一意のハッシュ値を迅速に推定できます。大規模なデータセット内の値。 hyperloglog アルゴリズムを使用すると、非常に大規模なデータセット内の重複した Web ページを迅速に識別できます。

2. 使用手順:

Redis HyperLogLog は、コレクション内の要素数を推定するために使用できるデータ構造であり、非常に少ないメモリを使用して大量のデータを維持できます。従来の推定アルゴリズムよりも正確で、大量のデータを処理する場合に非常に高速です。

簡単な例では、HyperLogLog を使用して、Web サイトにアクセスする独立した IP の数を計算できます。具体的には、次の手順に従います。

まず、HyperLogLog を作成します。データ構造: PFADD hll:unique_ips 127.0.0.1
各アクセスの IP を unique_ips データ構造に追加します: PFADD hll:unique_ips 192.168.1.1
計算されたコレクション内の要素数の概算を取得します: PFCOUNT hll:unique_ips
Youより正確なカウントを取得するために、複数の HyperLogLog 構造 (日別または時間別など) を渡すことができます。

HyperLogLog は多くのメモリを節約できますが、これは推定アルゴリズムであり、誤差の範囲は完全に正確ではないことに注意してください。実際にそれを使ってみます。

3. ページビューを使用してリクエスト IP 重複排除を実装する例

Redis で HyperLogLog データ型を使用する方法

4. Jedis クライアントの使用

1. 依存関係の追加、導入jedis の依存関係:

<dependency>
    <groupId>redis.clients</groupId>
    <artifactId>jedis</artifactId>
    <version>3.6.0</version>
</dependency>

ログイン後にコピー

2. Jedis オブジェクトを作成します:

Jedis jedis = new Jedis("localhost");

ログイン後にコピー

3. HyperLogLog データ構造に要素を追加します:

jedis.pfadd("hll:unique_ips", "127.0.0.1");

ログイン後にコピー

4. collection おおよその値:

Long count = jedis.pfcount("hll:unique_ips");
System.out.println(count);

ログイン後にコピー

5. 複数の HyperLogLog 構造を結合することで、より正確なカウントを取得できます。 Jedis では、PFMERGE コマンドを使用して HyperLogLog データ構造をマージできます:

jedis.pfmerge("hll:unique_ips", "hll:unique_ips1", "hll:unique_ips2", "hll:unique_ips3");

ログイン後にコピー

5. Redission は依存関係を使用します

1. RedissonClient オブジェクト

Config config = new Config();
config.useSingleServer().setAddress("redis://localhost:6379");
RedissonClient redisson = Redisson.create(config);

ログイン後にコピー

を作成します

2. RHyperLogLog オブジェクトの作成

RHyperLogLog<String> uniqueIps = redisson.getHyperLogLog("hll:unique_ips");

ログイン後にコピー

3. 要素の追加

uniqueIps.add("127.0.0.1");

ログイン後にコピー

4. おおよその数量の取得

long approximateCount = uniqueIps.count();
System.out.println(approximateCount);

ログイン後にコピー

5. 複数の HyperLogLog オブジェクトの結合

RHyperLogLog<String> uniqueIps1 = redisson.getHyperLogLog("hll:unique_ips1");
RHyperLogLog<String> uniqueIps2 = redisson.getHyperLogLog("hll:unique_ips2");
uniqueIps.mergeWith(uniqueIps1, uniqueIps2);

ログイン後にコピー

6 .HyperLogLog はどのような機能とメソッドを提供しますか?

機能:

精度は低いですが、メモリの使用量はほとんどありません。
二重にカウントせずに新しい要素を挿入することをサポートします。
メモリ使用量とカウント精度を最適化するための手順を提供します。たとえば、PFADD、PFCOUNT、PFMERGE、その他の命令です。
データセット内のさまざまな要素の数、つまりセットのカーディナリティを推定できるようになります。
これらのコレクションの合計カーディナリティの近似値を取得するために、複数の HyperLogLog オブジェクトに対するマージ操作をサポートします。

HyperLogLog で一般的に使用されるメソッド:

PFADD キー要素 [要素 ...]: 1 つ以上の要素を HyperLogLog 構造に追加します。
PFCOUNT key [key ...]: 1 つ以上の HyperLogLog 構造のカーディナリティ推定値を取得します。
PFMERGE destkey sourcekey [sourcekey ...]: 1 つ以上の HyperLogLog 構造をターゲット構造にマージします。
PFSELFTEST [numtests]: HyperLogLog 評価のパフォーマンスと精度をテストします (Redis4.0 バージョンのみ)

ただし、 HyperLogLog は大量のメモリを節約できますが、依然として推定アルゴリズムであり、誤差の範囲は完全に正確ではなく、ある程度の計算コストがかかります。実際のアプリケーションに応じて、要素数の推定に HyperLogLog または他のデータ構造を使用するかどうかを検討する必要があります。

7. 使用シナリオの概要:

HyperLogLog を使用する Redis の主な機能は、大規模なデータストリーム (ビュー、IP、都市) の場合に重複排除カウントを実行することです。

具体的には、Redis HyperLogLog が重複排除とカウントに使用されるいくつかのシナリオを次に示します。

ページビューのカウント - Web アプリケーションでは、HyperLogLog を使用して、各ページのユニーク訪問者数をカウントできます。 HyperLogLog テクノロジーを使用して、さまざまな期間にわたるこのページへの平均訪問数を計算します。
HyperLogLog は、ビッグデータコレクション内のユーザー数を分析する際に非常に役立ちます。確率ベースのデータ構造は、一意のユーザー ID などのデータセットを扱う場合に特に効果的です。 HyperLogLog は、ハッシュ化後に限られた数のハッシュ値のみを保存し、データセットのサイズを推定できます。
広告クリック数のカウント - Web サイトまたはアプリケーションの広告分析では、HyperLogLog を使用して有効クリック数、つまり個別のクリック数または一意のクリック数をキャプチャできます。

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