1. MapReduce/Hadoop
1.1. 编程模型
1.1.1. 整体思路
- 解决思路
- 程序员写串行程序
- 由系统完成并行分布式的执行
- 程序员保证串行程序的正确性
- 编程序时不需要思考并行的问题
- 调试时只需要保证串行执行正确
- 系统负责并行分布执行的正确性和效率
- Multi-threading, Socket programming, Data distribution, Job distribution, coordination, load balancing, Fault tolerance
- 缺点：
- 牺牲了程序的功能！
- <key, value>
- 数据由一条一条的记录组成
- 记录之间是无序的
- 每一条记录有一个key，和一个value
- key: 可以不唯一
- key与value的具体类型和内部结构由程序员决定，系统基本上把它们看作黑
1.1.3. Map-shuffle-Reduce
Map(ik,iv) -> {<mk,mv>}
Reduce(mk,{mv}) -> {<ok,ov>}
Map 函数
shuffle
为了做Reduce，系统内部做了一个shuffle的操作。
Reduce
Map-shuffle-Reduce
1.1.4. Word count举例
1.1.5. 与SQL Select语句的关系
1.2. 系统实现
1.2.1. 系统架构
系统架构
MapReduce/Hadoop 系统架构
1.2.2. 工作过程
提交作业：
用户向JobTracker提交JobConf。JobConf包括Map函数、Reduce函数(Jar)、配置信息(例如，几个Mappers，几个Reducers)、输入路径、输出路径等Map Task 读数据
JobTracker给mappers分配任务，mapper从HDFS中读取数据块并处理。
Split：一个HDFS数据块
Split 的个数可能多于Mappers个数
- 每个split对应一个Map Task
- 每个Mapper可能需要处理多个Task
优化：就近处理
- JobTracker尽量Mapper处理本机data node存储的split，从而减少网络数据传输的开销
InputFormat
- Hadoop提供TextInputFormat，KeyValueInputFormat，SequenceFileInputFormat
- 如何从提供的输入路径获得数据
- 如何把输入数据分成split
- 如何将数据分解成<ik,iv>
程序员可以编写自己的InputFormat
- Map Task 执行
对于一个split，Mapper
- 对每个<ik, iv>调用一次Map函数生成<mk,mv>
- 对每个mk调用Partitioner计算其对应的Reduce task id
- 属于同一个Reduce task的<mk,mv>存储于同一个文件，放在本地硬盘上
- 每个文件按照mk自小到大排序
Partitioner：
- Hadoop默认使用HashPartitionerReduce taskid=hash(mk) % ReduceTaskNumber
- 程序员可以编写自己的Partitioner
- shuffle
- Reducer从每个Map task传输中间结果文件
- 每个文件本身已经排好序了
- 对多个结果文件进行归并，从而实现group by
- Reduce
- 对于每个<mk,{mv}>调用一次Reduce函数
- 产生的<ok, ov>写入输出文件
- OutputFormat
- 每个Reduce task 产生一个单独的文件
1.2.3. 容错
HeartBeat(心跳)消息定期发送，向JobTracker汇报进度
JobTracker可以及时发现不响应的机器或速度非常慢的机器
- 这些异常机器被称作Stragglers
一旦发现Straggler
- JobTracker就将它需要做的工作分配给另一个worker
Straggler是Mapper，将所对应的splits分配给其它的Mapper
- 输入数据是分布式文件，所以不需要特殊处理
- 通知所有的Reducer这些splits的新对应Mapper
- Shuffle时从新对应的Mapper传输数据
Stragger是Reducer，在另一个TaskTracker执行这个Reducer
Grep
Sorting
Join
2. Microsoft Dryad
Dryad是对MapReduce模型的一种扩展
- 组成单元不仅是Map和Reduce，可以是多种节点
- 节点之间形成一个有向无环图DAG(Directed Acyclic Graph) ，以表达所需要的计算
- 节点之间的数据传输模式更加多样
- 可以是类似Map/Reduce中的shuffle
- 也可以是直接1:1、1:多、多:1传输
- 比MapReduce更加灵活，但也更复杂–需要程序员规定计算的DAG
Microsoft内部云计算系统Cosmos基于Dryad
3. 同步图计算系统
3.1. 图算法
3.2. 同步图计算
3.2.1. 图计算模型
3.2.1.1. 特点
- BSP模型
- 基于顶点的编程模型
3.2.1.2. 如何结束
