HyperLogLog(关于基数统计)


写在前面

今天在复习Redis的一种在Redis 2.8.9 版本更新的结构的时候,知道了这个数据结构是基于一种优秀的算法HyperLogLog,基数统计算法(简单来说就是统计集合中的元素数量,但是对比set有了很大的优化),就去了解了一下这种算法的精妙之处。

HyperLogLog

这种数据结构在Redis这种NoSQL型数据库中可以非常省内存的去统计各种计数,比如注册 IP 数、每日访问 IP 数、页面实时UV、在线用户数,共同好友数等。这个是应用场景。

127.0.0.1:6379[1]> PFADD k1 a b c d 1 2 3 4 1 2 3 4 5
(integer) 1
127.0.0.1:6379[1]> PFCOUNT k1
(integer) 9
127.0.0.1:6379[1]> PFADD k2 a b c d 1 2 3 
(integer) 1
127.0.0.1:6379[1]> PFMERGE k1 k2
OK
127.0.0.1:6379[1]> PFCOUNT k1
(integer) 9
127.0.0.1:6379[1]> PFADD k2 a b c 5 6 1 2 3 4
(integer) 1
127.0.0.1:6379[1]> PFCOUNT k2
(integer) 10
127.0.0.1:6379[1]> keys *
1) "k2"
2) "k1"
127.0.0.1:6379[1]> PFCOUNT k2
(integer) 10
127.0.0.1:6379[1]> PFCOUNT k1
(integer) 9
127.0.0.1:6379[1]> PFMERGE k1 k2 
OK
127.0.0.1:6379[1]> PFCOUNT k1
(integer) 10

从上面的示例可以看出,有三个操作:PFADD、PFCOUNT、PFMERGE。

优点

1、使用少量内存就可以统计大量的数据,比如在Redis 中一个键为12K,就可以统计2^64的数据量。

2、统计存在一定的误差,误差率整体较低,标准误差为 0.81%(但是对于一些有一定容错率的业务场景,如IP统计、在线用户数等,这种误差是可以忽略不计的);

3、误差可以被设置辅助计算因子进行降低。

原理:来自于一篇论文http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf

参考

关于基数统计 - 知乎

Redis入门 - 数据类型:3种特殊类型详解 | Java 全栈知识体系

11. 优秀的基数统计算法–HyperLogLog - 古明地盆 - 博客园


文章作者: AllenMirac
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 AllenMirac !
  目录