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

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

核心提示： 为了更好地理解已经明确基数的大数据集的挑战，我们假设你的日志文件包含16个字符的ID,并且你想统计不同ID的数量.例如:4f67bfc603106cb2这16个字符需要用128位来表示，云计算用1.5KB内存为十亿对象计数方法，6万5千个ID将需要1MB的空间，我们每天收到30多亿条事件记录，所以通过控制原始map的

为了更好地理解已经明确基数的大数据集的挑战，我们假设你的日志文件包含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的大小，我们可以估算碰撞的次数，以致我们将在最终结果中看到误差有多大。

1 2 下一页