统计功能是一类极为常见的需求，比如下面这个场景：
要完成这个统计任务，最直观的方式是使用一个SET保存页面在某天的访问用户 ID，然后通过对集合求差SDIFF和求交SINTER完成统计：
# 2020-01-01 当日的 UV
SADD page:uv:20200101 "Alice" "Bob" "Tom" "Jerry"
# 2020-01-02 当日的 UV
SADD page:uv:20200102 "Alice" "Bob" "Jerry" "Nancy"
# 2020-01-02 新增用户
SDIFFSTORE page:new:20200102 page:uv:20200102 page:uv:20200101
# 2020-01-02 新增用户数量
SCARD page:new:20200102
# 2020-01-02 留存用户
SINTERSTORE page:rem:20200102 page:uv:20200102 page:uv:20200101
# 2020-01-02 留存用户数量
SCARD page:rem:20200102
优点：
缺点：
SUNION、SINTER、SDIFF计算复杂度高，大数据量情况下会导致 Redis 实例阻塞，可选的优化方式有：
当用户 ID 是连续的整数时，可以使用BITMAP实现二值统计：
# 2020-01-01 当日的 UV
SETBIT page:uv:20200101 0 1 # "Alice"
SETBIT page:uv:20200101 1 1 # "Bob"
SETBIT page:uv:20200101 2 1 # "Tom"
SETBIT page:uv:20200101 3 1 # "Jerry"
# 2020-01-02 当日的 UV
SETBIT page:uv:20200102 0 1 # "Alice"
SETBIT page:uv:20200102 1 1 # "Bob"
SETBIT page:uv:20200102 3 1 # "Jerry"
SETBIT page:uv:20200102 4 1 # "Nancy"
# 2020-01-02 新增用户
BITOP NOT page:not:20200101 page:uv:20200101
BITOP AND page:new:20200102 page:uv:20200102 page:not:20200101
# 2020-01-02 新增用户数量
BITCOUNT page:new:20200102
# 2020-01-02 留存用户
BITOP AND page:rem:20200102 page:uv:20200102 page:uv:20200101
# 2020-01-02 留存用户数量
BITCOUNT page:new:20200102
优点：
缺点：
前面两种方式都能提供准确的统计结果，但是也存在以下问题：
考虑下面这一场景：
cardinality counting
针对这一特定的统计场景，Redis 提供了HyperLogLog类型支持基数统计：
# 2020-01-01 当日的 UV
PFADD page:uv:20200101 "Alice" "Bob" "Tom" "Jerry"
PFCOUNT page:uv:20200101
# 2020-01-02 当日的 UV
PFADD page:uv:20200102 "Alice" "Bob" "Tom" "Jerry" "Nancy"
PFCOUNT page:uv:20200102
# 2020-01-01 与 2020-01-02 的 UV 总和
PFMERGE page:uv:union page:uv:20200101 page:uv:20200102
PFCOUNT page:uv:union
优点：
HyperLogLog计算基数所需的空间是固定的。只需要 12KB 内存就可以计算接近 \(2^{64}\) 个元素的基数。
缺点：
HyperLogLog的统计是基于概率完成的，其统计结果是有一定误差。不适用于精确统计的场景。
HyperLogLog是一种基于概率的统计方式，该如何理解？
我们来做一个实验：不停地抛一个均匀的双面硬币，直到结果是正面为止。
用 0 和 1 分别表示正面与反面，则实验结果可以表示为如下二进制串：
+-+
第 1 次抛到正面 |1|
+-+
+--+
第 2 次抛到正面 |01|
+--+
+---+
第 3 次抛到正面 |001|
+---+
+---------+
第 k 次抛到正面 |000...001| (总共 k-1 个 0)
+---------+
进行 n 实验后，将每次实验抛硬币的次数记为 \(k_1, k_3,\cdots,k_n\)，其中的最大值记为 \(k_{max}\)。
理想情况下有 \(k_{max} = log_2(n)\)，反过来也可以通过 \(k_{max}\) 来估计总的实验次数 \(n = 2^{k_{max}}\)。
实际进行实验时，极端情况总会出现，比如在第 1 次实验时就连续抛出了 10 次反面。
如果按照前面的公式进行估计，会认为已经进行了 1000 次实验，这显然与事实不符。
为了提高估计的准确性，可以同时使用 m 枚硬币进行 分组实验。
然后计算这 m 组实验的平均值 \(\hat{k}_{max} = \frac{\sum_{i=0}^{m}{k_{max}}}{m}\)，此时能更准确的估计实际的实验次数 \(\hat{n}=2^{\hat{k}_{max}}\)。
通过前面的分析，我们可以总结出以下经验：
可以通过二进制串中首个 1 出现的位置 \(k_{max}\) 来估计实际实验发生的次数 \(n\)
HyperLogLog借鉴上述思想来统计集合中不重复元素的个数：
bucket中分别统计
HyperLogLog实现，使用8bit 输出的 hash 函数并以 4 个桶进行分组统计 映射为二进制串 分组 计算k
| | |
V V V
+---------+
hash("Alice") => |01|101000| => bucket=1, k=1
+---------+ 分组统计 k_max
+---------+
hash("Bob") => |11|010010| => bucket=3, k=2 +----------+----------+----------+----------+
+---------+ | bucket_0 | bucket_1 | bucket_2 | bucket_3 |
+---------+ ==> +----------+----------+----------+----------+
hash("Tom") => |10|001000| => bucket=2, k=3 | k_max= 1 | k_max= 2 | k_max= 3 | k_max= 2 |
+---------+ +----------+----------+----------+----------+
+---------+
hash("Jerry") => |00|111010| => bucket=0, k=1
+---------+
+---------+
hash("Nancy") => |01|010001| => bucket=1, k=2
+---------+
分组计数完成后，用之前的公式估计集合基数为 \(2^{\hat{k}_{max}}= 2^{(\frac{1+2+3+2}{4})} = 4\)。
在 Redis 的实现中，对于一个输入的字符串，首先得到 64 位的 hash 值：
由于使用了 64 位输出的 hash 函数，因此可以计数的集合的基数没有实际限制。
HyperLogLog的标准误差计算公式为 \(\frac{1.04}{\sqrt{m}}\)（\(m\) 为分组数量），据此计算 Redis 实现的标准误差为 \(0.81\%\)。
下面这幅图展示了统计误差与基数大小的关系：
分析该图可以得出以下结论：
原文：https://www.cnblogs.com/buttercup/p/14099176.html