<div class="iteye-blog-content-contain" style="font-size:14px;">
<p style="color:#333333;font-size:14px;font-family:Helvetica, Tahoma, Arial, sans-serif;line-height:24px;"><span style="color:#262626;font-family:'Helvetica Neue', HelveticaNeue, Helvetica, Arial, 'Lucida Grande', sans-serif;font-size:15px;line-height:25.200000762939453px;">This is a guest post by Matt Abrams (@abramsm), from Clearspring, discussing how they are able to accurately estimate the cardinality of sets with billions of distinct elements using surprisingly small data structures. Their servers receive well over 100 billion events per month.</span></p>
<p style="color:#333333;font-size:14px;font-family:Helvetica, Tahoma, Arial, sans-serif;line-height:24px;">在<a href="http://www.google.com/url?q=http%3A%2F%2Fclearspring.com%2F&sa=D&sntz=1&usg=AFQjCNGLySXAkyxC5vAYZgsEnf9t29xzTw" style="color:#3366bb;text-decoration:none;font-family:'Helvetica Neue', HelveticaNeue, Helvetica, Arial, 'Lucida Grande', sans-serif;font-size:15px;line-height:25.200000762939453px;">Clearspring</a>，我们从事统计数据。统计一组不同元素且数量很大的数据集时，是一个挑战。</p>
<p style="color:#333333;font-size:14px;font-family:Helvetica, Tahoma, Arial, sans-serif;line-height:24px;">为了更好地理解已经明确基数的大数据集的挑战，我们假设你的日志文件包含16个字符的ID,并且你想统计不同ID的数量.例如:</p>
<p style="color:#333333;font-size:14px;font-family:Helvetica, Tahoma, Arial, sans-serif;line-height:24px;">4f67bfc603106cb2</p>
<p style="color:#333333;font-size:14px;font-family:Helvetica, Tahoma, Arial, sans-serif;line-height:24px;">这 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内存的空闲机器，所以我们需要一个更好的解决方案。</p>
<p style="color:#333333;font-size:14px;font-family:Helvetica, Tahoma, Arial, sans-serif;line-height:24px;">解决这一问题的常见办法是使用<span style="color:#0066cc;"><a href="http://blog.csdn.net/hguisu/article/details/7880288" style="color:#336699;text-decoration:none;">位图</a></span>（博客：<a href="http://blog.csdn.net/hguisu/article/details/7880288" style="color:#336699;text-decoration:none;font-family:'Microsoft YaHei';line-height:30px;"><span style="color:#3333ff;">海量数据处理算法—Bit-Map</span></a>）。 位图可以快速、准确地获取一个给定输入的基数。位图的基本思想是使用哈希函数把数据集映射到一个bit位，每个输入元素与bit位是一一对应。这样 Hash将没有产生碰撞冲突，并减少需要计算每个元素映射到1个bit的空间。虽然Bit-map大大节省了存储空间，但当统计很高的基数或非常大的不同 的数据集，它们仍然有问题。例如，如果我们想要使用Bit-map计数十亿，你将需要Bit-map位，或需要每个约120 MB的计数器。稀疏的位图可以被压缩，以获得更多的空间效率，但也并不总是有帮助的。</p>
<p style="color:#333333;font-size:14px;font-family:Helvetica, Tahoma, Arial, sans-serif;line-height:24px;">幸运的是，<a href="http://www.google.com/url?q=http%3A%2F%2Falgo.inria.fr%2Fflajolet%2FPublications%2FDuFl03.pdf&sa=D&sntz=1&usg=AFQjCNHij4lkOvtFkqLQ7BwDCOX3DHx2IQ" style="color:#0066cc;text-decoration:none;">基数估计</a>是一个热门的<a href="http://www.google.com/url?q=http%3A%2F%2Falgo.inria.fr%2Fflajolet%2FPublications%2FDuFl03-LNCS.pdf&sa=D&sntz=1&usg=AFQjCNHRJ_TiQ8JpEXwjPibzmMkzWmWXsg" style="color:#0066cc;text-decoration:none;">研究</a>领域。我们已经利用这项研究提供了一个开源实现的基数估计、集合元素检测和top-k算法。</p>
<p style="color:#333333;font-size:14px;font-family:Helvetica, Tahoma, Arial, sans-serif;line-height:24px;"><span style="color:#ff0000;">基数估计算法就是使用准确性换取空间</span>。 为了说明这一点，我们用三种不同的计算方法统计所有莎士比亚作品中不同单词的数量。请注意，我们的输入数据集增加了额外的数据以致比问题的参考基数更高。 这三种技术是：Java HashSet、Linear Probabilistic Co |
|
转播
