HyperLogLog

Redis 三种高级数据结构: bitmap、hyperloglog、geo

1. 适用场景

如果允许统计在巨量数据面前的误差率在可接受的范围内，1000万浏览量允许最终统计出少了一两万这样子，那么就可以采用HyperLogLog算法来解决上面的计数类似问题。

官方说误差在 0.81%，只是一个在海量数据前提下的平均误差，数据量越小，误差发生的可能越大

2. 原理

2.1 伯努利实验

扔硬币，无论抛了多少次，只要出现了正面，就记录为一次试验。这个试验就是伯努利试验。

假设进行了 n 次实验，每一次实验都会抛 k 次，那么第一次实验会抛 k1 次，第二次实验会抛 k2 次，一直到第 n 次实验会抛 kn 次（这里的 k 次指的是抛了 k 次才抛出来正面）

对于 n 次实验，会存在一个最大抛掷次数 k_max，比如抛了 12 次才抛到正面

所以可以得到结论

n 次伯努利过程的投掷次数都不大于 k_max
n 次伯努利过程，至少有一次投掷次数等于 k_max

结合极大似然估算得到 n = 2^k_max

第一次试验: 抛了3次才出现正面，此时 k=3，n=1
第二次试验: 抛了2次才出现正面，此时 k=2，n=2
第三次试验: 抛了6次才出现正面，此时 k=6，n=3
第n 次试验：抛了12次才出现正面，此时我们估算， n = 2^12

假设上面例子中实验组数共3组，那么 k_max = 6，最终 n=3，我们放进估算公式中去，明显： 3 ≠ 2^6 。也即是说，当试验次数很小的时候，这种估算方法的误差是很大的。

2.2 Redis 的实现

将每一个元素都进行 hash，得到一个 64 位的 bit 串，转换成 bit 串是类比于抛硬币，1 是正面，0 是反面
前 14 位用来分桶（一共 16384 个桶），每个桶有 6 个比特位，桶的比特位用来保存结果
后 50 位会进行计算，从右往左计算第一个 1 出现的位置，参考抛硬币此时相当于一次实验结束，此时桶就保存第一个 1 出现的位置到最右边的一个长度
分到一个桶里的数据可能是多个，所以桶会保存所有长度最大的那个值
由于只会计算 50 位，所以最大长度就是 50，那么 6 个比特位就可以表示到64，所以桶最少最需要 6 个比特位即可
桶拿到的最大长度，这个结果其实相当于 k_max，根据这个值，我们通过极大似然估算，会得到一个结果 2^k_max 这个就是总数的估算值
16384 个桶 = 2^14; k_max 最大是 50，所以可以通过 16384 * 6 /8 / 1024 K 存储空间就能统计多达 2^64 个数