必懂的NoSQL理论-Map-Reduce(下)

本文主要内容:一开始我们会讨论把map-reduce切分成个两个阶段的内容,然后会说有关如何处理增量的基础理论。

上一文:必懂的NoSQL理论-Map-Reduce(中)

系列文章:

必懂的NoSQL理论-Map-Reduce(上)

必懂的NoSQL理论-Map-Reduce(中)

Composing Map-Reduce Calculations 组合Map-Reduce计算

map-reduce是一种思考并发处理的方式,为了在集群上更好的并发的处理计算,我们将计算过程组织成为一个相对直观的模型,这个结果是我们经过与灵活性权衡后得到的。(ps:简单就意味着不够灵活) 由于这需要权衡,所以我们的计算过程就要受到一定程度的约束和限制。什么限制?就是在一个map task里边,你只能操作一个聚合内的数据( a single aggregate);同样的在一个reduce task里边,我们只能操作具有同一个key的数据。这就意味着我们不得不去重新考虑我们如何组织我们的程序(programs)使得我们的 mapper和reducer可以在这种约束下依然工作的很好。

一个简单的限制就是你不得不按照reduce操作的要求来组织你的计算操作。一个很好的例子就是计算平均数。现在我们再来说说我们的老例子,就是订单的例子。假设我们想要知道每个产品的平均的下单数量。平均数的一个重要的属性就是他们不是“组合”——什么意思呢?就是如果我现在拿到两组订单,我不能把他们两个的平均值合并然后求出平均值。而是我要拿到一个总的数量以及每个组的订单数量,然后把每个组总量以及订单量进行分别合并求和,然后再从合并后的总和合并后的数量中最后求出平均量。(ps:其实这是小学时学的数学。)

图7.6. 当我计算平均数的时候,总和和数量可以在reduce的计算中被合并,但是最后的平均数必须要通过合并后的总和(sum)和合并后的数量(count)中 计算得出。

寻找优雅的reduce算法时所有的这种思路也可以用在我们的计数上。我们为了计数,就让map函数输出一个计数字段(count fields),这个字段的值为1。这些1最后求和后就可以得到一个总量了(如图:7.7)

图7.7. 当我们要计数时,每个map都输出1,这样把所有的1加起来就可以算出总订单量了。

7.3.1. A Two Stage Map-Reduce Example 举例说明两个阶段

由于map-reduce比较复杂,那么我们可以使用“管道及过滤器”(pipes-and-filters)的手段把map-reduce计算切分成多个阶段,也就是一个阶段的输出是下一个阶段的输入,就有点像UNIX的管道。

现在举个例子,我们想要把2011年的每个月的产品的销量与上一年进行比较。要想做这件事情,我们将会把整个计算过程切分成两个阶段。第一个阶段将生成某产品在一年中的某个月的销量。第二个阶段的输出是上一年的那个月的销量(见图7.8)。

图7.8. 一个计算过程被切分成两个map-reduce阶段,后面的三张图会详细的介绍里边的细节

第一个阶段(图7.9) 就是读取原始的订单记录,然后输出一系列每个月每个产品的销售情况的key-value对。

图7.9.创建产品月销量记录

这个阶段类似于我们之前举的那些map-reduce例子。唯一不同的地方就是使用了“组合key”(composite key)的方式,这样做是为了我们可以基于多个字段的值来reduce我们的数据。

第二阶段的mapper(图7.10)就是按年份处理上面的那个输出。一个2011年的记录用来生成当年的数量,而一条2010年的记录用来生成上一年的数量。其他年份(比如2009年的)将不会被任何一个mapper作为结果输出,也就是其他年份的被忽略掉了。

图7.10. 第二个阶段的mapper负责创建出用来计算同比增加所用的基础记录。

此时(图7.11)的reduce就是对记录的一个合并(merge)的过程,就是把两份记录中的数值汇总到一起,把两个不同年份的输出最后reduce成一个值(此外,还根据reduce之后的值算出销量的增幅)。

图7.11. reduction的阶段负责把两条不完整的记录合并起来。

把这样一个报表的生成过程分解为多个 map-reduce步骤后,我们的编程工作就更简单了。和很多的数据转换(transformation)的例子一样,一旦我们找到了一个可以让各个步骤轻易组装的“转换框架”(transformation framework),那么我们就可以轻松的把很多个“小步骤”组合在一起来完成任务,而不是把所有的逻辑都塞入一个“大步骤”中。

“两阶段map-reduce”的做法的另外一个好处就是那些生成的中间结果(中间输出,英文是intermediate output)是非常有用的,这些输出可以用来计算其他的输出数据。所以这些中间输出是可以复用的。复用是很重要的,因为它可以节省你编程和执行的时间。这些中间记录( intermediate records)你可以存到数据库中,来构成物化视图(materialized view)。前面我们讲过有关物化视图的内容。尤其是map-reduce操作的早期阶段所生成的数据保存起来特别有价值,因为很多的数据访问操作都会用到这些数据,所以一次性构建好这些数据,提供给下游来使用这些数据,可以节省很多的工作。然而和所有的“复用”行为一样,最好是有实际的查询需要了,再去复用,凭空想出的复用很少能派上用场。所以在构建复用数据之前,要见识到各种不同形式的查询需求,在这个基础上,再把它们中具有共性的、共同的部分放入到物化视图中。

Map-reduce是一种模型,一种pattern。可以用任何的编程语言去实现。然而,受其风格和气质所限,最好还是使用一门专门为map-reduce运算设计的语言去实现。(ps:这个说法貌似有点怪怪的) Apache 的Pig,是Hadoop的一个分支,就是这样的一个专门的语言,可以用它来轻松的编写map-reduce程序。用Hadoop框架当然要比使用纯粹的底层的java库编写要容易的多。与之类似的还有,如果想要通过使用类似SQL的语法(SQL-like syntax)来编写map-reduce程序,那么可以使用另一个Hadoop的分支:hive[Hive]。(ps:这里说了什么可以忽略,因为现在已经有更先进的了)

