MIT 6.824 分布式系统 Lab 1: MapReduce

发表于 分类于 ， 阅读次数： 本文字数： 1k 阅读时长 ≈ 4 分钟

6.824 已经做完很久了，由于日常不怎么用得到，已经忘光了。

重温一下，刚好更新到Spring 2024。

本次 Lab 1 讲的是分布式计算的 MapReduce。

#背景

MapReduce 源自 Google 在 OSDI '04 发表的论文，论文的作者是 Jeff Dean 和 Sanjay。主要提出了一种简单、可拓展的分布式计算编程模型。

对于用户来说，只需要实现 Map() 和 Reduce() 两个函数，即可享受到分布式计算的好处，这就是 MapReduce 的设计初衷。

#思想

MapReduce 需要用户将计算过程表达成以下两个函数：

  • Map(key, value) -> list(ikey, ivalue)
  • Reduce(ikey, list(ivalue)) -> list(ivalue)

到这里聪明的人可能已经感受到一点并行的思想，其实 MapReduce 是把一个任务分解成一系列子任务，每个子任务由 Map 函数去执行。这些子任务的输出会被重组，然后分门别类送到 Reduce 函数去执行。

MapReduce 的 Motivation 是：

  • 很多大数据计算任务都是大量输入对应到小量的输出；
  • 分而治之，一个复杂计算任务往往可以分成多个更简单的部分；
  • 子任务之间往往可以并行执行； -> Map

怎么区分”多个更简单的部分”？使用ikey标示子任务。

#MapReduce 程序示例

#Word Count

Word count任务是统计一批文本中每个词出现的数量

Map任务：统计一个分块中的词频

Reduce任务：合并所有分块的词频

#Grep

Map任务：对一个分块做grep

Reduce任务：合并所有的grep结果

#计算图的逆

已知所有的<source, target>边，计算每个target被哪些source引用

Map任务：逆转一组边，得到<target, source>

Reduce任务：按target合并所有的source

#分布式排序

Map任务：原样输出

Reduce任务：原样输出

#框架实现

MapReduce 框架负责调度和执行用户编写的 Map 和 Reduce 任务。

根据环境（机器配置，网络拓扑，故障概率，和存储成本）不同，可以有很多不同的实现方案

#概览

框架首先将输入数据分成MM块，然后对每一块分别执行map过程，这个过程是在多个机器上并行执行的；

在map全部完成后，将中间结果按照某些策略分成RR块，然后并行执行reduce过程；

#容错设计

Worker节点的保障：Master节点会周期性地ping Worker节点；失联Worker节点已完成的任务会重新调度。

Master节点的保障：Master节点会周期性做checkpoint方便故障时重新开始。

出错时的语义保证：需要实现map/reduce任务提交是原子性的

  • map任务通过提交临时文件名，由master做改名实现。
  • reduce任务完成时会把工作临时文件改名为目标文件。

#局部性

分析局部性主要是考虑到带宽资源的限制。

论文中实现的 MapReduce 是建立在 GFS (Google File System) 上的，GFS 会对文件进行分块然后保存三份副本。

作者在实现时考虑到了底层GFS的影响，会尽量调度任务到有副本或者距离副本近的机器上。

#任务划分粒度

在 map 阶段，输入数据会被划分成MM 个分块，在 reduce 阶段，中间结果会被划分成RR 个分块。

#备份任务

TODO

#实现优化

#回到 Lab 1

Lab 1 是实现 MapReduce 框架的两个组件 Coordinator（ Master） 和 Worker。

  • Coordinator 负责分发任务给 Worker，会启动一个 RPC Server；
  • Worker 从 Coordinator 那里获取 Map 或 Reduce 任务并执行。

整个 MapReduce 框架包括：

  • main/mrcoordinator.go 是 Coordinator 的入口，会调用 MakeCoordinator() 然后等待；
  • main/mrworker.go 是 Worker 的入口，会加载用户程序获得 mapf 和 reducef，然后调用 Worker；
  • mr/coordinator.go 实现 Coordinator 的逻辑；
  • mr/worker.go 实现 Worker 的逻辑；
  • 用户程序会被编译成 go plugin，被框架加载然后调用。

#Lab 2: Raft

Raft 是一种经典的分布式共识协议。

节点状态: Follower、Candidate、Leader

#Lab 3: