hyperloglog底层剖析

发表于 | 分类于 |
字数统计: 2.3k | 阅读时长 ≈ 8

[TOC]

原理

举一个例子，假设你抛很多次硬币，如果抛到正面，就继续抛；如果抛到反面，就记录下在这之前连续抛到了多少次正面k，然后开始下一轮。

如果你告诉我，你最多的时候，连续抛了2次正面后就抛到反面了。那我认为你可能并没有抛多少轮，可能是3轮或者4轮就会发生这样的情况。

但如果你告诉我，你最多的时候，连续抛了10次正面后就抛到反面了，那我认为你可能抛的轮次比较多，因为连续抛到10次正面的概率是非常小的。那如果要根据这个已知信息估计你总共抛了多少轮硬币呢？这就是HLL的原理。

1
2
3
我们想想抛硬币，反面记0，正面记1，正反面的概率都是1/2。第一次出现正面的位置记为ρ(x)，那么ρ(0001)=3，0001出现的概率是1/23=1/16。换句话讲，就是进行16次实验，很可能出现一次或以上0001。再换句话讲，进行n轮实验，最大ρ(x)为y，那么可以估算进行出n=2y。
我们可以通过多次抛硬币实验的最大抛到正面的次数来预估总共进行了多少次实验，同样可以可以通过第一个1出现位置的最大值k_max来预估总共有多少个不同的数字（整体基数）。
我们只要把要去重的key，转换成一串01字符串，就能套用上面的统计方法了。在数据量小时，误差会比较大.于是引入了桶的概念，计算m个桶的加权平均值，这样就能得到比较准确的答案了

image-20201226154059005

  • 对于一个输入的字符串，首先得到64位的hash值，用前14位来定位桶的位置（共有 2的14次方 ，即16384个桶）。后面50位即为伯努利过程，每个桶有6bit，记录第一次出现1的位置count，如果count>oldcount，就用count替换oldcount。

模仿上面的流程，多个不同的用户 id，就被分散到不同的桶中去了，且每个桶有其 k_max。然后当要统计出页面有多少用户点击量的时候，就是一次估算。最终结合所有桶中的 k_max，代入估算公式，便能得出估算值。
每个桶有6bit，即[000 000],最大为[111 111]，表示63。

优化

于是引入了桶的概念，计算m个桶的加权平均值，这样就能得到比较准确的答案了（实际上还要进行其他修正）。最终的公式如图

HyperLogLog公式 hei

其中m是桶的数量，const是修正常数，它的取值会根据m而变化。p=log2m

我们回到Redis，对于一个输入的字符串，首先得到64位的hash值，用前14位来定位桶的位置（共有214，即16384个桶）。后面50位即为伯努利过程，每个桶有6bit，记录第一次出现1的位置count，如果count>oldcount，就用count替换oldcount。

为什么要统计 Hash 值中第一个 1 出现的位置？

因为第一个 1 出现的位置可以同我们抛硬币的游戏中第一次抛到正面的抛掷次数对应起来，根据上面掷硬币实验的结论，记录每个数据的第一个出现的位置 K，就可以通过其中最大值 Kmax 来推导出数据集合中的基数：N = 2Kmax

1.比特串

通过hash函数，将数据转为比特串，例如输入5，便转为：101。为什么要这样转化呢？

是因为要和抛硬币对应上，比特串中，0 代表了反面，1 代表了正面，如果一个数据最终被转化了 10010000，那么从右往左，从低位往高位看，我们可以认为，首次出现 1 的时候，就是正面。

那么基于上面的估算结论，我们可以通过多次抛硬币实验的最大抛到正面的次数来预估总共进行了多少次实验，同样也就可以根据存入数据中，转化后的出现了 1 的最大的位置 k_max 来估算存入了多少数据。

2.分桶

在Redis中的HyperLogLog中，共分为2^14个桶，每个桶有6个bit，占用内存为=2^14*6/8/1024=12K。

redis-hyperloglog

1
而Redis 最大能够统计的数据量是 264，即每个桶的 maxbit 需要 6 个 bit 来存储，最大可以表示 maxbit = 63，于是总共占用内存就是：(214) x 6 / 8 (每个桶 6 bit，而这么多桶本身要占用 16384 bit，再除以 8 转换成 KB),算出来的结果就是 12 KB

