日常接需求的时候, PM提出来一个需要统计页面UV/PV的需求你怎么做?

场景

下面有三个选择:

  1. 甩给公司的大数据部门, 让他们搞去
  2. 开始记录ip ,然后去重统计, b数/mysql/redis/hashMap等等
  3. bitmap
  4. 使用 HyperLogLog 算法

首先, 选1的时候看公司架构怎么说, 如果人家给你排期到半个月后了你这需求还做不做了?

其次, 选2是我们的大多数情况, 而且是最直白的一种统计方式. 这种方式的好处就是统计准确, 且能保留住数据, 在特定的业务里面还能复用(比如做个ip黑名单, 反作弊啥的). 当然缺点也很明显, 如果你的服务请求量特别大, 那么你存储数据的体积增长特别快.

比如放到redis的集合里面(曾经我就这么干过), 把所有请求的ip存到redis中, 最后统计集合中元素的个数, 后来运维开始在群里嚷嚷:咱们缓存服务的内存要不够用啦! 运维把大key一列, 嗯? xx, 你这缓存能优化一下不? 这几百mb的冷数据扔缓存里面太浪费资源了balabala

总之就是你得优化一下了, 那么怎么优化呢?

bitmap也是一种不错的方式, 把十进制映射到bit字节上, 比如 10000000 个基数, 那么转换后就变成了 100000000/8/1024/1024 ≈ 12M, 这也是个不错的选择, 不过key很多的情况下占用空间也不少

经过我一番谷歌+翻文档, 发现了这么个神奇的东西: HyperLogLog, 基于概率这种玄学的算法

在redis中的使用

Redis 在 2.8.9 版本添加了 HyperLogLog 结构, 它的优势就是每个key仅需12kb的内存, 就能存储 2^64 个不同元素的基数, 存储空间小且固定, 缺点就是元数据无法直接提取了

这种是基于概率的算法, 既然是概率就包含着不确定性, 存在统计误差, 不过大部分场景是能hold住的, 如果需要绝对精确的情况, 不要用这个

使用的命令如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
127.0.0.1:6379> PFADD test_uv id1 id2 id3 id4 id1
(integer) 1
127.0.0.1:6379> PFCOUNT test_uv
(integer) 4
127.0.0.1:6379> PFADD test_uv2 id1 id2 id5
(integer) 1
127.0.0.1:6379> PFMERGE test_uv3 test_uv test_uv2
OK
127.0.0.1:6379> PFCOUNT test_uv3
(integer) 5

PFADD 添加基数

PFCOUNT 统计个数

PFMERGE 两个key合并

就是这么简单, 粗暴

算法原理

这个我也是看的别人的, 所以就把这两篇文章列出来自己复习一下: