Redis カーディナリティ統計HyperLogLog はメモリが少ないため、非常に使いやすい

Redis には、文字列、ハッシュ、リスト、セット、順序付きセットなど、一般的に使用されるデータ構造がいくつかあることは以前から知られていました。実際、Redis はその後多くの追加を行いました。そのうちの 1 つは HyperLogLog で、もう 1 つはバージョン 3.2 で追加された GEO (地理的位置) でした。

ここでHyperLogLogの構造を簡単に紹介します。

最初に使用法について話しましょう: この構造は、登録されている IP の数、毎日アクセスされる IP の数、ページのリアルタイム UV (PV は文字列)、オンライン ユーザーの数など。

ここでの用途はすべてxxxの数値であるため、このデータ構造の特徴は、数えたい数量をより正確に推定できることですが、統計の詳細な内容を知ることは不可能です。たとえば、毎日訪問される IP の数を数えることによって、その時点で訪問される IP の総数を取得できますが、これらの IP が何であるかを知る方法はありません。

もちろん、上記の内容をカウントする必要があるため、数量を把握し、すべての詳細なリストを取得できます。ただし、大規模な Web サイトの場合、毎日 100 万の IP が存在し、1 つの IP が 15 バイトを消費すると大まかに計算されるため、100 万の IP は 1500 万になります。

HyperLogLog をもう一度見てみましょう。Redis の各キーは 12K のコンテンツを占有しており、保存されているコンテンツに関係なく、理論上のストレージはおよそ 2^64 の値に近くなります。 12K さん、このデータ構造の役割はご存知でしょう。そのため内部の詳細を知ることはできない。これはカーディナリティ推定に基づいたアルゴリズムであり、比較的正確にカーディナリティを推定することしかできず、セット内の固有の要素を保存して識別するために少量の固定メモリを使用できます。また、この推定値のベースは必ずしも正確であるとは限りません。これは標準誤差が 0.81% の近似値です。

ここで記録するコンテンツが多ければ多いほど、コレクションで使用されるコンテンツとのコントラストを明確にすることが容易になります。これは、範囲内で許容される値の数に関係なく、HyperLogLog 構造がグレー表示され、 12Kのメモリを占有します。

例えば、毎日 1 億件の IP アクセスがあると仮定して、毎日の IP を記録する場合、集計を使用すると、1 日あたりのメモリ使用量は 1.5G になり、1 か月分の記録を保存すると仮定すると、45G の容量が必要になります。しかし、HyperLogLog を使用すると、1 日あたり 12,000、月あたり 360,000 になります。 IP の特定の情報を知る必要がない場合は、これらの記録をメモリ内に 1 年間保持することも、削除しないこともできます。必要に応じて、他の手段を通じてすべての IP アクセス記録も保存します。毎日の情報を保存することで、月ごとの IP の総数 (MERGE)、年間の IP の総数などを計算できます (重複を削除)。

以下は HyperLogLog コマンドの紹介です。実際、このコマンドはコレクション コマンドと似ていますが、コマンドが少なく、リストを取得できない点が異なります。また、このデータ構造では ~

PFADD

を使用するにはバージョン 2.8.9 以降が必要です。このコマンドの実行後、HyperLogLog の内部構造が更新され、実行後に HyperLogLog の内部カーディナリティ推定が発生するとフィードバックが与えられます。 , 変更があった場合は1が返され、変更がなかった場合(既に存在しているものとみなされます)は0が返されます。
このコマンドのもう 1 つの利点は、キーのみを含めることができ、値を持たないことです。これは、値のない空のキーのみが作成されることを意味します。
キーが存在する場合は何もせずに 0 を返し、キーが存在しない場合は作成して 1 を返します。

このコマンドの時間計算量はO(1)なので、お気軽に使ってください~

コマンド例:

redis> PFADD  ip:20160929  "1.1.1.1"  "2.2.2.2"  "3.3.3.3"
(integer) 1
redis> PFADD  ip:20160929 "2.2.2.2"  "4.4.4.4"  "5.5.5.5"  # 存在就只加新的
(integer) 1
redis> PFCOUNT  ip:20160929  # 元素估计数量没有变化
(integer) 5
redis> PFADD  ip:20160929 "2.2.2.2"  # 存在就不会增加
(integer) 0

実際、数が少ないときはかなり正確であることがわかりました(笑)。

PFCOUNT

実際、これは上記の研究ですでに使用されており、ここでもう一度紹介します。

コマンドが単一のキーに適用される場合、このキーのカーディナリティ推定値を返します。キーが存在しない場合は 0 が返されます。
複数のキーに適用すると、それらのキーの結合推定値を返します。これらのキーを結合するのと同様に、このコマンドを呼び出して出力します。

このコマンドが単一の値で動作する場合、時間計算量は O(1) であり、平均定数時間は非常に低くなります。N 個の値で動作する場合、時間計算量は O(N) であり、このコマンドの定数はの複雑さは低くなります。

コマンド例:

redis> PFADD  ip:20160929  "1.1.1.1"  "2.2.2.2"  "3.3.3.3"
(integer) 1
redis> PFCOUNT  ip:20160929
(integer) 3
redis> PFADD  ip:20160928  "1.1.1.1"  "4.4.4.4"  "5.5.5.5"
(integer) 1
redis> PFCOUNT  ip:20160928  ip:20160929
(integer) 5

PFMERGE

複数の HyperLogLog を 1 つの HyperLogLog にマージします。実際、これは理解しやすく、結合された推定カーディナリティも、すべての HyperLogLog 推定カーディナリティの和集合に近似します。

このコマンドの最初のパラメータはターゲット キーで、残りのパラメータはマージされる HyperLogLog です。コマンド実行時、対象のキーが存在しない場合は作成してマージします。

このコマンドの時間計算量は O(N) です。ここで、N はマージされる HyperLogLog の数です。ただし、このコマンドの定数時間の複雑さは比較的高くなります。

コマンド例:

edis> PFADD  ip:20160929  "1.1.1.1"  "2.2.2.2"  "3.3.3.3"
(integer) 1
redis> PFADD  ip:20160928  "1.1.1.1"  "4.4.4.4"  "5.5.5.5"
(integer) 1
redis> PFMERGE ip:201609   ip:20160928   ip:20160929
OK
redis> PFCOUNT  ip:201609
(integer) 5

到此HyperLogLog所有的命令就都介绍完了，没错，目前就只有这三个。其实也很简单的，知道了这个结构的用法，也就知道什么时候适合用了，对我们非常珍贵的内存还是很有帮助。