【大数据处理与分析】MapReduce：04 实例分析：WordCount

【作者主页】Francek Chen【专栏介绍】⌈ ⌈⌈大数据技术原理与应用⌋ ⌋⌋专栏系统介绍大数据的相关知识分为大数据基础篇、大数据存储与管理篇、大数据处理与分析篇、大数据应用篇。内容包含大数据概述、大数据处理架构Hadoop、分布式文件系统HDFS、分布式数据库HBase、NoSQL数据库、云数据库、MapReduce、Hadoop再探讨、数据仓库Hive、Spark、流计算、Flink、图计算、数据可视化以及大数据在互联网领域、生物医学领域的应用和大数据的其他应用。【GitCode】专栏资源保存在我的GitCode仓库https://gitcode.com/Morse_Chen/BigData_principle_application。文章目录一、WordCount 的程序任务二、WordCount 的设计思路三、WordCount 的具体执行过程四、一个 WordCount 执行过程的实例小结本文给出一个 WordCount 实例来阐述采用 MapReduce 解决实际问题的基本思路和具体实现过程。一、WordCount 的程序任务在编程语言的学习过程中一般都会以“HelloWorld”程序作为入门范例WordCount 就是类似“HelloWorld”的 MapReduce 入门程序见表1。表2给出了一个 WordCount 的输入和输出实例。表1 WordCount程序任务项目描述程序WordCount输入一个包含大量单词的文本文件输出文件中每个单词及其出现次数频数并按照单词字母顺序排列每个单词和其频数占一行单词和频数之间有间隔表2 一个WordCount的输入和输出实例输入输出Hello WorldHello HadoopHello MapReduceHadoop 1Hello 3MapReduce 1World 1二、WordCount 的设计思路首先需要检查 WordCount 程序任务是否可以采用 MapReduce 来实现。在前文我们曾经提到适合用 MapReduce 来处理的数据集需要满足一个前提条件待处理的数据集可以分解成许多小的数据集而且每一个小数据集都可以完全并行地进行处理。在 WordCount 程序任务中不同单词之间的频数不存在相关性彼此独立可以把不同的单词分发给不同的机器进行并行处理因此可以采用 MapReduce 来实现词频统计任务。其次确定 MapReduce 程序的设计思路。思路很简单即把文件内容解析成许多个单词然后把所有相同的单词聚集到一起最后计算出每个单词出现的次数并输出。最后确定 MapReduce 程序的执行过程。把一个大文件切分成许多个分片每个分片输入给不同机器上的 Map 任务并行执行完成“从文件中解析出所有单词”的任务。Map 的输入采用 Hadoop 默认的 key, value 输入方式即文件的行号作为 key该行号对应的文件的一行内容作为 valueMap 的输出以单词作为 key1 作为 value即 单词,1 表示单词出现了 1 次。Map 阶段完成后会输出一系列单词,1这种形式的中间结果然后 Shuffle 阶段会对这些中间结果进行排序、分区得到 key, value-list 的形式比如hadoop, 1,1,1,1,1再分发给不同的 Reduce 任务。Reduce 任务接收到所有分配给自己的中间结果一系列键值对以后就开始执行汇总计算工作计算得到每个单词的频数并把结果输出到分布式文件系统。在后面的 MapReduce 编程实践内容中会介绍如何编写 WordCount 的具体实现代码。三、WordCount 的具体执行过程对于 WordCount 程序任务整个 MapReduce 过程实际的执行顺序如下。1执行 WordCount 的用户程序采用 MapReduce 编写会被系统分发部署到集群中的多台机器上其中一个机器作为 Master负责协调调度作业的执行其余机器作为 Worker可以执行 Map 或 Reduce 任务。2系统分配一部分 Worker 执行 Map 任务一部分 Worker 执行 Reduce 任务MapReduce 将输入文件切分成 M 个分片Master 将 M 个分片分给处于空闲状态的 N 个 Worker 处理。3执行 Map 任务的 Worker 读取输入数据执行 Map 操作生成一系列key,value形式的中间结果并将中间结果保存在内存的缓冲区中。4缓冲区中的中间结果会被定期刷写到本地磁盘上并被划分为 R 个分区这 R 个分区会被分发给 R 个执行 Reduce 任务的 Worker 进行处理Master 会记录这 R 个分区在磁盘上的存储位置并通知 R 个执行 Reduce 任务的 Worker 来“领取”属于自己处理的那些分区的数据。5执行 Reduce 任务的 Worker 收到 Master 的通知后就到相应的 Map 机器上“领取”属于自己处理的分区。需要注意的是正如之前在 Shuffle 过程阐述的那样可能会有多个 Map 机器通知某个 Reduce 机器来“领取”数据因此一个执行 Reduce 任务的 Worker可能会从多个Map 机器上“领取”数据。当位于所有 Map 机器上的、属于自己处理的数据都已经“领取”回来以后这个执行 Reduce 任务的 Worker 会对“领取”的键值对进行排序如果内存中放不下则需要用到外部排序使得具有相同 key 的键值对聚集在一起就可以开始执行具体的 Reduce 操作了。6执行 Reduce 任务的 Worker 遍历中间数据对每一个唯一 key 执行 Reduce 函数结果写入输出文件中执行完毕后唤醒用户程序返回结果。WordCount 的执行过程具体如图1所示。图1 WordCount的执行过程四、一个 WordCount 执行过程的实例假设执行单词统计任务的 MapReduce 作业中有 3 个执行 Map 任务的 Worker 和 1 个执行 Reduce 任务的 Worker。一个文档包含 3 行内容每行分配给一个 Map 任务来处理。Map 操作的输入是 key, value 形式其中key 是文档中某行的行号value 是该行的内容。Map 操作会将输入文档中的每一个单词以 key, value 的形式作为中间结果进行输出如图2所示。图2 Map过程示意然后在 Map 端的 Shuffle 过程中如果用户没有定义 Combiner 函数则 Shuffle 过程会把具有相同 key 的键值对归并成一个键值对如图3所示。具体而言若干个具有相同 key 的键值对k 1 k_1k1​,v 1 v_1v1​,k 1 k_1k1​,v 2 v_2v2​,…,k 1 k_1k1​,v n v_nvn​会被归并成一个新的键值对k 1 k_1k1​,v 1 v_1v1​,v 2 v_2v2​,…,v n v_nvn​。比如在图2最上面的 Map 任务输出结果中存在 key 都是World的两个键值对“World”,1经过 Map 端的 Shuffle 过程以后这两个键值对会被归并得到一个键值对“World”,1,1这里不再给出 Reduce 端的 Shuffle 结果。然后这些归并后的键值对会作为 Reduce 任务的输入由 Reduce 任务为每个单词计算出总的出现次数。最后输出排序后的最终结果就会是“Bye”,3、“Hadoop”,4、“Hello”,3、“World”,2。图3 用户没有定义Combiner时的Reduce过程示意在实际应用中每个输入文件被 Map 函数解析后都可能会生成大量类似“the”,1这样的中间结果很显然这会大大增加网络传输开销。在前面介绍 Shuffle 过程时我们曾经提到过对于这种情形MapReduce支持用户提供 Combiner函数来对中间结果进行合并后再发送给 Reduce 任务从而大大减少网络传输的数据量。对于图2中的 Map 输出结果如果存在用户自定义的 Combiner 函数则 Reduce 过程示意如图4所示。图4 用户定义Combiner函数则Reduce过程示意小结WordCount 是 MapReduce 的入门程序任务是对文本中的单词进行频数统计并按字母顺序输出。其设计思路是利用 MapReduce 的并行处理能力将大文件切分为多个分片由不同 Map 任务解析出每个单词并输出 单词,1经过 Shuffle 阶段的排序、分区和合并可选用Combiner减少传输量形成 单词, [1,1,…]再由 Reduce 任务汇总计算每个单词的总次数最终输出结果。该实例清晰展示了 MapReduce 从数据切分、Map 映射、Shuffle 归约到 Reduce 聚合的完整执行流程是理解分布式计算框架的典型范例。欢迎点赞 | 收藏⭐ | 评论✍ | 关注