浅尝HyperLogLog

[CharLemAznable]

看到Hazelcast的分布式数据结构介绍中, 提到了Cardinality Estimator：实现了HyperLogLog算法的数据结构, 于是顺便了解一下

什么是HyperLogLog.

HyperLogLog是针对大数据统计存储应用场景下的知名算法。

HyperLogLog是在大数据的情况下关于数据基数的空间复杂度优化实现。

[CharLemAznable]

基本概念

基数计数(cardinality counting)通常用来统计一个集合中不重复的元素个数，例如统计某个网站的UV，或者用户搜索网站的关键词数量。

数据分析、网络监控及数据库优化等领域都会涉及到基数计数的需求。

基数计数的实现存在两个问题：

• 空间复杂度：当统计的数据量变大时，相应的存储内存也会线性增长
• 时间复杂度：当集合变大，判断其是否包含新加入元素的成本变大

大数据量背景下，要实现基数计数，

• 首先需要确定存储统计数据的方案，以及如何根据存储的数据计算基数值
• 另外还有一些场景下需要融合多个独立统计的基数值：例如对一个网站分别统计了三天的UV，现在需要知道这三天的UV总量是多少，怎么融合多个统计值

[CharLemAznable]

基数计数方法

B树

B树最大的优势是插入和查找效率很高，可以快速判断新来的数据是否已经存在，并快速将元素插入B树。

要计算基数值，只需要计算B树的节点个数。

但是，B树结构只是加快了查找和插入效率，并没有节省存储内存。

bitmap

bitmap可以理解为通过一个bit数组来存储特定数据的一种数据结构，每一个bit位都能独立包含信息，bit是数据的最小存储单位，因此能大量节省空间，也可以将整个bit数据一次性load到内存计算。

新加入一个元素，只需要将已有的bit数组和新加入的数字做按位或计算。

bitmap中1的数量就是集合的基数值。

bitmap还可以轻松合并多个统计结果，只需要对多个结果求异或就可以。

bitmap对于内存的节约量是显而易见的，但还是不够。统计一个对象的基数值需要12M，如果统计10000个对象，就需要将近120G了，同样不能广泛用于大数据场景。

概率算法

目前还没有发现更好的更高效的大数据场景基数计数算法，因此在不追求绝对准确的情况下，使用_概率算法_算是一个不错的解决方案。

概率算法不直接存储数据集合本身，通过一定的概率统计方法预估基数值，这种方法可以大大节省内存，同时保证误差控制在一定范围内。

目前用于基数计数的算法包括：

• Linear Counting(LC)：早期的基数估计算法
• LogLog Counting(LLC)：相比于LC更加节省内存
• HyperLogLog Counting(HLL)：基于LLC的优化和改进，能够比LLC的基数估计误差更小

[CharLemAznable]

HyperLogLog的惊人表现

用bitmap存储1一亿个统计数据大概需要12M内存，而在HLL中，只需要不到1K内存就能做到。

Redis中实现的HyperLogLog，只需要12K内存，在标准误差0.81%的前提下，能够统计2^64个数据。

HLL的基本做法

• 通过hash函数，将数据转为比特串
• 分桶：就是分多少轮。存储一个单位是比特(bit)，长度为 L 的大数组 S ，将 S 平均分为 m 组(桶/轮)，每组所占有的比特个数是平均的，设为 P 。
  • L = S.length
  • L = m * P
  • 以 K 为单位，S 占用的内存 = L / 8 / 1024

在Redis中，HyperLogLog设置为：m=16834，P=6，L=16834 6。占用内存为=16834 6 / 8 / 1024 = 12K。 第0组	第1组	....	第16833组
[000 000]	[000 000]	....	[000 000]

• 对应 设定，每个比特串的前多少位转为10进制后，其值就对应于所在组(桶/轮)的标号。 剩下的比特串，从低位到高位看，第一次出现 1 的位置数值存入组(桶/轮)中，最大占用P(bit)。

将不同的输入分散到不同的桶中去，要计算输入集合的基数时，计算所有桶中数值的调和平均数，就能得到基数的估算值。

[CharLemAznable]

HyperLogLog的原理：伯努利试验

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

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

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

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

伯努利试验容易得出有以下结论：

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

第一个结论用数学公式表示为：

P_n (X ≤ k_max) = (1 − 1 / 2 ^ k_max) ^ n

第二个结论用数学公式表示为：

P_n (X ≥ k_max) = 1 - (1 − 1 / 2 ^ (k_max - 1)) ^ n

可以推导：

当 n ≪ 2 ^ k_max 时，P_n (X ≥ k_max) ≈ 0

当 n ≫ 2 ^ k_max 时，P_n (X ≤ k_max) ≈ 0

因此，我们似乎就可以用2 ^ k_max的值来估计n的大小。 即结合极大似然估算的方法，发现在n和k_max中存在估算关联：n = 2 ^ k_max。

总结为：

进行了 n 次进行抛硬币实验，

每次分别记录下第一次抛到正面的抛掷次数 k ，

可以用 n 次实验中最大的抛掷次数 k_max 来预估实验组数量 n ：

n = 2 ^ k_max

这种通过局部信息预估整体数据流特性的方法似乎有些超出我们的基本认知，需要用概率和统计的方法才能推导和验证这种关联关系。

[CharLemAznable]

从 伯努利试验 到 HyperLogLog

回到基数统计的问题，我们需要统计一组数据中不重复元素的个数。

集合中每个元素的经过hash函数后可以表示成0和1构成的二进制数串，

一个二进制串可以类比为一次抛硬币实验，1是抛到正面，0是反面。

二进制串中从低位开始第一个1出现的位置可以理解为抛硬币试验中第一次出现正面的抛掷次数k。

那么基于伯努利试验的结论：我们可以通过多次抛硬币实验的最大抛到正面的次数来预估总共进行了多少次实验，

同样，可以通过第一个1出现位置的最大值k_max来预估总共有多少个不同的数字，即整体基数。

HyperLogLog核心在于观察集合中每个数字对应的比特串，通过统计和记录比特串中最大的出现1的位置来估计集合整体的基数，可以大大减少内存耗费。

[CharLemAznable]

Redis中的HyperLogLog

• PFADD key element [element ...] 添加指定元素到 HyperLogLog 中。
• PFCOUNT key [key ...] 返回给定 HyperLogLog 的基数估算值。
• PFMERGE destkey sourcekey [sourcekey ...] 将多个 HyperLogLog 合并为一个 HyperLogLog。