mapreduce 论文 - 阅读笔记

雨点打透心脏的1/2处 2022-10-25 15:28 258阅读 0赞

**一.概要**

*  MapReduce是一种编程模型，它是一种用于处理和生成大型数据集的实现。用户通过指定一个用来处理键值对(Key/Value)的map函数来生成一个中间键值对集合。然后，再指定一个reduce函数， 它用来合并所有的具有相同中间key的中间value 。

**二.编程模型**

*  由用户所编写的Map函数接收输入，并生成一个中间键值对集合。MapReduce这个库会将所有共用一个键的值组合到一起，传递给Reduce函数
 *  Reduce函数接收一个中间键以及该键的值得集合作为输入。它会将这些值合并起来，生成一组更小的值得集合。

案例  
从大量文档统计计算出每一个单词出现的数量

map(String key, String value):
        // key: document name
        // value: document contents
        for each word w in value:
            EmitIntermediate(w,"1");
    reduce(String key, Iterator values):
        // key: a word
        // values: a list of counts
        int result = 0;
        for each v in values:
            result += ParseInt(v);
        Emit(AsString(result));

map函数会返回一个单词加上它出现的次数的键值对（在这个例子中，返回的出现次数就是1）。  
reduce函数会将该单词的出现次数统计在一起。

**三.具体实现**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70_pic_center]

*  用户程序中的MapReduce库会先将输入文件切分为M个片段，通常每个片段的大小在16MB到64MB之间。接着，它会在集群中启动许多个进程。
 *  有一个进程是比较特殊的，那就是master。剩下的进程都是worker，master会对这些worker进行任务分配。这里有M个Map任务以及R个Reduce任务要进行分配。master会给每个空闲的worker分配一个map任务或者一个reduce任务。
 *  被分配了map任务的worker会读取相关的输入数据片段。它会从输入数据中解析出键值对，并将它们传入用户定义的Map函数中。Map函数所生成的中间键值对会被缓存在内存中
 *  每隔一段时间，被缓存的键值对会被写入到本地硬盘，并通过分区函数分到R个区域内。这些被缓存的键值对在本地磁盘的位置会被传回master。master负责将这些位置转发给执行reduce操作的worker。
 *  当master将这些位置告诉了某个执行reduce的worker，该worker就会使用RPC的方式去从保存了这些缓存数据的map worker的本地磁盘中读取数据。当一个reduce worker读取完了所有的中间数据后，它就会根据中间键进行排序，这样使得具有相同键值的数据可以聚合在一起。之所以需要排序是因为通常许多不同的key会映射到同一个reduce任务中。如果中间数据的数量太过庞大而无法放在内存中，那就需要使用外部排序。
 *  reduce worker会对排序后的中间数据进行遍历。然后，对于遇到的每个唯一的中间键，reduce worker会将该key和对应的中间value的集合传入用户所提供的Reduce函数中。Reduce函数生成的输出会被追加到这个reduce分区的输出文件中。
 *  当所有的map任务和reduce任务完成后，master会唤醒用户程序。此时，用户程序会结束对MapReduce的调用。

完成之后，MapReduce的输出结果会存放在输出文件之中。

**3.1 Master的数据结构**

*  master 中保存了每一个Map和Reduce任务的状态(闲置,正在运行，以及完成), 以及非空闲任务的worker机器的ID
 *  它将map任务所生成的中间文件区域的位置传递给reduce任务。

**3.2容错**

**Worker故障**

*  master会周期性ping 每一个worker .如果在一定时间内没有收到worker的相应，那么master 会将该worker 进行标记为 failed . 所有由该worker完成的Map任务会重置为空闲状态，由其他的worker去进行完成。

**Master故障**

一个简单的解决好办法就是让master周期性的将上文所描述的数据结构写入磁盘，即checkpoint。如果这个master挂掉了，那么就可以从最新的checkpoint创建出一个新的备份，并启动master进程。然而，因为只有一个master，所以我们并不希望它发生故障。因此如果master故障了，我们目前的实现会中断MapReduce计算。客户端可以检查该master的状态，并且根据需要可以重新执行MapReduce操作。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/3e534527a3b34f13b52905835781310f.png