Spark的核心RDD,内存中集群计算的容错抽象

背景

传统分布式计算框架的局限性

• 分布式计算框架是针对大数据应用场景的计算框架，以分布式的形式把巨大的计算任务分成小的单机可以承受的计算任务，解决常规单机计算模式无法支撑巨大数据量的问题。
• 当前的框架提供了用于访问集群的计算资源的大量抽象，但是缺乏用于利用分布式内存的抽象，这使得一些需要在多个并行操作之间重用中间结果的应用程序效率低下，如：
  • 机器学习和图应用中常用的迭代算法，包括PageRank，K-means聚类和逻辑回归等
  • 交互式数据挖掘工具（用户反复查询一个数据子集）
• 在当前大多数的框架中，在多个并行操作之间重用数据的方法是将其写入外部稳定的存储系统中，例如分布式文件系统。由于数据复制，磁盘I /O和序列化会导致大量开销，极大程度的影响了计算的性能和效率。

​

基于内存的分布式计算构想

• 需要提供一种新的分布式计算构想，既能够保持传统分布式计算框架，如MapReduce及其相关模型的优势特性，即自动容错、位置感知性调度和可伸缩性，同时可以支持重用中间结果
• 将计算的中间结果存储由磁盘转为内存，消除磁盘I/O加载中间结果所带来的开销
• Apache Spark --> RDD 诞生

为什么需要RDD？

RDD的提出

为了满足基于内存的分布式计算思想，需要定义一种分布式计算抽象，保证在分布式环境中能够正确、高效地完成任务。

如何定义这种分布式内存抽象，需要考虑多方面的因素：

• 分布式内存抽象需要具有传统分布式计算框架的优点，即自动容错、位置感知性调度和可伸缩性
• 将中间结果存储由磁盘转化为内存，提高迭代计算的性能
• 数据集不可变，记录数据转换过程，从而实现对出错数据的恢复，提高分布式并行计算下共享数据的容错性

基于以上原则，从而有了RDD，即弹性分布式数据集的概念。

RDD的定义

RDD（Resilient Distributed Datasets）弹性分布式数据集，是一种分布式的内存抽象。

RDD具有以下属性：

• 只读：不能修改，只能通过转换操作生成新的 RDD
• 分布式：可以分布在多台机器上进行并行处理
• 弹性：计算过程中内存不够时会和磁盘进行数据交换
• 基于内存：可以全部或部分缓存在内存中，在多次计算间重用

RDD VS DSM

为了了解RDD作为分布式内存抽象的好处，将RDD与传统的分布式共享内存（DSM）进行了比较。

与DSM相比，RDD的特点：

• RDD只能通过粗粒度转换创建/写入，而DSM允许对每个内存位置进行读写。这将RDD限制为执行批量写入的应用程序，但这样有利于实现有效的容错。 特别是，RDD可以使用lineage恢复分区，不需要引起检查点的开销。另外，出现问题时只有RDD的丢失分区需要重新计算，并且它们可以在不同的节点上并行执行，不需要回滚整个程序。
• RDD不可更改，通过备份任务的复制，RDD可以处理落后任务（即运行很慢的节点），这点与MapReduce类似；DSM则难以实现备份任务，因为任务及其副本均需读写同一个内存位置的数据并干扰彼此的更新。
• 对于RDD中的批量操作，运行时将根据数据存放的位置调度任务，从而提高性能。面对扫描类型操作，如果内存不足以缓存整个RDD，就进行部分缓存，将内存容纳不下的分区存储到磁盘上。

如何实现RDD？

RDD 接口

一般通过以下公共接口来表示每个RDD：

• 一组RDD分区（partition），即数据集的基本组合单位。对于RDD来说，每个分片都会被一个计算任务处理，并决定并行计算的粒度。
• 一个计算每个分区的函数，即在父RDD上执行何种计算。Spark中RDD的计算是以分片为单位的。
• RDD之间的依赖关系，RDD的每次转换都会生成一个新的RDD，所以RDD之间就会形成类似于流水线一样的前后依赖关系。这个依赖描述了RDD之间的lineage。在部分分区数据丢失时，Spark可以通过这个依赖关系重新计算丢失的分区数据，而不是对RDD的所有分区进行重新计算。
• 元数据，描述分区模式和数据存放的位置。例如，一个表示HDFS文件的RDD包含：各个数据块（block）的一个分区，并知道各个数据块放在哪些节点上。而且这个RDD上的map操作结果也具有同样的分区，map函数是在父数据上执行的。

下表总结了RDD的内部接口：

RDD 之间的依赖关系

• 在Spark应用的执行流程中，逻辑运算会使用许多转换操作，而每个转换操作都会生成新的RDD，所以RDD之间就会形成类似流水线的前后依赖关系。设计接口的一个关键问题就是，如何表示RDD之间的依赖。
• RDD之间的依赖关系可以分为两类：窄依赖（narrow dependencies）和宽依赖（wide dependencies）
• 下图说明了窄依赖和宽依赖之间的区别（方框表示RDD，实心矩形表示partition分区）

宽依赖与窄依赖

区分窄依赖和宽依赖

• 窄依赖：每个父RDD的一个Partition最多被子RDD的一个Partition所使用，例如map、filter、union等操作都会产生窄依赖；
• 宽依赖：一个父RDD的Partition会被多个子RDD的Partition所使用，例如groupByKey、reduceByKey、sortByKey等操作都会产生宽依赖；
• 比喻：窄依赖（独生子女） 宽依赖（超生）

窄依赖相较于宽依赖的优势

