HyperLogLog,可能很多人对redis这个功能都很陌生,在日常开发中也很少用到它,或者用了它也没有深入的了解过,下面我们将详细介绍。HyperLogLog简称HLL,它是LogLog算法的升级版,其功能是能够为大数据场景提供“不精确”的去重计数。
该算法具有以下特性:
要理解该算法,首先要从伯努利试验开始,伯努利试验的基本含义:
伯努利试验(Bernoulli trial,或译为白努利试验)是只有两种可能结果(“成功”或“失败”)的单次随机试验。
抛硬币就是一个典型的场景,硬币拥有正反两面,一次地上抛至落下,最终出现正反面的概率都是50%。假设一直抛一枚硬币直到出现正面为止,只要第一次出现正面我们就记录为一次试验。如果经过n伯努利试验(即出现了n次正面),假设每次试验的投掷次数为k,第一次试验的投掷次数为k1,类推得出第n次试验的投掷次数为kn,那么这 k1 ~ kn 中必然会有一个最大的抛掷次数,我们记为k_max。
由此试验我们可以得到两个结论:
结合极大似然估算的方法,发现n与k_max存在估算关联:n=2^kmax,套用这个公式会发现,当实验次数较小时该算法的误差会非常大,我们来举一个简单的例子:
第1次实验:抛掷1次出现正面,则k=1,n=1
第2次实验:抛掷3次出现正面,则k=3,n=2
第3次实验:抛掷5次出现正面,则k=5,n=3
第n次实验:抛掷k次出现正面,则n=2^k
假设n组实验中k_max=5,最终的实验结果估算n=2^5,如果n很小时,等式很明显不成立
如何减小估算误差呢?通常的做法是增加实验次数,但是只做一轮的话误差率仍然不够小。那如果我们做多个轮次然后求平均呢?
上述多轮次求平均的算法就是LogLog算法的实现了。
HyperLogLog算法在LogLog的基础上做了进一步的优化,为了解决k_max的出现个别大数值导致平均值波动过大的影响,HLL算法将k_max平均替换为调和平均值,具体计算方式变更为:k_max调和平均=m/(1/k_max1 + 1/k_max2 + ... + 1/k_maxn)。
HLL公式
一个可视化的HLL算法演示地址:
http://content.research.neustar.biz/blog/hll.html
上面的内容我们对伯努利试验到HLL算法的演化过程做了一个简单的推演,那么这种算法如何落地实现呢?如何用更少的内存,更加高性能的方式实现呢?
下面我们来看一个实际的场景:
拼刀刀有一个活动页面,我们需要统计每天该活动页的UV(一个用户的多次点击只算一次)。
我们结合上面的HLL算法很容易得出:
用户id如何得到轮次m与每个轮次的k_max呢?我们可以把用户id 通过hash函数计算得到一个bit串,可以使用bit串的低n位来表示实验轮次,用剩下的bit位表示每个轮次的k_max。如图:
用户id计算得到的bit串结构
在Redis中采用MurmurHash64A函数计算出64位的bit串来计算轮次序号与每个轮次的k_max,其中低14位用于计算轮次序号,高50位用于计算轮次的k_max。Redis实现采用了16384轮次(刚好2^14+1次,加1是因为有0),高50位从低位到高位最先出现1的索引位置位为k_max,那么最极端的情况就是第50位出现1,50使用二进制存储最大需要6个二进制位,因此Redis每个轮次的k_max采用了6个bit位存储。因此得到了Redis统计2^64个数使用的空间是:16384*6/8/1024=12k。
说明:如果出现桶冲突,即低14位相同时,高50位保留k_max最大的。
下面我们看一下HLL在Redis中的实际存储结构,如下图:
HLL存储结构
在实际的算法实现中要考虑到空间利用率问题,因此Redis设计了不同的编码来存储不同阶段的统计数据,以此来提升空间利用率,有以下几种编码:
密集编码:
HLL密集编码
密集编码每个桶需要了6bit,那么必然存在跨字节的情况,Redis采用了比较巧妙的方式去定位桶,具体实现如下:
#define HLL_BITS 6 /* Enough to count up to 63 leading zeroes. */
// 二进制为:00111111
#define HLL_REGISTER_MAX ((1<<HLL_BITS)-1)
/* Store the value of the register at position 'regnum' into variable 'target'.
* 'p' is an array of unsigned bytes. */
// 将位置为'regnum'的值存入变量'target','p'是一个无符号字节的数组
// 获取指定桶
#define HLL_DENSE_GET_REGISTER(target,p,regnum) do {
uint8_t *_p = (uint8_t*) p;
// 计算桶所属哪一个字节
unsign计算ed long _byte = regnum*HLL_BITS/8;
// 计算桶起始bit的所属位置
unsigned long _fb = regnum*HLL_BITS&7;
// 处理跨字节
unsigned long _fb8 = 8 - _fb;
// 获取第一个字节中的位
unsigned long b0 = _p[_byte];
// 获取第二个字节中的位
unsigned long b1 = _p[_byte+1];
// 计算跨字节合并后的序列(第一个字节的高_fb位与第二个字节的低_fb8位合并,可结合上面图看)
target = ((b0 >> _fb) | (b1 << _fb8)) & HLL_REGISTER_MAX;
} while(0)
/* Set the value of the register at position 'regnum' to 'val'.
* 'p' is an array of unsigned bytes. */
// 设置指定桶
#define HLL_DENSE_SET_REGISTER(p,regnum,val) do {
uint8_t *_p = (uint8_t*) p;
unsigned long _byte = regnum*HLL_BITS/8;
unsigned long _fb = regnum*HLL_BITS&7;
unsigned long _fb8 = 8 - _fb;
unsigned long _v = val;
// 设置跨字节的第一个字节的低_fb位
_p[_byte] &= ~(HLL_REGISTER_MAX << _fb);
_p[_byte] |= _v << _fb;
// 设置跨字节的第二个字节的高_fb8位
_p[_byte+1] &= ~(HLL_REGISTER_MAX >> _fb8);
_p[_byte+1] |= _v >> _fb8;
} while(0)
稀疏编码:
稀疏编码-XZERO
稀疏编码-ZERO+VAL
PFADD:将一个输入参数存入到HyperLogLog结构中,如果输入引起近似基数变化,该命令返回1,否则返回0。
redis> PFADD hll a b c d e f g
(integer) 1
redis> PFCOUNT hll
(integer) 7
PFCOUNT:返回指定key的近似基数值,支持多个key的查询,当多key查询时,会将多个key的HLL结构合并为一个临时HLL,然后返回这个合并结果的基数值。
redis> PFADD hll foo bar zap
(integer) 1
redis> PFADD hll zap zap zap
(integer) 0
redis> PFADD hll foo bar
(integer) 0
redis> PFCOUNT hll
(integer) 3
redis> PFADD some-other-hll 1 2 3
(integer) 1
redis> PFCOUNT hll some-other-hll
(integer) 6
PFMERGE:将多个HLL结构合并为一个HHL结构。
redis> PFADD hll1 foo bar zap a
(integer) 1
redis> PFADD hll2 a b c foo
(integer) 1
redis> PFMERGE hll3 hll1 hll2
OK
redis> PFCOUNT hll3
(integer) 6
为什么要用使用HyperLogLog?举一个例子:"我们统计一下莎士比亚所有作品中不同的单词数"
数据结构 |
占用字节数 |
词数 |
误差率 |
HashMap |
10447016 |
67801 |
0% |
Bitmap |
3384 |
67080 |
1% |
HyperLogLog |
512 |
70002 |
3% |
可以看出HyperLogLog能够使用更小的空间完成统计,试想如果你统计的是全球每个作者的所有作品中不同的单词数,HyperLogLog的优势就更加突出。但同时其也存在一些统计精度问题。
如果是允许一定误差的统计,可以选择HyperLogLog。如果需要较为精确的统计可以使用Bitmap,详见我的另外一篇文章《Redis之Bitmap(位图)》。下面是一些常见的HyperLogLog使用场景:
统计网站不重复用户的访问量(可以用用户id作为输入)。
比如我们可以统计经过路口的不同车辆数(可以用车牌作为输入)。
统计百度每天不同搜索关键词查询的次数。
以上就是Redis HyperLogLog(基数统计)的介绍