Redis 应用-HyperLogLog

系列文章

• Redis应用-分布式锁
• Redis应用-异步消息队列与延时队列
• Redis应用-位图
• Redis应用-HyperLogLog
• Redis应用-布隆过滤器
• Redis应用-限流
• Redis应用-Geo

如果你要统计网站的PV，你可以使用Redis计数器就好了，每来一个请求，调用一次incrby即可。但是如果要统计UV就没那么简单呢，它需要去重，当然你肯定想到了Redis中的去重的Set集合，当一个请求过来使用sadd添加用户ID,通过scard取出集合的大小。但是如果上千万的UV，使用集合来统计，就非常浪费空间了。而Redis提供的HyperLogLog数据结构正是来解决这类统计问题的，当然在数据量很大的情况下，他会有一定的误差。

HyperLogLog算法是一种非常巧妙的近似统计海量去重元素数量的算法。它内部维护了 16384 个桶（bucket）来记录各自桶的元素数量。当一个元素到来时，它会散列到其中一个桶，以一定的概率影响这个桶的计数值。因为是概率算法，所以单个桶的计数值并不准确，但是将所有的桶计数值进行调合均值累加起来，结果就会非常接近真实的计数值。

具体的原理解析可参考探索HyperLogLog算法

使用方法

HyperLogLog 使用比较简单，主要提供提供了两个指令

• pfadd 增加计数
• pfcount 获取计数

HyperLogLog还提供了第三个指令 pfmerge，用于将多个 pf 计数值累加在一起形成一个新的 pf 值。

比如在网站中我们有两个内容差不多的页面，运营需要将两个页面的数据进行合并。其中页面的 UV 访问量也需要合并，这时候就可以使用pfmerge。

pf 的内存只有12k

HyperLogLog 实现中用到的是 16384 个桶，也就是 2^14，每个桶的 maxbits 需要 6 个 bits 来存储，最大可以表示 maxbits=63，于是总共占用内存就是2^14 * 6 / 8 = 12k字节

本文亦在微信公众号【小道资讯】发布，欢迎扫码关注！

本作品采用《CC 协议》，转载必须注明作者和本文链接