分布式系统 MapReduce

2024-04-12 20:03:38

MapReduce

一、作者想达成什么目标？

让没有并行和分布式经验的程序员也可以利用大型分布式系统的资源。
隐藏掉那些关于并行化、数据分发、负载均衡、容错(fault-tolerance)的混乱而棘手的细节(messy details)。

二、作者发明了什么技术方法？

一种编程模型和它的实现。
用户只要写一个map函数，和一个reduce函数。

MapReduce的概要

输入被分成M个文件

 Input1 -> Map -> a,1 b,1 c,1   
 Input2 -> Map ->     b,1  
 Input3 -> Map -> a,1     c,1
                  |   |   |
                  |   |   -> Reduce -> c,2
                  |   -----> Reduce -> b,2
                  ---------> Reduce -> a,2

MR为每个文件调用一次Map(), 产生一系列 k2,v2，"中间"数据
对于每个键k2，MR收集它所有的值v2，并传递给一个Reduce调用
（注：同一个key都是分给同一个Reduce）
Reduce处理的结果是一组 <k2, v3>
总之：
[ map(k1, v1) -> list(k2, v2)
reduce(k2, list(v2) -> list(k2, v3)]

例子：单词计数

Example: word count
  input is thousands of text files
  Map(k, v)
    split v into words
    for each word w
      emit(w, "1")
  Reduce(k, v)
    emit(len(v))

MapReduce 隐藏了一些痛苦的细节

启动服务器上的软件
跟踪任务的完成
数据移动
从失败中恢复

并行化：可扩展性很好

N台电脑可以带来N倍的吞吐量
这里的假设是输入文件和要输出的key都非常多！
不同的输入文件是可以并行的，不同的key也是可以并行的。
Map任务都可以并行化。Reduce任务也一样！

数据分发：对性能最大的限制是网速

解决办法是Locality！——减少数据移动。
Map的计算结果直接存在本地磁盘，而不是存在网络文件系统上。
MR节点，同时也都用作GFS节点。
输入文件在哪个节点，就安排这个节点做该文件的Map工作，省得移动数据。

负载均衡

如果很多台电脑等1台慢的电脑，就非常影响效率。
解决办法：
任务比工人多得多。早完成的，就可以做其他任务，不用干等着。

故障容忍

MR处理方法很简单：重新运行失败的Map或者Reduce任务。
为什么能这么简单？
因为Map和Reduce是“纯函数”，不保存状态，不读写其他文件（除了指定的输入/输出），任务之间没有（hidden）通信。
要求是“纯函数”很大程度上限制了MapReduce的灵活性。
但是这对于保持简单性非常关键。

哪些应用不适合用MapReduce做？

小数据。例如网站后端。
大数据的小更新。例如：在一个很大的索引上加几个新文件。
无法预测的读。
多次的shuffle，例如page-rank。
更灵活的系统允许做这些，但是系统也更复杂。（MapReduce优势就是简单！！）

三、作者完成得怎么样？

MapReduce单枪匹马地将集群计算普及。

缺点：牺牲了效率和灵活性。
优点： Scales well.
优点：容易编程 – 失败和数据移动都被隐藏了。

这些都是来自实践的非常好的trade-off！！

四、Lab1

作业本身并不难。尤其是因为go语言有chan这个机制。worker的循环利用只要把完成任务的worker重新加入到chan里面就可以了。非常简单！
但是这里也有个坑。作业里面registerChan容量是0，如果你发送的时候没有人接收就会阻塞。执行到最后2个任务的时候，旧任务完成没有新任务了，就阻塞。我的解决办法是改成非阻塞的，用select加default。
另外一个坑是go程之间不要共享数据。我用for循环创建go程，给每个go程分配任务编号i，由于是内部函数，可以用外部函数的变量，我就没有传i进去。结果变成所有go程都共享这个i，就会出错！！！

码农公寓