Hadoop内部技术: 阅读MapReduce架构设计和实现原理的深入分析

良好的可扩展性: 随着公司业务的发展，累积数据量（例如搜索公司的网页量）将越来越大. 当数据量增加到一定程度时，现有群集可能无法满足其计算能力和存储容量，此时，管理员可能希望通过添加计算机来线性扩展群集容量.

高容错能力: 在分布式环境中，随着群集大小的增加，群集中的故障率（此处的“故障”包括硬件故障和不良数据，例如磁盘损坏，机器停机以及相互之间的通信故障）由用户程序错误引起的节点或软件错误）将显着增加，从而增加任务失败和数据丢失的可能性. 为此，Hadoop通过计算迁移或数据迁移等策略提高了群集的可用性和容错能力.

2.3 MapReduce编程模型概述2.3.1 MapReduce编程模型简介从MapReduce本身的命名特性可以看出，MapReduce包括两个阶段: Map和Reduce. 用户只需编写两个函数map（）和reduce（）即可完成一个简单的分布式程序的设计.

map（）函数将键/值对作为输入，并生成另一组键/值对作为中间输出，以写入本地磁盘. MapReduce框架将根据键值自动聚合这些中间数据，并将具有相同键值的数据（用户可以设置聚合策略，默认为对键值进行哈希计算）数据统一移交给reduce （）函数.

The

reduce（）函数将键和相应的值列表作为输入. 合并相同的键值后，将生成另一组键/值对作为最终输出，并将其写入HDFS.

下面以MapReduce-WordCount中的“ hello world”程序为例，介绍程序设计方法.

“ hello world”程序是我们编写的用于学习任何编程语言的第一个程序. 它简单易懂，可以帮助读者快速入门. 同样，分布式处理框架也有自己的“ hello world”程序: WordCount. 它完成的功能是计算输入文件中每个单词的出现次数. 在MapReduce中，可以这样写（伪代码）.

地图部分如下:

//键: 字符串偏移量

//值: 一行字符串内容

map（字符串键，字符串值）:

//将字符串拆分为单词words = SplitIntoTokens（value）;

对于单词中的每个单词w:

EmitIntermediate（w，“ 1”）;

减少部分如下:

// key: 一个单词//值: 该单词reduce的出现列表（字符串键，迭代器值）:

int result = 0;

对于每个v值:

result + = StringToInt（v）;

Emit（key，IntToString（result））;

用户编写MapReduce程序后，他根据某些规则指定该程序的输入和输出目录，并将其提交给Hadoop集群. 图2-2显示了Hadoop中的作业执行过程. Hadoop将输入数据分为几个输入分割（输入分割，以下称为分割），并将每个分割交给Map Task； Map Task会连续从相应的拆分中解析出键/值，然后调用map（）函数进行处理，在处理之后，将结果划分为几个分区（partitions），然后根据Reduce的数量将其写入本地磁盘任务;同时，每个Reduce任务从每个Map Task读取其自己的分区，然后使用基于排序的方法通过相同的键收集数据，调用reduce（）函数进行处理，然后将结果输出到文件中.

图2-2对WordCount程序进行仔细的操作可能会注意到上面的程序仍然缺少三个基本组件，其功能是: ①指定输入文件格式. 将输入数据分为几个拆分，然后将每个拆分中的数据解析为map（）函数所需的键/值对. ②确定将map（）函数生成的每个键/值对发送到哪个Reduce Task函数. ③指定输出文件格式，即每个键/值对以什么形式保存在输出文件中.

在Hadoop MapReduce中，这三个组件是InputFormat，Partitioner和OutputFormat，它们都需要用户根据自己的应用程序要求进行配置. 对于上面的WordCount示例，默认情况下Hadoop采用的默认实现可以满足要求，因此无需提供它.

总而言之，Hadoop MapReduce提供了5个可编程组件，即InputFormat，Mapper，Partitioner，Reducer和OutputFormat

. 本书将在第3章中详细介绍它们的设计思想和扩展实现.

2.3.2 MapReduce编程示例

MapReduce可以解决的问题具有一个共同的特征: 任务可以分解为多个子问题，这些子问题是相对独立的，彼此之间没有约束. 这些子问题并行处理后，任务将得到解决. . 在实际应用中，这种问题非常大. Google在论文中提到了MapReduce的一些典型应用，包括分布式grep，URL访问频率统计，Web连接图反转，反向索引构造，分布式排序等. 这两个都是相对简单的应用. 这是一些更复杂的应用程序.

（1）前K个问题

在搜索引擎领域，经常需要计算最近最流行的K个查询词. 这是一个典型的“前K个”问题，即从大量查询中计算出频率最高的前K个. 可以将这个问题分解为两个MapReduce作业，分别完成对词频进行计数和查找词频最高的前K个查询词的功能. 这两个作业之间存在依赖性，第二个作业取决于前一个作业的输出. 第一次分配是一个典型的WordCount问题. 对于第二项工作，map（）函数首先输出前K个最频繁的词，然后reduce（）函数汇总每个Map任务获得的前K个查询词，并输出频率最高的前K个查询词.

（2）K-means聚类K-means是基于距离的聚类算法. 它使用距离作为相似性的评估指标，并认为两个对象之间的距离越近，相似性就越大. 该算法解决的问题可以抽象为: 给定正整数K和N个对象，如何将这些数据点划分为K个簇？

针对这个问题使用MapReduce计算的想法如下: 首先，随机选择K个对象作为初始中心点，然后连续迭代计算直到满足终止条件（最大数量的上限）. 达到迭代次数或数据点与中心点之间的距离的平方和最小）. 在第一次迭代中，map（）函数计算从每个对象到中心点的距离，选择最接近每个对象（对象）的中心点（center_point），并输出对. reduce（）函数计算每个群集中对象的平均距离，并将这K个平均值用作下一轮的初始中心点.

