HyperLogLog is a method for estimating the number of elements in a set and was added in Redis version 2.8.9, released on April 22, 2014.   This document was written based on version 4.0.9.

• Use: It is mainly used to get an approximation with an error of 1% or less for very large data. For example, you can use it to count a search engine's daily queries. It uses very little memory and the error is small.
• Memory usage: The biggest advantage is that it uses very little memory.   If you use a Java HashSet or a Redis Set, memory usage grows with the number of elements. For example, storing 1 million numbers in a Redis Set uses 4,848kb, and storing 10 million numbers uses 46,387kb, but Redis HyperLogLog uses a fixed 12kb regardless of the number of elements. Compared with a Set of 1 million numbers, that is only 0.25% of the memory.
  Redis HyperLogLog uses 16384 registers and 6 bits per register, so the memory used is 12kb.   Calculation: 16,384 * 6bits = 98,304bits / 8 = 12,288bytes
• Cardinality estimation error: The HyperLogLog error is 1.04/SQRT(m). m is the number of registers; Redis uses 16384, so the error is 0.81%.
• HyperLogLog is an algorithm published by Philippe Flajolet in 2007. The name HyperLogLog comes from extending the previous algorithm, Loglog Counting, so Hyper was added.
• Salvatore used the PF prefix for HyperLogLog related commands to honor Philippe Flajolet.
• Add speed: To compare insert speed between HyperLogLog and Set, 1 million items were added with PFADD and SADD. PFADD took 5.23 seconds and SADD took 8.64 seconds, so PFADD was about 1.6 times faster.
• Query speed: Both PFCOUNT and SCARD are O(1). When checked with Slowlog, both took 4 microseconds.
• HyperLogLog data does not use a separate data structure; it uses String. Inside the String is the HyperLogLog data structure.
• References
• Philippe Flajolet's original 2007 paper: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
• Original 2003 paper by Marianne Durand and Philippe Flajolet: Loglog Counting of Large Cardinalities
• Original 2013 Google paper on a practical HyperLogLog implementation: HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm
• Salvatore's HyperLogLog introduction: Redis new data structure: the HyperLogLog
• Article introduced on NAVER D2: Estimation using probabilistic data structures - cardinality estimation and HyperLogLog
• Interesting article: 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