云计算用1.5KB内存为十亿对象计数方法

　2012-12-25 19:05:29　来源：WEB开发网　　　

核心提示：Hyper LogLog顾名思义，Hyper LogLog计数器就是估算Nmax为基数的数据集仅需使用loglog(Nmax)+O(1) bits就可以，云计算用1.5KB内存为十亿对象计数方法(2)，如线性计数器的Hyper LogLog计数器允许设计人员指定所需的精度值，在Hyper LogLog的情况下，如果估算

Hyper LogLog

顾名思义，Hyper LogLog计数器就是估算Nmax为基数的数据集仅需使用loglog(Nmax)+O(1) bits就可以。如线性计数器的Hyper LogLog计数器允许设计人员指定所需的精度值，在Hyper LogLog的情况下，这是通过定义所需的相对标准差和预期要计数的最大基数。大部分计数器通过一个输入数据流M，并应用一个哈希函数设置h(M)来工作。这将产生一个S = h(M) of {0,1}^∞字符串的可观测结果。通过分割哈希输入流成m个子字符串，并对每个子输入流保持m的值可观测，这就是相当一个新Hyper LogLog（一个子m就是一个新的Hyper LogLog）。利用额外的观测值的平均值，产生一个计数器，其精度随着m的增长而提高，这只需要对输入集合中的每个元素执行几步操作就可以完成。其结果是，这个计数器可以仅使用1.5 kb的空间计算精度为2%的十亿个不同的数据元素。与执行 HashSet所需的120 兆字节进行比较，这种算法的效率很明显。

合并分布式计数器
我们已经证明了使用上面描述的计数器我们可以估算大集合的基数。但是，如果你的原始输入数据集不适合于单台机器，将怎么做呢？这正是我们在Clearspring所面临的问题。我们的数据分散在数百台服务器上，并且每个服务器只包含整个数据集子集的一部分。这事实上我们能合并一组分布式计数器的内容是至关重要的。这个想法有点令人费解，但如果你花费一些时间去思考这个问题，就会发现其与基本的基数估计值相比并没有太大的不同。因为这个计数器表示映射中的位作为基数，我们可以采取两个兼容计数器并将他们bit位合并到单一的map上。这个算法已经处理碰撞，所以我们可以得到一个基数估计所需的精密，即使我们从来没有把所有的输入数据到一台机器。这是非常有用的，节省了我们在网络中移动数据的大量时间和精力。
Next Steps
希望这篇文章能帮助你更好地理解这个概念和概率计数器的应用。如果估算大集合的基数是一个问题，而你又碰巧使用一个基于JVM的语言，那么你应该使用stream-lib项目——它提供了其他几个流处理工具以及上文所述的算法的实现。

上一页 1 2