Lec1: MapReduce

开个新坑，也是赫赫有名的神课啊，老师跟6.S081一样，也是我们的老熟人，Frans Kaashoek和Robert Morris。课程内容呢，大家也都知道，用Go语言讲的分布式系统。

第一节课一般来说都是废话，将规章制度和课程大纲和教学计划之类的，但是这次一反常规，讲了MapReduce这个分布式中的重要概念。

网络分区

这是Lecture 1前期讲的一个概念，也是分布式系统的一个重要概念。

对于一个 $n$ 个节点组成的网络来说，如果 $n$ 个节点可以被分为 $k$ 个不相交且覆盖的 group , 每个 group 内所有节点全是两两正常连接，而任意两个 group 之间的任何节点无连接。当 $k = 1$ 时，网络正常，当 $k > 1$ 时，我们称之为network partition。

大白话就是说，要把一个网络集群下的节点分成几个不相交且全覆盖的组，每个组内的节点之间全是正常连接，而任意两个组之间的节点都没有连接，那么就叫它为网络分区。

为什么说这个概念重要呢？因为当网络发生分区时，集群的几个组之间就无法通信，并且各自为政，互相都以为除了自己这个组之外全世界都已经挂了。一般是由集群中的某个节点故障引起的，会造成的大规模故障。

如果有 1% 的请求耗时高于 99% 的请求耗时，影响用户体验，甚至拖垮服务，我们就认为它不是一个好的分布式系统。

MapReduce

MapReduce是一种编程模型，是由Google提出的一个分布式计算模型，其核心思想是将大数据集分解为多个小数据集，然后并行地对小数据集进行处理，最后再合并处理结果。

本质上来说，它利用的是一种分治的思想，用来实现高可用（因为集群化中节点的失效往往不会导致整个集群的崩溃）、可扩展（集群中的节点可以动态增加或减少等维护）、高效率（分布式代表着并行计算，因此可以充分利用多核CPU的优势）的计算（可以是经典统计字母出现的次数，也可以是排序等算法）。

Map: 输入数据集被分解为多个小数据集，并行地对每个小数据集进行处理，结果被保存在内存中。
Reduce: 对Map的结果进行汇总，得到最终结果。

几个概念:

Coordinator：负责调度任务，分配任务给Worker，监控Worker的运行状态，并在必要时重新调度任务。
Worker：负责执行任务，并将结果返回给Coordinator。
Master：负责管理Worker节点，包括监控Worker的健康状态、分配任务、监控任务的执行进度等。

执行过程:

Split -> Map -> Shuffle -> Reduce

Split: coordinator将文件分配给特定的worker节点。
Map: worker节点执行map任务，将生成的中间结果存储在本地磁盘，worker在map任务执行完毕后，告知master中间结果的存储位置。
Shuffle: 将map端无规则输出的结果进行分组，洗牌成有一定规律的数据，以便reduce端进行接受处理。
worker节点并行地对洗牌后的每组数据进行reduce操作，将结果聚合返回给coordinator。

注意只有最终结果才是全局的，中间结果只会被存在worker节点的内存或磁盘中。

容错性

如果coordinator没有收到来自worker的响应，那么coordinator会认为该worker已经挂了，从而将该worker上的任务重新分配给其他worker（可能分配给同一个worker），以保证task的执行。

其实一个map函数也是可能被执行两次的，因为worker节点可能执行完之后，出现了网络故障，导致响应没有传达给coordinator，这时coordinator会认为该worker已经挂了，然后重新分配任务给其他worker执行map。而且最关键的是，map被执行两次其实是可以被接受的，因为基于幂等性问题，相同的输入得到的输出是相同的，因此不会影响最终结果。

异常场景

map在worker上的执行符合事务性，即使worker执行了99%的任务，到最后出现了故障，coordinator也会重新分配重新完全执行这个任务。
map产生的中间结果只会保存在worker本地文件系统当中。而且得益于持久化的保存机制，之前map生成的中间结构都可以被recover。
我们可以接受worker的崩溃，但是无法接受coordinator的崩溃

Struggler: 对于一些执行缓慢的worker它们会被称为struggler，这时coordinator会将其上的任务重新分配给其他闲置的worker，而它们的工作也不会白费，因为这样可以达到backup的效果。这样既不会因为木桶效应拖慢整个集群的运行，也可以增加资源利用率，并且备份保存运行信息。