MapReduce Review

本文是carolz童鞋整理的MapReduce课复习资料，由2015年复习提纲Slide整理而来。

###Ch1 并行计算技术简介###

####1 为什么需要并行计算####

#####提高计算机性能的基本手段#####
提高字长 流水线微体系结构技术 提高集成度 提升主频

#####迫切需要发展并行计算技术的主要原因#####
单处理器性能提升达到极限
应用规模和数量急剧增大，超大的计算量/计算复杂度

####2 并行计算技术的分类####

#####有哪些主要的并行计算分类方法？#####
按数据和指令处理结构：弗林分类

• 单指令单数据流
• 单指令多数据流
• 多指令单数据流
• 多指令多数据流

按并行类型

• 位级并行
• 指令级并行
• 线程级并行（数据级并行、任务级并行）

按存储访问类型

• 共享内存（UMA）
• 分布式共享存储体系结构：本地存储器+全局存储器
• 分布式内存：各处理器使用本地独立的存储器

后两者统称NUMA

按存储访问构架

按系统类型

• 多核/众核并行计算系统
• 对称多处理系统
• 大规模并行处理
• 集群
• 网格

按计算特征

• 数据密集型并行计算：大规模Web信息搜索
• 计算密集型并行计算：气象预报
• 数据密集与计算密集混合型并行计算：3D电影渲染

按并行程序设计模型/方法

• 共享内存变量
• 消息传递方式
• MapReduce方式

####3 并行计算的主要技术问题####

#####并行计算有哪些方面的主要技术问题？####

• 多核/多处理器网络互连结构技术
• 存储访问体系结构
• 分布式数据与文件管理
• 并行计算任务分解与算法设计
• 并行程序设计模型和方法
• 数据同步访问和通信控制
• 可靠性设计与容错技术：节点的失效与恢复
• 并行计算软件框架平台
• 系统性能评价和程序并行度评估

#####如何评估程序的可并行度？（掌握Amdahl定律的重要作用）#####

S=1/((1-P)+P/N)
S：加速比
P：程序可并行比例
N：处理器数目

一个并行程序可加速程度是有限制的，并非可无限加速，并非处理器越多越好。

####4 MPI并行程序设计####

• MPI功能与特点
  功能：基于消息传递的高性能并行计算编程接口。提供点对点通信（同步/异步）、节点集合通信（一对多，多节点计算控制，对结果的规约(reduce)计算功能）、用户自定义的复合数据类型传输。
  特点：提供可靠的、面向消息的通信；在高性能科学计算领域广泛使用，适合于处理计算密集型的科学计算；独立于语言的编程规范，可移至性好。

