Redis データ型学習のための HyperLogLog の簡単な分析-Redis-php.cn

Redis データ型学習のための HyperLogLog の簡単な分析

青灯夜游

リリース： 2022-01-21 10:01:19

転載

1934 人が閲覧しました

この記事では、通常、コレクション内の一意の要素の数を数えるために使用される Redis データ型の HyperLogLog について説明します。お役に立てば幸いです。

Redis データ型学習のための HyperLogLog の簡単な分析

今日は金曜日です。あなたは楽しく釣りをしています。プロダクトマネージャーから要件文書が電子メールで送信されます。おそらく需要は次のとおりです。企業は Web サイトの毎日の訪問者 IP をカウントする必要があり、この統計は数か月から数年の範囲の長期的な動作です。

要件を読むと、これはとても簡単だと感じるでしょう。Redis のコレクションタイプを使用してこの機能を簡単に実装できます: 毎日コレクションタイプのキーを生成し、SADD を使用して毎日の訪問者 IP を保存し、 SCARD コマンドを使用すると、1 日あたりの訪問者 IP 数を簡単に取得できます。

すぐにコードの入力を終えてテストに合格し、関数がオンラインになりました。オンラインになって一定期間実行すると、Redis が配置されているサーバーが警告を発し始めることがわかります。その理由は、一部のキーのメモリ使用量が大きすぎるためです。調べてみると、これらのキーはすべて同じであることがわかりました。訪問者のIPを保存するキーを設定します。そのとき初めて、あなたは自分自身のために大きな穴を掘ったことを知り、頭を撫でました。

IP アドレスを IPv4 形式で保存するには最大 15 バイトが必要で、Web サイトには 1 日あたり最大 100 万人の訪問者がいると仮定します。これらのコレクションキーは、1 か月あたり 0.45 GB のメモリ、1 年あたり 5.4 GB のメモリを使用します。これは IPv4 形式の推定値にすぎません。IPv6 形式がより多くのメモリを占有する場合は、 SADD と SCARD の時間計算量は O(1) ですが、メモリ消費量は許容範囲外です。

あなたは、Redis の公式 Web サイトを閲覧し、Redis が製品のニーズを満たすだけでなく、メモリの占有量も少なくできるデータ型 HyperLogLog も提供していることを知りました。 [関連する推奨事項: Redis ビデオチュートリアル ]

HyperLogLog アルゴリズム

HyperLogLog は、セットのカーディナリティを計算するために特別に作成された確率的アルゴリズムです。特定のセットのおおよそのカーディナリティを計算できます。

概算のカーディナリティは、セットの実際のカーディナリティではありません。実際のカーディナリティより若干小さいか大きい場合がありますが、推定されたカーディナリティと実際のカーディナリティの間の誤差は妥当な範囲内になります。必要のない人 HyperLogLog アルゴリズムを使用すると、非常に正確な統計を取得できます。

HyperLogLog の利点は、おおよそのカーディナリティの計算に必要なメモリがセットのサイズによって変化しないことです。セットに含まれる要素の数に関係なく、HyperLogLog の計算に必要なメモリは常に一定です、そして非常に少数です。

Redis の各 HyperLogLog タイプは、ほぼ 2⁶⁴ 要素をカウントするために 12KB のメモリ空間を使用するだけでよく、アルゴリズムの標準誤差はわずか 0.81% です。

HyperLogLog タイプを使用して上記の機能を実装した場合、1 日あたり 100 万人の訪問者があったとしても、1 か月で占有するメモリは 360 KB だけです。

PFADD

PFADD コマンドは、1 つ以上の指定されたセット要素をカウントするために使用できます。

PFADD キー要素 [要素...]

指定された要素がカウントされているかどうかに応じて、PFADD コマンドは 0 または 1 を返す場合があります。

指定されたすべての要素がカウントされた場合、PFADD コマンドは 0 を返し、HyperLogLog によって計算されたおおよそのカーディナリティが変更されていないことを示します。
指定された要素内に以前にカウントされていない要素が少なくとも 1 つ存在するために、HyperLogLog によって計算されたおおよそのカーディナリティが変化した場合、PFADD コマンドは 1 を返します。

例:

redis> PFADD letters a b c -- 第一次添加
(integer) 1
redis> PFADD letters a     -- 第二次添加
(integer) 0

ログイン後にコピー

このコマンドを呼び出す際に要素を指定せずにキーのみを指定することも可能です。キーが存在する場合は何も動作しません。存在しない場合、データ構造が作成されます (1 を返します)。

PFCOUNT

PFCOUNT コマンドを使用すると、HyperLogLog によってコレクションに対して計算されたおおよそのカーディナリティを取得できます。指定されたキーが存在しない場合は、0 が返されます。

PFCOUNT key [key...]

例:

redis> PFCOUNT letters
(integer) 3

ログイン後にコピー

複数の HyperLogLog が PFCOUNT に渡される場合、PFCOUNT コマンドは最初にすべての HyperLogLog の和集合が返され、おおよそのカーディナリティが返されます。

redis> PFADD letters1 a b c
(integer) 1
redis> PFADD letters2 c d e
(integer) 1
redis> PFCOUNT letters1 letters2
(integer) 5

ログイン後にコピー

PFMERGE

PFMERGE コマンドは、複数の HyperLogLog に対して和集合計算を実行し、計算された和集合 HyperLogLog を指定されたキーに保存できます。

PFMERGE destKey sourceKey [sourceKey...]

指定されたキーがすでに存在する場合、PFMERGE コマンドは既存のキーを上書きします。

redis> PFADD letters1 a b c
(integer) 1
redis> PFADD letters2 c d e
(integer) 1
redis> PFMERGE res letters1 letters2
OK
redis> PFCOUNT res
(integer) 5

ログイン後にコピー

PFMERGE コマンドと PFCOUNT コマンドは非常に似ていることがわかります。実際、PFCOUNT コマンドは、複数の HyperLogLog のおおよそのベースを計算するときに次の操作を実行します。 #内部的に呼び出されます PFMERGE コマンドは、指定されたすべての HyperLogLog の結合を計算し、その結合を一時的な HyperLogLog に保存します。

一時 HyperLogLog に対して PFCOUNT コマンドを実行して、そのおおよそのカーディナリティを取得します。
一時的な HyperLogLog を削除します。
結果の近似基数を返します。

プログラムが複数の HyperLogLog で PFCOUNT コマンドを呼び出す必要があり、この呼び出しが複数回繰り返される可能性がある場合は、この呼び出しを対応する PFMERGE コマンド呼び出しに置き換えることを検討できます。毎回和集合を再計算するのではなく、指定された HyperLogLog に保存されるため、プログラムは不必要な和集合計算を最小限に抑えることができます。