2023-06-13：统计高并发网站每个网页每天的 UV 数据，结合Redis你会如何实现？

答案2023-06-13：

选用方案：HyperLogLog

如果统计 PV （页面浏览量）那非常好办，可以考虑为每个网页创建一个独立的 Redis 计数器，并将日期添加为键（key）的后缀。当网页收到请求时，对应的计数器将被递增。对于每天的访问数据，您可以为该日期创建一个新的 Redis 计数器。

但是 UV（独立访客数） 不一样，它要去重，确保同一用户在一天之内的多次访问只被计数一次。为了实现这一点，每个请求都需要带上一个唯一的用户标识符（ID），以便对用户进行去重。

一种简单的实现方式是为每个页面创建一个独立的 Redis Set 集合，用于存储当天访问该页面的用户 ID。当有新的请求过来时，可以使用 Redis 的 SAdd 命令将用户 ID 添加到集合中。通过 Redis 的 SCard 命令可以获取集合大小，从而获得该页面的 UV 数据。

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

这就是HyperLogLog的用武之地，Redis 提供了 HyperLogLog 数据结构就是用来解决这种统计问题的。虽然 HyperLogLog 提供的是不精确的去重计数方案，但误差在一定范围内，例如 Redis 提供的 HyperLogLog 数据结构的标准误差为 0.81%，这样的精确度已经可以满足很多实际需求。

因此，对于大规模元素的去重计数问题，使用 HyperLogLog 的优点在于在满足精度要求的同时大大减少了存储空间的占用。这种算法被广泛用于大规模的在线去重计数场景中，例如计算裸访客（naked visitors）和独立 IP 访问者等。在实际使用中，需要根据具体的应用场景和数据特点选择合适的参数（比如哈希函数、采样次数等），以求得更好的精确度和性能表现。

HyperLogLog与集合方案对比

百万级用户访问网站

image.png

HyperLogLog使用

操作命令

HyperLogLog提供了3个命令: pfadd、pfcount、pfmerge。

pfadd

pfadd key element [element …]

pfadd用于向HyperLogLog 添加元素,如果添加成功返回1:

pfadd u-9-30 u1 u2 u3 u4 u5 u6 u7 u8

image.png

pfcount

pfcount key [key …]

pfcount用于计算一个或多个HyperLogLog的独立总数，例如u-9-30 的独立总数为8:

image.png

如果此时向插入一些用户，用户并且有重复

image.png

如果我们继续往里面插入数据，比如插入100万条用户记录。内存增加非常少，但是pfcount 的统计结果会出现误差。

pfmerge

pfmerge destkey sourcekey [sourcekey ... ]

pfmerge可以求出多个HyperLogLog的并集并赋值给destkey，请自行测试。

可以看到，HyperLogLog内存占用量小得惊人，但是用如此小空间来估算如此巨大的数据，必然不是100%的正确，其中一定存在误差率。前面说过，Redis官方给出的数字是0.81%的失误率。

HyperLogLog原理概述

基本原理

HyperLogLog 算法是基于概率论中的伯努利试验，并结合了极大似然估算方法，并做了分桶优化。

实际上，在大数据场景中，目前还没有发现更好的高效算法来准确计算基数。因此，在不需要追求绝对准确性的情况下，使用概率算法是解决这一问题的一个不错方案。概率算法不直接存储数据集合本身，通过一定的概率统计方法来估算基数，这种方法可以大大节省内存，同时保证误差控制在一定范围内。目前用于基数计数的概率算法包括：

举个例子来理解HyperLogLog 算法，有一天A和B玩打赌的游戏。

规则如下: 抛硬币的游戏，每次抛的硬币可能正面，可能反面，没回合一直抛，直到每当抛到正面回合结束。

然后我跟B说，抛到正面最长的回合用到了7次，你来猜一猜，我用到了多少个回合做到的？

image.png

进行了n次实验，比如上图：

第一次试验: 抛了3次才出现正面，此时 k=3，n=1

第二次试验: 抛了2次才出现正面，此时 k=2，n=2

第三次试验: 抛了4次才出现正面，此时 k=4，n=3

…………

第n 次试验：抛了7次才出现正面，此时我们估算，k=7

B说大概你抛了128个回合。这个是怎么算的。

k是每回合抛到1所用的次数，我们已知的是最大的k值，可以用kmax表示。由于每次抛硬币的结果只有0和1两种情况，因此，能够推测出kmax在任意回合出现的概率 ，并由kmax结合极大似然估算的方法推测出n的次数n = 2^(k_max) 。概率学把这种问题叫做伯努利实验。

但是问题是，这种本身就是概率的问题，我跟B说，我只用到12次，并且有视频为证。

所以这种预估方法存在较大误差，为了改善误差情况，HLL中引入分桶平均的概念。

同样举抛硬币的例子，如果只有一组抛硬币实验，显然根据公式推导得到的实验次数的估计误差较大；如果100个组同时进行抛硬币实验，受运气影响的概率就很低了，每组分别进行多次抛硬币实验，并上报各自实验过程中抛到正面的抛掷次数的最大值，就能根据100组的平均值预估整体的实验次数了。

