Lecture #09 & #10

Hadoop分布式文件系统

从大数据分析软件栈讲，是采用分布式文件系统，比如GFS和NFS。

为什么要用Hadoop

§速度：
•Twitter每天处理400,000,000条推文
§多样性
•结构化数据库，应用程序日志文件，网页，XML，音频和视频
•在了解数据结构之前构建应用程序
§数据量
•从2005年到2020年，世界数据预计将增长200倍

Hadoop 历史

§分布式存储模型（谷歌文件系统）
•专为在大量廉价机器上运行而设计
•硬件故障容错
§分布式计算模型（MapReduce）
•将计算资源放到数据上，GFS。
•极大地简化了并行编程编程

Hadoop file system实际上就是GFS的开源实现。
GOOGle最早做的MapReduce是闭源的，但是Apache的Hadoop MapReduce是开源的
Google做的上层软件是BigTable，Apche Hbase是其开源形式

HDFS的NameNode和DataNode

HDFS 的设计和开发实际上就是GFS的开源实现。
但是叫法不一样，HDFS的NameNode就是GFS的MetaData，而实际的Data叫DataNode，HDFS也支持POSIX的接口，它同样会截获指令，让系统知道是在使用HDFS。通过HDFS去访问文件。
HDFS对硬件上没有任何冗余，完全是软件上的冗余配置。

Hadoop 集群架构

这是开源的软件，很多的创业公司的互联网服务，就买20个节点机器，然后配一套集群的管理软件，然后再装HDFS，然后再装MapRdue，目前初创公司的大数据的应用就是通过市场上能够买到的硬件配上开源软件来作为支撑

HDFS的rack机柜

HDFS如何写

冗余度分成3个副本，此时NameNode元数据记录，Rack1节点存储副本1，Rack2节点存储7和9. 如果7down了，那么根据IP地址算出一个比较近的副本的所在位置，可用。

HDFS写过程

在所有写入操作完成后要写NameNode。然后返回success后，客户端只需要访问一次NameNode，后面访问这几个数据不再需要访问NameNode，这里面也有Data flow和Control Flow分开的线路。Data Flow考虑的是物理的拓扑结构，怎么最快的把数据传输，Control Flow告诉数据的顺序是怎么样的。

HDFS如何读

一个文件有两个block组成，A和B，A的冗余备份是1，5，6位置，B的冗余备份有1，2，10位置，那么会根据距离的考虑，选取DataFlow选取最快的数据副本。

MapReduce

什么是MapReduce

§MapReduce是一种用于在集群上使用并行分布式算法处理大型数据集的编程模型，非常简化适用于特定任务。
§主要内容：

• 写Map地图
• 随机（开发人员不用管 Framework自动处理）
• 写Reduce减少

Hadoop Framework负责细节：

• 验证任务完成
• 复制数据
• 文件I / O.
• 联网
• 同步
• 故障恢复

MapReduce编程模型

§采用一组输入键/值对，并生成一组输出键/值对
（谷歌很多数据分析都可以用key/value去表达，比如网页被引用很多次，那么代表这个网页热度很高，用url作为ley，然后引用次数为valve。再就是关键字，用关键字作为key，然后用被搜索的频率作为valve）
§计算过程主要写两个函数
§Map（由用户编写）：获取输入对并生成一组中间键/值对

• MapReduce库将与同一中间密钥I关联的所有中间值组合在一起，并将它们传递给Reduce函数。
  §Reduce（由用户编写）：接受中间密钥I和该密钥的一组值并将这些值合并在一起，根据相同的key来把很多个Valve给合并起来，减少数据

Mapreduce Framework

§安排和重新在相应的节点上运行任务
§拆分输入
§把Map的输出送到Reduce的输入里
§接收结果

节点内部的是Combine，跨节点的是Reduce。

MapReduce执行的功能

§容错功能
§局部性
§任务粒度
§备份任务

MapReduce执行

§当用户程序调用MapReduce函数时：

1. MapReduce库首先将输入文件拆分为M个部分，然后启动计算机集群上的许多程序副本
2. 其中一份是master，其余的是worker。 M映射Map任务和R Reduce要分配的任务。 Map肯定要比Reduce要多。Master选择闲置的worker并为worker分配一个map任务或reduce任务。
3. 一个worker负责一个拆分快，读取相应的输入拆分，解析键/值对并将每对传递给定义好的Map函数。 中间键/值对被缓冲在存储器中。
4. 周期性地，缓冲中的key/valve对被写入本地磁盘，通过分区功能划分为R区域Reduce。 这些缓冲对的位置被传递回Master以转发给分配到Reduce任务的worker。
5. 当主服务器通知reduce任务的worker时，它从map worker的本地磁盘读取缓冲数据，按key排序，以便所有出现的相同密钥组合在一起
6. reduce任务的korker将密钥和相应的中间值集传递给用户的reduce函数。 reduce函数的输出附加到此reduce分区的最终输出文件
7. 当所有map任务和reduce任务完成后，master会唤醒用户程序，MapReduce调用将返回用户代码

MapReduce Fault Tolerance容错机制

§MapReduce库可以很好地容错

• mater定期ping每个worker（hearbeat）
• 如果未收到响应，则主服务器将工作程序标记为失败
• 工作人员完成的任何地图任务都将重置回其初始空闲状态，因此可以随时顶替那个down了的worker。
• 同样，任何map任务或reduce任务正在进行中失败
• 完成的映射任务在发生故障时重新执行，因为它们的输出存储在故障机器的本地磁盘上且无法访问。 完成的reduce任务不需要重新执行，因为它们的输出存储在全局文件系统中。

局部性

§MapReduce在分配任务时考虑局部性
§输入数据（由HDFS管理）存储在本地磁盘上; HDFS将每个文件分成块（例如64 / 128MB）并在不同的机器上存储每个块的几个副本（通常为3个副本）
§MapReduce主服务器将输入文件的位置信息考虑在内，并尝试在含有数据块的节点上，来进行Map任务
§如果失败，主服务器会尝试在该任务的输入数据的副本最近的位置安排相同的Map任务（例如，在与包含数据的计算机位于同一网络交换机上的工作计算机上）
§当在群集中的大部分工作者上运行大型MapReduce操作时，大多数输入数据在本地读取并且不消耗网络带宽

MapReduce任务粒度

§Map阶段细分为M个部分
§Reduce阶段为R件
§理想情况下，M和R应远大于worker数量
§让每个worker执行许多不同的任务可以改进：动态负载平衡；当工作人员出现故障时加速恢复：已完成的许多Map任务可以分散到所有其他worker节点上进行Reduce。
§由于Master必须做出O（M + R）调度决策并在内存中保持O（M * R）状态，因此M和R的大小有实际界限。

MapReduce备份任务

§Stragglers：机器花费了不同的时间来完成计算中最后几个map或reduce任务中的一个，例如 具有坏磁盘的计算机可能会遇到频繁的可纠正错误，从而将其读取性能从30MB / s降低到1MB / s。

§缓解落后者问题的一般机制
§Master计划剩余正在进行的任务的备份多个执行，可以算两遍或者三遍。 无论主要执行还是备份执行完成，哪一个先完成，任务都会标记为已完成。