常见的基数估算算法

背景

排重值计算是一种常见的基本计算。如计算网站上今天来访问的人数，实质上是计算用户唯一标识的排重数。

精确的排重值算法，需要记录下每个出现过的具体的值。在数据量达到百万级，甚至百亿级时，记录所需要的内存空间就会成为瓶颈。

一般会想，内存成为瓶颈时，可以存储在外存（如硬盘）上。但是考虑到外存的性能IO瓶颈和CPU消耗，成本会比较高。

大多数场景下，我们并不需要精确的排重值计算结果。这时，就有了下面的估计算法，能够在占用内存和计算误差间取一个平衡。在保证误差范围的情况下，把内存占用放到最小。

估算算法的主要思想是：

1. 做数据准备，对排重值做hash，由计算原值改为计算hash后的值. 
2. 使用基数估计(cardinality counting)，来做近似计算

讲一步阅读：

1. 解读Cardinality Estimation算法（第一部分：基本概念）

数据准备算法

• murmurhash32
• murmurhash64

基数估计方法

基于bitmap的基数计算

bitmap基数计算是使用bitmap来表示集合。用一个很长的bit数组，来表示集合。如使用00100100表示集合{2,5,6}

优点：合并效率高，只需要按位或运算即可。

缺点：bitmap长度与集合中元素个数无关，与基数的上限相关。

如果场景为受访链接的排重数，由于受访链接的基数很高，因此占用内存会很大，不适合于大数据场景。

基于概率的基数计算

• Linear Counting
• LogLog Counting
• Adaptive Counting
• HyperLogLog Counting
• HyerLogLog++ Counting

Linear Counting

思路：将n个元素，hash到m位的bitmap中，hash完成后bitmap中有u个bit为0，

反推：根据最大似然估计(MLE)，E(n)=-mlog(u/m)

误差：令t=n/m，则 Bias(E(n)/n)=E(E(n)/n)=(e^t-t-1)/(2n)

即：n越大, m与n接近时，误差才小。

如果：n>>m，则bitmap基本全为1了，即u=0，则LC估算就失效了

原理：详见 解读Cardinality Estimation算法（第二部分：Linear Counting）

上文中总结的非常好，就不再叙述了。

优点：LC合并方便，按位或。

缺点：空间复杂度仍为O(N_max)不够。

LogLog Counting

LogLog Counting(LLC)与LC相比，能够指数级的节省内存，即空间复杂度为O(log2(log2(Nmax)))。比如，基数的上限为1亿时，bitmap需要12.5M内存，LC只需要不到1K(640字节)的内存，同时标准误差不超过4%。

思路：

待补充

优点：内存使用极少

缺点：n不是特别大时，误差过大。改善方法为HyperLogLog Counting和Adaptive Counting算法。

原理：详见解读Cardinality Estimation算法（第三部分：LogLog Counting）

HyperLogLog Counting

(HLL在线DEMO) Sketch of the Day: HyperLogLog

实验：

优点：内存占用 loglog(Nmax)+O(1) bits

缺点：需要自己控制误差，可能会高估结果。

原理：详见[转]高压缩空间占用的 Hyper LogLog 算法

Adaptive Counting

原理：详见解读Cardinality Estimation算法（第四部分：HyperLogLog Counting及Adaptive Counting）

进一步阅读资料

1. 五种常用基数估计算法效果实验及实践建议

2. HLL++算法：14年3个Google工程师做的，论文在：http://static.googleusercontent.com/media/research.google.com/fr//pubs/archive/40671.pdf

3. New cardinality estimation algorithms for HyperLogLog sketches论文，17年另一个Google工程师 Otmar Ertl做的。

4. 听TalkingData张宁讲海量数据OLAP分析实践

5. 神奇的HyperLogLog算法

附录：误差参考

使用2^16（64K）位时，估算结果如下：

Linear Counting with Murmurhash:

actual: 50000, estimated: 50062, error: 0.12%

actual: 100000, estimated: 99924, error: 0.08%

actual: 150000, estimated: 149865, error: 0.09%

actual: 200000, estimated: 199916, error: 0.04%

actual: 250000, estimated: 250123, error: 0.05%

actual: 300000, estimated: 299942, error: 0.02%

actual: 350000, estimated: 349801, error: 0.06%

actual: 400000, estimated: 400101, error: 0.03%

actual: 450000, estimated: 449955, error: 0.01%

