本章内容

简介

HyperLogLog是一种基数估算算法，可以用于在数据量很大的情况下，只需要使用很小的空间就能够近似的统计出所有数据的基数。

在Redis中，HyperLogLog是一种高级数据结构，可以使用该结构来进行基数估算，它的标准误差率为0.81%，这意味着即使在非常大的数据集上，它也可以提供非常准确的结果。

应用场景

HyperLogLog的主要应用场景：

• 独立访客统计：通过收集用户IP或其他标识符，将其添加到HyperLogLog中，统计得到一个独立访客数量的估算值。
• 活跃用户数统计：通过将用户标识符（如：用户ID）添加到HyperLogLog中，统计得到活跃用户数的近似值。
• 布隆过滤器：通过与布隆过滤器结合使用，实现数据的高效检索，其中布隆过滤器用于判断元素是否存在于集合中，HyperLogLog用于估算集合中不重复元素的数量。
• 统计分析：通过将数据特征或标识符添加到HyperLogLog中，统计得到不同特征对应的数量（如：兴趣爱好、商品种类等）。

常用命令

pfadd命令

• 格式：pfadd key element [element …]。
• 功能：向HyperLogLog中添加元素。
• 返回值：HyperLogLog中元素发生变更时返回1；否则返回0。
• 时间复杂度：O(1)。

pfcount命令

• 格式：pfcount key [key …]。
• 功能：统计基数。
• 返回值：
• 单个 key：返回HyperLogLog中存储的基数统计结果，如果key不存在则返回0。
• 多个 key：返回多个key对应的HyperLogLog合并结果。内部处理：创建一个临时HyperLogLog合并多个key对应的HyperLogLog。
• 时间复杂度：O(n)，n为key的个数。

pfmerge命令

• 格式：pfmerge destkey sourcekey[sourcekey ...]。
• 功能：合并多个HyperLogLog。
• 返回值：OK。
• 时间复杂度：O(n)，n为HyperLogLog的个数。

实现原理

HyperLogLog算法的理论基础与伯努利试验有关。

伯努利实验

伯努利试验（Bernoulli experiment）是在同样的条件下重复地、相互独立地进行的一种随机试验，其特点是该随机试验只有两种可能结果：发生或者不发生。假设该项试验独立重复地进行了n次，那么就称这一系列重复独立的随机试验为n重伯努利试验，或称为伯努利概型。

伯努利实验过程

一个硬币存在正反两面，每抛出一次，正面朝上的概率为50%（即：1/2），连续抛硬币直到出现正面朝上，记录第一次出现正面朝上的位置为k。

假如连续抛出3次硬币才出现正面朝上，那么k=3，k概率为：k = 1/2*1/2*1/2（即：(1/2)^k）。

这种找出硬币正面朝上的行为可以看作是伯努利过程，连续经历n次伯努利过程，可以找到n次正面朝上的k对应的位置（k1、k2、…...、kn）。

如图所示：

通过概率统计发现，n与k之间存在一定的联系，经历n次伯努利过程，找出k中的最大值k_max，n与k的关系为：n ≈ 2^k_max。

经历5次伯努利过程找出正面朝上的k：

• 第一次抛掷2次出现正面朝上：k=2，n=1。
• 第二次抛掷5次出现正面朝上：k=5，n=2。
• 第三次抛掷6次出现正面朝上：k=6，n=3。
• 第四次抛掷10次出现正面朝上：k=10，n=4。
• 第五次抛掷3次出现正面朝上：k=3，n=5。

按以上n与k的关系：显然2^10不等于4 ，出现很大误差。因此，需要通过优化算法来减小误差。

估值优化

估值优化方式：

• 增加伯努利过程轮数，取平均值。假设以x次伯努利试验为一轮，得到每轮找出的k_max，经历m轮伯努利试验后，平均值为：k_average = (k_max_1 + k_max_1 …... + k_max_m)/m。
• 增加修正因子，修正因子是一个不固定的值，会根据实际情况来进行值的调整。这种方式涉及很多数学理论知识，感兴趣的同学可自行查阅相关资料。

以上增加伯努利过程轮数，取平均值的方式就是LogLog算法的实现，其计算公式：

其中：

