mit6.824之MapReduce
mit6.824：MapReduce系统
最近决定开始学习mit6.824 Distributed Systems课程，主要包括阅读论文，课堂笔记和完成project，内容均在mit6.824 课程主页上找到。第一部分是经典的MapReduce系统设计，通读MapReduce论文，在此总结记录个人认为MapReduce设计的要点。
- MapReduce执行流程
- Fault Tolerance(容错机制)
- MapReduce 系统优化
MapReduce执行流程
MapReduce包括Map和Reduce两部分，具体的执行流程如下图（from MapReduce osdi04）所示。MapReduce运行于由大量PC或者server组成的Google File System (GFS)集群上。集群中的节点分为Master和Worker两种。
当User Program向Master节点提交一个任务后，Master节点会向M个Worker节点分发任务信息，每个worker节点会从GFS读取相应的文件，并调用相应的map函数执行，在map任务都执行完毕后，进入Reduce阶段。Master节点向worker节点分配Reduce任务，对应的worker会执行相应的reduce函数，生成最终的output，并通知master节点输出文件的存放地址。
Fault Tolerance (容错机制）
任何一个分布式系统都要考虑当某些节点宕机或者网络连接断开的情况，需要保证即使部分节点失去连接也能完成任务。在MapReduce系统中我们认为Master节点是可靠的（关于Master的容错我们会在后续博客讨论），仅讨论当部分在执行Task(Map or Reduce)的worker节点在执行任务过程中失去连接后如何进行容错。
在MapReduce系统中，Master节点会维持与每一个worker节点的连接，每隔一段时间发送一次确认信息，如果worker节点没有回应，则标记该worker节点失去连接，倘若该节点正在执行任务，则需要重新分配对应的任务。
Map task fail
执行map任务的worker节点需要在本地生成对应的中间文件(local intermidate file)，并通知master节点任务已经完成，告知master节点中间文件的存放路径和名称。此时若某一个执行map的worker节点失去连接，master节点只需要将原本分配与该节点的task信息发送给一个新的worker节点即可。由于中间结果文件都是在每个worker节点本地生成，因此不需要考虑中间文件覆盖的问题。
Reduce task fail
执行reduce task的worker节点需要读取所有map任务生成的中间文件，执行reduce函数，生成结果文件。在MapReduce设计中，结果文件的名称都是规定好的例如reduce-1代表r=1的task的结果文件。reduce task在执行过程中，会不断将结果Append到一个随机命名的文件，只有在task完成后，才会将该文件重命名为规定好的名称。
因此，如果worker节点在执行reduce任务时失去连接，master同样只需要将task重新分配给新的节点即可。
Summary
对于两种任务的容错，master节点都只需要将任务分配给新的worker重新执行即可。这是因为map和reduce生成结果文件的过程都是原子性（atomic）的，因此不需要考虑输出互相覆盖的问题。map任务的输出文件是存储在本地的，而reduce任务的结果虽然是保存在GFS上，但是只有在生成完毕后才会重命名为对应的名称。由于生成文件过程是原子的（重命名这一操作的原子性由文件系统保证），任务失败只需要分配新的worker节点重启任务即可。
MapReduce 系统优化
论文同时给出了对MapReduce系统的几种优化技术，这些技术对于分布式系统设计具有重要的借鉴和参考意义。
Locality
缓存中会利用数据的时间和空间局部性来减少缓存写入写出次数，对于分布式系统，空间局部性具有重要的价值。我们假定任务的输入数据是存储在GFS上的，GFS通常将每个文件划分为64MB大小的块，并复制多个拷贝存储在不同的节点上。空间距离较近的两个节点数据传输时间更短，对于同一个内网的两个节点更加明显。因此Master节点在分配一个任务时，可以优先将任务分配给包含输入数据拷贝的节点，如果没有这样的节点，在尽量分配给具备数据拷贝节点的邻居。最终，大部分输入数据并不需要额外的传输，节省了网络带宽，降低任务总执行时间。
Decide M and R
我们建议使用较大的M和R数值，较大的M&R代表更多同时更小的任务，同时具有如下三个优点：
- 提高并行度，更大的M和R意味着更多可以同时运行的task数量
- 改善动态的负载均衡
- 当worker fail时，更小的任务可以降低重启任务的代价
对于master节点，需要进行O(M+R)次调度，并保持O(M*R)的状态数据，但其常数是非常小的，相比带来的改善，内存增加的开销完全可以忽略。
在实际应用中，R往往被用户指定来限定最终输出文件的数量，我们通常选择一个合适的M值使得每个Map Task的输入数据通常是16或64MB （这是由于GFS中一个文件快的大小恰好是64MB，根据具体实现细节，这一数值也会改变）以充分利用GFS的数据空间局部性。在Google内部应用中，通常选择10^5 级别的M。
Local Combiner
有时候Map任务会输出大量重复的key，例如WordCount任务，Map输出的是
Lab1
Lab1目标是实现一个简单的MapReduce系统，只要按照标准Map Reduce系统结构实现即可，网上的讲解和代码也很多，就不赘述了。