写在前面的话
本章是ddia的第十章，批处理
本章的阅读是非常吃力和不解的，因为我的MapReduce只在读书时了解过一些概念，要强行来读这上面的文字是比较头疼的，只能大概的去想象描述的问题，在读完之后有时间需要去实践一下了解下MapReduce和Hadoop实际是怎么玩的。
整体来说本章描述的批处理的两个核心问题是分区和容错，MapReduce通过Mapper进行分区排序，确保将相关数据放在一起，而容错更多是使用物化中间状态，使得单个任务的恢复非常容易。
其他部分还介绍了各种MapReduce的连接算法，很遗憾这部分我并没有看太明白，雾里看花，很遗憾。
批处理
三种不同类型的系统：
- 服务(在线系统)
服务等待客户的请求或指令到达。每收到一个，服务会试图尽快处理它，并发回一个响应，核心指标是响应式时间
- 批处理系统(离线系统)
一个批处理系统有大量的输入数据，跑一个作业来处理它，生成一些输出数据。主要指标通常是吞吐量
- 流处理系统(准实时系统)
介于在线和离线(批处理)之间，流处理消费输入并产生输出，流式作业在事件发生后不久就会对事件进行操作。
使用Unix工具进行批处理
Unix哲学
- 让每个程序都做好一件事。要做一件新的工作，写一个新程序，而不是通过添加“功能”让老程序复杂化
- 期待每个程序的输出成为另一个程序的输入。不要将无关信息混入输出。避免使用严格的列数据或二进制输入格式
- 设计和构建软件，甚至是操作系统，要尽早尝试，最好在几周内完成。不要犹豫，扔掉笨拙的部分，重建它们
- 优先使用工具来减轻编程任务，即使必须曲线救国编写工具，且在用完后很可能要扔掉大部分。
简而言之：自动化，快速原型设计，增量式迭代，对实验友好，将大型项目分解成可管理的块
统一的接口
在Unix中，这样的接口是一个文件
逻辑与布线相分离
Unix工具的另一特点是：标准输入(stdin)和标准输出(stdout)
将输入/输出布线与程序逻辑分开，可以将小工具合成更大的系统
透明度和实验
Unix的好处：
- 输入文件通常被视为不可变的，可以任意尝试而不会损坏输入文件
- 可以在任何时候结束管道，输出到less，调试非常有用
- 可以将一个流水线阶段的输出写入文件，作为下一阶段的输入，而无需重新运行整个管道
局限：
- 只能在一台机器上运行
MapReduce和分布式文件系统
一个MapReduce作业可以和一个Unix进程相类比：
- 接受一个或多个输入，产生一个或多个输出
- 产生一个或多个输出
- 在分布式文件系统上读写文件(HDFS)
HDFS(Hadoop分布式文件系统)
- 基于无共享原则
- 共享磁盘存储由集中式存储设备实现
- 不需要特殊的硬件，只需要通过传统数据中心网络连接的计算机
- 在概念上创建了一个大型文件系统，可以使用所有运行有守护进程的机器的磁盘
MapReduce作业执行
处理模式：
- 读取一组输入文件，分解成记录(
records) - 调用mapper函数，从每条输入中提取一堆键值
- 按键排序所有的键值对
- 调用Reducer函数遍历排序后的键值对
Map和Reduce是编写自定义数据处理代码的地方
需要实现两个回调函数Mapper和Reducer，其行为如下
Mapper：
- Mapper会在每条输入记录上调用一次，其工作是从输入记录中提取键值
- 可以生成任意数量的键值对
- 每个记录都是独立处理的
Reducer： - 拉取由Mapper生成的键值对，收集属于同一个键的所有值，并使用在这组值列表上迭代调用Reducer
- Reducer可以产生输出记录
分布式执行MapReduce
原则：将计算放在数据附近
- 在其中一台存储输入文件副本的机器上运行每个Mapper，会节省通过网络复制输入文件的开销，减少网络负载并增加局部性
MapReduce工作流
通过目录名隐式实现的:
- 第一个作业必须将其输出配置为HDFS中的指定目录，第二个作业必须将其输入配置为从同一个目录
- 从MapReduce框架的角度来看，这是是两个独立的作业。
工作流中的一项作业只有在先前的作业完成后才能开始。
为了处理这些作业之间的依赖，产生了不少的工作流调度器
- Oozie，Azkaban，Luigi，Airflow和Pinball
Reduce端连接与分组
在批处理的语境中讨论连接时，我们指的是在数据集中解析某种关联的全量存在
示例
场景：
- 左侧是用户活动
- 右侧是用户的档案
- 分析任务需要将左右简单关联，例如确定哪些页面更受哪些年龄段的用户欢迎
最简单方法：
逐个遍历活动事件，为每个遇到的用户ID查询用户数据库
- 缺点：
- 性能差：处理吞吐量受限于网络速度。
- 非确定：查询远程数据可能导致变动。
排序合并连接
流程：
- 通过键对Mapper输出进行分区，对键值进行排序(使有相同ID的结果彼此相邻)
- 执行实际的连接逻辑，Reducer将出生日期存储在局部变量中，然后使用相同的用户ID遍历活动事件，输出观看网址和年龄的结果对
排序合并连接：Reducer一次处理一个特定用户ID的所有记录，只需要将一条用户记录保存在内存中，不需要发出任何网络请求
把相关数据放在一起
使用MapReduce编程模型，能将计算的物理网络通信层面(从正确的机器获取数据)从应用逻辑中剥离出来(获取数据后执行处理)
GROUP BY
使用MapReduce实现这种分组操作的最简单方法是设置Mapper，以便它们生成的键值对使用所需的分组键。然后分区和排序过程将所有具有相同分区键的记录导向同一个Reducer。因此在MapReduce之上实现分组和连接看上去非常相似。
处理倾斜
对于某些热点对象，例如“社交网络中的名人”，可以使用一些算法补偿
MapReduce作业只有在所有Mapper和Reducer都完成时才完成，所有后续作业必须等待最慢的Reducer才能启动
例如 Pig中的倾斜连接
- 首先运行抽样确定热键
- Mapper将热键关联记录随机发送到几个Reducer上
- 与热键相关的记录需要被复制到所有处理该键的Reducer上
Hive的偏斜优化
- 在表格元数据中显式指定热键
- 对于热键，使用Map端连接
Map端连接
如果能对输入数据作出假设，就可以使用Map端连接来加快连接速度
广播散列连接
- Mapper将较小输入整个加载到内存中。
- 将较小输入存储在本地磁盘上的只读索引中
分区散列连接
当连接两端输入有相同的分区数，且两侧的记录都是使用相同的键与相同的哈希函数做分区时
散列连接方法可以独立应用于每个分区
例如 可以根据用户ID的最后一位十进制数字来对活动事件和用户数据库进行分区
Map端合并连接
如：输入数据集以相同的方式分区和基于相同的键排序，Mapper可以执行归并操作：按键递增的顺序依次读取两个输入文件，将具有相同键的记录配对
MapReduce工作流与Map端连接
- Reduce端连接的输出是按照连接键进行分区和排序的
- Map端连接的输出则按照与较大输入相同的方式进行分区和排序
批处理的工作流的输出
批处理不是事务，也不是分析，他的输出通常不是报表，而是一些其他类型的结构
建立搜索索引
MapReduce的初衷是为其搜索引擎建立索引
可以用于对固定文档构建用于全文搜索的索引
如果文档集合发生改变
- 定期冲泡整个索引工作流
- 增量建立索引
键值存储作为批处理输出
构建机器学习系统与推荐系统，这些输出通常是某种数据库
批处理的输出回到web应用可用的数据库中：
直接可能：
直接在Mapper或Reducer中使用你最爱数据库的客户端库，并从批处理作业直接写入数据库服务器，一次写入一条记录坏处
- 为每条记录发起网络请求效率很低
- MapReduce经常并行运行任务，可能导致该数据库可能被压垮
- 需要操心作业部分成功对其他系统可见的结果
更好方案
在批处理作业内创建一个全新的数据库，并将其作为文件写入分布式系统中的作业输出目录，再批量加载到处理只读查询的服务器中
批处理输出的哲学
- 如果输出错误或损坏，可以简单回滚重新运行纠正输出
- 回滚很容易，利于敏捷开发
- 如果map或Reduce任务失败，会重新调度容忍故障，自动重试
- 同一组文件可以用作不同作业的输入
- 将逻辑与布线(配置输入和输出目录)分离，可以重用代码
Hadoop与分布式数据库对比
大规模并行处理数据库：专注于在一组机器上并行执行分析SQL查询
MapReduce：更像一个可以运行任意程序的通用操作系统
存储多样性
分布式文件系统中的文件只是字节序列，可以是任何数据模型和编码。
因此，Hadoop通常被用于实现ETL过程
事务处理系统中的数据以某种原始形式转储到分布式文件系统中，然后编写MapReduce作业来清理数据，将其转换为关系形式，并将其导入分布式数据仓库以进行分析
处理模型多样性
MapReduce使工程师能够轻松地在大型数据集上运行自己的代码
不同的处理模型都可以在共享的单个机器集群上运行，所有这些机器都可以访问分布式文件系统上的相同文件
针对频繁故障设计
当一个节点在执行查询时崩溃：
- 大规模并行处理数据库：中止整个查询，让用户重新提交查询或自动重新运行，并且在内存中保留尽可能多的数据以避免从磁盘读取的开销
- MapReduce：可以容忍单个Map或Reduce任务的失败，以单个任务的粒度重试工作
MapReduce之后
MapReduce的直接使用是非常困难的，因此有很多高级编程模型被创造出来，例如
- Pig
- Hive
- Cascading
- Crunch
物化中间状态
将中间状态写入文件的过程称为物化
Unix管道并没有完全物化中间状态，只是使用了一个小的内存缓冲区，将输出增量的流向输入
MapReduce的完全物化中间状态对比Unix管道的不足之处
- 作业只有在前驱作业中所有任务完成时才会启动，Unix会将管道连接的进程同时启动，一旦生成输出就会消费。前驱任务的完全完成会拖慢整个工作流程的执行
- Mapper通常是多余的。如果Reducer和Mapper的输出有着相同的分区与排序方式，那么Reducer就可以直接串在一起，而不用与Mapper相互交织
- 将中间状态存储在分布式文件系统中意味着这些文件被复制到多个节点。临时数据的复制是很过分的。
数据流引擎
为了解决MapReduce的问题，新的批处理出现了，例如
- Spark
- Tez
- Flink
共同特点：把整个工作流作为单个作业来处理，而不是把它分解为独立的子作业
容错
为了避免写入：如果一台机器发生故障，并且该机器上的中间状态丢失，则它会从其他仍然可用的数据重新计算
如果中间状态数据要比源数据小得多，或者如果计算量非常大，那么将中间数据物化为文件可能要比重新计算廉价的多
图与迭代处理
可以在分布式文件系统中存储图(包含顶点和边的列表的文件)，但是这种“重复至完成”的想法不能用普通的MapReduce来表示，因为它只扫过一趟数据
迭代的实现风格：
- 外部调度程序运行批处理来计算算法的一个步骤
- 当批处理过程完成时，调度器检查它是否完成
- 如果尚未完成，则调度程序返回到步骤1并运行另一轮批处理
Pregel处理模型
顶点在一次迭代到下一次迭代的过程中会记住它的状态，所以这个函数只需要处理新的传入消息。如果图的某个部分没有被发送消息，那里就不需要做任何工作
容错
在迭代结束时，定期存档所有顶点的状态来实现的，即将其全部状态写入持久化存储
如果某个节点发生故障并且其内存中的状态丢失，则最简单的解决方法是将整个图计算回滚到上一个存档点，然后重启计算