基于大型集群的快速通用数据处理架构
摘要
提出了一种集群计算架构，能够解决以下几个问题：
- 为了满足不断增长的数据量和处理速度需求；
- 单一的机器处理能力并没有跟上数据增长的速度，使得这些有价值的数据越来越难以被使用；
- 除了简单的查询，像机器学习和图分析这样的复杂算法也得到日益广泛的应用。
- 除了批量处理，一些组织还需要在实时数据源上进行流分析，以保证能够及时采取行动。
通过简单的扩展 MapReduce，为其增加了数据共享原语，也就是所谓的弹性分布式数据集（RDDs）。
第一章 简介
单机的处理能力和 I/O 性能并没有跟上海量数据的这种增长。这样一来，越来越多的企业不得不向外扩展他们的计算至集群模式。
集群环境带来的挑战：
- 并行化：以并行的方式重写应用程序
- 容错：大规模的情况下节点故障将变得很常见
- 动态地扩展和缩减计算资源
MapReduce 的一个简单扩展，称为弹性分布式数据集（RDDS）,它增加了高效的数据共享元语，以及大大增加了它的通用性。由此产生的架构比当前系统有几个关键优势：
- 在相同的运行环境下，它支持批处理、交互式、迭代和流计算，结合这些模式提供丰富的应用编程，并且相对于单一模式的系统能更好的发挥其性能。
- 它以很小的代价在这些计算模式上提供结点故障和 straggler 的容忍功能。事实上，在一些地方（如流和 SQL），基于 RDD 产生的新系统比现有的系统有更强的容错性。
- 它实现的性能往往比 MapReduce 高 100 倍，并可媲美各个应用领域的专业系统。
- 这很适合多组织用户管理，允许应用程序弹性地扩缩容和响应式地共享资源。
1.2弹性分布式数据集(RDDS)
弹性分布式数据集 (RDDs)，它是 MapReduce 模型一种简单的扩展和延伸。RDDS能在并行计算阶段之间能够高效地数据共享。RDDs 是一个可以避免复制的容错分布式存储概念。取而代之，每一个 RDD 都会记住由构建它的那些操作所构成的一个图，类似于批处理计算模型，可以有效地重新计算因故障丢失的数据。
我们使用 RDD 机制实现了多类模型，包括多个现有的集群编程模型和之前模型所没有支持的新应用。我们讨论以下四类模型。
- 迭代式算法： 一种目前已经开发的针对特定系统最常见的的工作模式是代算法，比如应用于图处理，数值优化，以及机器学习中的算法。
- 关系查询：Shark提供完整的容错机制，能够在短查询和长查询中很好的扩展，同时也能在 RDD 之上提供复杂分析函数的调用(例如, 机器学习)。
- MapReduce RDD 通过提供 MapReduce 的一个超集，能够高效地执行 MapReduce 程序。
- 流式数据处理 我们的系统与定制化系统最大的区别是我们也使用 RDD 实现了流式处理。D-Streams 把流式计算的执行当做一系列短而确定性的批量计算的序列，将状态保存在 RDD 里。D-Stream 模型通过根据相关 RDD 的依赖关系图进行并行化恢复，就能达到快速的故障恢复，这样不需要通过复制。
Spark 相对较小:共 34，000 行 Scala(公认的高级语言)代码。几百行代码实现MapReduce，8000 行代码实现了离散 Stream，12000行代码实现一个以 Apache Hive 作为 Spark 前段进行查询的 SQL 系统。
第二章 弹性分布式数据集
我们所提出的弹性分布式数据集（RDDs），这种全新的抽象模式令用户可以直接控制数据的共享。RDD 具有可容错和并行数据结构特征，这使得用户可以指定数据存储到硬盘还是内存、控制数据的分区方法并在数据集上进行种类丰富的操作。
RDD提供一种基于粗粒度变换（如， map, filter, join）的接口，该接口会将相同的操作应用到多个数据集上。这使得他们可以通过记录用来创建数据集的变换（lineage），而不需存储真正的数据，进而达到高效的容错性。当一个RDD的某个分区丢失的时候，RDD记录有足够的信息记录其如何通过其他的RDD进行计算，且只需重新计算该分区。因此，丢失的数据可以被很快的恢复，而不需要昂贵的复制代价。
2.2RDD概述
从形式上看，RDD是一个分区的只读记录的集合。RDD只能通过在稳定的存储器或其他RDD的数据上的确定性操作来创建。用户可以控制 RDD 的其他两个方面：持久化和分区。
用户可以控制 RDD 的其他两个方面：持久化和分区。
Spark 直到 RDD 第一次调用一个动作时才真正计算 RDD。这也就使得 Spark可以按序缓存多个变换。
2.2.3RDD模型的优点
| 方面 | RDDs | 分布式共享内存 |
|---|---|---|
| 读 | 粗细粒度 | 细粒度 |
| 写 | 粗粒度 | 细粒度 |
| 一致性 | 不重要（不可变） | 取决于应用程序/运行 |
| 容错性 | 细粒度并且使用 lineage开销低 | 需要检查点和程序回滚 |
| straggler缓解 | 可以使用后备任务 | 难 |
| 工作分配 | 根据数据局部性自动分配 | 取决于应用程序（运行时透明） |
| 当没有足够的 RAM时行为 | 类似于现有的数据流系统 | 性能不佳（交换？） |
首先，在 RDDs 上的批量操作过程中，任务的执行可以根据数据的所处的位置来进行优化，从而提高性能。
RDDS 不太适用于通过异步细粒度更新来共享状态的应用，比如针对 Web 应用或增量网络爬虫的存储系统。
我们可以将 transformations 操作理解成一种惰性操作，它只是定义了一个新的 RDD，而不是立即计算它。相反，actions 操作则是立即计算，并返回结果给程序，或者将结果写入到外存储中。
2.4抽象RDDs
我们提供了一个通用接口来抽象每个 RDD，并提供 5 种信息：一组分区，他们是数据集的最小分片；一组 依赖关系，指向其父 RDD；一个函数，基于父 RDD 进行计算；以及划分策略和数据位置的元数据。
最有趣的问题在于如何表示 RDD 之间的依赖关系。我们发现，比较
合理的方式是将依赖关系分成两类：窄依赖：每个父 RDD 的分区都至多被一个子 RDD 的分区使用；宽依赖：多个子 RDD 的分区依赖一个父 RDD 的分区。
2.5.1作业调度
当用户对一个 RDD 执行 Action(如 count 或 save)操作时， 调度器会根据该 RDD 的 lineage，来构建一个由若干 阶段(stage) 组成的一个 DAGG(有向无环图)以执行程序，每个 stage 都包含尽可能多的连续的窄依赖型转换。各个阶段之间的分界则是宽依赖所需的 shuffle 操作，或者是 DAG 中一个经由该分区能更快到达父 RDD 的已计算分区。之后，调度器运行多个任务来计算各个阶段所缺失的分区，直到最终得出目标 RDD。
调度器向各机器的任务分配采用延时调度机制并根据数据存储位置(本地性)来确定。
2.5.4内存管理
Spark提供了三种对持久化RDD的存储策略：未序列化Java对象存于内存中、序列化后的数据存于内存、磁盘存储。
对于有限可用内存，我们使用以 RDD 为对象的 LRU 回收算法来进行管理。当计算得到一个新的 RDD 分区，但却没有足够空间来存储它时，系统会从最近最少使用的 RDD 中回收其一个分区的空间。除非该 RDD 便是新分区对应的 RDD，这种情况下，Spark 会将旧的分区继续保留在内存，防止同一个 RDD 的分区被循环调入调出。
2.5.5检查点恢复
虽然 lineage 可用于错误后 RDD 的恢复，但对于很长的 lineage 的 RDD 来说，这样的恢复耗时较长。由此，将某些 RDD 进行检查点操作(Checkpoint)保存到稳定存储上，是有帮助的。
第三章 基于RDD的模型
3.1 简介
简单回顾一下之前的章节，RDD 可以提供如下特性：
- 在一个集群中对于任意记录具有不变性的存储（在 Spark 中以 Java 对象的方式来表示）
- 通过每一条记录的 key 字段来控制数据分区
- 将粗粒度的操作用于分区的操作
- 利用内存存储的低延迟特性
3.3 Shark:RDDs 上的 SQL
Shark 使用 RDD 模型来执行大部分的计算，这些计算是在内存中完成的，与此同时，Shark还提供一个细粒度的容错模型。
首先，为了高效地存储和处理关系数据，我们实现了在内存
中按列压缩存储数据的技术。
3.4 实现
Shark 在 Spark 上执行 SQL 查询的步骤与传统的 RDBMS 类似：查询解析，生成逻辑计划和生成物理计划的。
对于一个给定的查询，Shark 使用 Apache Hive 查询编译器来解析该查询并生成抽象语法树。然后语法树被转换成一个逻辑计划，并对该计划进行一些基本的逻辑优化，如采用谓词下推
（pushdown）。到目前为止，Shark 和 Hive 都采用相同的方法。Hive 会将操作转换成由多个MapReduce 阶段组成的物理计划。至于 Shark，它的优化器采用额外的规则优化，如推送 LIMIT
到各个分区，并创建一个由 RDDs 转换，而不是 MapReduce 任务组成的物理计划。Spark 的 master 使用标准的 DAG 调度技术执行这个依赖图。
第四章 离散流
4.1 简介
这里提出一种名为 离散流(D-Streams) 的新式流数据处理模型来克服上述问题。与管理长时间存在的操作不同，D-Streams 结构将各运算流化成为一系列短时间间隔的无状态、确定性的批计算。
4.3 离散流（D-Streams）
D-Streams 通过将计算构造为一组短的，无状态的，确定性的任务代替连续的，有状态的操作来避免传统流处理的问题。然后，它们将状态存放在内存中，再通过容错的数据结构（RDDs）
可以重新计算出该状态。
