HyperLogLog Implementation in Redis, pt.4

Redis: HyperLogLog の実装について その4

 

その他のトピック。

 

要素の追加

追加する要素のハッシュを求め、インデックスと base-2 rank を求める。
各インデックスごとにより大きい値をレジスタに保存するだけ。

 

データのマージ

$2^{14}$ 個の全てのレジスタを走査し、各位置に対して値の大きいほうを保持する。
非常に高速なマージ処理も HyperLogLog の特長である。

 

dense 表現について

dense 表現では、sparse 表現と異なり、全部のインデックスの値が配列的に保持されている。

Redis では以下のような構造のバイト配列を定義することで、メモリ使用量を圧縮している。
(各レジスタの値は 0〜50 の範囲内であるため、それぞれ 6 ビットで表現可能)

 * +--------+--------+--------+------//
 * |11000000|22221111|33333322|55444444
 * +--------+--------+--------+------//

sparse から dense へ変換が行われるタイミングは以下。

• PFADD
  • 追加する要素の base-2 rank が 33 以上だった場合 (sparse では表現不可)
  • sparse 表現の使用サイズが サーバ変数 server.hll_sparse_max_bytes を超えた場合
    (デフォルトは 3000)

• PFMERGE: マージ実行後は必ず dense 表現になる
• PFDEBUG TODENSE key: デバッグ用のコマンド

 

 

Related Posts

• mog project: HyperLogLog Implementation in Redis, pt.1
• mog project: HyperLogLog Implementation in Redis, pt.2
• mog project: HyperLogLog Implementation in Redis, pt.3