在之前的文章, Cardinality Counting 中, 我们介绍的方法, 都是可以精确统计基数的. 但是, 在现在动辄 TB,PB 级数据量的情况下, 无论是 BTree 还是 bitmap, 都有很多缺陷, 并且精确性这一优势也被海量数据的前提所抵消(想象一下, 统计 uv 时, 100000000 和 100000001 有区别吗).
相反的, 我们可以采用一些基于概率的方法, 在误差可控的前提下, 对基数做出合理的估计.
目前, 最常用的基数估计方法, 是 HyperLogLog(HLL).
算法思想
HLL 算法的思想其实是基于 LogLog Counting(LLC), 论文详见 2003 年的Loglog Counting of Large Cardinalities. 下面简单介绍一下其基本思想.
首先, 我们对每一个元素用适当的哈希算法进行哈希 (结果均匀, 碰撞可以忽略不计) 得到一个二进制 01 序列. 对每一个元素, 统计其由低到高, 第一个出现 1 的 bit 位置, 记为 m. 遍历所有的元素, 得到 m 的最大值 M, 则可以用 2^M 来估计基数 n 的大小.
直观上讲, 如果一个集合中元素的个数越多, 则其中元素哈希后得到的 01 序列, 第一个 1 出现的位置的最大值 M 也会越大, 所以用 2^M 来估计 n 似乎是合理的.
但是, 为什么是 2^M, 而不是 2xM 或者 3^M 呢?
概率分析
这其中, 有一些概率论方面的推理:
由于哈希算法的良好特性, 则每一个元素哈希后的 01 序列都可以看做一次不断抛硬币的过程, 正面为 1, 反面为 0. 不断抛硬币直到得到一个正面的过程, 就是一个伯努利过程.
那么考虑如下两个问题:
进行 n 次伯努利过程, 抛硬币的次数均不大于 k 的概率
进行 n 次伯努利过程, 至少有一个抛硬币次数等于 k 的概率
分析过程如下:
1. 针对一次伯努利过程,
p(X<=k) = 1 - p(X>k),p(n>k)表示前 k 次的结果都是反面,
所以
p(X<=k) = 1 - p(X>k) = 1 - (1/2)^k
那么对于 n 次伯努利过程, 第一个问题的概率就是
pn(X<=k) = (1-(1/2)^k)^n
2. 概率论教导我们,"至少"=1-"都不".
- pn'(X==k) = 1 - pn(X!=k) = 1-(1-P(X==k))^n
- = 1 - (1-(1/2)^k)^n
当 n<<2^k 时, pn'(X==k)0.
当 n>>2^k 时, pn(X<=k)0.
如果我们取 k 为这 n 次伯努利过程中抛掷硬币次数的最大值 M, 那么我们将发现, 理应, pn'(X==M)>> 0 且 pn(X<=M)>> 0. 所以 n<<2^m 和 n>>2^M 都将不成立. 那么, 用 2^M 作为 n 的一个粗略估计就是恰当.
当然, 为了减少偶然因素的影响, LLC 还使用了分桶平均的策略; 另外, 为了实现无偏的估计, 还是用了偏差修正系数. 不过这些都不影响其最基础的思想来源于上面的伯努利过程.
LLC 与 HLL
LLC 的空间复杂度仅有 O(log(logNmax)), 并且非常易于合并(分桶比较记录值得大小, 去 max 即可).
HLL 在 LLC 的基础上做了进一步的改进, 使得其估计误差更小更稳定. 因此, 在海量数据统计领域, HLL 获得了广泛的应用.
目前, redis 中内置了 HLL 的实现(PFADD, PFCOUNT, PFMERGE), 用 12K 内存, 即可统计接近 2^64 个不同元素的基数, 可以说是非常强大了. 此外, postgresql 也提供了扩展插件用于支持 HLL.
来源: https://juejin.im/entry/5affa8c56fb9a07aa43c77f3