「大数据」（七十九）Spark之Lineage机制
【导读：数据是二十一世纪的石油，蕴含巨大价值，这是·情报通·大数据技术系列第[79]篇文章，欢迎阅读和收藏】
1 基本概念
容错性 ：对于流式计算来说，容错性至关重要。首先我们要明确一下 Spark 中 RDD 的容错机制。每一个 RDD 都是一个不可变的分布式可重算的数据集，其记录着确定性的操作继承关系（ lineage ），所以只要输入数据是可容错的，那么任意一个 RDD 的分区（ Partition ）出错或不可用，都是可以利用原始输入数据通过转换操作而重新算出的。
一般来说，分布式数据集的容错性有两种方式： 数据检查点和记录数据的更新 。
面向大规模数据分析，数据检查点操作成本很高，需要通过数据中心的网络连接在机器之间复制庞大的数据集，而网络带宽往往比内存带宽低得多，同时还需要消耗更多的存储资源。
因此， Spark 选择记录更新的方式。但是，如果更新粒度太细太多，那么记录更新成本也不低。因此， RDD 只支持粗粒度转换，即只记录单个块上执行的单个操作，然后将创建 RDD 的一系列变换序列（每个 RDD 都包含了他是如何由其他 RDD 变换过来的以及如何重建某一块数据的信息。因此 RDD 的容错机制又称“血统 (Lineage) ”容错）记录下来，以便恢复丢失的分区。
Lineage 本质上很类似于数据库中的重做日志（ Redo Log ），只不过这个重做日志粒度很大，是对全局数据做同样的重做进而恢复数据。
虽然只支持粗粒度转换限制了编程模型，但我们发现 RDD 仍然可以很好地适用于很多应用，特别是支持数据并行的批量分析应用，包括数据挖掘、机器学习、图算法等，因为这些程序通常都会在很多记录上执行相同的操作。RDD 不太适合那些异步更新共享状态的应用，例如并行 web 爬行器。
2 术语解释
RDD ： （ Resilient Distributed Datasets 弹性分布式数据集），是 spark 中最重要的概念，可以简单的把 RDD 理解成一个提供了许多操作接口的数据集合，和一般数据集不同的是，其实际数据分布存储于一批机器中（内存或磁盘中）。它具备像 MapReduce 等数据流模型的容错特性，并且允许开发人员在大型集群上执行基于内存的计算。
为了有效地实现容错， RDD 提供了一种高度受限的共享内存，即 RDD 是只读的，并且只能通过其他 RDD 上的批量操作来创建。尽管如此， RDD 仍然足以表示很多类型的计算，包括 MapReduce 和专用的迭代编程模型（如 Pregel ）等。
RDD 是只读的、分区记录的集合。RDD 只能基于在稳定物理存储中的数据集和其他已有的 RDD 上执行确定性操作来创建。这些确定性操作称之为转换，如 map 、 filter 、 groupBy 、 join （转换不是程开发人员在 RDD 上执行的操作）。
RDD 不需要物化。RDD 含有如何从其他 RDD 衍生（即计算）出本 RDD 的相关信息（即 Lineage ），据此可以从物理存储的数据计算出相应的 RDD 分区 [2] 。
RDD 作为数据结构，本质上是一个只读的分区记录集合。一个 RDD 可以包含多个分区，每个分区就是一个 dataset 片段。RDD 可以相互依赖。如果 RDD 的每个分区最多只能被一个 Child RDD 的一个分区使用，则称之为 narrow dependency ；若多个 Child RDD 分区都可以依赖，则称之为 wide dependency 。不同的操作依据其特性，可能会产生不同的依赖。例如 map 操作会产生 narrow dependency ，而 join 操作则产生 wide dependency 。
3 Lineage 机制
3.1 Lineage 简介
相比其他系统的细颗粒度的内存数据更新级别的备份或者 LOG 机制， RDD 的 Lineage 记录的是粗颗粒度的特定数据 Transformation 操作（如 filter 、 map 、 join 等）行为。当这个 RDD 的部分分区数据丢失时，它可以通过 Lineage 获取足够的信息来重新运算和恢复丢失的数据分区。因为这种粗颗粒的数据模型，限制了 Spark 的运用场合，所以 Spark 并不适用于所有高性能要求的场景，但同时相比细颗粒度的数据模型，也带来了性能的提升。
3.2 两种依赖关系
RDD 在 Lineage 依赖方面分为两种：窄依赖 (Narrow Dependencies) 与宽依赖 (Wide Dependencies, 源码中称为 Shuffle Dependencies) ，用来解决数据容错的高效性。
· 窄依赖是指父 RDD 的每一个分区最多被一个子 RDD 的分区所用，表现为一个父 RDD 的分区对应于一个子 RDD 的分区 或多个父 RDD 的分区对应于一个子 RDD 的分区，也就是说一个父 RDD 的一个分区不可能对应一个子 RDD 的多个分区。1 个父 RDD 分区对应 1 个子 RDD 分区，这其中又分两种情况：1 个子 RDD 分区对应 1 个父 RDD 分区（如 map 、 filter 等算子）， 1 个子 RDD 分区对应 N 个父 RDD 分区（如 co-paritioned （协同划分）过的 Join ）。
· 宽依赖是指子 RDD 的分区依赖于父 RDD 的多个分区或所有分区，即存在一个父 RDD 的一个分区对应一个子 RDD 的多个分区。1 个父 RDD 分区对应多个子 RDD 分区，这其中又分两种情况：1 个父 RDD 对应所有子 RDD 分区（未经协同划分的 Join ）或者 1 个父 RDD 对应非全部的多个 RDD 分区（如 groupByKey ）。
本质理解： 根据父 RDD 分区是对应 1 个还是多个子 RDD 分区来区分窄依赖（父分区对应一个子分区）和宽依赖（父分区对应多个子分区）。如果对应多个，则当容错重算分区时，因为父分区数据只有一部分是需要重算子分区的，其余数据重算就造成了冗余计算。
对于宽依赖， Stage 计算的输入和输出在不同的节点上，对于输入节点完好，而输出节点死机的情况，通过重新计算恢复数据这种情况下，这种方法容错是有效的，否则无效，因为无法重试，需要向上追溯其祖先看是否可以重试（这就是 lineage ，血统的意思），窄依赖对于数据的重算开销要远小于宽依赖的数据重算开销。
窄依赖和宽依赖的概念主要用在两个地方：一个是容错中相当于 Redo 日志的功能；另一个是在调度中构建 DAG 作为不同 Stage 的划分点。
3.3 依赖关系的特性
第一，窄依赖可以在某个计算节点上直接通过计算父 RDD 的某块数据计算得到子 RDD 对应的某块数据；宽依赖则要等到父 RDD 所有数据都计算完成之后，并且父 RDD 的计算结果进行 hash 并传到对应节点上之后才能计算子 RDD 。
第二，数据丢失时，对于窄依赖只需要重新计算丢失的那一块数据来恢复；对于宽依赖则要将祖先 RDD 中的所有数据块全部重新计算来恢复。所以在长“血统”链特别是有宽依赖的时候，需要在适当的时机设置数据检查点。也是这两个特性要求对于不同依赖关系要采取不同的任务调度机制和容错恢复机制。
3.4 容错原理
在容错机制中，如果一个节点死机了，而且运算窄依赖，则只要把丢失的父 RDD 分区重算即可，不依赖于其他节点。而宽依赖需要父 RDD 的所有分区都存在，重算就很昂贵了。可以这样理解开销的经济与否：在窄依赖中，在子 RDD 的分区丢失、重算父 RDD 分区时，父 RDD 相应分区的所有数据都是子 RDD 分区的数据，并不存在冗余计算。在宽依赖情况下，丢失一个子 RDD 分区重算的每个父 RDD 的每个分区的所有数据并不是都给丢失的子 RDD 分区用的，会有一部分数据相当于对应的是未丢失的子 RDD 分区中需要的数据，这样就会产生冗余计算开销，这也是宽依赖开销更大的原因。因此如果使用 Checkpoint 算子来做检查点，不仅要考虑 Lineage 是否足够长，也要考虑是否有宽依赖，对宽依赖加 Checkpoint 是最物有所值的。
4 Checkpoint 机制
通过上述分析可以看出在以下两种情况下， RDD 需要加检查点。
1. DAG 中的 Lineage 过长，如果重算，则开销太大（如在 PageRank 中）。
2. 在宽依赖上做 Checkpoint 获得的收益更大。
由于 RDD 是只读的，所以 Spark 的 RDD 计算中一致性不是主要关心的内容，内存相对容易管理，这也是设计者很有远见的地方，这样减少了框架的复杂性，提升了性能和可扩展性，为以后上层框架的丰富奠定了强有力的基础。
在 RDD 计算中，通过检查点机制进行容错，传统做检查点有两种方式：通过冗余数据和日志记录更新操作。在 RDD 中的 doCheckPoint 方法相当于通过冗余数据来缓存数据，而之前介绍的血统就是通过相当粗粒度的记录更新操作来实现容错的。