当我们执行命令pfadd key value时，首先会通过hash函数将value转换为64位比特串。其中，前14位用来确定分桶(刚好有2^14个桶)，后50位用来获取第一个出现1的位数(从右向左)，因为最大为50，因此使用6个bit完全可以表示。 pfadd

不同的value，会被设置到不同桶中去，如果出现了在同一个桶的，但是后面第一个出现1的位数不同。那么比较这个桶新的值是否比原来的值大，如果大于，则替换。否则，保持不变。

底层源码剖析

Redis 源码分析

我们首先来看一下 HyperLogLog 对象的定义

1
2
3
4
5
6
7
struct hllhdr {
    char magic[4];      /* 魔法值 "HYLL" */
    uint8_t encoding;   /* 密集结构或者稀疏结构 HLL_DENSE or HLL_SPARSE. */
    uint8_t notused[3]; /* 保留位, 全为0. */
    uint8_t card[8];    /* 基数大小的缓存 */
    uint8_t registers[]; /* 数据字节数组 */
};

HyperLogLog 对象中的 registers 数组就是桶，它有两种存储结构，分别为密集存储结构和稀疏存储结构，两种结构只涉及存储和桶的表现形式，从中我们可以看到 Redis 对节省内存极致地追求。

密集存储结构

密集型的存储结构非常简单，就是 16384 个 6 bit 连续串成 的字符串位图：

img

我们都知道，一个字节是由 8 个 bit 组成的，这样 6 bit 排列的结构就会导致，有一些桶会 跨越字节边界，我们需要 对这一个或者两个字节进行适当的移位拼接 才可以得到具体的计数值。

假设桶的编号为 index，这个 6 bity 计数值的起始字节偏移用 offset_bytes 表示，它在这个字节的其实比特位置偏移用 offset_bits 表示，于是我们有：

1
2
3
offset_bytes = (index * 6) / 8
offset_bits = (index * 6) % 8
复制代码

前者是商，后者是余数。比如 bucket 2 的字节偏移是 1，也就是第 2 个字节。它的位偏移是 4，也就是第 2 个字节的第 5 个位开始是 bucket 2 的计数值。需要注意的是 字节位序是左边低位右边高位，而通常我们使用的字节都是左边高位右边低位。

这里就涉及到两种情况，如果 offset_bits 小于等于 2，说明这 6 bit 在一个字节的内部，可以直接使用下面的表达式得到计数值 val：

1
2
val = buffer[offset_bytes] >> offset_bits  # 向右移位
复制代码

如果 offset_bits 大于 2，那么就会涉及到 跨越字节边界，我们需要拼接两个字节的位片段：

示意图稀疏存储结构

稀疏存储适用于很多计数值都是零的情况。下图表示了一般稀疏存储计数值的状态：

img

当 多个连续桶的计数值都是零 时，Redis 提供了几种不同的表达形式：

（XX+1）

(连续多少个桶)

  • 00xxxxxx：前缀两个零表示接下来的 6bit 整数值加 1 就是零值计数器的数量，注意这里要加 1 是因为数量如果为零是没有意义的。比如 00010101 表示连续 22 个桶为0。
  • 01xxxxxx yyyyyyyy：6bit 最多只能表示连续 64 个零值计数器，这样扩展出的 14bit 可以表示最多连续 16384 个桶计数值。这意味着 HyperLogLog 数据结构中 16384 个桶的初始状态，所有的计数器都是零值，可以直接使用 2 个字节来表示。
  • 1vvvvvxx：中间 5bit 表示计数值，尾部 2bit 表示连续几个桶。它的意思是连续 (xx +1) 个桶计数值都是 (vvvvv + 1)。比如 10101011 表示连续 4 个计数值都是 11。

1vvvvxx (xx+1)-> (vvvv+1)

注意

上面第三种方式

的计数值最大只能表示到 32，而 HyperLogLog 的密集存储单个计数值用 6bit 表示，最大可以表示到 63。当稀疏存储的某个计数值需要调整到大于 32 时，Redis 就会立即转换 HyperLogLog 的存储结构，将稀疏存储转换成密集存储。

作者：我没有三颗心脏
链接：https://juejin.cn/post/6844904079601188877
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。