Redis:HyperLog使用と適用シーン

この文書では、redisのHyperLogLogdeコマンドの使用とその他の統計方法、および適用シーンについて説明します.最後に,HyperLogLogアルゴリズムに関する参照リンクを記録した.

概要

基数カウントの進化

一般集合またはデータ構造を使用して、HashSetまたはB+ツリー

のような処理を行う.

bitmap

確率アルゴリズム

アルゴリズム白話説明

redisでのHLLの使用

pfadd追加

pfcount獲得基数値

pfmerge複数key

をマージ

アプリケーションシーン

参照リンク

概要

Redisは2.8.9バージョンでHyperLog構造を追加した.

Redis HyperLogは基数統計を行うアルゴリズムであり、HyperLogの利点は、入力要素の数や体積が非常に大きい場合、基数を計算するのに必要な空間が常に固定され、小さいことである.

Redisでは、HyperLogLogキーごとに12 KBのメモリを消費するだけで、2^64個近くの異なる要素の基数を計算することができます.これは,基数を計算する際,要素が多ければ多いほどメモリを消費する集合とは対照的である.

ただし、HyperLogは入力要素に基づいて基数を計算するだけであり、入力要素自体は格納されないため、HyperLogは集合のように入力された各要素を返すことはできない.

以上の比較的公式な紹介と説明は、個人的に以下のようにまとめられています.

HyperLogLogはアルゴリズムであり、redis独自の

ではない.

は基数統計を行うことを目的としているため、集合ではなくメタデータを保存せず、数値ではなく数だけを記録する.

の消費空間は極めて小さく、入力の非常体積のデータ量

をサポートする.

コアは基数推定アルゴリズムであり、主に計算時のメモリの使用とデータのマージの処理として表現される.最終値に一定の誤差がある

redisのhyperlogkeyごとに12 Kのメモリを使用して、タグベース(公式ドキュメント)

を使用します.

pfaddコマンドは、12 kメモリを一度に割り当てるのではなく、基数の増加に伴ってメモリ割り当てを徐々に増加させる.pfmerge操作ではsourcekeyがマージされて12 kサイズのkeyに格納されます.これはhyperloggマージ操作の原理(2つのhyperloggマージ時に各バケツの値を個別に比較する必要がある)で理解しやすいです.

誤差は、基数推定の結果が0.81%標準エラー(standard error)を有する近似値であることを示す.許容範囲

RedisはHyperLogLogの記憶を最適化し、カウントが比較的小さい場合、その記憶空間は疎行列記憶を採用し、空間占有は小さく、カウントが徐々に大きくなり、疎行列占有空間が閾値を徐々に超えた場合に一度に稠密行列に転換し、12 kの空間

を占有する.
基数カウントの進化
一般的な集合またはデータ構造を使用して、HashSetまたはB+ツリーなどの処理を行います.
ええ、データ量が大きくなると崩れてしまいます.
bitmap

は、各要素が現れるかどうかをビット配列で表し、各要素は1ビットに対応し、必要な総メモリはn bitである.メモリ消費量を大幅に削減し、ビット操作を迅速に行うことができます.

1 1億個のデータの基数値を統計するには、約10000000/8/1024/1024≒12 Mのメモリが必要であり、メモリ消費量の削減効果が顕著である.しかし、1つのオブジェクトの基数値を統計するには12 Mが必要であり、10000のオブジェクトを統計するには120 G近くが必要であり、ビッグデータシーンでも広く使用できない.

かくりつアルゴリズム

は現在、ビッグデータシーンで基数を正確に計算する効率的なアルゴリズムが発見されていないため、絶対的な正確さを追求しない場合、確率アルゴリズムを使用することは良い解決策と言える.確率アルゴリズムはデータ集合自体を直接記憶せず,一定の確率統計法により基底数値を推定し,メモリを大幅に節約し,誤差制御を一定範囲内に保証することができる.

現在基数カウントに使用されている確率アルゴリズムは、

