必懂的NoSQL理论－Map-Reduce（中）

本文主要内容：分区和归并

上一文：必懂的NoSQL理论－Map-Reduce（上）

Partitioning and Combining 分区和归并

在最简单的情况下，我们可以认为一个map-reduce job只有一个reduce函数。所有的运行在各个节点上的map任务的输出（outputs）最后都被放到一起然后发送给reduce。这样做是可以正常工作的，然而我们其实可以做更多的事情，提高并发能力以及减少数据的传输。（如图7.3）

图7.3. 分区后就允许多个reduce函数在不同key下并发的运行来做reduce操作

我们可以做的第一件事情就是通过把各个mapper的输出做分区来提高并发。每个reduce函数只能操作具备相同key的一组结果。这样做是一个局限——因为这意味着reduce函数的参数不能有多个key；但这也是一个优势：那就是可以并发的运行多个reducer。为了发挥这种并发的优势，在每个处理节点上的mapper的输出结果被按照key给分割开来，一般情况下，多个key被按照key来group在一起然后放入分区。框架然后把所有节点上应该归入某个“分区”的数据拿过来，把这些数据合并成一组，放入那个“分区”里，然后把这份数据发送给reducer。这样的话，多个reducer就可以并发的在各个分区上进行运算数据了，然后把最终的结果合并到一起。（这一步也被叫做“shuffling”，洗牌，并且分区（partitions）也被叫做“buckets”或者“regions”）。（ps：也就是这里其实有两个分区，一个是mapper输出结果的第一次分组，叫做分区，或者叫做分组。第二次分区是交给reducer之前做的分区）

接下来我们需要解决的问题就是：如何减少在map和reduce的阶段中节点和节点间传递的数据量。这些数据很多都是重复的，而且都是由多个拥有相同的key的key-value对组成。归并函数（combiner function）把那些有相同的key的数据合并成了一个value。（见图7.4）归并函数本质上其实就是一个reducer函数——的确，在很多情况下用同一个函数就可以被用来归并作为最终的reduction。reduce函数需要符合特定的格式才能被用作执行归并（combine）：就是reduce函数的输出必须要和它的输入参数匹配。如果满足了这个条件，我们就把这种函数叫做可归并的reducer（combinable reducer）。

图7.4 在通过网络发送数据之前就把数据归并，减少传输量

当然了，并不是所有的reduce函数都可以被用做归并操作。比如说现在需要统计购买某个产品的客户数（同一个客户多次购买不重复计算）。map函数对于这样的一个操作就需要吐出产品（product）和客户（customer）。reduce函数然后就可以把这些给合并并计算出指定产品的每个客户出现的次数，最后输出产品（product）和客户数（count）（见图7.5）。但这个reducer的输出和自己的输入是不一样的，所以这个reducer就不能被用做combiner（归并）。这种情况下你依然可以运行一个归并函数（combining function）：功能就是把重复的product-customer的对子给去掉，但是这样还是和最终的reducer不太一样。

图7.5 这个reduce函数是用来计算购买某个茶叶的客户数量，不能被用做“归并”

当你拥有了可归并的reduce函数（combining reducers），map-reduce框架就不仅可以安全的并发的运行（同时还能reduce不同的分区），而且还可以在不同的时间和地点陆续的reduce同一个分区。除了可以在传递之前就在某个节点对数据进行归并外，我们甚至可以在mapper还没执行完的时候就做归并。这样的话，我们的map-reduce处理过程就更加的灵活了。有些map-reduce框架要求必须是所有的reducer们同时也是combiner。这么做是最为灵活的。在这些框架里，如果你需要构建一个不具备归并能力的reducer，那么你就需要把整个map-reduce过程分成几个步骤来做。

下集我们主要说有关组合Map-Reduce计算（Composing Map-Reduce Calculations）的内容，敬请期待！