如何使用Redis实现页面UV统计-HyperLogLog实现详解

2021/6/17 19:30:20

本文主要是介绍如何使用Redis实现页面UV统计-HyperLogLog实现详解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

Redis中的HyperLogLog使用

Redis中的HyperLogLog提供了两个指令pfaddpfcountpfadd用于增加计数,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次才出现正面。无论抛了多少次,只要出现了正面,就记录为一次试验。这个试验就是伯努利试验。

如果你觉得自己学习效率低,缺乏正确的指导,可以加入资源丰富,学习氛围浓厚的技术圈一起学习交流吧!
[Java架构群]
群内有许多来自一线的技术大牛,也有在小厂或外包公司奋斗的码农,我们致力打造一个平等,高质量的JAVA交流圈子,不一定能短期就让每个人的技术突飞猛进,但从长远来说,眼光,格局,长远发展的方向才是最重要的。

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

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

估算优化

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

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

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

程序实现

通过上面的内容我们已经知道,在抛硬币的例子中,可以通过一次伯努利试验中出现的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个桶,每个桶有6bit,占用内存为=2^14*6/8/1024=12Kredis-hyperloglog

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

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

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

最后

给大家分享一篇一线开发大牛整理的java高并发核心编程神仙文档,里面主要包含的知识点有:多线程、线程池、内置锁、JMM、CAS、JUC、高并发设计模式、Java异步回调、CompletableFuture类等。

文档地址:一篇神文就把java多线程,锁,JMM,JUC和高并发设计模式讲明白了

码字不易,如果觉得本篇文章对你有用的话,请给我一键三连!关注作者,后续会有更多的干货分享,请持续关注!



这篇关于如何使用Redis实现页面UV统计-HyperLogLog实现详解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程