Linear Counting(LC):初期の基数推定アルゴリズムでは、LCは空間複雑度の面で優れていないが、実際にはLCの空間複雑度は上記の簡単なbitmap法と同じである(ただし定数項レベルの低下がある)、いずれもO(Nmax)である.

LogLog Counting(LLC)：LogLog CountingはLCよりメモリを節約し、空間複雑度はO(log 2(Nmax))のみである.

HyperLogLog Counting(HLL)：HyperLogLog CountingはLLCの最適化と改良に基づいており、同じ空間的複雑度の場合、LLCの基数推定誤差よりも小さくすることができる.

三者の進化参考文章:不思議なHyperLogアルゴリズム
アルゴリズム白話説明
一般的な説明:データセットのために8ビットのハッシュ列を生成すると仮定すると、00000111を得る確率は低く、すなわち、連続する0を大量に生成する確率は低い.連続5個の0を生成する確率は1/32であり,この列を得たとき,このデータセットの基数は32であると推定できた.
もっと深いのは数学の公式で、本文の最後の参考リンクを参考にして研究に行くことができます
ええ、もっと多くの原理と実現はここでコピーして貼り付けないで、個人もとても完全な理解がなくて、実現してもテストがなくて、だから本文の下で関連する参考の文章を記録します
redisでのHLLの使用
時間の複雑さ、戻り値、コマンドの仕方、使用例などについて詳しく説明しています.
この文書では、各コマンドの概要をまとめ、個人的なケースを示します.
pfadd追加

影響基数推定値は1を返し、そうでない場合は0を返す.keyが存在しない場合は

が作成されます.

時間複雑度O(1)

127.0.0.1:6379> pfadd m1 1 2 3 4 1 2 3 2 2 2 2
(integer) 1

pfcount取得基数値

は基数値を得るが,白話では脱重値(1,1,2,2,3)と呼ぶ挿入pfcountは3

を得る.

は、複数のkey

を一度に統計することができる

時間複雑度O(N)、Nがkeyの個数

の戻り値は、0.81%の標準エラー(standard error)を有する近似値である.

127.0.0.1:6379> pfadd m1 1 2 3 4 1 2 3 2 2 2 2
(integer) 1
127.0.0.1:6379> pfcount m1
(integer) 4

pfmerge結合複数key

複数のkeyの並列セット

をとる

コマンドはOKのみを返します.

時間複雑度O(N)

127.0.0.1:6379> pfadd m1 1 2 3 4 1 2 3 2 2 2 2
(integer) 1
127.0.0.1:6379> pfcount m1
(integer) 4
127.0.0.1:6379> pfadd m2 3 3 3 4 4 4 5 5 5 6 6 6 1
(integer) 1
127.0.0.1:6379> pfcount m2
(integer) 5
127.0.0.1:6379> pfmerge mergeDes m1 m2
OK
127.0.0.1:6379> pfcount mergeDes
(integer) 6

シーンの適用
説明:

基数は大きくなく、データ量が大きくなければ使えない.

には限界があり、基数の数しか統計できないが、具体的な内容が何なのか分からない.

はbitmapと比較して2つの特定の統計状況に属し、簡単に言えば、HyperLogの重量除去はbitmapよりずっと便利である

一般的にbitmapとhyperloglogを組み合わせて使用することができ、bitmapはどのユーザーがアクティブであるかを識別し、hyperloglogカウント

一般的な使用方法:

統計登録IP数

統計毎日アクセスIP数

統計ページリアルタイムUV数

統計オンラインユーザー数

統計ユーザが毎日異なる単語を検索する個数

リファレンスリンク

不思議なHyperLogLogアルゴリズム

Redis new data structure: the HyperLogLog

原論文ページ:HyperLogLog:the analysis of a near-optimal cardinality estimation algorithm

java HyperLogLogのgithub

を実現

基数推定アルゴリズムの概要

hyperlogjava版

を使用

参考java使用例:Probabilistic data Structures–Bloom filter and HyperLogLog for Big Data