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

(0)

相关推荐

  • 今日头条怎么收集生肖卡瓜分十亿现金红包?

    今日头条中集齐12生肖卡和再加上发财两个字,所以需要14张卡,就可以瓜分10亿现金,下面我们就来看看详细的教程. 1.我们先打我们的今日头条app,然后进入到主页之后,你会看到下面有一个十亿现金,点击 ...

  • 大内存手机十大品牌排行榜

    排行榜123网依托全网大数据,根据品牌评价以及销量评选出了2019年大内存手机十大品牌排行榜,前十名分别是酷比/Koobee.京合.努比亚/Nubia.君问数码 .如果您正在查找大内存手机什么牌子好? ...

  • 今日头条十亿现金红包怎么领怎么提现

    今日头条十亿现金红包怎么领怎么提现,这里,让小编给大家介绍一下. 操作方法 01 首先我们需要在手机上安装今日头条app,然后打开这个程序. 02 接着在首页上会弹出十亿现金红包的界面,直接点击. 0 ...

  • 全球点击超过十亿的8首欧美神曲

    在这个互联网时代,好听的歌曲会被传播的很快,一首首好听的歌曲得到得到快速的点击和传播后成为神曲.下面给大家盘点全球点击超过十亿的8首欧美神曲. 操作方法 01 <Faded>从纯音乐到女唱 ...

  • 支付宝钱包怎么看十年账单?手机支付宝钱包十年账单查看方法

    支付宝钱包十年账单怎么看?大家可以通过下文来了解支付宝钱包十年账单查看方法,十年过去了,“剁手”的钱到底花了多少呢?如果你想了解的话,就请参考下文步骤来查看吧。 登陆支付宝钱包之后点击“我的账单”就可 ...

  • 支付宝十年账单哪里看?支付宝钱包十年账单查看方法

    支付宝“十年账单”正式推出 十年,你可能已经忘记的,我们都记得。今日,是支付宝十周岁的日子,于此同时,支付宝“十年账单”也终于正式推出了。10账单不仅记录着过去十年的收支情况,还可以帮你预测十年之后的 ...

  • 支付宝十年账单如何查看?支付宝十年账单查询方法图解

    支付宝十年账单如何查看?对于大部分的网购朋友们来说,支付宝相信是很多人在网购过程中所必备的,但是大家是否一直以来都很清楚自己的账单情况呢?最近网上有一个关于支付宝十年账单怎么查的话题讨论,可以帮助大家 ...

  • 手机/电脑查看支付宝十年账单日记方法图解

    “支付宝,我和你有什么仇什么怨!”不少网友在看到支付宝的十年账单后,都发出这样的惊呼。支付宝十周年账单正式推出了,这份账单不仅记录了这个十年你的收支情况,还为你预测了下一个十年的财富值。昨天小编跟大家 ...

  • win7系统使用过程中总提示内存不足的原因及解决方法

    在使用win7系统的过程中,有时候会遇到一些常见的故障问题,比如有的用户反映在操作使用win7系统的时候,系统总弹出“计算机的内存不足”的提示。大部分用户遇到这种情况往往不懂得如何处理。其实只要我们了 ...