分桶平均的基本原理是将统计数据划分为m个桶，每个桶分别统计各自的kmax,并能得到各自的基数预估值，最终对这些基数预估值求平均得到整体的基数估计值。LLC中使用几何平均数预估整体的基数值，但是当统计数据量较小时误差较大；HLL在LLC基础上做了改进，采用调和平均数过滤掉不健康的统计值。

什么叫调和平均数呢？举个例子

求平均工资：A的是1000/月，B的30000/月。采用平均数的方式就是：(1000 + 30000) / 2 = 15500

采用调和平均数的方式就是：2/(1/1000 + 1/30000) ≈ 1935.484

可见调和平均数比平均数的好处就是不容易受到大的数值的影响，比平均数的效果是要更好的。

结合Redis的实现理解原理

现在我们和前面的业务场景进行挂钩：统计网页每天的 UV 数据。

从前面的知识我们知道，伯努利实验就是如果是出现1的时机越晚，就说明你要做更多的实验，这个就好比你要中500万的双色球，你大概要买2000万张不同的彩票（去重），而如果是换成 二进制来算，可能是 第几十次才出现1。而你买一个中奖只有500块的排列3（3个10进制数），而如果是换成 二进制来算，你只需要10次左右出现1。

1.转为比特串

这里很重要的一点：hash函数，可以把不同的数据转成尽量不重复的数据，这点就有点像去重。

如果是64位的二进制，是不是hash函数可以把 2的64次方个不同的数据转成不一样的二进制。这里就跟放入了2的64次方个元素一样。

那么基于上面的估算结论，我们可以通过多次抛硬币实验的最大抛到正面的次数来预估总共进行了多少次实验（多少个不同的数据），同样存储的时候也可以优化，每次add一个元素时，只要算法最后出现1的位数，把这个位数做一个最大的替换久可以。（如果添加的元素比 记录之前位数小则不记录，只要大才记录）

2.分桶

分桶就是分多少轮。抽象到计算机存储中去，就是存储的是一个以单位是比特(bit)，长度为 L 的大数组 S ，将 S 平均分为 m 组，注意这个 m 组，就是对应多少轮，然后每组所占有的比特个数是平均的，设为 P。容易得出下面的关系：

比如有4个桶的话，那么可以截取低2位作为分桶的依据。

比如

10010000 进入0号桶

10010001 进入1号桶

10010010 进入2号桶

10010011 进入3号桶

Redis 中的 HyperLogLog 实现

pfadd

image.png

当我们执行这个操作时，lijin这个字符串就会被转化成64个bit的二进制比特串。

这里很重要的一点：hash函数，可以把不同的数据转成尽量不重复的数据，这点就有点像去重。

如果是64位的二进制，是不是hash函数可以把 2的64次方个不同的数据转成不一样的二进制。这里就跟放入了2的64次方个元素一样。

那么基于上面的估算结论，我们可以通过多次抛硬币实验的最大抛到正面的次数来预估总共进行了多少次实验（多少个不同的数据），同样存储的时候也可以优化，每次add一个元素时，只要算法最后出现1的位数，把这个位数做一个最大的替换久可以。（如果添加的元素比 记录之前位数小则不记录，只要大才记录）

0010....0001 64位

然后在Redis中要分到16384个桶中（为什么是这么多桶：第一降低误判，第二，用到了14位二进制：2的14次方=16384）

怎么分？根据得到的比特串的后14位来做判断即可。

image.png

根据上述的规则，我们知道这个数据要分到 1号桶，同时从左往右（低位到高位）计算第1个出现的1的位置，这里是第4位，那么就往这个1号桶插入4的数据（转成二进制）

如果有第二个数据来了，按照上述的规则进行计算。

那么问题来了，如果分到桶的数据有重复了（这里比大小，大的替换小的）：

规则如下，比大小（比出现位置的大小），比如有个数据是最高位才出现1，那么这个位置算出来就是50，50比4大，则进行替换。1号桶的数据就变成了50（二进制是110010）

所以这里可以看到，每个桶的数据一般情况下6位存储即可。

所以我们这里可以推算一下一个key的HyperLogLog只占据多少的存储。

16384*6 /8/1024=12k。并且这里最多可以存储多少数据，因为是64位吗，所以就是2的64次方的数据，这个存储的数据非常非常大的，一般用户用long来定义，最大值也只有这么多。

pfcount

进行统计的时候，就是把16384桶，把每个桶的值拿出来，比如取出是 n,那么访问次数（里面）就是2的n次方。

image.png

然后把每个桶的值做调和平均数，就可以算出一个算法值。

同时，在具体的算法实现上，HLL还有一个分阶段偏差修正算法。我们就不做更深入的了解了。

image.png

const和m都是Redis里面根据数据做的调和平均数。

福大大架构师每日一题java当死，golang当立。最新面试题，涉及golang，rust，mysql，redis，云原生，算法，分布式，网络，操作系统。561篇原创内容

公众号

收录于合集 #福大大架构师每日一题

832个

上一篇文心一言 VS 讯飞星火 VS chatgpt （40）-- 算法导论5.4 4题