1. MapReduce理论

1.1. MapReduce的基本思想

• 如何对付大数据处理：分而治之
• 上升到抽象模型：Mapper与Reducer
• 上升到构架：统一构架，为程序员隐藏系统底层细节

1.2. 分而治之

不可分拆的计算任务或相互间有依赖关系的数据无法进行并行计算，例如求解斐波那契数列。

1.3. 构建抽象模型：Map和Reduce

典型流式大数据问题的特征：

• 大量数据记录/元素进行重复处理（Map）
• 对每个数据记录/元素作感兴趣的处理、获取感兴趣的中间结果信息（Map）
• 排序和整理中间结果以利后续处理
• 收集和整理中间结果（Reduce）
• 产生最终结果输出（Reduce）

map：将一种键值对转化为另一种键值对

reducer：将一组键值对经过整理后产生一种新的键值对

1.4. MapReduce构架

1.4.1. 主要需求和目标

• 实现自动并行化计算
• 为程序员隐藏系统层细节

1.4.2. MapReduce的功能

• 计算任务的划分和调度
• 数据的分布存储和划分
• 处理数据与计算任务的同步
• 结果数据的收集整理(sorting, combining, partitioning…)
• 系统通信、负载平衡、计算性能优化处理
• 处理系统节点出错检测和失效恢复

MapReduce最大的亮点是，将需要做什么和具体怎么做分开了，程序员只需编写少量处理问题本身的代码。

具体而言：

• 任务调度：将一个job划分为很多task，框架会为这些任务分配和调度map和reduce节点，并监控执行状态、负责map同步控制、进行计算性能优化处理等。
• 数据/代码互定位：本地化数据处理，即节点尽可能处理本地磁盘的数据，这是一种代码向数据的迁移。反之，也可以将数据迁移至离数据尽可能近的节点，这时数据向代码的迁移。
• 出错处理：检测并隔离出错节点，并分配新节点以执行计算任务。
• 分布式数据存储和文件管理：海量数据分布式存储；多备份容错处理
• Combiner和Partitioner：前者可用于减少数据通信开销，后者可以按特定策略将mapper的输出划分到同一reducer节点

1.5. MapReduce的主要设计思想和特点

• 向“外”横向扩展，而非向“上”纵向扩展：大量低端服务器组成高性能集群
• 失效被认为是常态：但不会因为节点失效而影响计算服务的质量
• 把处理向数据迁移：数据/代码互定位
• 顺序处理数据、避免随机访问数据：大规模数据访问，随机访问效率很低
• 为应用开发者隐藏系统层细节：省去并行化、容错、同步、收集、存储等细节
• 平滑无缝的可扩展性：计算性能随节点数目增长保持几乎线性增长

2. Google MapReduce

MapReduce是Google于2004年在计算机系统顶级会议OSDI上发表的成果，大数据课没让大家拜读一下原著属实觉得有些遗憾。

2.1. 基本流程

• 数据按64MB划分，准备由相应用户作业程序处理；系统中有负责调度的Master节点和数据处理工作节点Map和Reduce
• 用户提交作业给Master节点，后者寻找和配备可用的Mapper或Reducer节点
• 主节点启动Map节点读取数据，它们尽可能读取本地或本机架的数据，然后执行map和combine处理
• map结束后将结果键值对写入本地存储，并告知Master节点结果文件的存放位置
• 主节点启动Reduce节点，它们根据从Master节点获取的信息，远程读取map的中间结果，执行reduce
• Reduce节点将结果写入输出文件

为什么Master节点和用户节点不是一个节点？

• Master节点负责全局资源管理，而用户节点可能会有很多，不方便管理资源
• Master节点在集群内，和其它工作节点之间带宽大

为什么由Mapper在本地磁盘写入中间结果？为什么不能直接发射给对应Reducer？

• 首先显然不能写入本地内存，大数据会很“大”；
• 其次若直接发射给对应Reducer，当某个Reducer崩溃，它所拥有的所有相应Mapper的中间结果都用不了了，它们没有备份，只能让所有相应Mapper重新执行任务；反之若写入本地磁盘，Mapper崩溃的话只需重新执行该Mapper的任务即可。

2.2. 失效处理

主节点失效：设置作业执行情况的检查点，当节点失效时可以从最近的检查点开始执行（然而原论文提到，由于主节点失效的可能性很低，所以根本没实现这一功能，建议用户手动重启XD）

工作节点失效：由主节点向工作节点发送心跳检测（？）

2.3. 带宽和计算优化

带宽优化：用Combiner对Mapper的输出结果合并，减少对网络带宽的占用。

计算优化：在map或reduce阶段即将完成时，让多个节点执行未完成的任务，择最先完成者。这么做竟然可以让性能提高40%以上。

2.4. 数据分区

有时必须把属于一个Reduce节点的数据归并到一起，这就用到Partitioner。后面说明“可扩展带属性倒排索引”会提到。

数组排序是Partitioner的经典应用之一，需要将Mapper输出结果按一个分段函数进行划分。Reducer节点接收到数据后，进行自动排序（由MapReduce框架支持）。

3. Hadoop MapReduce

在Apache基金会和一众强者联手之下，三件套很快就有了开源版本，造福世界。

3.1. 开源版三件套

• Master节点——JobTracker
• Worker节点——TaskTracker
• MasterServer——NameNode
• ChunkServer——DataNode

3.2. 主要组件

3.2.1. InputFormat的功能

• 选择文件或者其它对象，用来作为输入
• 定义 InputSplits，将一个文件分为不同任务
• 为 RecordReader 提供一个工厂，用来读取这个文件

