如果要我们设计一个基于Redis统计页面UV的实现方案，可能的实现方案有什么？大家可能很容易想到的一个方案就是使用Set对象保存每一个访问页面的用户id，因为Set结构天然就支持去重功能，因此使用scard取出的Set集合大小即为页面UV。但是，如果页面UV非常巨大时，使用Set结构存储就会非常浪费空间。Redis提供了HyperLogLog数据结构来解决这类统计问题，既节省内存占用，又能保证统计结果在可接受的误差之内。

Redis中的HyperLogLog使用

Redis中的HyperLogLog提供了两个指令pfadd和pfcount。pfadd用于增加计数，pfcount用于获取计数。针对上面的统计页面UV的场景，当用户访问页面时，就使用pfadd指令将用户id添加到HyperLogLog中，最后执行pfcount就能获取到页面UV。

HyperLogLog算法介绍

实际上，HyperLogLog是一种够提供不精确的去重计的算法。存在以下的特点：

1. 能够使用极少的内存来统计巨量的数据，在Redis中实现的HyperLogLog，只需要12K内存就能统计2^64个数据。
2. 计数存在一定的误差，误差率整体较低。标准误差为0.81%。
3. 误差可以被设置辅助计算因子进行降低。

伯努利试验

“

伯努利试验是数学概率论中的一部分内容，它的典故来源于抛硬币。

”

硬币拥有正反两面，每次的上抛至落下，出现正反面的概率都是1/2。第一次出现正面的概率是1/2，连续2次出现正面的概率就是1/4, 连续出现K次正面的概率就是2^(-k)。假设一直抛硬币，直到它出现正面为止，我们记录为一次完整的试验，中间可能抛了一次就出现了正面，也可能抛了4次才出现正面。无论抛了多少次，只要出现了正面，就记录为一次试验。这个试验就是伯努利试验。

那么对于n次的伯努利试验，假设每次伯努利试验所经历了的抛掷次数为k。那么第一次伯努利试验，次数设为k1，以此类推，第n次对应的是kn。其中，对于这n次伯努利试验中，必然会有一个最大的抛掷次数k_max。

最终结合极大似然估算的方法，发现在n和k_max中存在估算关联：n * 2^(-k_max)=1，即n = 2^(k_max)。

估算优化

我们只进行n次伯努利试验称为一轮实验。当n足够大的时候，估算的误差率会相对减少，但仍然不够小。但是如果我们进行更多轮次实验，然后再取每轮的 k_max的平均数。最终再估算出 n，这样子的误差就会相对减少很多。下面是LogLog的估算公式：

上面公式的DVLL对应的就是n，constant是修正因子，它的具体值是不定的，可以根据实际情况而分支设置。m代表的是试验的轮数。头上有一横的R就是平均数：(k_max_1 + ... + k_max_m)/m。

这种通过增加试验轮次，再取k_max平均数的算法优化就是LogLog的做法。而 HyperLogLog和LogLog的区别就是，它采用的不是平均数，而是调和平均数。调和平均数比平均数的好处就是不容易受到大的数值的影响。下面举个例子：

程序实现

通过上面的内容我们已经知道，在抛硬币的例子中，可以通过一次伯努利试验中出现的k_max来估算n。

将数据转换为比特串

通过hash函数，将数据转换为比特串，例如输入5，可以转换为为：101。这么做的目的是和抛硬币对上，在比特串中，0代表反面，1代表正面。如果一个数据最终被转化了10010000，那么从右往左看，我们可以认为，首次出现1的时候，就是正面。基于上面的估算结论，我们可以根据存入数据中，转化后的出现了1的最大的位置k_max来估算存入了多少数据，即n = 2^(k_max)。

分桶

分桶就是分多少轮。具体到程序实现上，就是将输入数据hash转换为比特串的时候，先确定桶号，然后再将第一个出现1的个位数值设置到该桶中。

Redis中的HyperLogLog实现

在Redis中的HyperLogLog中，共分为2^14个桶，每个桶有6个bit，占用内存为=2^14*6/8/1024=12K。

当我们执行命令pfadd key value时，首先会通过hash函数将value转换为64位比特串。其中，前14位用来确定分桶(刚好有2^14个桶)，后50位用来获取第一个出现1的位数(从右向左)，因为最大为50，因此使用6个bit完全可以表示。

不同的value，会被设置到不同桶中去，如果出现了在同一个桶的，但是后面第一个出现1的位数不同。那么比较这个桶新的值是否比原来的值大，如果大于，则替换。否则，保持不变。

最终，2^14个桶都保存了出现1的最大值k_max，此时调用pfcount时，按照前面介绍的估算方式，便可以计算出key的设置了多少次valu，也就是统计值，即2^14*2^(k_max平均)。

参考

1. juejin.im/post/684490…
2. juejin.im/post/684490…