MapReduce and Distributed Filesystems

MapReduce 有点像 昨天 讲的 Unix 工具，它通常不会修改到输入档案，除了输出以外它没有副作用 (side effect)，最大差别是它能分散到上千台机器执行。

MapReuce 读取和写入都在 分散式档案系统 (distributed filesystem) 上作业，像实作了 MapReduce 的 Hadoop 那样，Hadoop 的档案系统称之为 HDFS (Hadoop Distributed File System)，一个重新实现 Google File System (GFS) 的 open source。

HDFS 以 shard-nothing 原则为基础 (2020 Day 20)，此原则不需要特殊的硬体，只要透过网路把传统数据中心的电脑连起来就好了，在每一台机器上都会执行 守护行程 (daemon process) - DataNode，再找一台 Master 执行 NameNode 就可追踪所有档案区块在哪一台 DataNode 上。

为了容错，档案会被切成多个小块 (file blocks)，然後复制到多台节点上，这概念就像 RAID，透过同台机器 冗余 (redundancy) 的硬碟预防硬碟坏掉，HDFS 的架构如下图，有兴趣的就自己去研究啦，今天主角是 MapReduce。

MapReduce Job Execution

MapReduce 是一个程序框架让你能写少少的程序就能在分散式档案系统上处理很大量的资料，我们延用 昨天 的分析 nginx log 例子，瞧瞧 MapReduce Job 的资料处理模式为何，它们其实很相似：

1. 读取输入档案，然後分解成 records，以 log 例子来看，records 等於行（也就是用 \n 当分隔）。
2. 呼叫 mapper 函式去每一行 record 提取 key 和 value 出来，以 log 例子来看就是 awk '{print $7}' 步骤。
3. 用 key 排序所有 key-value 组合，以 log 例子来看就是第一次的 sort 命令。
4. 呼叫 reducer 函式去迭代已排序 key-value 组合，如果同一个 key 出现多次，排序步骤使它们在 list 中相邻，所以可以很简单的把它们整合在一起，且不用在记忆体中保存太多状态，以 log 例子来看就是 uniq -c 步骤。

这 4 步就是 MapReduce 的 Job，第 2 步的 map 和 第 4 步的 reduce 是你需要写程序的地方，第 1 步由 parser 处理，第 3 步由 MapReduce 处理，因为 mapper 在输出资料给 reducer 前会做好排序。

昨天的 log 例子还有第 5, 6 步，从 MapReudce 的观点来看，这会是第 2 次的 MapReduce Job 了。

MapReduce 的分散式执行 (Distributed execution of MapReduce)

跟 Unix 命令主要的差异是 MapReduce 能够 并行 (paralleize) 的在多台机器上执行，却不用写并行相关程序，mapper 和 reducer 一次只处理一笔 record，它们并不在意输入从哪来，输出到哪去，所以这个框架能在很多台机器中处理复杂的资料。

下图 10-1 展示了 Hadoop MapReduce Job 的资料流，它的并行以 分区 (partition) 为基础，job 的输入源通常是 HDFS 资料夹，资料夹中的每一个 file block，可视为由多个 map 任务分别处理的分区，map task 标记为 m1, m2, m3。

每一个 map 任务的输入资料通常是几百 mb，MapReduce 的资源调度器 (scheduler) 会尝试在有输入资料存在的机器上执行 Map 任务，此原则也称为 putting the computation near the data ，省下了透过网路做数据复制的时间，增加本地性。

而 reudce 阶段也会做 分区 (partition)，为了确保所有 key-value 组合中相同 key 的资料最终能抵达同个 reducer，框架会使用 key 的 hash 值 (2020 Day 27) 来决定 key-value 该去哪个 reducer。

Key-value 组合必须要排序完，但资料集若太大就不适合在单台机器上用传统的排序演算法排序，取而代之的是，排序会分阶段进行，首先每一个 map 任务会以 key 的 hash 值做分区，然後每个分区会把资料写入至已排序档案中，存到 mapper 机器的本地硬碟上，类似 2020 Day 9 - SSLTables and LSM-Trees 的方式。

当 mapper 读完 & 写完已排序档案後，MapReduce 资源调度器就会通知 reducer 可以开始去每一台 mapper 复制下载资料，这个以 reducer 分区、排序、复制资料的过程也被称为 shuffle。

接下来 reducer 就开始合并资料，保留资料顺序，然後就开始迭代资料，执行你想计算的逻辑啦，最後就看你要不要把输出资料写到分散式档案系统中了。