前言

很久之前面团子的时候没问到如何进行UV，PV统计，当时回答得不是很好，只是提到到可以用Redis的hyperloglog进行UV统计，但是如何进行统计，用了有什么好处，却不能回答上来。过去了这么久，最近忽然项目上某个点又让我想起这回事，于是回过来学习一遍。

UV统计

比如我现在的博客，对于上面的每篇文章，我希望统计每天有多少唯一的用户访问了该文章，如何实现统计？

Set统计

这是最直接能想到的方案，对于每篇文章，有个Set对应，每次有访客访问文章，直接把用户uid加入到set里面，最后直接获取set的size就能实现了。但是实际在这种情景下，我关注的是用户的最终数量，而不是具体的用户，把用户的信息也存入set中，难免造成了空间的浪费。

布隆过滤器统计

类似set的改进思想，我现在不存用户的具体信息，只要判断用户是否存在，用户是否唯一。如何实现？可以考虑使用BitMap来实现。

具体的，使用一个BitMap，将用户的uid进行哈希取模，再直接存入BitMap，这样就能减少了不必要的空间浪费，考虑到哈希冲突的话，最终的数量结果必然存在一定的偏差，同时在用户量实际很大的情况下，BitMap也会变得很大，这种方案也是不能采取的。

HyperLogLog统计

使用Redis的hyperloglog进行统计。hyperloglog是Redis提供的一个天然适合UV统计的数据结构，它的固定大小是12k，但是却能支持统计最大2^64个数，也就是达到十亿级别，对于一般的业务绰绰有余。但是由于内部采用的相关的概率计算，也导致了结果存在*0.81%*的偏差。但是对于UV统计的大部分场景来说基本能满足要求了。

具体使用的话，用redis-cli可以看看直接使用的方法：

1
2
3
PFADD uv_10_21 xiaoming		# 添加计数
PFCOUNT uv_10_21	#获取计数
PFMERGE uv_weekly uv_10_21 uv_10_22 	# 合并

其实也就是这三个主要的命令。

HyperLogLog的实现

其实看完HyperLogLog，自然会有几个疑问？

  • 如何做到只使用12kb统计的？
  • 为什么会存在0.81%的偏差呢？

看完他的实现原理，上面两点大概也能了解清楚了。

伯努利试验

现在开始抛硬币，抛出的结果是可正可反，理论上正反的概率都是**50%**。

那么可以这样定义一次完整的伯努利试验：抛n次硬币，直到出现一次正面。

现在进行k次伯努利试验，可能出现这样的结果：

1
2
3
4
第一次试验: 抛了3次才出现正面，此时 k=1，n=3
第二次试验: 抛了2次才出现正面，此时 k=2，n=2
第三次试验: 抛了6次才出现正面，此时 k=3，n=6
.....

能自然得到一个结论：

  1. k次伯努利过程的投掷次数都不大于 n_max。
  2. k次伯努利过程，至少有一次投掷次数等于 n_max

这个结论貌似没什么用？往一个场景发散，假设我现在运气极差，我能不能直到一万次，乃至一亿次才投出一个正面？能，理论上当然能，但是这是一种极小概率的事情，但是并不是不能发生，如果发生了，那么极大概率我进行了极多次的伯努利试验。

那么在次数足够多的情况下，我们可以得出一个极大似然估计：k = 2^（n_max）

优化

继续上面的投硬币，很明显存在很大的问题。比如我现在实际只进行了100次试验，也就是n=100，但是中间走走狗屎运，直接连抛100次才抛出硬币正面，即k=100，那么按照上面的公式计算出来的k和实际的k就存在很大的差值了。

有没有方法解决？上面的例子就是的原因是k_max的由于偶然性导致偏大导致估算n时出现了问题。那么多进行几轮，记录每次的k_max，最后取平均值不就解决问题了吗？考虑到平均性，采用效果更好的调和平均数。即：

image-20241027181800536

实际算法

上面提到的实际只是概率论上的一个算法，而和HyperLogLog之间有何关系呢？回到到最初的问题，现在要进行唯一值统计，那么假设统计对象每次就是一次伯努利试验，统计k个对象就是相当于进行了k次伯努利试验，那么现在就能够通过记录伯努利试验中的抛掷硬币次数n_max，反推出进行的实际伯努利试验次数k。考虑到上面提到的偏差性，进行统计的时候取调和平均值，最终减少估算值的偏差。

比特串

现在有两个问题：

  1. 统计的对象如何转换成一次伯努利试验？
  2. 伯努利试验是个概率性试验，如何保证随机性？

这两个问题其实都可以通过哈希函数来实现，通过对对象进行哈希计算，得到一个固定长度的比特串。这些哈希函数具有良好的随机性特性，使得输入数据被均匀分布到比特串的所有可能状态。这种随机性是算法估算效果的基础，因为它确保了输入数据不会集中在某些特定桶中。

对于比特串，0表示反面，1表示正面，从低位开始读，直到获取到1，那么中间的位数就相当于伯努利试验的投掷硬币次数n。

分桶策略

如何模拟多轮试验？HyperLogLog中采用一个分桶策略，每个桶相当于一轮伯努利试验，也就是每次的伯努利试验的结果n，随机放入到一个桶中，最后对所有桶的n，进行取调和平均值，得到最终的试验次数k。而对于一个比特串，分成高位和低位，高位部分再进行哈希取模，得到桶所在的索引，对低位部分，再进行上面所说的“伯努利试验”，得到n_max，并更新到对应的桶中。

最终算法

实际中，HyperLogLog除了上面所说的，还引入了一个校准常数αm，这个常数比较复杂吧，博主也没展开去了解，它大概的作用应该就是进一步保证结果的准确性。那么最终得到的公式就是：

image-20241027214553631

其中E就是总数据量，也就是上面说的n，m是桶的数量，也就是2^b，M[i]就是第i个桶中的n_max。

基于上面这个公式，进一步讲的话在数据较少或较多的情况下，还会进行小基数或者大基数修正，这里也不展开讲了。

讨论

Q：HyperLogLog为什么固定消耗12kb?

分桶策略决定的，默认情况下HyperLogLog有2^14个桶，也就是16384 个桶。对于某个桶，采用6位的空间来保存最终的k_max

Q：HyperLogLog理论上统计的上限是多少？

由桶的位数决定的，默认情况下桶的6位的，即2^6=64，那么能记录的最大k_max为2^64，统计上限也就是这个。

Q：为什么桶要设置成6位的呢？

  1. 前导零计数范围
    • 计数值表示的是哈希值的前导零数量。如果使用 6 位的计数值，那么最多可以记录到 63，因为 6 位的整数范围是 0 到 63。
    • 在基数估计中，记录前导零数量到 63 已经足够，因为超过这个值对于估算误差的贡献变得很小，同时很少会出现更长的前导零。
  2. 节省内存
    • 每个桶用 6 位记录前导零数量，相较于使用 8 位（1 字节）或更大位数，6 位更节省内存。HyperLogLog 设计时就是为了在大数据场景下尽可能压缩内存使用，这样既能保证精度，又能降低空间需求。
    • 在实现时，6 位的存储可以用不同的优化手段，如位压缩，进一步降低内存消耗。
  3. 理论与精度平衡
    • 6 位的前导零计数足以支持 HyperLogLog 达到 1.6% 左右的估计精度。增加更多位数不会显著提升精度，反而会增加内存开销，因此选择 6 位作为桶的计数值是经过实验和理论验证的合理选择。