3.2.2. InputSplit

定义了输入到单个Map任务的输入数据。一个节点可能启动多个Map任务。

3.2.3. RecordReader

读取InputSplit定义的数据分块，并将其转化成键值对，以输入到Mapper。

3.3. 容错处理和计算性能优化

• 失败任务重新执行，由JobTracker决定重新执行哪一个任务
• 为提高速度，Hadoop可能会自动重复执行某任务（投机执行）

4. GFS

GFS是Google于2003年发表于SOSP上的成果，这可又是一个一个系统顶会啊。

GFS一个最显著的特征是：众人拾柴火焰高。它由众多的廉价磁盘组成，坏了就换，数据可靠性由分布式文件系统支持，好比用一万块钱的成本做十万块钱的事情。当然，MapReduce就是基于它开发的。

4.1. 设计原则

• 廉价本地磁盘分布存储
• 多数据自动备份：磁盘出错是常态，但所有备份都出错就很罕见
• 为上层MapReduce提供API支持

4.2. 架构

• Master：保存了三种元数据：命名空间（或者说分布式文件系统目录结构）、Chunk与文件名的映射表、Chunk各副本的位置信息。当然第3个元数据也会保存在对应的各个ChunkServer上。
• ChunkServer：保存实际的数据。每个Chunk有3个副本，保存到不同的ChunkServer。

4.3. 数据访问过程

• 应用程序询问Master要访问的文件名或数据块索引，Master返回ChunkServer的信息；
• 应用程序向ChunkServer发送数据请求。

这个事情有点像BitTorrent是吧？有一个中介介绍节点之间认识，但数据的传输是直接P2P的。

5. HDFS

5.1. 基本特征

• 对顺序读进行优化，而随机访问负载高
• 支持一次写入多次读取，支持追加，不支持对已写入数据更新
• 数据没有本地缓存
• 基于块存储文件（类似GFS）
• 多副本存储：风险均摊，副本距离尽可能远

5.2. 基本构架

和GFS几乎一毛一样，毕竟开源版实现

5.3. HDFS可靠性和出错恢复

• NameNode向DataNode发送心跳检测，无回应则寻找新节点替代，并重新分布失效数据
• 负载均衡
• 数据一致性检查
• 主节点失效：从FsImage、EditLog和检查点恢复
• 安全模式：刚启动时，NameNode等待每一个DataNode汇报情况

6. BigTable

2006年OSDI。它和前面的GFS、MapReduce并称“大数据处理三件套”。它为结构化数据提供了一定的操作能力。

6.1. 动机

• 需要存储多种数据
• 海量的服务请求
• 商用数据库并不适用

6.2. 目标

• 广泛的适用性：满足不同类型数据的存储和操作
• 很强的可扩展性：根据需要随时加入/撤销服务器节点
• 高吞吐量数据访问：PB级
• 高可用性和容错性：能够应对各种情况
• 自动管理：自动加入和撤销服务器，负载均衡
• 简单性：系统设计尽量简单

6.3. 数据模型

• 行关键字：可能在水平方向分为若干子表
• 列关键字：列族:列名，同一列族可能压缩存储
• 时间戳：最近的n个版本，或者限定时间内所有不同版本数据

6.4. 基本构架

主服务器：

• 新子表分配：创建新表、合并表或分列表都会产生新子表。它会为新子表寻找一个空间足够大的子表服务器。
• 子表监控：Chubby保存了子表服务器的基本信息，由此主服务器可获取子表服务器状态，并在其故障时执行更换，或负载过重时执行均衡。

子表服务器：

子表基本存储结构SSTable：一个SSTable是GFS的一个Chunk，由索引维护。每个SSTable都由多个Block构成。

子表寻址：3级B+树：Chubby服务器获取根子表、根子表找到二级索引子表、获取最终SSTable的位置

7. HBase

HDFS只提供了最底层的API，仍缺乏对于半结构化数据的操作能力。此时，BigTable的开源版——HBase应运而生。HBase也是数据库，但是——像Hadoop MapReduce那样，具有强大的扩展能力。

HBase的数据模型包括行、列和时间戳。若列为空则不存储。

看HBase的物理存储格式，三维立体浑元劲儿。上面的anchor就是列族，在下图中由平面中的一部分表示。

构架和BigTable都是一样的，一个主服务器和若干子表服务器。表（Table）分为若干子表（Region），它们存在子表服务器上。子表由存储块（Store）构成，每个Store由内存中的memStore和文件中的StoreFile构成。和BigTable几乎完全一样，换个名字而已。

查询数据时，先查memStore，查不到再查StoreFile。HBase中用三层B+存储各个子表的位置，它们分别是：zookeeper中的根子表、.META.表的第一个子表、.META.表。

HBase在Shell里的操作就不多说了，考试不可能考。

8. Hive

Hive由Facebook驱动开发，它提供了类似于SQL的执行引擎，模块组成和传统的数据库非常相似。执行过程很简单，这玩意是基于MapReduce和HDFS运作的，Driver处理各种Query，而对后者的解析和优化由Compiler完成。随后Driver控制Execution Engine模块，它会启动一个Hadoop任务来完成所有的计算。

Hive的Shell操作都是SQL那些，上网一搜就有了。这里写写如何用HDFS中的文件创建一个Hive表：

hive> create table shakespeare (freq int, word string) row format
 delimited fields terminated by ‘\t’ stored as textfile;
hive> load data inpath “shakespeare_freq” into table shakespeare;