HyperLogLog を使用して Redis を実装する方法

1. 概要

Redis は、カーディナリティ統計のためにバージョン 2.8.9 で HyperLogLog データ構造を追加しました。利点は、入力要素の数が非常に多い場合、カーディナリティの計算に必要なスペースが比較的少なくて済むことです。小さく、一般に比較的一定です。

Redis では、ほぼ 2^64 の異なる要素のカーディナリティを計算するために、各 HyperLogLog キーに必要なメモリは 12 KB だけです。これは、要素が多いコレクションほど多くのメモリを消費するカーディナリティの計算とは対照的です。ただし、HyperLogLog は入力要素に基づいてカーディナリティを計算するだけで、入力要素自体は保存しないため、コレクションのように入力の個々の要素を返すことはできません。

2. カーディナリティとは何ですか?

たとえば、データ セットが {1, 3, 5, 7, 5, 7, 8} の場合、このデータのカーディナリティ セットはセットは {1, 3, 5 ,7, 8}、カーディナリティ (非繰り返し要素) は 5 です。カーディナリティの推定とは、許容誤差範囲内でカーディナリティを迅速に計算することです。

3. コマンド

現在、HyperLogLog でサポートされているコマンドは PFADD、PFCOUNT、および PFMERGE の 3 つだけです。まずは一つずつ紹介していきましょう。

3.1 PFADD

利用可能な最も古いバージョン: 2.8.9。時間計算量: O(1)。

PFADD コマンドは、要素 (複数の要素を指定可能) を HyperLogLog データ構造に追加し、最初のパラメーター キーで指定されたキーに格納できます。カーディナリティ推定 (評価された要素の数) が変化した場合は 1 を返し、それ以外の場合は 0 を返します。つまり、コマンドの実行後にカーディナリティ推定が変化したかどうかを確認します。指定されたキーが存在しない場合は、空の HyperLogLog データ構造 (つまり、指定された文字列長とエンコーディングを持つ Redis 文字列) が作成されます。要素パラメータを指定せずにキーのみを指定してコマンドを呼び出すこともできます。キーが存在する場合は何もせず 0 を返し、キーが存在しない場合は新しい HyperLogLog データ ノードが作成されて 1 を返します。基本的に、要素を保存せずに新しい HyperLogLog データ構造を生成するだけです。

(1) 構文形式：

PFADD key element [element ...]

(2) 戻り値：

整数型、要素が 1 つ以上追加された場合は 1 が返され、それ以外の場合は 0 が返されます。 。

(3) 例:

127.0.0.1:6379> PFADD hll a b c d e f g
(integer) 1
127.0.0.1:6379> pfcount hll
(integer) 7

3.2 PFCOUNT

利用可能な最も古いバージョン: 2.8.9。時間計算量: O(1)。複数の比較的大きなキーの場合、時間計算量は O(N) です。

PFCOUNT コマンドを使用して、HyperLogLog の推定カーディナリティ値 (つまり、要素の数) を取得します。このコマンドは、キーが存在しない場合は 0 を返し、それ以外の場合はキーのカーディナリティの推定値を返します。複数のキーの場合、複数の HyperLogLog を一時的な HyperLogLog にマージすることで計算された、複数の HyperLogLog の和集合のカーディナリティ推定値が返されます。 HyperLogLog は、最小限の一定量のメモリを使用して、コレクションの一意の要素の数をカウントできます。各 HyperLogLog は、12K とキー自体の数バイトのみを使用します。

(1) 構文形式:

PFCOUNT key [key ...]

(2) 戻り値:

Integer、指定された HyperLogLog のカーディナリティ推定値を返します。複数の HyperLogLog がある場合、和集合はカーディナリティの推定値。

(3) 例:

127.0.0.1:6379> PFADD hll foo bar zap
(integer) 1
127.0.0.1:6379> PFADD hll zap zap zap
(integer) 0
127.0.0.1:6379> PFADD hll foo bar
(integer) 0
127.0.0.1:6379> PFCOUNT hll
(integer) 3
127.0.0.1:6379> PFADD some-other-hll 1 2 3
(integer) 1
127.0.0.1:6379> PFCOUNT some-other-hll
(integer) 3
127.0.0.1:6379> PFCOUNT hll some-other-hll
(integer) 6

(4) 制限事項:

HyperLogLog によって返される結果は正確ではなく、エラー率は約 0.81% です。

このコマンドを使用すると、HyperLogLog が変更され、最後に計算されたベースを保存するために 8 バイトが使用されます。したがって、技術的に言えば、PFCOUNT は書き込みコマンドです。

(5) パフォーマンスの問題

集中的な HyperLogLog の処理には理論的には時間がかかりますが、キーが 1 つだけ指定されている場合でも PFCOUNT コマンドは高いパフォーマンスを発揮します。これは、PFCOUNT が最後の計算の基数をキャッシュし、ほとんどの場合 PFADD コマンドがレジスタを更新しないため、この基数が常に変更されるわけではないためです。したがって、1 秒あたり数百のリクエストの効果を達成できます。

PFCOUNT コマンドを使用して複数のキーを処理すると、HyperLogLog がマージされます。この手順は非常に時間がかかります。さらに重要なのは、共用体の計算されたカーディナリティをキャッシュできないことです。複数のキーを使用する場合、PFCOUNT の実行には時間がかかることがあります (通常はミリ秒程度)。そのため、過度に使用することはお勧めできません。

このコマンドの単一キー実行セマンティクスと複数キー実行セマンティクスは異なり、パフォーマンスも異なることに注意してください。マルチキー実行セマンティクスを過度に使用することはお勧めできません。

3.3 PFMERGE

利用可能な最も古いバージョン: 2.8.9。時間計算量: O(N)、N はマージされる HyperLogLog の数です。

PFMERGE コマンドを使用して、複数の HyperLogLog を 1 つの HyperLogLog にマージできます。マージされた HyperLogLog のカーディナリティの推定値は、指定されたすべての HyperLogLog の結合を取得することによって計算されます。計算結果は指定したキーに保存されます。

構文形式:

PFMERGE destkey sourcekey [sourcekey ...]

戻り値:

OK を返します。

例:

127.0.0.1:6379> PFADD hll1 foo bar zap a
(integer) 1
127.0.0.1:6379> PFADD hll2 a b c foo
(integer) 1
127.0.0.1:6379> PFMERGE hll3 hll1 hll2
OK
127.0.0.1:6379> PFCOUNT hll3
(integer) 6

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