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 も提供していることを知りました。

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

このコマンドを呼び出す際に要素を指定せずにキーのみを指定することも可能です。キーが存在する場合は何も動作しません。 If 存在しない場合は、データ構造が作成されます (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 に保存されるため、プログラムは不必要な和集合計算を最小限に抑えることができます。

ビジネス シナリオ

HyperLogLog の機能は、カウント (月次、年次統計)、重複排除 (スパム SMS 検出)、およびその他のシナリオに非常に適しています。

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