（3）贝叶斯分类贝叶斯分类是一种使用概率统计知识进行分类的统计分类方法. 该方法包括两个步骤: 训练样本和分类. 它的实现是通过多个MapReduce作业完成的，如图2-3所示. 其中，训练样本可以通过三个MapReduce作业来实现: 第一个作业（ExtractJob）提取文档特征，该作业只需要由Map完成；第二个作业（ClassPriorJob）计算该类别的先验概率，即计算每个类别的文件中文档的数量，并计算类别概率；第三个作业（ConditionalProbilityJob）计算单词的条件概率，即计算所有文档中出现的次数，并计算单词的条件概率. 后两个任务的具体实现与WordCount相似. 分类过程由作业（PredictJob）完成. 此作业的map（）函数计算要分类的每个文档属于每个类别的概率，reduce（）函数查找每个文档具有最高概率的类别，并输出（ docid属于类别标签）.

图2-3在MapReduce上实现的朴素贝叶斯分类算法

上面介绍了MapReduce可以解决的一些问题. 为了使读者更深入地了解MapReduce，下面介绍一些MapReduce无法解决或难以解决的问题.

1）斐波那契数值计算. 在斐波那契数值计算中，下一个结果需要依赖于先前的计算结果，也就是说，该问题不能划分为几个不相关的子问题，因此无法使用MapReduce解决.

2）层次聚类方法. 分层聚类方法是使用最广泛的聚类算法之一. 分层聚类方法使用迭代控制策略来逐步优化聚类. 根据一定的相似性（通常是距离）判断标准，它将最相似的部分合并或划分最不相似的部分. 根据“自上而下”和“自下而上”的两种方法，可将其分为分解式层次聚类方法和合并式层次聚类方法两种. 以分解后的层次聚类算法为例，其主要思想是，一开始将每个对象归为一类，然后连续迭代直到所有对象合并为一个大类（或达到一定的终止条件）. 在轮次迭代中，需要计算两个对象之间的距离，并将距离最近的两个对象组合为一种类型. 该算法需要计算两个对象之间的距离，也就是说，每个对象都与其他对象相关，因此该问题无法分解为几个子问题，而MapReduce无法解决该问题.

2.4 Hadoop的基本体系结构

Hadoop由两部分组成，即分布式文件系统和分布式计算框架MapReduce. 其中，分布式文件系统主要用于数据的分布式存储，MapReduce建立在分布式文件系统上，对存储在分布式文件系统中的数据进行分布式计算. 本书主要涉及MapReduce，但考虑到其某些功能与底层存储机制有关，因此将首先介绍分布式文件系统.

在Hadoop中，MapReduce底部的分布式文件系统是一个独立的模块. 用户可以根据一组约定的接口实现自己的分布式文件系统，然后进行简单配置后，存储在文件系统中的数据将可以由MapReduce处理. Hadoop默认使用的分布式文件系统是HDFS（Hadoop分布式文件系统，Hadoop分布式文件系统），它与MapReduce框架紧密集成. 本节首先介绍分布式存储系统HDFS的基本体系结构，然后介绍MapReduce计算框架.

2.4.1HDFS架构

HDFS是高度容错的分布式文件系统，适合在廉价计算机上进行部署. HDFS可以提供​​高吞吐量的数据访问，非常适合于数据集上的应用程序.

HDFS的体系结构如图2-4所示. 通常，采用主/从架构，主要由以下几部分组成: 客户端，NameNode，Secondary，NameNode

和DataNode. 下面分别描述这些组件.

图2-4 HDFS架构图

（1）客户

客户端（代表用户）通过与NameNode和DataNode进行交互来访问HDFS中的文件. 客户端提供了一个类似于POSIX的文件系统界面，供用户调用.

（2）NameNode

整个Hadoop集群中只有一个NameNode. 它是整个系统的“主”hadoop运行mapreduce作业的工作原理，负责管理HDFS目录树和相关的文件元数据信息. 该信息基于两个文件: “ fsimage”（HDFS元数据镜像文件）和“ editlog”（HDFS文件更改日志）

The

窗体存储在本地磁盘上，并在HDFS重新启动时进行重构. 此外，NameNode还负责监视每个DataNode的运行状况. 一旦发现DataNode关闭，该DataNode将从HDFS中移出，并再次备份其上的数据. （3）次要NameNode

次要NameNode的最重要任务不是对NameNode元数据执行热备份，而是定期合并fsimage并编辑日志并将其传输到NameNode. 这里应该注意，为了减轻对NameNode的压力，NameNode不会合并fsimage并进行编辑，而是将文件存储在磁盘上，而是将其移交给辅助NameNode.

（4）DataNode

通常，在每个从节点上安装一个DataNode，它负责实际的数据存储并定期将数据信息报告给NameNode. DataNode以固定大小的块为基本单位来组织文件内容. 默认情况下，块大小为64MB. 当用户将大文件上传到HDFS时，该文件将被分为几个块并存储在不同的DataNode中. 同时，为了确保数据的可靠性，同一块将以流水线方式（默认为3，可以配置此参数）写入不同DataNode上的多个块. 剪切后存储文件的过程对用户是透明的.

2.4.2Hadoop MapReduce架构

与HDFS一样，Hadoop MapReduce也使用主/从（M / S）架构，如图2-5所示. 它主要由以下组件组成: 客户端，JobTracker，TaskTracker和任务. 下面分别描述这些组件.

图2-5 Hadoop MapReduce架构图

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-281369-1.html