英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
Spark-在工作集上进行集群计算
MateiZaharia,MosharafChowdhury,MichaelJ.Franklin,ScottShenker,IonStoica
加利福利亚伯克利大学
摘要
MapReduce以及它的变体已经在集群上成功实现了大规模数据密集型程序。然而，这些系统中的大多数都是建立在非循环数据流模型之上的，而这个模型也许对于其他一些应用而言并不适用。本文关注如下类型的应用：那些期望在并行操作中重复使用数据集的应用。这包括一些迭代机器学习算法，以及交互式数据分析工具。我们建立了一个叫做Spark的框架用于支持这些应用，与此同时框架也保留了MapReduce的可扩展性和容错性的特征。为了达到这个目标，Spark提出了一种叫做弹性分布式数据集（RDD）的抽象概念。RDD是一个只读的分布在集群各个节点上的数据集合，如果有分区失效的话RDD可以被重建。Spark在迭代式的机器学习任务上与Hadoop相比性能提升了10倍，也可以交互式的亚秒级查询39G的数据。
1.简介
一种新的集群计算模型变得流行起来，即在由非可靠主机建立的集群上进行并行数据计算，并自动提供任务调度、故障恢复以及负载均衡。MapReduce倡导了这种模型，而类似Dryad或者Map-Reduce-Merge的系统推广了对于这种类型的数据流的支持。这些系统提供给用户一种编程模型，即创建非循环数据流图并将数据传输给一组计算节点，并实现了可扩展和自动故障恢复。这允许底层系统管理任务调度以及进行故障恢复，而无需用户的参与。
虽然这种数据流编程模型对于大多数应用而言是非常有效的，但也有一些应用是无法使用非循环数据流高效的实现的。本文，我们关注如下类型的应用：希望在并行操作中重复使用数据集的应用。下面有两个例子，即Hadoop用户指出的MapReduce效率不高的例子：
迭代任务：许多机器学习算法在同一份数据集上迭代式的进行计算，用于进行参数调优（如：梯度下降）。虽然每一轮迭代可以被表达为一个MapReduce任务，但是每一个任务都需要从硬盘上重新加载数据，造成了明显的性能影响。
交互分析：Hadoop经常被用于在大的数据集上进行专门的查询分析，使用一些SQL接口如Pig或者Hive。理想状态下，用户应该将数据集加载到内存中，并且进行反复的查询。然而，使用Hadoop，查询会有明显的延迟（数十秒）因为它们作为独立的MapReduce任务执行，并从硬盘上加载数据。
本文提出了一种新型集群计算模型叫做Spark，支持上述工作集应用，并提供与MapReduce相同的可扩展性和容错性。
Spark中最主要的抽象叫做弹性分布式数据集（RDD），代表了分区分布在一系列机器节点上的对象集合，如果一个分区丢失了可以被重建。用户可以跨节点的缓存RDD到内存里，并且在多个类似于MapReduce的并行操作中复用它。RDD通过血统（lineage）这个概念实现容错性：如果RDD中的一个分区丢失了，RDD是知道它自己是如何从其他RDD转变而来的，所以有能力重新生成这个分区。虽然RDD并不是一个一般的共享内存的概念，但是它们在表达能力这方面，与可扩展性以及健壮性上这方面上，取得了一个最佳的平衡。并且我们发现RDD适用于各种应用程序。
Spark是用scala实现的，这是一种运行在Java虚拟机里的静态类型的高级语言，它和DryadLINQ一样有函数式编程的接口。另外Spark可以使用一种修改过的Scala解释器交互式的进行使用，它可以允许用户定义RDD、方法、变量和类，并且在一个集群中并行的操作它们。我们相信Spark是第一个支持用这种高效、多用途的编程语言交互式的访问集群当中的大量数据集的系统。
本文组织结构如下。第二节介绍了Spark的编程模型以及RDD。第三节展示一些示例任务。第四节介绍我们的实现方式，包括集成Scala语言以及它的解释器。第五小节展示最近的结果。我们在第六小节介绍相关的一些工作，并且通过第七小节的讨论结束全文。
2.编程模型
为了使用Spark，开发者需要编写driver程序，实现应用程序高级控制流以及启动各种并行操作。Spark提供了两种主要的并行编程的概念：弹性分布式数据集，以及在这些数据集上的并发操作（通过应用在这些数据集上的方法调用触发）。另外，Spark还提供两种限制类型的共享变量，可以被运行在集群上的方法使用，这个我们稍后解释。
2.1弹性分布式数据集
弹性分布式数据集（RDD）是一种只读的分区分布在多个节点上的，当有分区失效时可以被重建的对象集合。RDD中的元素并不需要实际的被存储起来，取而代之的是，RDD拥有足够的如何从初始数据中计算出来自己的信息。这就意味着，当有节点失效时，RDD是可以被重建的。
在Spark中，每个RDD都用一个Scala对象表示，开发者可以使用如下4种途径创建RDD：
通过共享文件系统中的文件创建，例如Hadoop分布式文件系统（HDFS）
通过“parallelizing”一个Scala集合（例如：数组），在driver程序里，表示将数据划分成多份并且将它们发送给多个节点
通过一个已存在的RDD转化。一个元素是类型A的数据集，可以通过一个叫做flatMap的操作，转化为元素是类型B的数据集，即将每一个元素通过一个用户定义的方法typeA=gt;List[B]。其他的转换也可以通过flatMap进行表达，包括map（让元素通过一个方法typeA=gt;B）和filter(挑选符合预期的元素)。
通过改变一个已存在RDD的持久化方式。默认情况下，RDD是懒加载的并且存活期是短暂的。换而言之，数据集当中的分区只有当RDD被并行操作使用时才会真正实例化，使用完毕后内存就会被释放。但是，用户可以使用以下两种操作修改RDD的持久化方式：
--数据集的cache操作是懒加载的，但是在第一次操作触发计算时RDD就会被保存到内存中，因为它将会被复用
--save操作会对数据集进行求值并且将它写到分布式文件系统里例如HDFS。save的版本可以在后序的操作中使用。
需要指明的是cache操作仅仅是一个暗示：如果集群中并没有足够的内存来保存数据集的每个分区，Spark将会在未能保存到内存里的分区被使用时重新将它们计算出来。我们这样设计，是为了让Spark能够在节点失效或者数据集过大的情况下，仍然可以正常工作。
我们还计划扩展Spark，使它能够支持其他层级的持久化（如，内存中的分区在多个其他节点中保存副本）。我们的目标是让用户可以在RDD存储代价、访问速度、丢失分区的概率、以及重新计算RDD的代价中进行权衡。
2.2并行操作
RDD支持多种并行操作。
reduce:使用方法将数据集中的元素结合在一起，然后返回结果给driver程序
collect:将数据集中的所有元素返回给driver程序。例如，最简单的并行更新一个数组的方法就是，先parallelize，然后再map，最后再collect这个数组
foreach:让数据集中的所有元素经过一个用户定义的方法。这只是一个有副作用的方法（也许会将数据复制到另一个系统，或者更新后面要说的共享变量）
我们需要指出当前Spark只支持一个在MapReduce里进行groupreduce的操作；reduce结果仅由单进程收集（driver）。我们计划在未来的版本里，使用“shuffle”操作来支持分布式数据集上的groupreduce，这部分将在第7节里进行描述。然而，就算只用一个reducer也足以实现大量有用的算法。例如，一篇最近的关于在多核系统里进行机器学习的论文，使用MapReduce在没有支持并行reduction的情况下实现了10个机器学习相关的算法。
2.3共享变量
开发者调用map、filter、reduce方法，会传递闭包（方法）给Spark。在函数式编程中，闭包会在创建时引用变量。当Spark在工作节点运行闭包时，这些变量会被复制到工作节点。
然而，Spark也允许开发者创建指定类型的两种共享变量，它们虽然简单但也很有用：
广播变量：如果一大份只读的数据（例如：查找表）被多个并行操作使用，那么它如果只复制给每个工作节点一次，比每次都复制给每个闭包要更好。Spark允许用户创建“广播变量”，它就只会复制给每个工作节点一次
累加器：这是一种开发者可以在方法当中进行累加的变量。它们可以被用作实现MapReduce的计数器，以及实现并行程序求和。累加器可以被定义为任何可以“加”并且有“零值”的类型。由于累加器只能进行累加，所以也是很容易实现容错性的。
3.示例
我们下面来展示一些Spark程序的示例。请注意我们省略了类型，因为Scala支持类型推断。
3.1文本搜索
假设我们想要检索一个存储在HDFS上的大的日志文件中包含“error”的行数。可以从一个文件类型的数据集开始如下实现：
我们首先创建一个叫做file的分布式数据集，它代表了HDFS文件中的行的集合。我们转换这个数据集得到一个包含“ERROR”的行的集合，并且map每一行为1，然后再通过reduce操作进行求和。filter、map、reduce方法的参数都是Scala语法。
请注意errs,ones都是懒加载的RDD，它们并未被真正实例化。当reduce方法被调用时，每一个工作节点都用流方式检测ones的输入块，然后添加它们来执行本地的reduce，最后再将本地的count值返回给driver端。在使用懒加载数据集这方面，Spark模仿了MapReduce。
Spark与其他一些框架不同之处在于，它可以跨操作的持久化中间数据集。例如，如果想要复用errs数据集，我们可以如下所示创建一个缓存的RDD:
我们现在可以在cachedErrs数据集上进行并行操作或由它转换出新的数据集，但是工作节点在第一次计算之后就会在内存中缓存这个数据集的所有分区，这样就可以极大的加快后序的操作。
3.2逻辑回归
接下来的程序实现逻辑回归算法，这是一个迭代式的分类算法，想要找到一个超平面w来很好的将点集划分成两个部分。这个算法使用梯度下降：即先用一个随机值初始化w，然后在每轮迭代中，用w带入方法进行求和并不断的修正w。因此在迭代中将数据缓存在内存中对于算法非常有利。我们并不解释逻辑回归的细节，而是用它来展示Spark的新的特性：
首先我们创建了一个叫做points的RDD，然后再使用一个for循环。for是Scala中的关键字，触发对一个集合的遍历操作并且有一个循环体闭包。即，代码for(plt;-points){body}与代码points.foreach(p=gt;{body})是等价的。因此，我们就触发了Spark的并行foreach操作。
其次，为了对于梯度进行求和，我们使用了一个叫做gradient的累加器（值是Vector类型）。注意，在循环中使用一个重载的 =方法对于gradient进行累加。循环与累加器的结合使得Spark程序与普通的串行程序看起来相同。事实上，这个例子与逻辑回归普通串行版本的不同之处只有3行。
3.3交替最小平方
我们最后的例子是一个叫做交替最小平方的算法（ALS）。ALS主要是为了解决协同过滤问题，比如根据用户历史的电影评级，来预测他们对于还未看过的电影的评级（类似于Netflix的挑战）。与前面的示例不同，ALS是CPU密集型的，而非数据密集型的。
我们简要概括下ALS算法，如果读者想要了解细节请看附录后面的文章。假设我们想要预测u个用户对于m个电影的评分，并且我们有一个部分填充的已知评级的用户电影对的矩阵R。ALS的模型R，是由两个矩阵M和U构成，它们的维度分别为m*k以及k*u。即，每个用户和每个电影都有个k维的特征向量来描述他们的特征。一个用户对于一个电影的评级是它的特征向量与电影的特征向量的点积。ALS使用已知的评级得到M和U，然后用M和U的叉积来预测未知电影的评级。以下是迭代步骤：
1.使用随机值来初始化M
2.优化U让M与R之间的误差最小
3.优化M让U与R之间的误差最小
4.重复2和3步骤直至算法收敛
ALS的步骤2和3可以在每个节点上并行的更新不同的用户/电影。然而，因为所有的步骤都要使用R，所以让R是一个广播变量是非常有帮助的，这样就不会在每一步中都将它重复的发送给计算节点。ALS的算法在Spark当中的实现如下所示。注意我们parallelize了集合0untilu(一个Scala的范围对象）并且collect它来更新每一个数组：
4.实现
Spark在Mesos之上构建，这是一个集群操作系统，允许并行程序细粒度的共享集群，并且提供了API让程序能够在集群上运行
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[441128]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
