本文介绍: 考虑这样一个场景如何统计一个大型网站的去重日活、月活用户(UV)?你可以通过 set 集合bitmap 这类常用工具,但有个最大的缺点是,如果数据量巨大,比如 1 亿,甚至 10 亿将耗费巨大内存消耗。有人研究出了这样一种算法叫 `HyperLogLog`,是一种概率性的统计算法每个 `HyperLogLog` 对象最大占用空间为 `12KB`,相当节省内存。你应该也猜到了,这么小的内存消耗,是无法记录真实的明细数据,统计数值也不是完全精准,有一定的误差比例。


前言

本文参考源码版本 redis6.2

考虑这样一个场景如何统计一个大型网站的去重日活、月活用户(UV)?

可以通过 set 集合bitmap 这类常用工具,但有个最大的缺点是,如果数据量巨大,比如 1 亿,甚至 10 亿将耗费巨大内存消耗。

有人研究出了这样一种算法HyperLogLog,是一种概率性的统计算法每个 HyperLogLog 对象最大占用空间12KB,相当节省内存

你应该也猜到了,这么小的内存消耗,是无法记录真实的明细数据,统计数值也不是完全精准,有一定的误差比例。


一、动手试试?

redis HyperLogLog 主要提供了三个操作PFADDPFCOUNTPFMERGE,分别用于添加、计数与合并

1. 添加

PFADD 指令语法

PFADD key [element [element ...]]

可用版本:>= 2.8.9
时间复杂度:O(1) 的复杂度添加一个元素

关于返回值:

看看效果

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)

返回值:

值得注意的是:该操作可能会修改 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 和多 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

由此,我们可以通过 k_max 记录估算基数 n大小

但还存在一个概率偏差较大问题我们可以通过进行多轮这样的 n 次实验然后通过调和平均数(也叫倒数平均数)找到多轮之间的均值作为最终的 k_final公式如下:

在这里插入图片描述

调和平均数结果偏向几个值中较小值,可以避免较大值的影响,这样一来,偏差便会小很多。

2. HyperLogLog

Log 表示对数,HyperLogLog 意思是超对数计算,是 LogLog 算法的改进版,有兴趣可以自行了解下。

以下是两个大基数集合的 HyperLogLog 估算偏差,横轴是数据量,纵轴是误差率(图来自 Antirez 博客):

在这里插入图片描述

2.1 工作原理

散列计算:通过哈希散列函数,将输入的值散列输出为 64 位 01 这样的二进制结合抛硬币实验我们可以把 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 数据的字段信息

稀疏编码 和 密集编码都采用 16字节 的固定头部,如下:

 +------+---+-----+----------+
 | HYLL | E | N/U | Cardin.  |
 +------+---+-----+----------+

继续看看对应hllhdr 底层数据结构

struct hllhdr {
    char magic[4];      
    uint8_t encoding;   
    uint8_t notused[3]; 
    uint8_t card[8];    
    uint8_t registers[];
};

大致是这样: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,对应的分组编号是 1000
  • ZERO:19:分组 1001-1019 被设置成 0
  • VAL:3,2两个分组被设置成 3,对应的分组编号是 1020、1021
  • XZERO: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 转码

默认情况下,当我们创建一个 HLL 结构时,使用稀疏编码:

  • 一是因为刚开始基数记录较少,可能出现较多空分组,这个时候可以压缩
  • 另外,由于基数少,出现 k_max 超过 32 的概率较小,稀疏编码完全能够容纳。

随着基数的增多,稀疏编码的优势将慢慢失去,当达到以下任一阈值条件时,稀疏编码将转换为密集编码:

  • 当稀疏编码存储的任意一个组里的计数值大于 32(k_max
  • 长度超过 3000 字节(可通过参数 hll-sparse-max-bytes 配置

相关参考:

原文地址:https://blog.csdn.net/ldw201510803006/article/details/126093455

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_12153.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注