一起了解 Redis 中的 HyperLogLog 算法？
如果觉得对你有帮助，能否点个赞或关个注，以示鼓励笔者呢？！
博客目录 | 先点这里
-
前提概念
- 需求
- 什么是 HyperLogLog ?
- 什么是基数？
- 基数统计
-
应用
- 需求
- 应用
-
原理
- 伯努利试验
- 原理
-
Redis 实践
- Redis HyperLogLog 与伯努利试验的联系？
- Redis HyperLogLog 的实现？
前提概念
什么是 HyperLogLog？
HyperLogLog
HyperLogLog
是一种算法，其来源于论文
《HyperLogLog the analysis of a near-optimal cardinality estimation algorithm》
，是 LogLog 算法的升级版本，
主要的目的就是利用统计学原理做近似基数统计
。优势就是利用一个较小的固定大小空间计算任意大小的
Distinct Value
。
Redis 的实践
HyperLogLog 并非 Redis 一家独有，Redis 只是基于 HyperLogLog 算法实现可一个 HyperLogLog 数据结构，并用该数据结构提供基数统计的功能。其优势就是可以做到只需要
12 kb
的空间大小，就可以实现接近
2^64
量级的基数统计。
HyperLogLog 数据结构并不会保存真实的元数据，所以其核心就是基数估算算法
在工程实践中，通常会用于 App 或页面的 UV 统计
什么是基数？
什么是集合？
在了解数学概念上的基数之前，我们先来了解下在数学上，是怎么描述
“集合”
的。
集合
（
Set
）, 也成集，是集合论的主要研究对象。集合是指具有某种特定性质的具体或抽象的对象汇总而成的集体。其中构成集合的这些对象则称之为该集合的
元素
集合特性
-
确定性
给定一个集合，任给一个元素，该元素只可能属于或不属于该集合。不存在模棱两可的情况 -
互异性
一个集合中，任何两个元素都可以被认为是不相同的，即每一个元素只会在集合中出现一次，具有去重性质 -
无序性
一个集合中，所有元素的地位都是相同的，元素之间是无序的
在本文中重点记住，
集合中的元素是具互异性的
什么是基数？
基数 (cardinal number) 在数学上，是集合论中刻画任意集合大小的一个概念。通俗点讲，
基数
就是对
集合
元素的
计数
。
-
结合对集合的理解，大白话就是，
基数就是指一个集合中不同元素的个数
-
元素集合可以是有限集合或无限集合，如果是有限集合，那么集合的基数就是一个特定的自然数；如果是无限集合，那么其基数就不是一个自然数了
基数？集合大小
我们知道基数就是对集合元素的计数，那说白了不就是集合元素的个数吗？为什么要引申出基数的概念，不直接使用集合大小？
这里直接贴上知乎 @lvony 的回答
- 基数就是严格意义上的集合元素多寡，为什么不直接用集合大小或者元素个数来描述，我觉得主要是所有集合的基数集合不是自然数集合的子集。换言之所有的自然数都是基数，但不是所有的基数都是自然数
- 如无穷集合的基数都不是自然数
基数统计
我们可以知道，基数可以简单理解成集合中不同元素的个数。那么什么是基数统计呢？在工程实践大数据领域，要精确的计算基数是十分困难的。为什么这么说呢？假设你要实现大数据集合的精确基数统计，通常我们会有两种思路
Set
我们可以采用集合的方式去统计元素基数，需要存储数据的元数据。假设有 10 亿个用户，每个用户占用 64 位的空间，那么总共就需要
1000000000 * 64 / 8 / 1024 / 1024 /1024
=
7.45 GB
。似乎咋一看还能接受，但是这只是单场景的基数统计，如果存在多个场景？时间范围再放大，那么空间就会跟随基数的增长而线性增长，这肯定是不能接受的
BitMap
那么既然 Set 占用空间过大，那么 BitMap 如何？位图倒是一个可以考虑的选项，将数据经过 hash 得到位图上的索引，并将该索引标记为 1，最后经过统计位图中 1 的个数，就可以做到基数统计。但是呢，也是有缺点的，
因为采用的是哈希算法，那么必然存在哈希冲突
，所以位图统计也并非是一个严谨的准确基数统计。为了降低冲突，必然会将位图的大小大于集合基数的一定倍数。
假设仍然是 10 亿用户数，假设位图的大小是基数的 2 倍，那么需要的空间就是
1000000000 * 2 / 8 /1024/1024
=
238 MB
, 这相比 Set 的空间占用，似乎已经可以接受了
概率算法
综上，位图的确是一个不错的选择，只需要 MB 级的空间就可以做 10 亿级别的基数统计。
但是如果有人跟你说它只需要 KB 级别的空间就可以做跟你同等量级甚至更大的基数统计呢？那位图还香吗？
在不追求绝对准确的情况下，倒是有很多基于概率算法的基数统计解决方案，比如
-
Linear Counting
-
LogLog Counting
-
HyerLogLog Counting
-
HyperLogLog++
而 Redis 则是采用 HyperLogLog 这种算法去实现的
应用
需求
-
统计页面
UV
- 统计 APP 或页面，每天被点击/浏览/观看的用户数量
-
注意是
UV
, 非
PV
- 不能占用大量空间，即非 O(n) 的空间复杂度
应用
Redis 原生提供了 HyperLogLog ，它是 LogLog 算法的升级版本，可以为我们提供
“非精准的去重计数估算”
，常用于 APP 或页面的 UV 统计
-
Redis Command
Redis 只为 HyperLogLog 提供了三个命令，所以还是相当简单的，我们一起来看一下 -
pfadd key element [element...]
O(1) 的插入时间复杂度, 向指定 key 的 HyperLogLog 数据结构插入一或多个元素 -
pfcount key [key...]
查询某 key 在 HyperLogLog 数据结构中的近似基数，如果该 key 不存在，则为 0 -
pfmerge destkey sourcekey [sourcekey...]
将多个 HyperLogLog 合并到一个 HyperLogLog
原理
伯努利试验
什么是伯努利试验？
伯努利试验 (Bernoulli trial)
伯努利试验 (
Bernoulli Trial
) 是在相同的条件下，重复地，互相独立地进行的一种随机试验
-
该随机试验只有两种互斥结果：
成功
或
失败
-
设试验只有 2 个可能结果：
AA
A
与
A‾
\overline{A}
A
，则称实验为
EE
E
伯努利试验；设
P(
A
)
=
p
(
0
<
p
<
1
)
P(A) = p (0<p<1)
P
(
A
)
=
p
(
0
<
p
<
1
)
, 此时
P(
A
‾
)
=
1
−
p
P (\overline{A} ) = 1 − p
P
(
A
)
=
1
−
p
伯努利过程（Bernoulli process）
假设该试验独立重复地进行了 n 次，那么我们就称这一过程的随机试验为
「n 重伯努利试验」
, 也称之
「伯努利过程」
单次伯努利试验是没有价值的，所以通常我们会反复进行多次伯努利试验，构成伯努利过程，然后观察其成功了多少次，失败了多少次
推论
设在一次试验中，事件 A 发生的概率为
p
(
0
<
p
<
1
)
p (0<p<1)
p
(
0
<
p
<
1
)
, 则在 n 重伯努利试验中
-
事件 A 恰好发生 k 次的概率为：
Pn
(
k
)
=
C
n
k
p
k
(
1
−
p
)
n
−
k
;
P_{n}(k) = C^k_np^k(1-p)^{n-k};
P
n
(
k
)
=
C
n
k
p
k
(
1
−
p
)
n
−
k
;
(k
=
0
,
1
,
2
,
3
,
.
.
.
,
k
)
(k=0,1,2,3,…,k)
(
k
=
0
,
1
,
2
,
3
,
.
.
.
,
k
)
-
事件 A 在第 k 次试验才首次发生的概率为
p1
(
1
−
p
)
k
−
1
p^1(1-p)^{k-1}
p
1
(
1
−
p
)
k
−
1
;(
k
=
0
,
1
,
2
,
3
,
.
.
.
,
k
)
;(k=0,1,2,3,…,k)
;
(
k
=
0
,
1
,
2
,
3
,
.
.
.
,
k
)
典型案例
我们以
“抛硬币”
为一次伯努利试验举例，每次抛硬币，只有
"正面"
和
"反面"
两种结果
假设每次试验抛一枚硬币，我们重复进行 50 次这样的试验，那么这就构成了一轮
伯努利过程
原理
伯努利过程
HyperLogLog 的实现是基于伯努利试验的结论实现的，所以要了解 HyperLogLog 的原理，我们得先回顾一下伯努利过程以及估算公式，这里还以经典案例
“抛硬币”
来举例
抛硬币只有两种结果，正面或反面，概率都是 50%， 我们假设抛掷到正面为成功，抛掷到反面为失败，对其进行实验，实验内容如下
-
掷一次硬币为一次
「伯努利试验」
-
假设我们以
100
次
「伯努利试验」
为一轮
「伯努利过程」
-
进行
10
轮
「伯努利过程」
因为每轮过程都进行了
100
次的试验（掷硬币），所以我们需要记录每轮过程中，首次出现正面时，是该轮过程的第几次试验（掷硬币），标记为
k
-
第一轮过程首次出现正面时，所进行的试验次数，为
k1
-
第二轮过程首次出现正面时，所进行的试验次数，为
k2
-
以此类推，第十轮过程首次出现正面结果时，所进行的试验次数为
k10
那么对于这进行了
10
轮的伯努利过程们而言，
每轮都存一个 k 值，我们取其中最大的 k ，作为最大抛掷次数，记为
k_max
- 在 n 轮的伯努利过程中，取投掷次数最大值记为 k_max，即取最大的 k 值
估算公式与优化
估算公式
熟悉了 k_max 和 伯努利过程的轮数之后，我们再来了解估算公式，即经过各种数学证明，我们可以得到
n
与
k_max
之间的关联估算公式
-
n=
2
k
_
m
a
x
n = 2^{k\_max}
n
=
2
k
_
m
a
x
-
n
是伯努利过程进行的次数 -
k_max
是所有进行的 n 轮伯努利过程中，最大的抛掷次数
-
什么意思呢？该公式的作用是什么？
-
即在
k_max
和
n
两个变量之间，知其一便知其二 -
如我们知道了 k_max = 10, 即抛掷 10 次硬币出现第一次正面结果，那么就可以说明至少已经进行了
n=
2
10
=
1024
n = 2^{10} = 1024
n
=
2
1
0
=
1
0
2
4
次伯努利过程了
但是呢，估算公式需要经过足够多的样本实验才能够进行有效的估算，即实验样本太小，误差过大，公式则没有实用价值。那么我们要怎么减少误差呢，提高估算公式的实用程度呢？
估算优化
既然估算在样本较小的时候存在误差，那么为了减小误差，我们就需要增加实验的次数，什么意思呢？有两种减小误差的方式
方式一
- 因为只进行了 10 轮伯努利过程，样本较小，那么我们就可以增加伯努利过程的次数，比如进行 1000 次，以此减小误差
- 这是一个好方法，但是不足够，依然可以继续努力
方式二
-
基于方式一的前提下，以 1000 轮伯努利过程为一次
「估算实验」
-
进行 10 次
「估算实验」
，
取 10 次实验的
均值
「估算实验」是随意取名的，防止概念混淆，仅仅是标记 1000 轮伯努利过程组成的一次实验
什么意思呢？
-
即进行
10
组 1000 轮伯努利过程，每组实验都可以得到一个
k_max
值，我们取 10 次实验得到的
k_max
值，并求其
均值
-
当然这里的 “均值” 指的是
调和平均数
，而非平时我们所说的算术平均数，可以做到去极端值的影响
小结
- 一轮伯努利过程由多次伯努利试验组成
- 一轮伯努利过程可以得到一个 k 值
- 多轮伯努利过程可以得到一个 k_max 值
- 以多轮伯努利过程标记为一次实验，那么多轮实验可以得到 k_max 的均值
Redis 实践
Redis HyperLogLog 与伯努利试验的联系？
通过以上内容的介绍，我们可以知道，
k_max
和
n
之间是可以相互推导的，知其一便知其二。那么该估算公式又如何在 Redis 的 HyperLogLog 中得到应用呢？
我们知道计算机的数据都是以二进制进行存储的，即
01010100
的二进制串的形式。而二进制的每一比特位就跟抛硬币一样，只有
0
和
1
两种结果。我们记 0 为失败，1 为成功，
“即每一个二进制串，我们都可以看作是一个伯努利过程”
K 值在哪？
从最低位（从右到左）开始数，第一个
1
所在的位置就是该次伯努利过程的
k
值
-
1
所在位置为伯努利过程首次获得成功的时刻。比如
1
所在的位置，从右往左数，是第 5 位，那么该次伯努利过程在第 5 次抛硬币时，首次得到正面结果。 -
1
的右边有多少个 0，也就说明在出现正面之前，抛了多少次反面
(图片源于网络)
比特串类比
假设有一串数据, 值为
00010000
, 我们类比成经典例子抛硬币，会一串比特串就是一轮伯努利过程，进行了
8
次掷硬币试验。
-
可以得知
k = 5
，从低位往高位数 （从右往左），第一个
1
出现在第 5 个位置上，那么该轮伯努利过程在第 5 次试验中获得正面结果
假设我们重复进行了 n 轮伯努利过程，每轮伯努利过程都会得到一个
k
, 第一次记为
k1
, 第二次记为
k2
, 第 n 次记录为
kn
，在这 n 轮伯努利过程中，假设我们最终得到
k_max = 8
，那么由已知数据，我们能知道总共进行了多少次伯努利过程吗？
-
当然可以，既然我们知道了 k_max = 8，那么根据公式
n=
2
k
_
m
a
x
n = 2^{k\_max}
n
=
2
k
_
m
a
x
, 那么
n=
2
8
=
256
n = 2^8 = 256
n
=
2
8
=
2
5
6
Redis HyperLogLog 的实现？
Redis 是如何实现 HyperLogLog 的呢？它又是如何与伯努利过程联系起来？又如何去减少误差呢？
我们这里假设一个需求，
需要统计当前访问 B 站首页的 UV 数量
执行过程
（一）
首选通过
Hash
函数, 将每个用户 ID 转成为
64
位的整数
（二）
因为一个 HyperLogLog 有 16834 个桶，所以我们需要知道该用户处于哪个桶中？
-
我们就将 64 位整数的
低位 14
位截取下来，用于获得桶的编号，比如当前用户的低 14 位值是 1020，那么该用户则处于第
1020
号桶
（三）
然后我们取剩余的
50 位
数值表示一个伯努利过程，
从低位往高位数，取第一个
1
出现的位置标记为 k, 并将 k 存储到 1020 号桶中
因为每个桶的大小是 6 bits, 可以表示 0 ~ 64 大小的 10 进制数，所以用户剩余数值只有 50 位，即 k 的取值范围是 1~50，那么自然不存在存储不了 k 的问题
（四）
因为桶只有 16834 个，而访问用户肯定远大于这个数值，所以 HyperLogLog 下的每个桶必然会被多次更新数值，
那么更新逻辑是什么？
- 假设 1020 号桶，此时存储的数值为 30，即该桶所记录的 k = 30
- 此时另一个用户 B 访问，其编号是 1020 号桶，但其得到的 k 值是 35；与现桶里存储的 k 值并不相同
-
此时我们要回想到一个桶其实就是一组
「估算实验」
， 而一组
「估算实验」
势必存在多轮伯努利过程，而我们的目的求得多轮伯努利过程中的最大 k, 所以我们得知逻辑如下- 如果新 k 值大于桶内记录的 k 值，则用新值覆盖旧值，即更新 k_max
- 如果新 k 值小于或等于桶内记录的 k 值， 则不动
（五）
此时如果我们要对该 HyperLogLog 进行基数统计了，要怎么办呢？
- 那么就对每个桶的 k_max 求调和平均值，并带入估算公式中，进行计算，求得 n
- n 就是我们需要的 B 站访问 UV
分桶
什么是分桶？
分桶就是将一块存储空间分成很多个小空间
-
将一定大小的空间平均分为
214
=
16384
2^{14} = 16384
2
1
4
=
1
6
3
8
4
份，我们称之为桶; 假设为 m，即
m = 16834
-
每个桶占用 6 bits, 即 6 位，固定大小; 假设为 p, 即
p = 6
-
那么该空间大小则为
(m
∗
p
)
/
8
/
1024
=
16834
∗
6
/
8
/
1024
(m * p) /8/ 1024 = 16834 * 6 / 8 / 1024
(
m
∗
p
)
/
8
/
1
0
2
4
=
1
6
8
3
4
∗
6
/
8
/
1
0
2
4
；
约等于 12 kb
为什么要分桶？
我们在原理的章节上有描述过，单批次的多组伯努利过程样本依然偏小，存在一定的误差，那么我们需要增加多组
「估算实验」
，并求其
k_max
均值
-
这里的一个桶其实就相当于一组
「估算实验」
-
所以 Redis 的 HyperLogLog 总共就有 16834 组
「估算实验」
这的确是一个比较大的数值了，自然也可以降低估算误差
多轮伯努利过程求 k_max ?
有一个点困扰了我一小段时间，就是伯努利的原理和 Redis 的实现有一段过程没有得到相互印证，就是在 Redis 中似乎没有看到多轮伯努利过程求 k_max 这个过程？
其实是有的，我们从以上信息得到几个点
- 每次的数据输入都是一次伯努利过程，即求得某个桶的某次伯努利过程的 K 值
-
因为 Redis 的 HyperLogLog 总共分为 16834 个桶，每个桶其实就是一个
「估算实验」
- 每个估算实验都存在多轮的伯努利过程，我们也知道一个桶必然存在多次的数据输入，每次输入就是一轮伯努利过程，每轮过程都会计算得到一个 k 值，并与桶内所记录 k_max 进行比较，从而得到最新的 k_max
问题
12 kb 可以记录多少的数据量？
我们在上面得知 Redis 的每个 HyperLogLog 都仅占用 12 kb 的内存空间，那么这个小小的空间中，支持我们统计多少的数据量呢，比如 UV ?
-
因为 Redis 会将输入数据转为 64 位的整数，这 64 为都会参与到计算中。所以一个 HyperLogLog 可以支持
264
2^{64}
2
6
4
种数值输入, 那么自然就是说可以支持
264
2^{64}
2
6
4
大小的数据量啦
参考资料