HyperLogLog は集合の要素数を推定する方法で、2014年4月22日に発表された Redis version 2.8.9 に新たに追加されました。   この文書は version 4.0.9 を基準に作成しました。

• 用途: 主に非常に大きなデータで誤差 1% 以下の近似値を求めるときに使います。 例えば、ある検索エンジンの1日の検索語数を計算するときに使えます。 メモリは非常に少なく使い、誤差は小さいです。
• メモリ使用量: 最大の利点はメモリを非常に少なく使うことです。   Java HashSet や Redis Set を使う場合、要素数に応じてメモリを使います。 例えば Redis Set に100万個の数字を保存すると 4,848kb、1000万個の数字を保存すると 46,387kb を使いますが、 Redis HyperLogLog を使うと要素数に関係なく固定で 12kb だけ使います。 これは100万個の数字の Set と比べるとわずか 0.25% だけ使うことになります。
  Redis HyperLogLog では 16384 個のレジスタ(register)を使い、レジスタあたり 6bits を使うので使用メモリ量は 12kb です。   計算式: 16,384 * 6bits = 98,304bits / 8 = 12,288bytes
• 要素数推定誤差: HyperLogLog の誤差は 1.04/SQRT(m) です。 m はレジスタ(register)数で、Redis では 16384 個を使うので誤差は 0.81% です。
• HyperLogLog は 2007年に Philippe Flajolet が発表したアルゴリズムです。 HyperLogLog という名前は、以前のアルゴリズム Loglog Counting を発展させたため Hyper を付けたものです。
• サルヴァトーレ(Salvatore)は Philippe Flajolet を称えるため HyperLogLog 関連コマンドに PF 接頭辞を使いました。
• 保存(add)速度: HyperLogLog と Set の保存速度を比較するため100万件のデータを PFADD と SADD で入れました。 PFADD は 5.23秒、SADD は 8.64秒で、PFADD が約 1.6倍速かったです。
• 取得速度: PFCOUNT と SCARD はどちらも O(1) です。Slowlog で確認したところどちらも 4 microseconds かかりました。
• HyperLogLog データは別の data structure を使わず String を使います。String 内部は HyperLogLog data structure です。
• 参考資料
• Philippe Flajolet が 2007年に発表した論文原本: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
• Marianne Durand と Philippe Flajolet が 2003年に発表した論文原本: Loglog Counting of Large Cardinalities
• 2013年に Google で HyperLogLog の実装をまとめた論文原本: HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm
• サルヴァトーレ(Salvatore)の HyperLogLog 紹介記事: Redis new data structure: the HyperLogLog
• NEVER D2 で紹介された資料: 確率的データ構造を用いた推定 - ユニーク要素数(Cardinality)推定と HyperLogLog
• 興味深い資料: Sketch of the Day: HyperLogLog — Cornerstone of a Big Data Infrastructure
• Hacker News
• Test Data
./redis-benchmark -p 6001 -r 100000 -n 1000000 pfadd hll __rand_int__ -> 1000000 requests completed in 5.23 seconds info memory -> used_memory: 583,520 memory usage hll -> 12,357 ./redis-benchmark -p 6002 -r 100000 -n 1000000 sadd myset __rand_int__ -> 1000000 requests completed in 8.64 seconds info memory -> used_memory: 6,068,480 memory usage myset samples 0 -> 4,848,493 ./redis-benchmark -p 6001 -r 1000000 -n 10000000 pfadd hll __rand_int__ -> 10000000 requests completed in 51.77 seconds info memory -> used_memory: 583,520 memory usage hll -> 12,357 ./redis-benchmark -p 6002 -r 1000000 -n 10000000 sadd myset __rand_int__ -> 10000000 requests completed in 84.47 seconds info memory -> used_memory: 49,407,112 memory usage myset samples 0 -> 46,387,195