Lineage机制的优化探究

伯克利实验室在一篇公开论文中，对RDD的定义是：基于内存的集群计算容错抽象。英文原文标题是：Resilient Distributed Datasets：A Fault-Tolerant Abstraction for In-Memory Cluster Computing。对于设计RDD来说，最大的挑战在于如何提供高效的容错（fault-toler-ance）而保证RDD中数据的健壮性。现有的集群上的内存存储抽象，如分布式共享内存、key/value存储、内存数据库以及Cache类系统等，都提供了对可变状态（如数据库表里的Cell）的细粒度更新。在这种设计下为了容错，就必须在集群结点间进行数据复制（data rep-licate）或者记录日志。这两种方法对于数据密集型的任务来说开销都非常大，因为需要在结点间复制大量的数据，而网络带宽远远低于RAM容量。

与这些框架细粒度的内存数据更新级别的备份或者LOG机制不同，RDD提供了基于粗粒度转换（coarse-grained transformation）的接口，例如map、filter、join，能够将同一操作施加到许多数据项上。于是通过记录这些构建数据集的粗粒度转换的日志，而非实际数据，就能够实现高效的容错。RDD数据集通过所谓的血统关系（Lineage）记住了它是如何从其他RDD中演变过来的，当某个RDD部分分区数据丢失时，RDD通过Lineage获取充足的关于丢失的那个RDD数据分区是如何从其他RDD产生的信息，从而通过重新计算来还原丢失的数据，避免了数据复制的高开销。

尽管基于粗粒度转换的接口第一眼看起来有些受限，不够强大，但实际上RDD却能很好地用于许多并行计算应用，因为这些应用本身自然而然地就是在多个数据项上运用相同的操作。事实上，RDD能够高效地表达许多框架的编程模型，如MapReduce、DryadLINQ、SQL、Pregel，以及它们处理不了的交互式数据挖掘应用。(www.xing528.com)

在RDD中将依赖划分成了两种类型：窄依赖（Narrow Dependencies）与宽依赖（Wide Dependencies（Shuffle Dependencies））。窄依赖是指父RDD的每一个分区最多被一个子RDD的分区所用，表现为一个父RDD的分区对应于一个子RDD的分区或多个父RDD的分区对应于一个子RDD的分区，也就是说一个父RDD的一个分区不可能对应一个子RDD的多个分区。宽依赖是指子RDD的分区依赖于父RDD的多个分区或所有分区，也就是说存在一个父RDD的一个分区对应一个子RDD的多个分区。例如，map就是一种窄依赖，而join则会导致宽依赖，除非父RDD是hash-partitioned。对于宽依赖，这种计算的输入和输出在不同的结点上，lineage方法对于输入结点完好，而输出结点宕机时，通过重新计算，这种情况下，这种方法容错是有效的，否则无效，因为无法重试，需要向上其祖先追溯看是否可以重试（这就是lineage，血统的意思），窄依赖对于数据的重算开销要远小于宽依赖的数据重算开销。

这种划分在容错机制中有两个用处。首先，窄依赖支持在一个结点上管道化执行，也就是pipeline操作。例如基于一对一的关系，可以在map、filter之后才开始一次性执行这两个连续的操作。其次，窄依赖支持更高效的故障还原。因为对于窄依赖，只有丢失的父RDD的分区需要重新计算，不依赖于其他分区，并不存在冗余计算。而对于宽依赖，一个子RDD分区的故障可能导致来自所有父RDD的分区丢失，因此就需要完全重新执行，但这样计算也会重新计算那些对应的并不是已丢失的子RDD的分区的数据，会产生冗余计算开销。因此对于宽依赖，Spark会在持有各个父分区的结点上，将中间数据持久化来简化故障还原，就像MapReduce会持久化map的输出一样。