必懂的NoSQL理论－Map-Reduce（下）
必懂的NoSQL理论－Map-Reduce（下）
本文主要内容：一开始我们会讨论把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框架是怎么来支持增量操作的。