Redis源码剖析——HyperLogLog
HyperLogLog算法核心原理
写在前面…
阅读Redis的源码你会发现,里面有个略微奇怪的结构,叫做HyperLogLog。大多数人第一反应这个可能是个日志相关的东西?实际上是Redis里相对复杂的一个非传统算法,其可被用于海量数据的统计。
上次写这篇文章是两年前了,最近因为一些原因重新深入研究了下…
介绍
在许多面向海量数据(千万、亿…)级别的应用中,如何高效的存储与计算是一个重要的话题。记录某个集合有多少个不同的元素被称为基数统计,基数统计是一个非常常见的场景,比如:
- 某个网站的用户UV
- 搜索引擎的关键字数量与词频
- 报警数量监控
- ….
抽象来说,基数统计就是做这样一件事情:假设我们有集合S={a, b, c, …},对于每一个新的元素x,我们需要判断元素x是否已经已经存在于集合S中,若存在则丢弃,不存在则加入,我们需要知道信息就是这个集合S的元素个数。
传统实现
- 通用性场景下:跳表、红黑树、AVL树、B族树…
- 整数统计场景下:BitMap
我们来进行一个简单的场景成本估计:假设对于某搜索引擎,统计搜索某个关键字的不同device_id个数,假设一个device_id地址占用空间4字节,1亿个不同的设备即4亿字节,换算约为380MB,对于红黑树或者跳表等传统数据结构来说,还需要算上大量的指针本身需要的空间,而这也可能仅仅只是一个query
HyperLogLog
只需要12KB内存,就可以对一个key统计将近2^64个基数,错误率仅仅在0.81%左右
算法原理
以下为算法原理推导
核心推导
先回顾下基本的概率论知识。
我们以抛硬币为例子切入,每次抛硬币的结果只能是正面或者反面,对于抛一次硬币这个动作,我们将它称为一次伯努利实验。连续的N次抛硬币,也就是N次连续的伯努利实验,我们将它称为伯努利过程。
下面我们规定如下的伯努利过程:在一轮伯努利过程中连续抛硬币,当硬币第一次为正面的时,我们将当前抛硬币轮次记作K,并终止本轮伯努利过程。
举个🌰:我们抛四次硬币,其结果分别为:反、反、反、正,即有K=4。
接下来,我们将以上的伯努利过程重复n轮,则有以下序列
{.wp-editor-md-post-content-link}
我们记录将以上多个伯努利过程中的K的最大值记录下来,将其记为Kmax。我们有以下两条显然恒成立的结论:
- n轮伯努利过程中,每个过程的抛硬币次数都不会大于Kmax
- n轮伯努利过程中,至少有一轮中抛硬币次数是等于Kmax的
对于以上两个结论,我们通过概率论的极大似然估计方法可以推导出我们的核心公式(准确来说应该是约等于)
{.wp-editor-md-post-content-link}
比如Kmax=7时,我们就可以反过来估算出n=128
关于这点,可以做个实验验证下,代码很简单,就不放了
{.wp-editor-md-post-content-link}
稍微优化一下
概率论告诉我们,估计的准确性比较依赖于样本的数量,因此我们将上图中的过程再重复M次,即得到M个Kmax值,计为Kmax_1、Kmax_2、Kmax_3、….、Kmax_M。到这一步,就已经得出了HyperLogLog算法的前人LogLog算法的核心思想。这就是LogLog算法的做法,其公式如下(其中m为进行的轮数,α为调节因子用于降低误差)
{.wp-editor-md-post-content-link}
在计算机中,我们知道这种思想通常被叫做分桶~
再优化一下
算术平均值公式
{.wp-editor-md-post-content-link}
调和平均值公式
{.wp-editor-md-post-content-link}
我们再将算术平均数优化一下,改成调和平均数,调和平均数的优点通过下面一个例子可以看出来:
1000、2000、3000、20000
算术平均值为6500
调和平均数为2124(近似)
调和平均数可以去掉较高数据的影响
Redis的实现
https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c
把抛硬币抽象到计算机中来
如何把抛硬币抽象到计算机来?当然是比特位了,0代表反面,1代表正面,非常简洁。
HpyerLogLog算法对于任何一个输入(可能是字符串,也可能是其他类型,但是这都不影响),将其Hash为一个比特串,比如10010010:第一次抛掷为反面,第二次抛掷为反面,第三次抛掷为反面,第四次抛掷为正面…….
这样,一个比特串就把一个伯努利过程很好的抽象了出来。
任何输入value字符串,都可以通过一个统一的hash函数来将其化为相同为比特位数的uint64
uint64_t MurmurHash64A (const void * key, int len, unsigned int seed) {
// 省略....
return h;
}
找到第一次为正面的实验并确定分桶
// 一些下面源码会用到的宏定义
#define HLL_P 14 //
#define HLL_Q (64-HLL_P)
#define HLL_REGISTERS (1<<HLL_P)
#define HLL_P_MASK (HLL_REGISTERS-1)
#define HLL_BITS 6
int hllPatLen(unsigned char *ele, size_t elesize, long *regp) {
uint64_t hash, bit, index;
int count;
// 求hash值
hash = MurmurHash64A(ele,elesize,0xadc83b19ULL);
// index 计算应该放在哪个桶
// HLL_P_MASK 为 (1 << 14) - 1
// 从这里可以知道 redis定义了2^14 即16384个桶
index = hash & HLL_P_MASK;
hash >>= HLL_P; // 将用来确定分桶的高14位全部置0
// 这句仅仅只是用来保证下面的循环一定可以终止
hash |= ((uint64_t)1<<HLL_Q);
bit = 1;
count = 1;
// 在剩下的50位找出第一个1的位置
while((hash & bit) == 0) {
count++;
bit <<= 1;
}
*regp = (int) index;
return count;
}
插入到桶中
int hllDenseAdd(uint8_t *registers, unsigned char *ele, size_t elesize) {
long index;
// 计算该元素第一个1出现的位置
uint8_t count = hllPatLen(ele,elesize,&index);
return hllDenseSet(registers,index,count);
}
int hllDenseSet(uint8_t *registers, long index, uint8_t count) {
uint8_t oldcount;
// 取出该桶中已被插入的最大值
HLL_DENSE_GET_REGISTER(oldcount,registers,index);
if (count > oldcount) {
// 若当前1的位置大于旧值才更新
HLL_DENSE_SET_REGISTER(registers,index,count);
return 1;
} else {
// 否则不处理,认为不影响基数估计
return 0;
}
}
使用的总内存计算
16384个桶,每个桶空间为6bit
即 (2^14*6) / 8 / 1024 = 12KB
相关使用
在Redis中,关于HyperLogLog在用户层面的操作命令只有几个,核心的便是以下这两ADD与COUNT
{.wp-editor-md-post-content-link}
当然还有非常好用的Merge,比如接着上面,我想合并20190414与20190415这两天的uv
参考文献
延伸阅读
- Google对于HyperLogLog的进一步改进
- 哪些我们常用的地方实际上也用了HLL
- 原文作者:Fh
- 原文链接:http://fhstack.github.io/post/2019-05-12-redisyuanmapouxihyperloglog/
- 版权声明:本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可,非商业转载请注明出处(作者,原文链接),商业转载请联系作者获得授权。