actual: 500000, estimated: 500065, error: 0.01%

Linear Counting with Lookup3hash:

actual: 50000, estimated: 49835, error: 0.33%

actual: 100000, estimated: 99461, error: 0.54%

actual: 150000, estimated: 149006, error: 0.66%

actual: 200000, estimated: 198501, error: 0.75%

actual: 250000, estimated: 248365, error: 0.65%

actual: 300000, estimated: 298065, error: 0.65%

actual: 350000, estimated: 347504, error: 0.71%

actual: 400000, estimated: 397292, error: 0.68%

actual: 450000, estimated: 446700, error: 0.73%

actual: 500000, estimated: 495944, error: 0.81%

Hyperloglog Counting with Murmurhash:

actual: 50000, estimated: 50015, error: 0.03%

actual: 100000, estimated: 100048, error: 0.05%

actual: 150000, estimated: 149709, error: 0.19%

actual: 200000, estimated: 201595, error: 0.80%

actual: 250000, estimated: 250168, error: 0.07%

actual: 300000, estimated: 299864, error: 0.05%

actual: 350000, estimated: 348571, error: 0.41%

actual: 400000, estimated: 398583, error: 0.35%

actual: 450000, estimated: 448632, error: 0.30%

actual: 500000, estimated: 498330, error: 0.33%

Hyperloglog Counting with Lookup3hash:

actual: 50000, estimated: 49628, error: 0.74%

actual: 100000, estimated: 99357, error: 0.64%

actual: 150000, estimated: 148880, error: 0.75%

actual: 200000, estimated: 200475, error: 0.24%

actual: 250000, estimated: 249362, error: 0.26%

actual: 300000, estimated: 299119, error: 0.29%

actual: 350000, estimated: 349225, error: 0.22%

actual: 400000, estimated: 398805, error: 0.30%

actual: 450000, estimated: 448373, error: 0.36%

actual: 500000, estimated: 498183, error: 0.36%

Adaptive Counting with Murmurhash:

actual: 50000, estimated: 50015, error: 0.03%

actual: 100000, estimated: 100048, error: 0.05%

actual: 150000, estimated: 149709, error: 0.19%

actual: 200000, estimated: 201059, error: 0.53%

actual: 250000, estimated: 249991, error: 0.00%

actual: 300000, estimated: 300067, error: 0.02%

actual: 350000, estimated: 349610, error: 0.11%

actual: 400000, estimated: 399875, error: 0.03%

actual: 450000, estimated: 450348, error: 0.08%

actual: 500000, estimated: 500977, error: 0.20%

Adaptive Counting with Lookup3hash:

actual: 50000, estimated: 49628, error: 0.74%

actual: 100000, estimated: 99357, error: 0.64%

actual: 150000, estimated: 148880, error: 0.75%

actual: 200000, estimated: 199895, error: 0.05%

actual: 250000, estimated: 249563, error: 0.17%

actual: 300000, estimated: 299047, error: 0.32%

actual: 350000, estimated: 348665, error: 0.38%

actual: 400000, estimated: 399266, error: 0.18%

actual: 450000, estimated: 450196, error: 0.04%

actual: 500000, estimated: 499516, error: 0.10%

Loglog Counting with Murmurhash:

actual: 50000, estimated: 59857, error: 19.71%

actual: 100000, estimated: 103108, error: 3.11%

actual: 150000, estimated: 150917, error: 0.61%

actual: 200000, estimated: 201059, error: 0.53%

actual: 250000, estimated: 249991, error: 0.00%

actual: 300000, estimated: 300067, error: 0.02%

actual: 350000, estimated: 349610, error: 0.11%

actual: 400000, estimated: 399875, error: 0.03%

actual: 450000, estimated: 450348, error: 0.08%

actual: 500000, estimated: 500977, error: 0.20%

Loglog Counting with Lookup3hash:

actual: 50000, estimated: 59870, error: 19.74%

actual: 100000, estimated: 103044, error: 3.04%

actual: 150000, estimated: 150435, error: 0.29%

actual: 200000, estimated: 199895, error: 0.05%

actual: 250000, estimated: 249563, error: 0.17%

actual: 300000, estimated: 299047, error: 0.32%

actual: 350000, estimated: 348665, error: 0.38%

actual: 400000, estimated: 399266, error: 0.18%

actual: 450000, estimated: 450196, error: 0.04%

actual: 500000, estimated: 499516, error: 0.10%