设为首页收藏本站

LUPA开源社区

 找回密码
 注册
文章 帖子 博客
LUPA开源社区 首页 业界资讯 开源资讯 查看内容

雅虎开源可以提升流操作速度的DataSketches

2016-1-25 22:09| 发布者: joejoe0332| 查看: 1074| 评论: 0|原作者: infoq|来自: infoq

摘要: 就像在Venture Beat上所宣布的那样,雅虎开源了DataSketches,这是一个用Java编写的随机流算法库。DataSketches允许进行通常来说开销很大的操作,像计算变量不同的值在流中出现的次数,而且消耗的时间少,占用的内存 ...

  就像在Venture Beat上所宣布的那样,雅虎开源了DataSketches,这是一个用Java编写的随机流算法库。DataSketches允许进行通常来说开销很大的操作,像计算变量不同的值在流中出现的次数,而且消耗的时间少,占用的内存小,误差可预测。


  正如他们在技术博客上所作的说明,雅虎内部已经使用DataSketches来提升多个产品的性能,包括FlurrySketch是 DataSketches的一个基本概念,这是一个流的“汇总(summary)”,其中每次更新都按同样方式处理,而不考虑历史更新。这个概念是 DataSketches性能的核心,因为传统的流处理需要保存一个随着时间增长的历史。例如,如果要计算每个唯一值出现的次数,就需要保存每个新出现的 唯一值,这样,对于后来的唯一值,检查时间将会增加;因此,每次更新都会以一种不同的、开销更大的方式处理。另一方面,sketch的构造方式使它只能保 存固定数量的、需要保存的信息,也就是说,所有的更新都以完全相同的方式执行。


  如果仔细研究下DataSketches背后的科学原理,那么我们就会发现,它以整合了KMV和自适应采样算法的Theta-Sketch框架为基础。感兴趣的读者可以读下这篇论文,它提供了该框架的形式化描述和特性说明,但在这里,我们将提供一种简化的、更为直观的描述。


  就让我们将这个 问题置于实时计算一个网站的独立访客的场景下。计算一个流中不同的变量值出现的次数,主要的问题是需要为每个已知的、不同的变量值存储一个副本。除此之 外,变量的每个新实例(例如,每次新访问网站)都需要对照已知的、不同的变量值所组成的列表进行检查,看看这是一个新访客,还是一个已有的访客。这就是 说,假如独立访客的数量为N,则系统需要的内存为O(N),每次网站访问需要花费长为O(log N)的时间来检查是否是一个独立访客。


  KMV(第k个 最小值)算法的策略是以存储更少的值(k个值)为基础,从中可以估计出N的大小,而且误差范围固定。要存储的值使用哈希函数计算得出,该函数将要测量的变 量(在这个例子中是指对页面的独立访问)映射成0到1之间的一个值;实际上,这个哈希函数是什么并不重要,只要结果可以均匀地分布在0到1之间就可以。每 次测量变量的一个新实例,我们就计算它的哈希值,并查看我们是否已经存储了该哈希值,如果没有,就存储它。实际上,主要的不同点是,在任何时刻,只有k个 最小的值会被保存:如果有一个新值加入到组中,那么第k+1个值会被移除,保证内存占用一直为O(k),时间成本一直为O(log k)。这样,不同值出现的次数就可以估计为(k-1)/KMV,其中,KMV为第k个最小值,或者是组中存储的、幸存下来的、最大的哈希值。


  从检查结果表达 式很容易推断出,如果我们比较两个流的数据,一个流中出现不同值的次数多于另一个,那么出现 更多不同值的流会产生更多的哈希值,因此,存储的第k个哈希值将会比另一个流的第k个哈希值小。在k相同的情况下,第k个哈希值越小,上述表达式计算得出 的值越大。由此可以得出结论,该表达式至少是与出现不同值的实际数量成正比的。


  有多篇研究论文已 经证明了,上文从形式上阐述的表达式是一个很好的估计,不过,一个简单的试验就可以提供描述性的证据。假设一个数据流出现199个不同的值,而且我们在算 法中让k=20。如果一个哈希函数将结果均衡分布在0到1之间,那出现的199个不同的值大体上将映射为0.005、0.01、0.015等等,直到 0.995。如果我们只保存20个最小的值,那么第20个值将是0.1,将这个值带入上述表达式,结果是(20-1)/0.1=190。


  除了性能外,DataSketches还有其他特性,例如,它能够组合已经分别计算好的sketch,并得到一个综合结果,而不需要要检查底层数据。这使用户可以计算单个组的数据或者数据分区,然后根据需要组合它们。Maven Central中提供了DataSketches库,以及用于Hadoop Pig、Hadoop Hive和Druid的适配器。


查看英文原文:Yahoo Open-Sources DataSketches for Faster Operations Over Streams


酷毙

雷人

鲜花

鸡蛋

漂亮
  • 快毕业了,没工作经验,
    找份工作好难啊?
    赶紧去人才芯片公司磨练吧!!

最新评论

关于LUPA|人才芯片工程|人才招聘|LUPA认证|LUPA教育|LUPA开源社区 ( 浙B2-20090187 浙公网安备 33010602006705号   

返回顶部