Hyperloglog原理

这篇几乎是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为底的对数。

// 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