本章内容
简介
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领域，关注【南秋同学】带你一起学习成长～