Kylin中有两个功能使用HyperLogLog（简称HLL）算法，一是计算Cube的Segment的统计信息，主要计算当前Segment大小，用来创建预分区的HBase表；另一个是在Distinct Count 度量值的实现，使用HLL估计值算法来计算Distinct Count指标的近似值，精度越大误差越小，当然使用存储空间越大。
伯努利试验
HLL算法源于伯努利试验，假设一直抛硬币，直到它出现正面为止，我们记录为一次完整的试验，中间可能抛了一次就出现了正面，也可能抛了4次才出现正面。无论抛了多少次，只要出现了正面，就记录为一次试验。这个试验就是伯努利试验。那么对于多次的伯努利试验，假设这个多次为n次。就意味着出现了n次的正面。假设每次伯努利试验经历了抛掷次数为k，第一次伯努利试验次数设为k1，以此类推，第n次对应的是kn。其中，对于这n次伯努利试验中，必然会有一个最大的抛掷次数k，例如抛了12次才出现正面，那么称这个为k_max，代表抛了最多的次数。
根据伯努利试验结合极大似然估计的方法，发现在n和k_max中存在估算关联：n = 2^(k_max)
LogLog计算公式：
HyperLogLog计算公式：
调和平均数计算公式：
constant取值：
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;
}
试验次数越多越接近抛的次数，试验的次数对应到算法里的分桶m，桶的大小取决于精度p (m=2^p)。硬币的正反面对应到二进制里的1和0，将待统计的值通过guava里的murmur3_128哈希函数计算出hash值取long型数值，long值转换为二进制64位的比特串，假设精度为14则从低位到高位的前14位对应的十进制值为桶的编号，桶的值为取前导0的个数并加上1 (Long.numberOfLeadingZeros(hash))，具体为什么要+1需要参考论文。公式里的是m次前导0的平均值。将抛硬币试验对应到LogLog公式计算出估计值。
LogLog算法采用的是前导0的平均值，平均值误差较大，比如你进行了m轮抛硬币，某一次点背抛了100次才出现正面，这样得到均值比较大。改进的HyperLogLog算法采用了调和平均数，参照调和平均值计算公式抹去分母很大的值对均值的影响。
Kylin统计信息计算
回到Kylin统计信息计算，默认使用HLL(14)精度来估算每个Cuboid中对应的维度组合的基数，比如计算BaseCuboid，将所有编码后的维度采用murmur3_128哈希函数计算出一个long型数值，取前导0+1作为桶的值，如果桶编号相同，会比较取大的前导0的值写入桶。待所有输入的值都写入BaseCuboid对应的HLLCounter对象后，开始计算基数。
HLLSnapshot内部类构造函数里的int[256]数组是用来计算调和平均数，cuboids估计大小的统计信息使用精度HLL(14)来计算的，rowkeys经过hash转换成long数值，占64个bit，极端情况下前导0是50+1，这样6个bit可以存储这些前导0的值，对应到byte数据类型的桶来存储，一个byte能够存储256个数值。即在DenseRegister中使用byte[2^14]数组来存储各个桶的值。计算数组桶调和平均数，先count桶的值（理论上是1~51）映射到int[256]数组中，然后应用DLL计算公式：alpha * m *m / (count(i) *1.0/(1L<<i) +…..)。有了每个cuboid的基数，就可以计算出每个cuboid的大小即 (维度+度量值) * DV。
近似的Distinct Count度量值实现上也是采取类似的计算流程，感兴趣的话可以阅读Kylin相关源码。
