HyperLogLog 基数估计算法

August 7, 2017

在redis中还有一个很奇怪的部分，Hyperloglog。看到这个东西后我的第一反应跟大多数人一样，这个日志的东西是干什么的？ 然而这并不是日志，而是一个十分高深的玩意儿，他的主要功能是估算诸如一个集合中的不同元素的个数，也就是基数估计。 这个算法号称用1.5Kb内存为十亿对象计数。 下面就来看一下这个算法，其实我也没有完全搞懂这个算法的所有细节，就简单的介绍下就好了。 背景 # 我们有很多场景，需要计算一个MultiSet的基数，如统计网站的访问IP数量等。 传统做法 # 在传统的做法中，我们可以开辟一个数据表每次累加出来。但是这个开销无论从时间上还是空间上，当数据量变大以后会变得十分巨大。随着一个参数的增长所以整个系统的参数都应该在上升，也就是说整个数据库系统都在面临巨大的压力。这个时候如果还这样做就很不明智了。 BitMap # 后来就聪明点了，这个应该就是程序员想出来的。 就是把每个IP映射到一个内存bit上，出现了就置1，没出现就是0。然后统计一下个数就可以了，抑或一下嘛。但是这个在空间上只做了个常数优化，搞过ACM的都明白，常数优化不算优化。 Linear Counting # 这个算法就是一个有一定数学基础的程序员搞出来的。 将IP映射到m个内存bit上去，然后还是统计1的数量，但是用最大似然估计的方式来估计总数的大小。这个在数学上是说的通的。 算法要求映射函数符合均匀分布，那么当基数很大的时候可以用正态分布逼近二项分布，正态分布的期望的最大似然估计是样本均值。所以我们就用这个最大似然估计来统计这个基数。 但是这个理论在很多情况下会有很大的误差，并且其对于m的要求很多，所以其空间复杂度也没有优化到哪里去。 LogLog Counting # 这个时候你应该懂标题中的LogLog是什么意思了吧，并不是日志的意思，而是算法复杂度。 这个算法对于Hash函数有下面几个要求： H的结果具有很好的均匀性，也就是说无论原始集合元素的值分布如何，其哈希结果的值几乎服从均匀分布（完全服从均匀分布是不可能的，D. Knuth已经证明不可能通过一个哈希函数将一组不服从均匀分布的数据映射为绝对均匀分布，但是很多哈希函数可以生成几乎服从均匀分布的结果，这里我们忽略这种理论上的差异，认为哈希结果就是服从均匀分布）。 H的碰撞几乎可以忽略不计。也就是说我们认为对于不同的原始值，其哈希结果相同的概率非常小以至于可以忽略不计。 H的哈希结果是固定长度的。 以上对哈希函数的要求是随机化和后续概率分析的基础。后面的分析均认为是针对哈希后的均匀分布数据进行。 这个算法的基础是伯努利试验以及其推论。 伯努利试验是说：一次实验的结果只有发生和不发生两种，重复做这个实验，直到结果发生为止，记录下实验的次数。 然后讲与我们这个算法的联系。 算法的思路前面还是差不多，先把每个元素都Hash到一个固定长度的二进制串。那么这些二进制串最高位1的位置就符合这个定义。每个串都是一个伯努利过程，最高位1的位置就是第一次事件发生的试验次数。 回到理论本身，理论本身并没有给出解决这个问题的结论。但是在其一些推论的公式中隐含了我们要求得的基数，也就是伯努利过程的数量。 由两个问题引出这个公式： 进行n次伯努利过程，所有投掷次数都不大于k的概率是多少？ 进行n次伯努利过程，至少有一次投掷次数等于k的概率是多少？ (公式回头补，页面不支持latex很鸡肋) 这两个公式我们考虑极限情况的时候，就会发现，n就在2^k附近。这个就做为n的粗略估计。 下面就是要做偏差修正了。