HyperLogLog Counting 算法

知其然必知其所以然,最近在看redis的义总问了我一个问题:一个网站的uv是怎么实现的?(当访问量非常大的时候,uv>1000,000,000的时候,还能用redis吗?)我最近正好搭了这个博客,pv和uv都是直接用的不蒜子这个插件,前两天也正好在想他这个uv是怎么实现的?

于是义总带我走进了HyperLogLog的世界:(以下简称HLL算法)

参考资料:

HLL算法的使用场景

HyperLogLog Counting是一种基数计数方法,它的优点:速度极快(常数时间),占用空间极小。缺点:只适用于统计页面UV(unique visitor)、微博的点赞数这种对精确度要求不是很高,且不需要返回集合内所有元素的场景。

  • 已知1亿bit数据,占用空间100000000/8/1024/1024≈12MB。
  • 假设我们统计的是用户ip地址,每个ip地址占用空间32bit。

几种基数计数方法,统计1个页面,数据量达到1亿条ip时,所占用的空间及时间复杂度对比:

B树 Bitmap redis的HyperLogLog算法
占用空间大小 32x12 ≈ 384MB 12MB 12KB
时间复杂度 O(logN) O(N) O(1)

HyperLogLog另一个特性

想统计今天和昨天两天合起来的uv,HyperLogLog也可以直接取两个天的ip取并集,返回近两天的uv。
而其他算法只能重新统计。

HLL算法原理

在基数计数方面,HyperLogLog之所以这么牛X,这么神秘,完全是因为它站在了概率统计这个巨人的肩膀上,根据伯努利实验总结出公式如下:

N:整个数据集合里面数据的数量(基数)
K:数据集每进来一个元素,对这个元素进行一次二进制hash,k表示hash值第一个1的位置。
Kmax:所有这些K中,最大的那个值。(它一定小于等于N)

(伯努利实验)证明:

抛硬币,正面朝上记为1,反面朝上记为0,连续抛X次,第一次出现正面时的投掷次数记为k。这个抛硬币的过程称为伯努利过程。对于n次伯努利过程,我们可以得到n个首次出现正面的投掷次数, ……,其中最大值记为,那么可以得到下面两个结论:

  1. n次伯努利过程的首次出现正面的投掷次数都不大于
  2. n次伯努利过程,至少有一次的首次出现正面的投掷次数等于

对于结论1,用数学公式可以表示为:,当n ≫ 时, ≈ 0。但是 = 1,所以n不可能远大于
对于结论2,用数学公式可以表示为:,当n ≪ 时, ≈ 0。但是 = 1,所以n也不可能远小于

因此我们可以得出结论,n ≈

HLL算法讲解

分桶平均

很显然,每次根据抛硬币来推测:我这种情况抛多少次能抛出来。这种“预估方法”误差有点大。
因此 HLL算法并不适用于当数据量非常小的时候,统计集合的基数。

只有当数据量上来的时候,做这种统计估计才有意义。同时HLL算法为了节省空间,引入了分桶平均的概念。基本原理是:将统计数据划分为m个桶(将元素的二进制hash % m),分别统计各个桶的值,求调和平均数(所有数的倒数的平均数,可以消除掉极大值和极小值对平均数结果带来的误差),进而得出整个集合的基数预估值 N。

Java代码实现:HyperLogLogCounting

偏差修正

上述经过分桶平均后的估计量看似已经很不错了,不过通过数学分析可以知道这并不是基数N的无偏估计。这部分的具体数学分析在“Loglog Counting of Large Cardinalities”中。

因此需要修正成无偏估计。方法:

  1. 增大桶的数量(增大数组长度)桶越多,每个统计数组越长,误差越小,但存储成本也就越大。
  2. 分阶段修正。

Redis中HyperLogLog的实现

Redis应用HyperLogLog的三个命令:PFADD、PFCOUNT、PFMERGE

Redis 的 HyperLogLog 实现中使用了 16384 个桶,也就是 2^14。
每次进来一个元素,对这个元素进行一次二进制hash的长度为64bit,因此每个桶需要用6bit的空间来装这个桶里面的Kmax值。
所以总共占用内存就是 2^14 * 6 / 8 = 12k 字节。
因为最大可以K值为63,所以redis理论上可以统计的集合的基数的最大值为 2^63。

同时Redis 对 HyperLogLog 的存储进行了优化,在计数比较小时,它的存储空间采用稀疏矩阵存储,空间占用很小,仅仅在计数慢慢变大,稀疏矩阵占用空间渐渐超过了阈值时才会一次性转变成稠密矩阵,才会占用 12k 的空间。


附两个数学公式的白话解释

结论1【n次伯努利过程的首次出现正面的投掷次数都不大于】数学公式 的白话解释:

  • 已知1次抛硬币正面朝上的概率为1/2,反面朝上的概率为(1 - 1/2)
  • 1次伯努利过程,第次还没出现正面(前次都是反面)的概率为: = =
  • 1次伯努利过程,投掷不大于次就出现正面的概率为:
  • n次伯努利过程,投掷不大于次就出现正面的概率为:

结论2【n次伯努利过程,至少有一次的首次出现正面的投掷次数等于】公式 的白话解释:

  • 已知1次伯努利过程,投掷不大于次就出现正面的概率为:1 -
  • n次伯努利过程,
    = 1 -
    = 1 -
    = 1 -
    = 1 -

本文标题:HyperLogLog Counting 算法

文章作者:NibNait  

发布时间:2019年07月03日 - 02:07

最后更新:2019年07月16日 - 02:07

原始链接:https://tianbin.org/learning/HyperLogLog/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%