就算在不使用NoSQL数据库的环境下,map-reduce模型也是很重要的。Google公司当初就用“map-reduce 系统”来操作存储在分布式文件系统上的文件——开源的Hadoop项目所用的方法也是这个。要使用map-reduce模型,就得将数据的计算操作分解成很多个步骤,很多个阶段,我们确实需要花些精力来适应这种约束和限制,但这样设计出的运算过程是非常适合运行在集群上的。面向聚合的数据库非常适合这种风格的计算模型。我们估计在不久的将来很多的企业将要处理海量的数据,这种情况下,只有面向集群的方案才能hold住——到那个时候,map-reduce将会被更广泛的了解和使用。

7.3.2. Incremental Map-Reduce 增量的map-reduce

我们刚才讨论的这些例子都使用完整的map-reduce计算流程,也就是从原始输入数据开始,直到算出最终的输出结果。许多的map-reduce计算,即使是放在集群的多台机器上,也需要花很长时间,而且新的数据还在不断的涌入,这就意味着我们需要重新执行计算流程来保证输出结果不过时。每次重新开始计算都要花很长时间,所以通常都会把map-reduce计算流程组织成允许“增量更新”的形式,这样就能把计算量减至最低了。

在map-reduce的map阶段,做增量是比较容易的——只要输入的数据改变了,mapper就重新执行。因为mapper们相互之间都是隔离的,所以增量更新是比较容易的。

比较复杂的是在reduce阶段进行增量更新,因为它要把来自很多的map输出汇聚到一块,如果某个map的输出数据改变了,那么就要触发一次新的redcution。根据reduce阶段的并发程度,我们可以减少重新reduce时候的计算量。如果我们正在把将要reduction的数据“分区”(partition),那么那些数据没有变化的分区就不需要被重新reduce了。类似的,如果也有combine(归并)的阶段的话,如果combiner的源数据也没改变的话,归并操作也不需要重新执行了。

如果我们reducer是可以用做归并(combinable)的话,那么我们就有更多的机会来避免重新计算了。如果这种变更是可叠加(additive)—也就是说,如果我们只是增加新的记录不变更也不删记录——那么我们就可以只针对现存的结果和新加的那部分来进行reduce操作。如果是破坏性的改变,也就是涉及到更新操作以及删除操作,那么我们就可以通过把reduce操作分解成很多个步骤并且只是重新计算那些输入被改变的步骤来避免重新计算——实际上,这种情况下,我们可以使用“依赖网络”(Dependency Network) [Fowler DSL] 来组织计算流程。

上面说的很多东西都可以用map-reduce框架来控制,所以你需要明白你所使用的那个map-reduce框架是怎么来支持增量操作的。

原文发布于微信公众号 - ImportSource(importsource)

原文发表时间:2016-06-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏吉浦迅科技

手把手在亚马逊EC2上搭建Keras GPU

由于需要使用越来越复杂的神经网络,我们还需要更好的硬件。但我们的电脑通常不能承受那么大的网络,不过你可以相对容易地在亚马逊上租用一个功能强大的计算机,比如E2服...

4966
来自专栏Flutter入门

偶遇FFmpeg(一) —— 初了解

FFmpeg的介绍网上还是很多的。官网的wiki上面也有很多内容。围绕目标,主要是有两套实现的思路。早期,其实是想通过自己编写C代码,来完成整个流程的。但是无奈...

2512
来自专栏跟着阿笨一起玩NET

浅谈数据库设计技巧(上)(转)

转一篇他人写的数据库设计技巧,感觉也不一定都正确,开拓一下思路吧。 说到数据库,我认为不能不先谈数据结构。1996年,在我初入大学学习计算机...

2381
来自专栏奇点大数据

python需要系统学习一下

1、python是脚本语言,作为程序员我觉得至少应该掌握一本通用脚本语言,因为脚本语言与编译语言的开发测试过程不同,可以极大的提高编程效率。

1382
来自专栏灯塔大数据

每周学点大数据 | No.75 Spark 实践案例——PageRank

本文为灯塔大数据原创内容,欢迎个人转载至朋友圈,其他机构转载请在文章开头标注 编者按:灯塔大数据将每周持续推出《从零开始学大数据算法》的连载,本书为哈尔滨工业大...

3898
来自专栏企鹅号快讯

Jira入门教程 敏捷开发管理(一)

# 简介 Jira是Atlassian公司出品的一款事务管理软件。无论是“需求”,还是“BUG”,或是“任务”,都是“事务”的一种,所以Jira可以胜任非常多的...

3.6K7
来自专栏机器人网

技术猿 | 室外移动机器人组合的导航定位系统设计

---- 对于在室外环境工作的移动机器人通常使用惯导/卫星组合导航方式。惯性导航系统[1]具有完全自主、抗干扰强、隐蔽能力好和输出参数全面等优点,但它的鲁棒性...

3145
来自专栏从流域到海域

用JAVA的DEA算法衡量社交媒体页面的流行度

原文作者:Vasilis Vryniotis

2746
来自专栏拂晓风起

【转】Flash:同志们,这些知识点你们知道多少?(一些必备的Flash开发知识点)

1222
来自专栏玉树芝兰

如何用Python提取中文关键词?

本文一步步为你演示,如何用Python从中文文本中提取关键词。如果你需要对长文“观其大略”,不妨尝试一下。

2222

扫码关注云+社区

领取腾讯云代金券