Redis之HyperLogLog(基数统计)

2022-10-26 今日头条搬长你好

HyperLogLog，可能很多人对redis这个功能都很陌生，在日常开发中也很少用到它，或者用了它也没有深入的了解过，下面我们将详细介绍。HyperLogLog简称HLL，它是LogLog算法的升级版，其功能是能够为大数据场景提供“不精确”的去重计数。

该算法具有以下特性：

算法实现复杂，理解难度大
计数存在一定的误差，Redis官方公布的误差率在0.81%左右
通过设置辅助计算因子能够降低误差，辅助因子要根据不同的场景设置
能够使用极少的内存来统计巨量的数据，Redis的实现中统计2^64个数据最大占用空间为16384*6/8/1024 = 12K

HLL算法原理

伯努利试验

要理解该算法，首先要从伯努利试验开始，伯努利试验的基本含义：

伯努利试验（Bernoulli trial，或译为白努利试验）是只有两种可能结果（“成功”或“失败”）的单次随机试验。

抛硬币就是一个典型的场景，硬币拥有正反两面，一次地上抛至落下，最终出现正反面的概率都是50%。假设一直抛一枚硬币直到出现正面为止，只要第一次出现正面我们就记录为一次试验。如果经过n伯努利试验（即出现了n次正面），假设每次试验的投掷次数为k，第一次试验的投掷次数为k1，类推得出第n次试验的投掷次数为kn，那么这 k1 ~ kn 中必然会有一个最大的抛掷次数，我们记为k_max。

由此试验我们可以得到两个结论：

n次伯努利试验的投掷次数都不大于k_max。
n次伯努利试验的投掷次数至少有一次等于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

上述多轮次求平均的算法就是LogLog算法的实现了。

HyerLogLog

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

Redis中的实现

上面的内容我们对伯努利试验到HLL算法的演化过程做了一个简单的推演，那么这种算法如何落地实现呢？如何用更少的内存，更加高性能的方式实现呢？

下面我们来看一个实际的场景：

拼刀刀有一个活动页面，我们需要统计每天该活动页的UV（一个用户的多次点击只算一次）。

我们结合上面的HLL算法很容易得出：

活动页的UV = 预测结果n；
某个用户点击活动页 = 一次试验，m个用户点击就是，m轮次；
输入条件是用户id，那么我们可以使用用户id计得出试验轮次序号与每个轮次的k_max；

用户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实现有两种编码，一种是稀疏编码，一种是密集编码。
稀疏编码：在HLL初期只存入了少量的数据时，存在大量的空桶，如果这个时候仍然用16384个桶来存储会造成很大的空间浪费，因此会利用压缩空间来存储。
密集编码：当桶的数量达到一定数量时，会进行一次编码转换，转换后会形成一个完整的结构，即16384个桶，每个桶占6bit。

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

XZERO编码：操作码由两个字节"01xxxxxx yyyyyyyy"模式表示，其中"xxxxxx yyyyyyyy"表示由1到16384(111111 11111111+1)个连续分组为空， "xxxxxx"为XZERO的高位，"yyyyyyyy"为低位，该编码是HLL的初始结构，大小刚好为两个字节（uint8_t registers[1]）。
ZERO编码：操作码用一个字节"00xxxxxx"模式表示，6位"xxxxxx"表示有1到64(111111+1)个连续分组为空，此编码可以有效压缩空桶。
VAL编码：操作码用一个字节"1xxxxxyy"模式表示，"xxxxx"表示投掷次数，最大次数为32（11111+1），这也是为什么大于32时会发生编码转换的原因，"yy"表示连续（n+1）个分组，此操作码可以表示1到32之间的值，重复1到4次。

HLL相关命令

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使用场景：

统计网站的UV

统计网站不重复用户的访问量（可以用用户id作为输入）。

统计城市交通网中每个红绿灯路口车次

比如我们可以统计经过路口的不同车辆数（可以用车牌作为输入）。

统计大数据集不重复记录数

统计百度每天不同搜索关键词查询的次数。

以上就是Redis HyperLogLog(基数统计)的介绍