阅读 143

Redis应用-HyperLogLog

系列文章

如果你要统计网站的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字节

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

关注下面的标签,发现更多相似文章
评论