Google的分布式计算模型Map Reduce map函数将输入分割成key/value对

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

http://www.nowamagic.net/librarys/veda/detail/1768

上一篇大规模分布式数据处理平台Hadoop的介绍中提到了Google的分布式计算模型Map Reduce，这里再单独拿出来了解一下。

并行计算简介

计算机的早期阶段，程序都是serial（连续的），类似于批处理程序。

并行计算的程序中，进程将一个任务分割成多个部分parts，每个“部分“都是能够并行处理的，每个“部分”可以同时运行在不同的cpu上，这些cpus可以是同一台机器上，也可以是通过网络运行在不同机器的cpu上。

如果一个程序想要通过并行来实现，第一步的工作是需要将待处理的工作分割成一系列的任务task，并且这些任务是能够并行的运行在处理器上，当然一些情况下，待处理的工作是没有办法分割成这样的一些列的任务的，例如对于计算Fibonacci这个工作：

F_k+2 = F_k + F_k+1

该工作是不能被分割为这样的一系列的任务的，因为每个计算的值是需要依赖上次计算的结果的。

下面给出一个能够被“并行”的例子：

如果有大量的数据需要被处理，如果这些数据能够被分割为等大小的小块（partitions）。更加具体话的说，对于下面的数组：

如果我们需要对于上面数组的每个元素都进行处理，并且每个计算是相对独立的话，任务之间不需要交互，这是一个使用master/worker的基本实现：

Master：

初始化该数组，并且将该数组分割成各个部分subarray
将每个subarray发送到各个worker
如果各个worker完成了对于数组元素的计算的话，master将接受各个worker的计算结果

Worker:

接受subarray
处理该subarray
将计算结构传递给master

什么是MapReduce?

在lisp语言中，map作为一个输入函数接受一个序列，然后处理每个序列中value值，然后reduce将最终的map计算出来的结果整理成最终程序输出。这就是MapReduce最初的思想来源，通过用户定义的map函数将输入分割成key/value对，然后处理该数据，最终通过Reduce函数将处理完成的记过合并。

下面是一个简单的示例程序：

map(String key, String value):
// key: document name
// value: document contents
for each word w in value:
EmitIntermediate(w, "1");
reduce(String key, Iterator values):
// key: a word
// values: a list of counts
int result = 0;
for each v in values:
result += ParseInt(v);
Emit(AsString(result));