Map-Reduce

Map-Reduce是由Google在2004年提出的大数据并行编程架构。分为Map（映射）和Reduce（化简）两个步骤。因此得名。它隐藏并行化、容错、数据分布、负载均衡等细节，能够搭建在普通PC上，程序猿能够非常方便完毕大数据并行编程。

并行运算的效率

• 假如使用1个处理器花费T1时长能够完毕任务，而使用了p个处理器须要Tp时长。

  那么加速比为：S(Speeup) = T1/Tp，效率为：E = S/p = T1 / (p Tp)

• 一般效率都小于1，并且p越大效率越低，可是在数据集增大时。效率会对应的有所提高。

传统的并行处理架构

数据并行架构：共享内存-切割任务

• 内存（数据）是共享的，把任务分为p个部分，分别由p个处理器完毕。为防止冲突。每一个处理器都要在開始工作时对使用的数据段加锁，以堵塞其它任务使用这一数据段。任务完毕之后。才会解锁。

• 非常显然，假设p个处理器同一时候对不同的数据段进行处理。效率是非常高的。但假设有冲突，就会带来额外的通信开销，减少效率。

消息传递架构：消息传递-切割数据

• 如MPI和PVM。
• 消息传递机制把数据分为p个数据段，p个CPU分别使用一个数据段完毕相同的任务。

• 这样的方式的问题是。一个CPU的运算须要使用还有一个CPU的运算结果以完毕下一步的任务。这样，它们之间就须要交换数据。
• 这个问题使得消息传递架构比数据并行架构更复杂。但消息传递架构更具有可扩展性。比方在数千个CPU的情况下，降低冲突是非常难做到的。

  
  

除了上述两种方式外，共享内存-切割数据和消息传递-切割任务也是能够的。

Map-Reduce架构

• Map-Reduce是一种抽象的消息传递。及数据并行化的架构。

• 
  

• 如图所看到的，左方为代处理数据集，右方为处理结果数据集。图中圆角矩形代表map和reduce节点，每一个相应一台电脑。

• Map函数把输入数据中的一个key/value对（k1,v1）映射为一组暂时key/value对（k2,v2）。

  每一个key/value对都是被独立操作的。并且没有改动原始数据。因此Map操作是能够高度并行的。如图示map1、map2……mapM。

• Reduce函数接收键为特定的k2的一组暂时key/value对，并合并这些结果得到终于结果（k2,v3），这里键值k2是不变的。

  如图示reduce1，reduce2……reduceR。

  相对来说实现并行要难一些。

• 除了这两个函数之外，还须要做一些额外工作。
  • 每一个Reduce节点仅仅接收键固定的暂时key/value对，平台要依据暂时key/value对的键把key/value对送至对应的Reduce节点。
  • 暂时key/value对的读写工作量也相当大。

Word counting

Word counting指的是给出一系列文档。统计全部单词的词频。Word counting就是Map-Reduce的Hello word!。

• 
  
• 输入数据：（k1,v1），k1是文档id，v1是文档内容，即图中的(d1,"w1w2w4")。d1代表文档id，w1代表一个单词
• Map函数：从文档中每读入一个单词。就产生一个暂时key/value对，即图中左边一列灰色宽箭头
• 暂时元素：（k2,v2），k2是单词，v2是单词出现次数。即图中的第二列(w1,2)
• Reduce函数：接收全部具有同一个k2的暂时key/value对，对v2求和得到v3，即图中右边一列灰色宽箭头
• 输出结果：（k2,v3）。v3是全部文档中单词k2的词频数