---
title: HyperLogLog原理
categories: [算法&数据结构]
math: true
---

> [!note]
> 这篇几乎是<https://juejin.cn/post/6844903785744056333>的转载-简略版

## 伯努利实验

在认识为什么`HyperLogLog`能够使用极少的内存来统计巨量的数据之前，要先认识下`伯努利试验`。

> `伯努利试验`是数学`概率论`中的一部分内容，它的典故来源于`抛硬币`。

硬币拥有正反两面，一次的上抛至落下，最终出现正反面的概率都是50%。假设一直抛硬币，直到它出现正面为止，我们记录为一次完整的试验，间中可能抛了一次就出现了正面，也可能抛了4次才出现正面。无论抛了多少次，只要出现了正面，就记录为一次试验。这个试验就是`伯努利试验`。

那么对于多次的`伯努利试验`，假设这个多次为`n`次。就意味着出现了`n`次的正面。假设每次`伯努利试验`所经历了的抛掷次数为`k`。第一次`伯努利试验`，次数设为`k1`，以此类推，第`n`次对应的是`kn`。

其中，对于这`n`次`伯努利试验`中，必然会有一个最大的抛掷次数`k`，例如抛了12次才出现正面，那么称这个为`k_max`，代表抛了最多的次数。

**最终结合极大似然估算的方法，发现在`n`和`k_max`中存在估算关联：`n = 2^(k_max)`。**需要用概率和统计的方法才能推导和验证这种关联关系。当然，当试验次数很小的时候，这种估算方法的误差是很大的。当 n 足够大的时候，估算的误差率会相对减少，但仍然不够小。

那么是否可以进行多轮呢？例如进行 100 轮或者更多轮次的试验，然后再取每轮的 k_max，再取平均数，即: `k_mx/100`。最终再估算出 n。下面是`LogLog`的估算公式：

$$
DV_{LL}=constant*m*2^R
$$

`constant`是修正因子，`m`代表的是试验的轮数，`R`是平均数：`(k_max_1 + ... + k_max_m)/m`。而 `HyperLogLog`和`LogLog`的区别就是，它采用的不是`平均数`，而是`调和平均数`。`调和平均数`比`平均数`的好处就是不容易受到大的数值的影响。

## HyperLogLog

那么这种估算方法如何和下面问题有所关联呢？

> 统计 APP或网页 的一个页面，每天有多少用户点击进入的次数。同一个用户的反复点击进入记为 1 次

1. **哈希**：通过`hash`函数，将数据转为二进制串。和抛硬币对应上，`比特串`中，0 代表了反面，1 代表了正面。如果一个数据最终被转化了 `10010000`，那么从右往左，从低位往高位看，我们可以认为，首次出现 1 的时候，就是正面。
2. **分桶**：分桶就是分多少轮。抽象到计算机存储中去，就是存储的是一个以单位是比特(bit)，长度为 L 的大数组 S ，将 S 平均分为 m 组，对应 m 轮实验。在 `Redis` 中，`HyperLogLog`设置为：m=16834，p=6，L=16834 * 6。占用内存为=16834 * 6 / 8 / 1024 = 12K。
3. **对应**：二进制串的低位作为桶编号，高位作为 kn，比如低两位作为桶编号，对于二进制串 1001011000011，桶编号为 11，kn 为 5

在 redis 中的应用，它的实现中，设有 16384 个桶，即：2^14 = 16384，每个桶有 6 位，每个桶可以表达的最大数字是：2^5+2^4+...+1 = 63 ，二进制为： `111 111`。在存入时，value 会被 hash 成 64 位，即 64 bit 的比特字符串，前 14 位用来分桶，前 14 位的二进制转为 10 进制就是桶标号。

之所以选 `14位` 来表达桶编号是因为，分了 16384 个桶，而 2^14 = 16384，刚好地，最大的时候可以把桶利用完，不造成浪费。假设一个字符串的前 14 位是：00 0000 0000 0010，其十进制值为 2。那么 index 将会被转化后放到编号为 2 的桶。

index 的转化规则：

首先因为完整的 value 比特字符串是 64 位形式，减去 14 后，剩下 50 位，那么极端情况，出现 1 的位置，是在第 50 位，即位置是 50。此时 index = 50。此时先将 index 转为 2 进制，它是：110010 。

因为16384 个桶中，每个桶是 6 bit 组成的。刚好 110010 就被设置到了第 2 号桶中去了。请注意，50 已经是最坏的情况，且它都被容纳进去了。那么其他的不用想也肯定能被容纳进去。

根据上面的做法，不同的 value，会被设置到不同桶中去，如果出现了在同一个桶的，即前 14 位值是一样的，但是后面出现 1 的位置不一样。那么比较原来的 index 是否比新 index 大。是，则替换。否，则不变。

最终地，一个 key 所对应的 16384 个桶都设置了很多的 value 了，每个桶有一个`k_max`。此时调用 pfcount 时，按照前面介绍的估算方式，便可以计算出 key 的设置了多少次 value，也就是统计值。

value 被转为 64 位的比特串，最终被按照上面的做法记录到每个桶中去。64 位转为十进制就是：2^64，`HyperLogLog` 仅用了：`16384 * 6 /8 / 1024 K` 存储空间就能统计多达 2^64 个数。

## 偏差修正

在估算的计算公式中，`constant` 变量不是一个定值，它会根据实际情况而被分支设置，例如下面的样子。

假设：m为分桶数，p是m的以2为底的对数，即 $p = log_2(m)$

```c
// m 为桶数
switch (p) {
   case 4:
       constant = 0.673 * m * m;
   case 5:
       constant = 0.697 * m * m;
   case 6:
       constant = 0.709 * m * m;
   default:
       constant = (0.7213 / (1 + 1.079 / m)) * m * m;
}
```

## 总结

HLL 核心在于 n 和 k_max 在统计学中的关系，使得多个元素的计数可以用常量空间估计得到。对于我们在应用 HLL 的时候要注意的是他的误差率是标准误差率，而不是最大误差率，也就是误差率可能会超过标准误差 0.81% 。

另外解读过原理之后我们知道，对于pfadd一个value进来之后，可能会导致后续的pfcount不会发生变化，也可能会增量大于1。

最后，HLL 是用位图进行存储的，而位图又是逻辑数据结构，其物理数据结构是 Redis 字符串，因此在做数据迁移的时候可以将 HLL 通过 set/get进行迁移。

## 参考

<https://juejin.cn/post/6844903785744056333>