• DVLL：伯努利试验次数。
• constant：修正因子。
• m：伯努利试验轮数。
• 头上带一横杠的R：平均值。

HyperLogLog与LogLog的区别是HyperLogLog使用了调和平均数（即：倒数平均数），调和平均数相比平均数的优点是能降低极大值对平均值的影响，其计算公式：

HyperLogLog实现原理

HyperLogLog处理流程大致分为三步：计算bit串、分组、对应分组。

1）计算bit串

如图所示：

图中，任一key经过hash后得到一个64bit的bit串，其中：

• 低14bit作为分组编号，共2^14 = 16384个分组。
• 剩余50bit作为基数估计，从低位到高位（即：从右至左）找出第一个1的位置，记为k，与当前分组的记录的k_current进行比较，如果k大于k_current，则更新；反之，不做处理。

2）分组

在Redis中，通过采用分组（分轮）策略来提高估值的准确率，将一个以bit为单位、长度为L的大数组S，平均分为m组（即：m轮），每组占有相同的比特个数，设为p。得出以下关系：

• L = S.length
• L = m * p
• 以K为单位，S（内存占用）= L / 8 / 1024。

在Redis中，HyperLogLog设置为：m=16834，P=6，L=16834 * 6。占用内存 = 16834 * 6 / 8 / 1024 = 12K。

每组用6bit存储k_max的原因：6bit可以存储的最大值为63（即：6bit全部为1），目前计算机一般为64位或32位操作系统，因此6位最节省内存，又能满足需求。

如图所示：

3）对应分组

假设某个key经过hash后得到的bit串为0011001...010101000 00000000000110。其中：

• 低14bit（00000000000110）转换为10进制得到的值为6，即：分组编号为6，对应第6个分组。
• 剩余50bit（0011001...010101000）中，第一个1的位置为4（即：k_max=4），与当前分组编号比较：4<6，不做处理，即：该key对应第6个分组。

统计访问页面的独立用户数

假设要统计访问某个页面的独立用户数，每个用户存在一个唯一的用户ID，将用户ID通过hash散列到不同的分组中，每个分组对应一个k_max，最后将k_max代入公式中得到估算值。估算公式：

内存优化

如果每个key都占用12KB的存储空间，对于那些需求远小于12KB的key，会造成存储空间的浪费。因此，在Redis中，为了节省内存空间，在HyperLogLog内部会采用不同的编码方式进行存储：

• 稀疏编码（默认）：应对数据量小的场景。
• 密集编码：应对数据量大的场景。

HyperLogLog底层采用SDS结构存储数据，为了区分普通字符串，在HyperLogLog头部使用了固定魔法字符串：HYLL。

满足以下任一条件时，稀疏编码会转换为密集编码：

• HyperLogLog中任一分组的计数值（即：k_max）大于32。
• HyperLogLog中存储内容大小超过参数hll-sparse-max-bytes（默认为3000字节）设定的值。

使用示例

客户端示例：

127.0.0.1:6379> pfadd page user1                # 添加key
(integer) 1
127.0.0.1:6379> pfcount page                    # 估算结果
(integer) 1
127.0.0.1:6379> pfadd page user2 user3 user4
(integer) 1
127.0.0.1:6379> pfcount page
(integer) 4
127.0.0.1:6379> pfadd page user2 user3 user1    # 添加已经存在的key
(integer) 0
127.0.0.1:6379> pfcount page
(integer) 4
127.0.0.1:6379>

代码实例：

/**
 * HyperLogLog基数统计
 * @return 估算结果
 */
@Override
public long hyperLogLog(){
    for (int i = 0; i < 100000; i++) {
        redisUtil.pfAdd("page","user" + i);
    }
    long result = redisUtil.pfCount("page");
    log.info("用户总数：" + 100000 + "，统计结果 : " + result);
    return result;
}

返回结果：

用户总数：100000，统计结果 : 99785

【阅读推荐】

更多精彩内容，如：

• Redis系列

• 数据结构与算法系列

• Nacos系列

• MySQL系列

• JVM系列

• Kafka系列

请移步【南秋同学】个人主页进行查阅。内容持续更新中......

【作者简介】

一枚热爱技术和生活的老贝比，专注于Java领域，关注【南秋同学】带你一起学习成长～