redis高级数据结构HyperLogLog

背景

在开始这一节之前，我们先思考一个常见的业务问题：如果你负责开发维护一个大型的网站，有一天老板找产品经理要网站每个网页每天的 UV 数据，然后让你来开发这个统计模块，你会如何实现？

如果统计 PV 那非常好办，给每个网页一个独立的 Redis 计数器就可以了，这个计数器的 key 后缀加上当天的日期。这样来一个请求， incrby 一次，最终就可以统计出所有的 PV数据。

但是 UV 不一样，它要去重，同一个用户一天之内的多次访问请求只能计数一次。这就要求每一个网页请求都需要带上用户的 ID，无论是登陆用户还是未登陆用户都需要一个唯一ID 来标识。

你也许已经想到了一个简单的方案，那就是为每一个页面一个独立的 set 集合来存储所有当天访问过此页面的用户 ID。当一个请求过来时，我们使用 sadd 将用户 ID 塞进去就可以了。通过 scard 可以取出这个集合的大小，这个数字就是这个页面的 UV 数据。没错，这是一个非常简单的方案。

但是，如果你的页面访问量非常大，比如一个爆款页面几千万的 UV，你需要一个很大
的 set 集合来统计，这就非常浪费空间。如果这样的页面很多，那所需要的存储空间是惊人的。为这样一个去重功能就耗费这样多的存储空间，值得么？其实老板需要的数据又不需要太精确， 105w 和 106w 这两个数字对于老板们来说并没有多大区别， So，有没有更好的解决方案呢？

这就是本节要引入的一个解决方案， Redis 提供了 HyperLogLog 数据结构就是用来解决这种统计问题的。 HyperLogLog 提供不精确的去重计数方案，虽然不精确但是也不是非常不精确，标准误差是 0.81%，这样的精确度已经可以满足上面的 UV 统计需求了。

HyperLogLog 数据结构是 Redis 的高级数据结构，它非常有用，但是令人感到意外的
是，使用过它的人非常少。

常见API

HyperLogLog 提供了两个指令 pfadd 、 pfcount和pfmerge，根据字面意义很好理解，一个是增加计数，一个是获取计数。 pfadd 用法和 set 集合的 sadd 是一样的，来一个用户 ID，就将用户 ID 塞进去就是。 pfcount 和 scard 用法是一样的，直接获取计数值。pfmerge用于将多个 pf 计数值累加在一起形成一个新的 pf 值（比如在网站中我们有两个内容差不多的页面，运营说需要这两个页面的数据进行合并。其中页面的 UV 访问量也需要合并，那这个时候 pfmerge 就可以派上用场了）。

HyperLogLog API中pf* 这个 pf 是什么意思？
它是 HyperLogLog 这个数据结构的发明人 Philippe Flajolet 的首字母缩写。

注意事项

HyperLogLog 这个数据结构不是免费的，不是说使用这个数据结构要花钱，它需要占据一定 12k 的存储空间，所以它不适合统计单个用户相关的数据。如果你的用户上亿，可以算算，这个空间成本是非常惊人的。但是相比 set 存储方案， HyperLogLog 所使用的空间那真是可以使用千斤对比四两来形容了。

不过你也不必过于当心，因为 Redis 对 HyperLogLog 的存储进行了优化，在计数比较
小时，它的存储空间采用稀疏矩阵存储，空间占用很小，仅仅在计数慢慢变大，稀疏矩阵占用空间渐渐超过了阈值时才会一次性转变成稠密矩阵，才会占用 12k 的空间。

实现原理

1、哈希函数

• 作用：使用一个强散列函数将输入的元素映射为固定长度的二进制串。这个哈希函数能保证输出的哈希值均匀分布，使得每个二进制位上出现0和1的概率均等，从而保证了统计的准确性。
• 举例：假设有元素“user1”“user2”等，经过哈希函数处理后，会得到对应的二进制串，如“user1”可能被哈希为“10100100”。

2、前导零统计

• 计算方法：对于每个元素经过哈希后的二进制串，统计从最高位开始连续零的个数，即前导零个数。前导零个数反映了元素哈希值的稀有程度，间接表示了元素的独特性。
• 举例：对于二进制串“10100100”，从最高位开始连续的零有2个，所以其前导零个数为2。一般来说，前导零个数越多，该元素的哈希值就越稀有，在整个数据集中越独特。

3、存储与计数

• 桶数组：Redis中的HyperLogLog结构内部维护了一个大小固定的桶数组，默认大小为
  2^14=16384个桶。每个桶用于存储对应的元素哈希值所观察到的最大前导零个数。
• 更新操作：当添加新的元素时，它会被哈希并找到对应的桶来更新该桶中的最大前导零计数值。如果新元素的前导零个数大于当前桶中存储的值，则更新桶中的值为新元素的前导零个数。

4、基数估算

• 计算方式：利用统计的所有桶中最长的前导零序列，通过预定义的公式计算出一个近似的基数（唯一元素数量）。这个公式基于概率论和统计学原理，通过对桶中最大前导零计数值的分析，推算出整个数据集的基数。
• 误差控制：标准误差大约是0.81%，这意味着对于大量数据，HyperLogLog能够以相对较小的误差估计基数。

pf 的内存占用为什么是 12k？

在 Redis 的 HyperLogLog实现中用到的是 16384 个桶，也就是 2^14，每个桶的 maxbits 需要 6 个 bits 来存储，最大可以表示 maxbits=63，于是总共占用内存就是 2^14 * 6 / 8 = 12k 字节。

总结

HyperLogLog 数据结构来进行估数，它非常有价值，可以解决很多精确度不高的统计需求。但是如果我们想知道某一个值是不是已经在 HyperLogLog 结构里面了，它就无能为力了，它只提供了 pfadd 和 pfcount 方法，没有提供 pfcontains 这种方法。HyperLogLog 底层通过桶、hash函数来对数据进行存储。