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轮，则有以下序列
{.wp-editor-md-post-content-link}
我们记录将以上多个伯努利过程中的K的最大值记录下来，将其记为Kmax。我们有以下两条显然恒成立的结论：

  1. n轮伯努利过程中，每个过程的抛硬币次数都不会大于Kmax
  2. 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

参考文献

延伸阅读