• 计算方面
  • 窄依赖允许在一个集群节点上以流水线的方式（pipeline）计算所有父分区。例如，逐个元素地执行map、然后filter操作；
  • 宽依赖需要首先计算好所有父分区数据，然后在节点之间进行shuffle操作，这与MapReduce类似。
• 容错恢复方面
  • 窄依赖能够更有效地进行失效节点的恢复，当RDD分区丢失时，由于父RDD的一个分区只对应一个子RDD分区，这样只需要重算和子RDD分区对应的父RDD分区即可，所以这个重算对数据的利用率是100%的；
  • 对于宽依赖，重算的父RDD分区对应多个字RDD分区，这样实际上父RDD中只有一部分的数据是被用于恢复这个丢失的子RDD分区的，另一部分对应子RDD的其他未丢失分区，这就造成了多余的计算，宽依赖中子RDD分区通常来自于多个父RDD分区，极端情况下，所有的父RDD分区都要重新计算。

RDD 应用举例

HDFS文件、Map、Union、Sample、Join

详见论文4 Representing RDDs部分

RDD 适用场景

• 虽然只支持粗粒度转换限制了编程模型，但RDD仍然可以很好地适用于很多应用，特别是支持数据并行的批量分析应用，包括数据挖掘，机器学习，图算法等，因为这些程序通常都会在很多记录上执行相同的操作。
• RDD不太适合那些异步更新共享状态的应用，例如并行web爬行器。
• 因此，我们的目标是为大多数分析型应用提供有效的编程模型，而其他类型的应用交给专门的系统。

Spark 基本架构及运行过程

• RDD是Spark的核心，也是整个Spark的架构基础
• 与许多专有的大数据处理平台不同，Spark建立在统一抽象的RDD之上，使得它可以以基本一致的方式应对不同的大数据处理场景，包括MapReduce，Streaming，SQL，Machine Learning以及Graph等

Spark 架构

Spark运行架构如下图所示：

​

• 在Spark中，RDD被表示为对象，通过对象上的方法（或函数）来调用转换
• 用户的驱动程序Driver通过对稳定存储中的数据进行转换（例如映射和筛选）来定义一个或多个RDD并调用它们上的操作（action），这些操作将值返回到应用程序或将数据导出到存储系统。例如：count（返回RDD中的元素个数），collect（返回元素本身），save（将RDD输出到存储系统）。
• 在Spark中，只有在action第一次使用RDD时，才会计算RDD，即懒计算（azily evaluated）
• Spark运行时，用户的驱动程序Driver启动多个工作程序Worker，Worker从分布式文件系统中读取数据块（block），并将计算出的RDD分区（partition）缓存在内存中。
• 用户可以请求将RDD缓存，以加速后期的重用。缓存的RDD一般存储在内存中，但如果内存不够，可以溢出到磁盘。

Spark 任务调度

RDD在Spark中的运行过程

Spark的任务调度流程分为RDD Objects、DAGScheduler、TaskScheduler以及Worker四个部分。

关于这四个部分的相关介绍具体如下：

• RDD Objects：当RDD对象创建后，SparkContext会根据RDD之间的依赖关系，构建有向无环图DAG（Directed Acyclic Graph），然后将DAG提交给DAGScheduler。
• DAGScheduler：将DAG划分成互相依赖的多个stage，划分stage的依据就是RDD之间的宽窄依赖（遇到宽依赖就划分stage），每个Stage都是TaskSet任务集合，并以TaskSet为单位提交给TaskScheduler。
• TaskScheduler：通过TaskScheduler管理Task，并通过集群汇中的资源管理器把Task发给集群中Worker的Executor。若期间有某个Task失败，则TaskScheduler会重试；若TaskScheduler发现某个Task一直没有运行完成，则有可能在空闲的机器上启动同一个Task，哪个Task先完成就用哪个Task的结果。但是，无论Task是否成功，TaskScheduler都会向DAGScheduler汇报当前的状态，若某个Stage运行失败，则TaskScheduler会通知DAGScheduler重新提交Task。需要注意的是，一个TaskScheduler只能服务一个SparkContext对象。
• Worker：Spark集群中的Worker接收到Task后，Worker启动Executor，Executor启动线程池执行Task，这个Task就相当于Executor中进程中的一个线程。一个进程中可以有多个线程在工作，从而可以处理多个数据分区（例如运行任务、读取或者存储数据）。

总结

弹性分布式数据集(RDD)是一种高效、通用和容错的抽象，用于在集群应用程序中共享数据。

RDD是Spark的核心，也是整个Spark的架构基础。总结RDD的特点如下：

• 一个不能修改（只读）的数据集，只能通过转换操作生成新的 RDD
• 支持跨集群的分布式数据机构，可以分布在多台机器上进行并行处理
• 将数据存储在内存中，支持多次并行计算对数据的重用
• 支持容错，在RDD分区出现问题时，窄依赖相较于宽依赖不会造成太多的冗余数据

参考借鉴以下论文和博文：

[1] Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing http://people.csail.mit.edu/matei/papers/2012/nsdi_spark.pdf

[2] https://zhuanlan.zhihu.com/p/67068559

[3] http://blog.sciencenet.cn/home.php?mod=space&uid=425672&do=blog&id=520947

[4] http://blog.sciencenet.cn/blog-425672-520961.html

[5] http://blog.sciencenet.cn/blog-425672-520969.html

[6] https://www.jianshu.com/p/8db27aedfba2

[7] https://book.itheima.net/course/1269935677353533441/1270998166728089602/1271000049186250754