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

为了更好地理解已经明确基数的大数据集的挑战，我们假设你的日志文件包含16个字符的ID,并且你想统计不同ID的数量.例如:

4f67bfc603106cb2

这16个字符需要用128位来表示。6万5千个ID将需要1MB的空间。我们每天收到30多亿条事件记录，每条记录都有一个ID。这些ID需要3840亿位或45GB的存储。而这仅仅是ID字段需要的空间。我们采取一种简单的方法获取日常事件记录中以ID为基数的数据。最简单的办法就是使用哈希集合且存放到内存中，其中哈希集包含唯一ID的列表(即输入文件中可能会有多条记录的id是相同，但在哈希集中只存放一条)。即使我们假设只有1/3的条记录ID是唯一的(即2/3的记录ID是重复的)，哈希集仍需要119GB的RAM，这其中不包括Java需要在内存中存储对象的开销。你需要一台配备几百GB内存的机器来计算不同的元素，并且这只是计算一天内日志事件记录的唯一ID的内存消耗。如果我们想要统计数周或数月的数据，这问题只会变得更加困难。我们身边当然不会有一台配备几百GB内存的空闲机器，所以我们需要一个更好的解决方案。

解决这一问题的常见办法是使用位图(博客：海量数据处理算法—Bit-Map)。位图可以快速、准确地获取一个给定输入的基数。位图的基本思想是使用哈希函数把数据集映射到一个bit位，每个输入元素与bit位是一一对应。这样Hash将没有产生碰撞冲突，并减少需要计算每个元素映射到1个bit的空间。虽然Bit-map大大节省了存储空间，但当统计很高的基数或非常大的不同的数据集，它们仍然有问题。例如，如果我们想要使用Bit-map计数十亿，你将需要Bit-map位，或需要每个约120 MB的计数器。稀疏的位图可以被压缩，以获得更多的空间效率，但也并不总是有帮助的。

幸运的是，基数估计是一个热门的研究领域。我们已经利用这项研究提供了一个开源实现的基数估计、集合元素检测和top-k算法。

基数估计算法就是使用准确性换取空间。为了说明这一点，我们用三种不同的计算方法统计所有莎士比亚作品中不同单词的数量。请注意，我们的输入数据集增加了额外的数据以致比问题的参考基数更高。这三种技术是：Java HashSet、Linear Probabilistic Counter以及一个Hyper LogLog Counter。结果如下：

该表显示，我们统计这些单词只用了512 bytes，而误差在3%以内。相比之下，HashMap的计数准确度最高，但需要近10MB的空间，你可以很容易地看到为什么基数估计是有用的。在实际应用中准确性并不是很重要的，这是事实，在大多数网络规模和网络计算的情况下，用概率计数器会节省巨大的空间。

线性概率计数器

线性概率计数器是高效的使用空间，并且允许实现者指定所需的精度水平。该算法在注重空间效率时是很有用的，但你需要能够控制结果的误差。该算法分两步运行：第一步，首先在内存中分配一个初始化为都为0的Bit-map，然后使用哈希函数对输入数据中的每个条目进行hash计算，哈希函数运算的结果是将每条记录(或者是元素)映射到Bit-map的一个Bit位上，该Bit位被置为1;第二步，算法计算空的bit位数量，并使用这个数输入到下面的公式来进行估算：

n=-m ln Vn

在公式中，m是 Bit-map的大小，Vn是空bit位和map的大小的比率。需要重点注意的是原始Bit-map的大小，可以远小于预期的最大基数。到底小多少取决于你可以承受误差的大小。因为Bit-map的大小m小于不同元素的总数将会产生碰撞。虽然碰撞可以节省空间，但同时也造成了估算结果出现误差。所以通过控制原始map的大小，我们可以估算碰撞的次数，以致我们将在最终结果中看到误差有多大。

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项目——它提供了其他几个流处理工具以及上文所述的算法的实现。