• MPI程序结构

  • MPI程序头文件

    ```

    - 初始化MPI环境  ```MPI_Init(&argc, &argv);

  • 并行计算与通信

  • 关闭MPI环境

    - MPI基本编程接口
    	- 初始化MPI ```MPI_Init(&argc, &argv);

  • 终止MPI并行计算

    - 确定指定范围内处理器/进程数目  ```MPI_Comm_Size(comm, size)

  • 确定一个处理器/进行的标识号

    rank)```

    - 发送一个消息  ```MPI_Send(buf, count, datatype, dest, tag, comm)

  • 接收消息

    count, datatype, source, tag, comm, status)```

    - MPI编程实例  
    
    ####5 为什么需要大规模数据并行处理####
    
    - 处理数据的能力大幅落后于数据增长
    - 海量数据隐含着更准确的事实
    
    #####什么是MapReduce？#####
    
    - 基于集群的高性能计算平台
    - 并行程序开发与运行框架
    - 并行程序设计模型与方法
    
    #####为什么MapReduce如此重要？#####
    
    - 高效的大规模数据处理方法
    - 改变了大规模尺度上组织计算的方式
    - 第一个不同于冯·诺依曼结构的、基于集群而非单机的计算方式的重大突破
    - 目前为止最成功的基于大规模计算资源的并行计算抽象方法
    
    ###Ch2 MapReduce简介###
    
    ####1 对付大数据处理-分而治之####
    
    - 大数据分而治之的并行化计算
    - 大数据任务划分和并行计算模型
    
    ####2 构建抽象模型-map和reduce
    
    - 主要设计思想：为大数据处理过程中的两个主要处理操作提供一种抽象机制
    - 典型的流式大数据问题的特征
    - map和reduce操作的抽象描述：提供一种抽象机制，把做什么和怎么做分开，程序员仅需要描述做什么，不需要关心怎么做
    - 基于map和reduce的并行计算模型和计算过程
    
    ####3 上升到构架-自动并行化并隐藏底层细节
    
    - 主要需求、目标和设计思想
    	- 实现自动并行化计算
    	- 为程序员隐藏系统层细节
    - mapreduce提供统一的构架并完成以下主要功能
    	- 任务调度
    	- 数据/代码互定位
    	- 出错处理
    	- 分布式数据存储与文件管理
    	- combiner和Partitioner(设计目的和作用)
    
    ####4 MapReduce的主要设计思想和特征
    
    - 向“外”横向扩展，而非向“上”纵向扩展
    - 失效被认为是常态
    - 把计算处理向数据迁移
    - 顺序处理数据、避免随机访问数据
    - 为应用开发者隐藏技术层细节
    - 平滑无缝的可扩展性
    
    ###Ch3 Google/Hadoop MapReduce基本架构（这章字好多啊同志们，要出问答题的节奏啊）
    
    ####1 MapReduce的基本模型和处理思想
    
    三个层面上的基本构思  
    
    - **如何对付大数据处理：分而治之**
    	- 对相互间不具有计算依赖关系的大数据，实现并行最自然的办法就是采取分而治之的策略
    - **上升到抽象模型：Mapper和Reducer**
    	- MPI等并行计算方法缺少高层并行编程模型，为了克服这一缺陷，MapReduce借鉴了Lisp函数式语言中的思想，用Map和Reduce两个函数提供了高层的并行编程抽象模型
    - **上升到构架：统一构架，为程序员隐藏技术细节**
    	- MPI等并行计算方法缺少统一的计算框架支持，程序员需要考虑数据存储、划分、分发、结果收集、错误恢复等诸多细节；为此，MapReduce设计并提供了统一的计算框架，为程序员隐藏了绝大多数系统层面的处理细节
    
    ####2 Google MapReduce的基本工作原理
    - **Google MapReduce并行处理的基本过程**
    	1. 有一个待处理的大数据，被划分为大小相同的数据块(如64MB)，及与此相应的用户作业程序
    	2. 系统中有一个负责调度的主节点(Master)，以及数据Map和Reduce工作节点(Worker)
    	3. 用户作业程序提交给主节点
    	4. 主节点为作业程序寻找和配备可用的Map节点，并将程序和数据传送给Map节点
    	5. 主节点也为作业程序寻找和配备可用的Reduce节点，并将程序传送给Reduce节点
    	6. 主节点启动每个Map节点执行程序，每个Map节点尽可能读取本地或本机架的数据进行计算
    	7. 每个Map节点处理读取的数据块，并做一些数据整理工作(combining, sorting等)并将中间结果存放在本地；同时通知主节点计算任务完成并告知中间结果数据存储位置
    	8. 主节点等所有Map节点计算完成后，开始启动Reduce节点运行；Reduce节点从主节点所掌握的中间结果数据位置信息，远程读取这些数据
    	9. Reduce节点计算结果汇总输出到一个结果文件，即获得整个处理结果
    - **带宽优化(Combiner的设计目的和作用)**
    	- 目的：解决大量的键值对数据在传送给Reduce节点时会引起较大的通信带宽开销问题
    	- 解决方案：每个Map节点处理完成的中间键值对将由combiner做一个合并压缩，即把那些键名相同的键值对归并为一个键名下的一组数值
    - **用数据分区解决数据相关性问题(Partitioner的设计目的和作用)**
    	- 问题：一个Reduce节点上的计算数据可能来自多个Map节点。因此，为了在进入Reduce节点计算之前，需要把属于一个Reduce节点的数据归并到一起
    	- 解决方案：在Map阶段进行了Combining以后，可以根据一定的策略对Map输出的中间结果进行分区(partitioning)，这样即可解决以上数据相关性问题，避免Reduce计算过程中的数据通信
    - **失效处理**
    	- **主节点失效**：主节点中会周期性地设置检查点(checkpoint)，检查整个计算作业的执行情况，一旦某个任务失效，可以从最近有效的检查点开始重新执行，避免从头开始计算的时间浪费
    	- **工作节点失效**：工作节点失效是很普遍发生的，主节点会周期性地给工作节点发送心跳检测，如果工作节点没有回应，则认为该工作节点失效，主节点讲终止该工作节点的任务并把失效的任务重新调度到其它工作节点上重新执行
    - **计算优化**
    	- 问题：Reduce节点必须要等到所有Map节点计算结束才能开始执行。因此，如果有一个计算量大、或者由于某个问题导致很慢结束的Map节点，则会成为严重的“拖后腿者”
    	- 解决方案：把一个Map计算任务让多个Map节点同时做，取最快完成者的计算结果
    
    ####3 Hadoop MapReduce的基本工作原理
    
    - **Hadoop MapReduce基本架构与工作过程**
    	- **JobTracker的作用**：对等于Google MapReduce中的Master。主要负责资源监控和数据调度。JobTracker监控所有的TaskTracker与作业的健康状态，同时JobTracker会跟踪任务的执行进度、资源使用量等信息
    	- **TaskTracker的作用**：对等于Google MapReduce中的Worker。会周期性地通过心跳将本节点上资源的使用情况和任务运行进度汇报给JobTracker，同时接收JobTracker发送过来的命令并执行相应的操作
    	- **MapReduce作业执行过程**
    		- 对于mapTask
    			- 首先通过用户提供的InputFormat将对应的InputSplit解析成一系列key/value，并依次交给用户编写的map()函数处理
    			- 接着将数据交给由用户定义的combiner进行一次本地规约
    			- 按照指定的partitioner对数据分片，以确定每个key/value将交给哪个reducer处理
    			- 将处理结果保存在本地磁盘上
    		- 对于reduceTask
    			- 由于其数据来自各个map task，首先需要通过HTTP请求从各个已经完成的Map task上拷贝对应的数据分片。
    			- 待所有数据拷贝完成后，再以key作为关键字对所有数据进行排序
    			- 将每组数据交由用户编写的reduce()函数处理，并将数据直接写到HDFS上作为最终输出结果
    - **Hadoop MapReduce主要组件**
    	- **文件输入格式InputFormat**：定义了数据文件如何分割和读取
    	- **输入数据分块InputSplits**：定义了输入到单个Map任务的输入数据
    	- **数据记录读入RecordReader**：定义了如何读取数据记录
    	- **Mapper**：每个Mapper实例生成一个java进程，负责处理一个InputSplit上的数据
    	- **Combiner**：合并相同key的键值对，减少传输给reduce节点时候的通信开销
    	- **Partitioner**：使用partitioner类来决定键值对传给哪一个reduce节点
    	- **Reducer**：做用户定义的reduce操作
    	- **文件输出格式OutputFormat**：写入到HDFS中，默认的RecordWriter是LineRecordWriter，以key\tvalue的格式输出
    - 容错处理与计算性能优化
    	- Hadoop系统会将失败的任务再次执行，TaskTracker将状态信息汇报给JobTracker，最终由JobTracker决定冲洗执行哪个任务
    	- 为了加快执行速度，Hadoop也会同时多次执行一个任务，以最先执行成功的为准
    
    ####4 分布式文件系统GFS的基本工作原理
    
    - **Google GFS的基本设计原则**
    	- 廉价本地磁盘分布存储
    	- 多数据自动备份解决可靠性
    	- 为上层MapReduce计算框架提供支撑
    - **Google GFS的基本架构和工作原理**
    	- **GFS Master的主要作用**：  
    	保存了GFS文件系统的三种元数据。前两种元数据可通过操作日志提供容错处理能力；第3个元数据直接保存在ChunkSercer上，Master启动Chunk Server注册时自动完成在Chunk Server上元数据的生成
    		- 命名空间
    		- Chunk与文件名的映射表
    		- Chunk副本的位置信息，每一个Chunk默认有3个副本  
    	- **GFS ChunkSever的主要作用**  
    	用来保存大量实际数据的数据服务器
    		- GFS中每个数据块划分缺省为64MB
    		- 每个数据块会分别在3个(缺省情况下)不同的地方复制副本
    		- 对每一个数据块，仅当3个副本都更新成功时，才认为数据保存成功
    		- 当某个副本失效时，Master会自动将正确的副本数据进行复制以保证足够的副本数
    		- GFS上存储的数据块副本，在物理上以一个本地的Linux操作他系统的文件形式存储，每一个数据块再划分为64KB的子块，每个子块有一个32位的校验和，读数据时会检查校验和以保证使用未失效的数据
    	- **数据访问工作过程**（第3条和第4条是什么鬼，难道不一样？可以看图意会╮(╯▽╰)╭）
    		1. 在程序运行前，数据已经存储在GFS文件系统中；程序实行时应用程序会告诉Master所要访问的文件名或者数据块索引是什么
    		2. Master根据文件名和数据块索引在其文件目录空间中查找和定位该文件或数据块，并找出数据块具体在哪些ChunkServer上；将这些位置信息送回给应用程序
    		3. 应用程序根据GFS Master返回的具体Chunk数据块位置信息，直接访问相应的ChunkServer
    		4. 应用程序根据Master返回的具体Chunk数据块位置信息直接读取指定位置的数据进行计算处理
    	- **GFS的系统管理技术**
    		- 大规模集群安装技术
    		- 故障检测技术
    		- 节点动态加入技术
    		- 节能技术
    
    ####5 分布式结构化数据表BigTable
    
    - BigTable的基本作用和设计思想（什么鬼，肯定不考）
    	- GFS是一个文件系统，难以提供对结构化数据的存储和访问管理。为此，Google在GFS之上又设计了一个结构化数据存储和访问管理。
    	- Google的很多数据结构，包括Web索引、卫星图像数据、地图数据等都以结构化的形式存在BigTable中
    	- BigTable提供了一定粒度的结构化数据操作能力，主要解决一些大型媒体数据的结构化存储问题。但与传统的关系型数据库相比，其结构化粒度没有那么高，也没有事务处理能力，因此它不是真正意义上的数据库。
    - BigTable的设计动机和目标
    	- 需要存储管理海量的结构化半结构化数据
    	- 海量的服务请求
    	- 商用数据库无法适用
    - BigTable数据模型-多维表
    	- 一个行关键字(row key)
    	- 一个列关键字(column key)
    	- 一个时间戳(time stamp)
    - BigTable基本构架
    	- 子表服务器：
    		- BigTable中的数据都以自表形式保存在子表服务器上，客户端程序也直接和子表服务器通信。当一个新子表产生时子表服务器的主要问题包括子表的定位、分配及子表数据的最终存储。
    	- 子表存储结构SSTable(对应于GFS数据块)：
    		- SSTable是BigTable内部的**基本存储结构**，以GFS文件形式存储在GFS文件系统中。一个SSTable实际上对应于GFS中的一个64MB的数据块(Chunk)
    		- SSTable中的数据进一步划分为64KB的子块，因此一个SSTable可以有多达1K个这样的子块。为了维护这些子块的位置信息，需要使用一个Index索引(一个SSTable一个Index)。
    	- 子表数据格式
    		- 概念上子表是整个大表的多行数据划分后构成。而一个子表服务器上的子表将进一步由很多个SSTable构成，每个SSTable构成最终的在底层GFS中的存储单位。
    		- 一个SSTable还可以为不同的子表所共享，以避免同样数据的重复存储。
    	- 子表寻址
    		- 子表地址以3级B+树形式进行索引：首先从Chubby服务器中取得根子表，最后获取最终的SSTable位置
    		- Chubby file -> Root Tablet -> Other METADATA Tablets -> UserTable
    
    ####6 Hadoop分布式文件系统HDFS
    
    - HDFS的基本特征
    	- 模仿GFS设计实现
    	- 存储极大数目的信息，将数据保存到大量节点当中，支持很大的单个文件
    	- 提供数据的高可靠性和容错能力，单个或多个节点不工作，对系统不会造成任何影响，数据仍然可用。通过一定数量的数据复制保证数据存储的可靠性和出错恢复能力
    	- 提供对数据的快速访问；并提供良好的可扩展性，通过简单加入更多服务器快速扩充系统容量，服务更多的客户端
    	- 与GFS类似，HDFS是MapReduce的底层数据存储支撑，并使得数据尽可能根据其本地局部性进行访问和计算
    	- HDFS对顺序读进行了优化，支持大量数据的快速顺序读出，代价是对于随机访问的负载较高
    	- 数据支持一次写入，多次读取；*不支持已写入的数据的更新操作*，但允许在文件尾部添加新的数据
    	- 数据不进行本地缓存（文件很大，且顺序读没有局部性）
    	- 基于块的文件存储，默认的块大小为64MB
    		- 减少元数据的量
    		- 有利于顺序读写（在磁盘上数据顺序存放）
    	- 多副本数据块形式存储，按照块的方式随机选择存储节点，默认副本数是3
    - HDFS的基本架构
    	- NameNode的作用：对等于GFS的Master，负责管理HDFS的目录树和相关的文件元数据信息，同时还负责监控各个DataNode的健康状态
    	- DataNode的作用：对等于GFS的ChunkServer，负责存储实际的数据，并将数据信息定期汇报给NameNode
    - HDFS数据分布设计
    	- 多副本数据块形式存储，按照块的方式随机选择存储节点。默认副本数为3（这话怎么这么眼熟）
    - **HDFS可靠性与出错恢复**
    	- DataNode节点的检测
    		- 心跳：NameNode不断检测DataNode是否有效
    		- 若失效，则寻找新的节点替代，将失效节点数据重新分布
    	- 集群负载均衡
    	- 数据一致性：校验和checksum
    	- 主节点元数据失效（与MapReduce类似）
    		- Multiple FsImage（文件系统状态） and EditLog（更新记录）
    		- CheckPoint
    - HDFS的安装和启动(卧槽这也有?!)
    - HDFS文件系统操作命令
    	- 如果考这个也太变态了吧，写几个基本的
    		- `bin/hadoop dfs -ls path`
    		- `bin/hadoop dfs -put localSrc dest`
    
    ####7 Hadoop分布式文件系统HDFS编程(这怎么考啊。。。假装不考(⊙﹏⊙)b)
    
    - FileSystem基类
    	- 是一个用来与文件系统交互的抽象类，可以通过实现FileSystem的子类来处理具体的文件系统，比如HDFS或其他文件系统
    - 创建文件
    	- ```public FSDataOutputStream create(Path f)

  • FSDataOutputStream create(Path f, boolean overwrite)```

    - ```public FSDataOutputSream create(Path f, boolean overwrite, int bufferSize)

