前言
考虑这样一个场景,如何统计一个大型网站的去重日活、月活用户(UV)?
你可以通过 set 集合、bitmap 这类常用工具,但有个最大的缺点是,如果数据量巨大,比如 1 亿,甚至 10 亿将耗费巨大内存消耗。
有人研究出了这样一种算法叫 HyperLogLog
,是一种概率性的统计算法,每个 HyperLogLog
对象最大占用空间为 12KB
,相当节省内存。
你应该也猜到了,这么小的内存消耗,是无法记录真实的明细数据,统计数值也不是完全精准,有一定的误差比例。
一、动手试试?
redis HyperLogLog 主要提供了三个操作:PFADD
、PFCOUNT
、PFMERGE
,分别用于添加、计数与合并。
1. 添加
PFADD key [element [element ...]]
关于返回值:
127.0.0.1:6379> PFADD hll a b c d e f g
(integer) 1
127.0.0.1:6379> PFCOUNT hll
(integer) 7
127.0.0.1:6379>
2. 统计
PFCOUNT
指令。语法:
PFCOUNT key [key ...]
可用版本: >= 2.8.9
时间复杂度:针对一个 key 是 O(1) 常量时间,如果是 N 个 key 就是 O(N)
返回值:
- 单个 key:正常是 HyperLogLog 对象存储的基数统计结果,如果 key 不存在则返回 0。
- 多个 key:则是返回多个 key 对应的 HyperLogLog 合并结果。内部处理时,会先创建一个临时的 HyperLogLog 对象,然后将 keys 对应的 HyperLogLog 对象全部合并过去。
值得注意的是:该操作可能会修改 HyperLogLog,因为最后8个字节编码了用于缓存的最新计算基数,也就是说,PFCOUNT
命令本质来说算一个写操作。
127.0.0.1:6379> PFADD hll foo bar zap
(integer) 1
127.0.0.1:6379> PFADD hll zap zap zap
(integer) 0
127.0.0.1:6379> PFADD hll foo bar
(integer) 0
127.0.0.1:6379> PFCOUNT hll
(integer) 3
127.0.0.1:6379> PFADD some-other-hll 1 2 3
(integer) 1
127.0.0.1:6379> PFCOUNT hll some-other-hll
(integer) 6
127.0.0.1:6379>
关于性能:
- 单 key:这种性能最好,由于计算结果会缓存起来,只要 HyperLogLog 对象没有变化,后续请求直接从缓存中获取结果。
- 多 key:这样性能要差的多,由于多 key 对应的 HyperLogLog 对象需要做合并操作,因此是没法缓存计算结果。
所以,在使用的时候我们应该清楚,该命令的单 key 和多 key 执行在语义上是不同的,具有不同的性能。
3. 合并
PFMERGE
指令。语法:
PFMERGE destkey sourcekey [sourcekey ...]
可用版本: >= 2.8.9
时间复杂度:合并 N 个 HyperLogLog 对象,时间复杂度是 O(N),通常会有更高的时间消耗
127.0.0.1:6379> PFADD hll1 foo bar zap a
(integer) 1
127.0.0.1:6379> PFADD hll2 a b c foo
(integer) 1
127.0.0.1:6379> PFMERGE hll3 hll1 hll2
OK
127.0.0.1:6379> PFCOUNT hll3
(integer) 6
127.0.0.1:6379>
二、原理
1. 伯努利过程
抛出一次,正面朝上的概率是 50%,连续抛硬币直到出现正面朝上,记第一次出现正面朝上的位置为 k
。
例如,抛一次出现正面的概率为 1/2,抛两次才出现正面的概率为 1/2*1/2,抛出 k 次才第一次出现正面的概率为 1/2^k
这种找出正面朝上的行为可以看作是伯努利过程
,连续进行 n 次伯努利过程,可以找到 n 次正面朝上的 k 对应的位置(k1,k2,… kn)
通过概率统计发现,n 与 k 直接存在一定的联系,找出 n 次 k 中的最大值 k_max,存在如下关系: n ≈ 2^k_max
但还存在一个概率偏差较大
的问题,我们可以通过进行多轮
这样的 n 次实验,然后通过调和平均数
(也叫倒数平均数
)找到多轮之间的均值作为最终的 k_final
,公式如下:
调和平均数结果偏向几个值中较小值,可以避免较大值的影响,这样一来,偏差便会小很多。
2. HyperLogLog
Log 表示对数,HyperLogLog 意思是超对数计算,是 LogLog 算法的改进版,有兴趣可以自行了解下。
以下是两个大基数集合的 HyperLogLog 估算偏差,横轴是数据量,纵轴是误差率(图来自 Antirez 博客):
2.1 工作原理
散列计算
:通过哈希散列函数,将输入的值散列输出为 64 位 0
和 1
这样的二进制串
,结合抛硬币实验,我们可以把 1 看作是正面,0 是反面。
在 redis 中,对于散列函数的 64 位输出,低 14 位(从右)作为分组编号,2^14 = 16384
个分组。剩下 50 位
作为基数估计。
剩下的 50 位,从低位到高位
(从右至左)找到第一个1
的位置,记为 k
,然后与当前分组的记录的 k_current
进行比较,如果大于 k_current
则更新,反之,不做任何处理。
为了降低概率偏差较大的影响,redis 采用分组
(多轮)策略,然后每一组都有一个 k_max
,并通过相应的计算找出最合适的 k_max 作为基数关联。
2.2 占用内存大小
12KB 的由来?
前面我们提到,64 位的散列输出只有 50 比特(bit
)用来找 k,也就是说 k 出现的位置最大就是 50
,因此,我们可以用 6 bit
(最大值可达 63)就可以存储。
总共有 16384
分组,也就是说有 16384 个 6 bit,即 12 KB
。
使用 12 KB 可以统计 2^64
个元素个数,只要在这个数量范围内,不管数量多少,都只占用 12 KB 的内存空间。
2.3 内存优化?
如果每个 key 都占用 12 KB 的空间,对于那些远小于 12 KB 的 key 来说,是不是太浪费了?
你应该也猜到了 redis 的套路,在其内部一般会采用不同的编码
方式,目的就是节省内存空间,具体是这样的:
不管是 稀疏编码 还是 密集编码,都采用 16384 个分组,如果每个分组采用 6个 bit,需要 12 KB 的空间,这正是密集编码的方案。
对于稀疏编码来说,如果每个分组也采用 6bit 就有点奢侈了,因为,很多分组都可能没有数据,各分组将白白浪费 6bit 的空间。
具体区别我们继续往下看~
3. 数据编码
redis 使用稀疏
和密集
两种编码处理与存储数据,默认情况下,redis 创建的 HyperLogLog 对象使用稀疏编码
,当稀疏编码长度超过一定值或者 k_max
超过一定值时发生编码转换。
固定头部?
HyperLogLog 简称 HLL
,没有采用新的数据结构,其底层仍然采用 sds
的结构存储数据(字符串位图)。
因此,为了区别普通字符串,在 HLL 头部使用了固定的字符串('HYLL'
)。
而为了更好地管理 HLL 数据,redis 使用了一个 hllhdr
(HLL头对象,HLL header)结构体来存储 HLL 数据的字段信息。
+------+---+-----+----------+
| HYLL | E | N/U | Cardin. |
+------+---+-----+----------+
struct hllhdr {
char magic[4];
uint8_t encoding;
uint8_t notused[3];
uint8_t card[8];
uint8_t registers[];
};
- magic:4字节,填充固定字符串:
HYLL
- encoding:1字节,填充 0 或 1,0 表示密集编码,1 表示稀疏编码
- notused:3字节,目前未使用,为将来使用保留
- card:8字节,缓存最近一次计算的基数
- registers:动态字节数组,用于 HLL 数据存储,不论编码是稀疏还是密集。散列值的低 14 位为分组序号,也就是说 redis 使用了 16384 个分组
大致是这样:redis 的 HLL 存储分为两部分:hllhdr
头部 和 registers
数据:
对于稀疏与密集编码的主要区别,可以简单理解为空分组较多
时使用稀疏编码存储,空分组较少
时使用密集编码存储,内部计算使用 HLL_RAW
编码。
缓存?
为了减少计算成本,redis 使用 card 来保存基数计数最新的计算结果(缓存
),card 最高位用来标识剩下的 63 位数据是否有效(1 无效,0 有效),如果数据被更改,那么 card 缓存的值将失效。
3.1 稀疏编码
稀疏编码的主要目的是想将多个连续空分组、多个连续相同值分组的进行压缩,具体压缩方式提供了三种操作码:
- ZERO:1 字节,形如
00xxxxxx
,其中00
是操作码的值,xxxxxx
6 bit 代表的整数表示有多少个连续分组被设置为 0。 - XZERO:2 字节,形如
01xxxxxx yyyyyyyy
,其中00
是操作码的值,剩下 14 bit 代表的整数表示有多少个连续分组被设置为 0。 - VAL:1 字节,形如
1vvvvvxx
,其中1
是操作码的值,vvvvv
5 bit 表示分组的值,xx
表示有多少个连续分组被设置为vvvvv
。
值得注意的是,对于 VAL 操作码,因为分组值只有 5 bit,我们在找 k_max 的时候不能查超过 32
,一旦超过内部就会自动转换成 密集编码。
例子:
对于一个空的 HLL,压缩后是这样:XZERO:16384
,也就是说用 2 字节
就表示了 16384 个分组,实际编码是 01111111 111111
,再加上 16 字节的固定头部,总共占用 18 字节。
再比如,我们有一个 HLL 只有三个非 0 分组,对应分组位置分别是 1000、1020、1021,对应的分组值分别是 2、3、3,我们来看看操作码组成:
XZERO:1000
:表示分组 0 – 999 都被设置成 0。VAL:2,1
:一个分组被设置成 2,对应的分组编号是 1000ZERO:19
:分组 1001-1019 被设置成 0VAL:3,2
:两个分组被设置成 3,对应的分组编号是 1020、1021XZERO:15362
:分组 1022-16383 被设置成 0
在这个例子中,仅用了 7 字节
,可见,比 12 KB 的密集编码要节省很多内存。
以下是 基数 和 占用内存(字节)的对比值:
100 267
200 485
300 678
400 859
500 1033
600 1205
700 1375
800 1544
900 1713
1000 1882
2000 3480
3000 4879
4000 6089
5000 7138
6000 8042
7000 8823
8000 9500
9000 10088
10000 10591
可以看到,随着基数的增加,稀疏编码占用的内存也在增加。
3.2 密集编码
密集编码相对来说就比较简单了,每个 key 占用固定的 12 KB
大小,其中有 16384
(2^14) 个分组,每个分组占 6bit
。
3.3 转码
随着基数的增多,稀疏编码的优势将慢慢失去,当达到以下任一阈值条件时,稀疏编码将转换为密集编码:
相关参考:
原文地址:https://blog.csdn.net/ldw201510803006/article/details/126093455
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_12153.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!