用户日活月活怎么统计 - Redis HyperLogLog 详解

HyperLogLog

提出问题

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

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

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

如果访问量很大,需要涉及很多数据的存储、去重,内存消耗很大。

Set自不必说,消耗很好。bitmap相比于Set也大大节省了内存,我们来粗略计算一下,统计1亿个数据的基数,需要的内存是:100000000/8/1024/1024 ≈ 12M。当数据量上去了,还是会消耗很大。

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

概念

HyperLogLog 是一种概率数据结构,用来估算数据的基数。数据集可以是网站访客的 IP 地址,E-mail 邮箱或者用户 ID。

基数就是指一个集合中不同值的数目,比如 a, b, c, d 的基数就是 4,a, b, c, d, a 的基数还是 4。虽然 a 出现两次,只会被计算一次。

Redis 的 HyperLogLog 通过牺牲准确率来减少内存空间的消耗,只需要12K内存,在标准误差0.81%的前提下,能够统计2^64个数据。所以 HyperLogLog 是否适合在比如统计日活月活此类的对精度要不不高的场景。

HyperLogLog 在 Redis 中的使用

Redis 提供了 PFADDPFCOUNTPFMERGE 三个命令来供用户使用 HyperLogLog。

PFADD 用于向 HyperLogLog 添加元素。

> PFADD visitors alice bob carol
(integer) 1
> PFCOUNT visitors
(integer) 3

如果 HyperLogLog 估计的近似基数在 PFADD 命令执行之后出现了变化, 那么命令返回 1 , 否则返回 0 。 如果命令执行时给定的键不存在, 那么程序将先创建一个空的 HyperLogLog 结构, 然后再执行命令。

PFCOUNT 命令会给出 HyperLogLog 包含的近似基数。在计算出基数后,PFCOUNT 会将值存储在 HyperLogLog 中进行缓存,知道下次 PFADD 执行成功前,就都不需要再次进行基数的计算。

PFMERGE 将多个 HyperLogLog 合并为一个 HyperLogLog , 合并后的 HyperLogLog 的基数接近于所有输入 HyperLogLog 的并集基数。

> PFADD customers alice dan
(integer) 1
> PFMERGE everyone visitors customers
OK
> PFCOUNT everyone
(integer) 4

基本原理

原文。

最新文章

  1. Java进击C#——语法之多线程
  2. Node.js 学习资源
  3. Excel标题与索引的对应关系
  4. Version history of VC++, MFC and ATL
  5. C#迭代重载等
  6. PoEdu - C++阶段班【Po学校】- 第1课
  7. Linux下Mysql安装
  8. UOJ#61. 【UR #5】怎样更有力气
  9. 第三百五十八天 how can I 坚持
  10. java nio2
  11. Picasso解决 TextView加载html图片异步显示
  12. input内文字点击消失 弹出层,可以写表单
  13. IOS web app一些实用的属性设置
  14. 学习TensorFlow,保存学习到的网络结构参数并调用
  15. 级联Cascade
  16. 根据key删除Map集合中的key-value映射
  17. python 常用代码
  18. elasticsearch安装ik分词器(极速版)
  19. js插件---在线类似excel生成图表插件解决方案
  20. apache的rewrite规则来实现URL末尾是否带斜杠

热门文章

  1. Mysql关键字之Group By(二)
  2. Hashset(不能添加相同的字符进入数组)
  3. Xilinx Zynq-7000 嵌入式系统设计与实现
  4. django中同通过getlist() 接收页面form的post数组
  5. 【Leetcode_easy】1033. Moving Stones Until Consecutive
  6. Flutter状态管理之provide和provider的使用区别
  7. ubuntu 18.04 安装搜狗输入法
  8. C#中HttpWebRequest、WebClient、HttpClient的使用
  9. C 语言函数手册:涵盖字符测试、字符串操作、内存管理、时间换算、数学计算、文件操作、进程管理、文件权限控制、信号处理、接口处理、环境变量、终端控制
  10. 公钥、私钥、数字签名、数字证书、对称与非对称算法、HTTPS