• 打开文件

  • abstract FSDataInputStream open(Path f, int bufferSize) throws IOException```

    - 获取文件信息
    - 获取目录信息
    - 文件读取
    - 文件写入
    - 关闭
    - 删除
    
    ###Ch4 Hadoop系统安装运行与程序开发（这章应该不考。。。吧）
    
    ####1 Hadoop安装方式
    
    - 单机方式
    - 单机伪分布式方式：用进程模拟NameNode, DataNode, JobTracker, TaskTracker等节点
    - 集群分布模式
    
    ####2 单机Hadoop系统安装基本步骤
    
    ####3 集群Hadoop系统安装基本步骤
    
    ####4 Hadoop集群远程作业提交与执行
    
    - 程序开发与提交作业基本过程
    - 集群分布式下远程提交作业
    
    ####Hadoop MapReduce程序开发
    
    ###Ch5 MapReduce算法设计
    
    ####1 MapReduce可解决哪些算法问题？
    
    - 基本算法
    	- 分布式排序 分布式文本匹配查找 关系代数操作 矩阵向量乘法 词频统计 单词同现关系分析 文档倒排索引
    - 复杂算法或应用
    	- Web搜索 Web访问日志分析 数据/文本统计分析 图算法 聚类 机器学习 数据挖掘 生物信息统计 统计机器翻译 广告推送 推荐系统
    
    ####2 回顾：**MapReduce流水线**（加粗）
    
    1. map(K1, V1) -> [(K2, V2)]
    2. shuffle and sort
    3. reduce(K2,[V2])->[(K3, V3)]
    
    其中[]表示一个list
    
    ####3 MapReduce排序算法
    
    *要写代码的地方都先占个坑！*
    
    ####4 MapReduce文档同现分析算法
    ####5 MapReduce文档倒排索引算法（加粗）####
    ####6 专利文献数据分析
    
    ###Ch6 HBase与Hive程序设计
    
    ####1 HBase基本工作原理
    - **HBase的设计目标和功能特点**
    	1. 针对HDFS缺少结构化半结构化数据存储访问能力的缺陷，针对一个分布式数据管理系统，解决大规模的结构化数据和半结构化数据存储访问问题
    	2. 基于列表存储模式和大数据表管理能力
    	3. 提供随机和实时的数据读写访问能力
    	4. 具有高可扩展性、高可用性、容错处理能力、负载平衡能力、以及对实时数据查询能力
    - HBase数据模型
    	1. 表中数据通过一个行关键字、一个列关键字、一个时间戳进行查询和定位
    	2. 物理存储格式上按照列族存储，一行中一个列族的数据不一定存放在一个HFile里，单同一行的数据在一个region里被管理；值为空的列不予存储，以节省存储空间；访问不同列族的数据设计不同的Memstore和HFile
    - HBase的基本构架
    	- 由一个master server和一组子表数据区服务器region server构成，大表中的底层数据存储在HDFS中
    - HBase的数据存储和管理
    	- 大表被分为多个子表Region，每个子表存在一个Region Server上，而一个Region Server可以存储多个region。每个region有很多个数据存储块store构成，每个store数据块又有存放在内存当中的memStore和存放在文件当中的StoreFile构成
    	- 当内存中的memStore数据达到一定大小时，系统将自动把数据写入到文件数据块StoreFile中，而每个文件数据块最终都写入到底层HDFS中
    
    ####2 HBase基本操作与编程方法示例
    - HBase shell操作
    	- 创建表格与列举表格
    	- 插入数据
    	- 描述表信息
    	- 输入数据与扫描数据
    	- 限制列进行扫描
    	- HBase中的disable和enable
    - HBase的java编程
    	- 创建表
    	- 删除表
    	- 查询数据
    	- 插入数据
    	- 删除数据
    	- 切分表
    
    ####3 Hive基本工作原理
    - 在Hadoop上用SQL进行数据分析
    - Hive的组成模块
    	- HiveQL：Hive的数据查询语言，与SQL类似，Hive提供了这个数据查询语言与用户的接口
    	- Driver：执行的驱动，用以将各个组成部分形成一个有机的执行系统
    	- Complier：将HiveQL编译成中间表示
    	- Execution Engine：执行引擎
    	- Metastore：用以存储元数据，保存最重要的信息，有关数据库中的数据表格描述，包括每个表格的格式定义，列的类型，物理分布情况
    - Hive的系统结构
    - Hive的数据模型
    - 元数据村粗：Metastore
    - 数据的物理分布情况
    - Hive系统的配置
    
    ####4 Hive基本操作示例
    - 启动Hive的命令行界面shell
    - 创建数据表
    - 装入数据
    - SELECTS and FILTERS
    - Group By
    - Join
    
    ###Ch7 高级MapReduce编程技术（天啊！这一章都是什么鬼！）
    
    ####1 复合键值对的使用（这个加粗了）
    - 用复合键值对让系统完成排序
    - 把小的键值对合并成大的键值对
    
    ####2 用户自定义数据类型
    - Hadoop内置的数据类型
    - 用户自定义数据类型
    	- 需要实现Writable接口
    	- 作为key或者需要比较大小的时候则需要实现WritableComparable接口
    
    ####3 用户自定义输入输出格式
    - Hadoop内置的文件输入格式
    	- TextInputFormat
    	- KeyValueTextInputFormat
    - Hadoop内置的RecordReader
    	- LineRecorderReader
    	- KeyValueLineRecordReader
    - 用户自定义InputFormat和RecordReader的方法
    - Hadoop内置的文件输出格式
    - Hadoop内置的RecordWriter
    - 用户自定义OutputFormat和RecordWriter的方法
    
    
    *要写代码的地方都先占个坑！*
    ####4 用户自定义Partitioner和Combiner
    ####5 迭代完成MapReduce计算
    ####6 组合式MapReduce任务
    - MapReduce子任务的顺序化执行
    - 具有数据依赖关系的MapReduce子任务的执行
    - MapReduce前处理和后处理步骤的链式执行
    	- ```ChainMapper.addMapper(...)

  • ####7 多数据源的连接
    - 用DataJoin类实现Reduce端Join
    	- 连接主键GroupKey与记录标签Tag
    	- DataJoinMapperBase
    	- DataJoinReducerBase
    	- TaggedMapOutput
    	- Mapper需要实现的抽象方法
    		- ```abstract Text generateInputTag(String inputFile)

    • abstract TaggedMapOutput generateTaggedMapOutput(Object value)
• 用文件复制实现Map端Join
  用distributed cache将一个或多个小数据量文件分布复制到所有节点上
• 带Map端过滤的Reduce端Join
• 多数据源连接解决方法的限制

####8 全局参数/数据文件的传递

• 全局作业参数的传递
  • Configuaration类专门提供以下用于保存和获取属性的方法
  • mapper/reducer类初始化方法setup()从configuration对象中读出属性
• 全局数据文件的传递（见上distributed cache的使用（第7个问题我还么得写上））

####9 其它处理技术

• 查询任务相关信息
• 划分多个输出文件集合
• 输入输出到关系数据库
• 从数据库中输入数据
  • DBInputFormat
  • DBRecordReader
• 向数据库中输出计算结果

###Ch8 基于MapReduce的搜索引擎算法

####1 网页排名图算法PageRank

PageRank是Google用来标识网页的等级或重要性的一种方法。其级别从1到10，PR值越高说明越受欢迎（越重要）。

• PageRank的基本设计思想和设计原则
  • 被许多优质网页所链接的网页，多半也是优质网页
  • 一个网页想要拥有较高的PR值的条件：
    • 有很多网页链接到它
    • 有高质量的网页链接到它
• PageRanks的简化模型及其缺陷
  • 可以把互联网上的各个网页之间的链接关系看成一个有向图
  • 对于任意网页u，它的PageRank值可以表现为
    
    其中B(u)表示所有链接到网页u的网页的集合
    L(v)表示网页v的对外链接个数
  • 缺陷：实际网络超链接环境没有那么理想化，会面临以下两个问题：
    • Rank Leak：一个独立的网页如果没有外出链接就会产生排名泄露
      • 将无出度的节点递归地从图中去掉，待其它节点计算完后再加上
      • 对无出度的节点添加一条边，指向指向它的那些节点
    • Rank Sink：整个网页图中若有网页没有入度链接，其产生的贡献就会被吞噬，排名就会下沉，PR会趋向于0
• PageRank的随机浏览模型
  • 假定一个上网者从一个随机网页开始浏览
  • 上网者不断点击当前网页的链接开始下一次浏览
  • 但是，上网者最终厌倦了，开始了一个随机的网页
  • 随机上网者用以上方式访问一个新网页的概率就等于这个网页的PR值
  • 这种随机模型更加接近于用户的浏览行为
• 随机浏览模型的PageRank公式
  
  d是初始设置的访问链接的概率
  N表示网页的总数
• 用MapReduce实现PageRank
  1. GraphBuilder
  2. PageRankIter
  3. Rankreview
  4. PageRank迭代终止条件

####2 全文搜索引擎算法的设计实现（灰色）

• 离线Web文档倒排索引处理
• 基于倒排索引实现在线全文检索

###Ch9 基于MapReduce的数据挖掘基础算法

####1 基于MapReduce的K-means并行化算法

• 数据挖掘并行算法研究的重要性
• K-means聚类算法
• 基于MapReduce的k-means并行算法设计
• 聚类算法应用实例

####2 基于MapReduce的分类并行化算法

• 分类问题的基本描述
• k-最近邻分类并行化算法
• 朴素贝叶斯分类并行化算法

####3 基于MapReduce的频繁项集挖掘算法

• 频繁项集挖掘基本问题
• 现有算法概述
• PSON: 基于MapReduce的并行化算法
• 并行化算法实验结果

###Ch10 Spark系统及其编程技术

####1 Spark系统简介

• 为什么会有Spark？
• Spark基本架构及组件
  • Master node + Driver
  • Worker node + Executors
• Spark的程序执行过程
  • Application(Driver+Executors), Job, Stage, Task
• Spark的技术特点
  • 基于内存计算的弹性分布式数据集（RDD）
  • 灵活的计算流图（DAG）
  • 覆盖多种计算模式（查询分析、批处理、流式计算、迭代计算、图计算、内存计算）
• Spark编程模型与编程接口
  • RDD Transformation & Action
  • Scala, Java, Python
• Spark的安装运行模式
  • Stand-Alone, YARN, MESOS, Docker

####2 Spark编程

• WordCount
• KMeans

####3 Spark环境中其他功能组件简介

• SparkSQL
• Spark Streaming
• GraphX
• MLlib

###Ch11 云计算技术简介

• 什么是云计算
• 云计算的主要特点
• 云计算的分类
• 云计算发展现状与趋势
• 云计算关键技术
• 云计算管理调度软件平台