Map-Reduce

读书笔记

---

【Rajaraman A, Ullman J D. 大数据: 互联网大规模数据挖掘与分布式处理[J]. 2012.】

基础介绍

1、物理结构

处理计算的节点存放在机架上，每个机架安放8-64个节点。单机架间通过以太网网络互连，多个机架之间一般采用另一级网络或交换机互连。

2、故障处理

为了使计算任务能正常完成，就决定了不可能一旦某部件出现故障就终止并重启计算过程，通常采用两种方式解决故障处理的问题。
(1)文件多副本存储;
(2)计算过程分多成多个任务进行。

3、系统结构

分布式文件系统的典型使用方式为：
(1)文件非常大；
(2)文件极少更新。
在分布式文件系统（DFS）中，文件被分成文件块，文件块通常在64MB大小。DFS的实际应用主要有：谷歌文件系统（GFS）、Hadoop文件系统（HDFS）等

Map-Reduce

1、基本计算过程

(1)有多个Map任务，其输入为DFS的一个或多个文件块。Map任务将文件块转换长键值对的序列；
(2)存在一个主控制器从Map任务中手机键值对并将结果分配给Reduce任务；
(3)Reduce任务每次作用一个键，将与之相关的值以某种方式组合。

2、执行细节

利用系统（如Hadoop）提供的调用库，用户程序会fork一个主控进程和运行在不同计算节点的工作进程（Map任务和Reduce任务）。Map任务数量不限，但是Reduce任务一般都有所限制，因为每个Map任务都必要给每个Reduce任务创建一个中间文件，这个中间文件的数目必须给予控制。

3、失效处理

除非主控节点奔溃，否则Map-Reduce作业总会执行完毕。

使用Map-Reduce的各种算法

1、矩阵-向量乘法

一个n*n的矩阵M，一个n维向量v，则他们的乘积是一个n维向量x，其第i个元素$x_i$的值为

$$x_i = \sum_{j=1}^n m_{ij}v_j$$
此时，相应的Map函数和Reduce函数为。
Map函数
每个Map函数将整个向量v和矩阵M的一个文件快作为输入。对每个矩阵元素$m_{ij}$，Map函数都会产生键值对（i，$m_{ij}v_j$）。因此，计算$x_i$的所有n个求和项$m_{ij}v_j$的键值都相同。
Reduce函数
Reduce任务将所有与i关联的值相加即可得到（i，$x_i$）。
当向量v大到无法放入内存时，一种替代方案是将矩阵分割成多个宽度相等的垂直条，同事将向量分割成同样数目的水平条，保证每个水平条的高度等于矩阵垂直条的宽度。

2、选择运算

Map函数
对R中的每个元组t，检测它是否满足C。如果满足，则产生一个键值对（t，t）。也就是说，键和值都是t。
Reduce函数
类似于恒等式，它仅仅将每个键值对传递到输出部分。

3、投影运算

投影运算与选择运算很相似，由于投影运算可能会产生多个相同的元组，因此Reduce函数必须要提出冗余元组。
Map函数
对R中的每个元组t，通过提出t中属性不在S中的字段得到元组r'，输出键值对（t'，t'）。
Reduce函数
将（t'，[t'，t'，…，t']）转换成（t'，t'），以保证对每一个键t'只产生一个（t'，t'）对。

4、自然连接运算

考虑将R（A，B）和S（B，C）进行自然连接运算。该自然连接运算实际上是要去寻找字段B相同的元组，即R中元组的第二个字段值等于S中元组的第一个字段值。
Map函数
对于R中的每个元组（a，b），生成键值对（b，（R，a）），对S中的每个元组生成键值对（b，（S，c））。
Reduce函数
将键b对应的输出结果为（b，[（$a_1$，b，$c_1$），（$a_2$，b，$c_2$），…]），也就是说，与b相关联的元组列表由来自R和S中的具有共同b值的元组组合而成。

5、矩阵乘法

矩阵M中的第i行第j列的元素记为$m_{ij}$，矩阵N中的第j行第k列的元素记为$n_{jk}$，矩阵P=MN，其第i行第k列的元素记为$p_{ik}$，其中

$$p_{ik} = \sum_j m_{ij}n_{jk}$$
把矩阵M看成是关系M（I，J，V），其元组为（i，j，$m_{ij}$）。矩阵N看成是关系N（J，K，W），其元组为（j，k，$n_{jk}$）。那么MN的运算也就可以理解为一个自然连接运算再加上分组聚合运算。也就是说对于M中的每个元组（i，j，v）和N中的每个元组（j，k，w），两个关系的自然连接会产生元组（i，就，k，v，w）。我们实际目标是对元素求积，也就是产生四字段元组（i，j，k，v*w）。得到上述结果关系后，接下来就是分组和聚合运算了。
Map函数
将每个矩阵元素$m_{ij}$传给键值对（j，（M，i，$m_{ij}$）），将每个矩阵元素$n_{jk}$传给键值对（j，（N，k，$n_{jk}$））。
Reduce函数
对每个键j，检查与之相关联的值的列表。对每个来自M的值（M，i，$m_{ij}$）和来自N的值（N，k，$n_{jk}$），产生元组（i，k，$m_{ij}$$n_{jk}$）。
Map函数
将上面的Reduce函数的输出作为输入，这些结果的形式为（j，[（$i_1$，$k_1$，$v_1$），（$i_2$，$k_2$，$v_2$），…，（$i_p$，$k_p$，$v_p$）]），其中每个$v_p$是对应的$m_{iqj}$和$n_{jkq}$的乘积。基于该元素可以产生p个键值对（（$i_1$，$k_1$），$v_1$），（（$i_2$，$k_2$），$v_2$），…，（（$i_p$，$k_p$），$v_p$）。
Reduce函数
对每个键（i，k），计算与此键关联的所有值的和，结果记为（（i，k），v），其中v是矩阵P的第i行第k列的元素值。

集群计算算法效率

1、开销模型

一个算法的通信开销是实现算法所有任务的通信开销之和。一般的，我们在估计算法运行时间的时候并不考虑每个人物的执行时间。
例如：假设对R（A，B）、S（B，C）这两个关系进行连接运算，关系R和S的规模分别为r和s。那么，R和S的每个文件快传递给一个map任务，所有Map任务的通信开销之和就是r+s。Map任务单额输出规模与输入规模大体相当。每个输出的键值对都传给一个Reduce任务，该Reduce任务不太可能与刚才的Map任务在同一个计算节点上运行。因此，Map任务到Reduce任务的通信有可能通过集群互联来实现，而不是从内存到磁盘的传输。该通信的开销是O（r+s），因此连接算法的通信开销为O（r+s）。

2、实耗通信开销

指在无环网络图所有路径中最大的通信开销，也就是路径上所有任务的通信开销之和。实耗通信开销就是任一Map任务的最大输入规模和任一Reduce任务的最大输入规模之和。

3、多路连接

待定