Redis源码剖析——HyperLogLog

/ 0评 / 0

HyperLogLog算法核心原理

写在前面...

阅读Redis的源码你会发现,里面有个略微奇怪的结构,叫做HyperLogLog。大多数人第一反应这个可能是个日志相关的东西?实际上是Redis里相对复杂的一个非传统算法,其可被用于海量数据的统计。
上次写这篇文章是两年前了,最近因为一些原因重新深入研究了下...

介绍

在许多面向海量数据(千万、亿...)级别的应用中,如何高效的存储与计算是一个重要的话题。记录某个集合有多少个不同的元素被称为基数统计,基数统计是一个非常常见的场景,比如:
- 某个网站的用户UV
- 搜索引擎的关键字数量与词频
- 报警数量监控
- ....

抽象来说,基数统计就是做这样一件事情:假设我们有集合S={a, b, c, ...},对于每一个新的元素x,我们需要判断元素x是否已经已经存在于集合S中,若存在则丢弃,不存在则加入,我们需要知道信息就是这个集合S的元素个数。

传统实现

  1. 通用性场景下:跳表、红黑树、AVL树、B族树...
  2. 整数统计场景下:BitMap

我们来进行一个简单的场景成本估计:假设对于某搜索引擎,统计搜索某个关键字的不同device_id个数,假设一个device_id地址占用空间4字节,1亿个不同的设备即4亿字节,换算约为380MB,对于红黑树或者跳表等传统数据结构来说,还需要算上大量的指针本身需要的空间,而这也可能仅仅只是一个query

HyperLogLog

只需要12KB内存,就可以对一个key统计将近2^64个基数,错误率仅仅在0.81%左右

算法原理

以下为算法原理推导

核心推导

先回顾下基本的概率论知识。
我们以抛硬币为例子切入,每次抛硬币的结果只能是正面或者反面,对于抛一次硬币这个动作,我们将它称为一次伯努利实验。连续的N次抛硬币,也就是N次连续的伯努利实验,我们将它称为伯努利过程。
下面我们规定如下的伯努利过程:在一轮伯努利过程中连续抛硬币,当硬币第一次为正面的时,我们将当前抛硬币轮次记作K,并终止本轮伯努利过程。
举个🌰:我们抛四次硬币,其结果分别为:反、反、反、正,即有K=4。
接下来,我们将以上的伯努利过程重复n轮,则有以下序列

我们记录将以上多个伯努利过程中的K的最大值记录下来,将其记为Kmax。我们有以下两条显然恒成立的结论:
1. n轮伯努利过程中,每个过程的抛硬币次数都不会大于Kmax
2. n轮伯努利过程中,至少有一轮中抛硬币次数是等于Kmax的
对于以上两个结论,我们通过概率论的极大似然估计方法可以推导出我们的核心公式(准确来说应该是约等于)

比如Kmax=7时,我们就可以反过来估算出n=128
关于这点,可以做个实验验证下,代码很简单,就不放了

稍微优化一下

概率论告诉我们,估计的准确性比较依赖于样本的数量,因此我们将上图中的过程再重复M次,即得到M个Kmax值,计为Kmax_1、Kmax_2、Kmax_3、....、Kmax_M。到这一步,就已经得出了HyperLogLog算法的前人LogLog算法的核心思想。这就是LogLog算法的做法,其公式如下(其中m为进行的轮数,α为调节因子用于降低误差)

在计算机中,我们知道这种思想通常被叫做分桶~
再优化一下
算术平均值公式

调和平均值公式

我们再将算术平均数优化一下,改成调和平均数,调和平均数的优点通过下面一个例子可以看出来:

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

当然还有非常好用的Merge,比如接着上面,我想合并20190414与20190415这两天的uv

参考文献

延伸阅读

发表评论

电子邮件地址不会被公开。 必填项已用*标注