hyperloglog是一种基于概率的基数计数数据结构,所谓基数计数,即是:
基数计数(cardinality counting)通常用来统计一个集合中不重复的元素个数,例如统计某个网站的UV,或者用户搜索网站的关键词数量。数据分析、网络监控及数据库优化等领域都会涉及到基数计数的需求。
大数据量背景下,要实现基数计数,首先需要确定存储统计数据的方案,以及如何根据存储的数据计算基数值;另外还有一些场景下需要融合多个独立统计的基数值,例如对一个网站分别统计了三天的UV,现在需要知道这三天的UV总量是多少,怎么融合多个统计值
对于基数计数,常用的方法有很多,B+树,bitmap,概率算法等等,这里,我们主要讨论概率算法中的一种,即为hyperloglog,常见的概率算法如下:
Hyperloglog的原理涉及到统计学知识,此处就省略了,想要详细了解的,可以参考神奇的HyperLogLog算法,这里主要是讨论中redis中hyperloglog的使用。
- redis中已经提供了hyperloglog这种高级数据结构来解决基数计数问题,HyperLogLog 提供不精确的去重计数方案,虽然不精确但是也不是非常不精确,标准误差是 0.81%,这样的精确度已经可以满足大部分精确的基数计数问题了。
- HyperLogLog 提供了两个指令 pfadd 和 pfcount,根据字面意义很好理解,一个是增加计数,一个是获取计数。pfadd 用法和 set 集合的 sadd 是一样的,来一个用户 ID,就将用户 ID 塞进去就是。pfcount 和 scard 用法是一样的,直接获取计数值
可以看到,hyperloglog的计数还是很精确的,要实验跟大数据下他的表现,就得各位自己去体验了。