Spark的速度快是以丧失计算结果正确性为代价的

标签: spark 速度 计算 | 发表时间:2015-06-05 10:51 | 作者:changming
出处:http://www.sunchangming.com/blog/

是的,Spark很快。但是它不保证它算出的值是对的,哪怕你要做的只是简单的整数累加。

Spark最著名的一篇论文是:《Spark: Cluster Computing with Working Sets》。当你读它的时候你需要明白:文中代码不保证计算结果是正确的。具体来说,它的Logistic Regression的代码在map阶段用到了accumulator。下面解释为什么这么做是错误的。

假设有这样一个简单的任务:

input file的每一行是100个整数,要求竖着加下来

例如:

输入

1 2 3 4 5 ... 100
1 2 3 4 5 ... 200
1 3 3 4 5 ... 100

输出

3 7 9 12 15 ... 400

很简单,对吧?是个猪都会算。 在hadoop上这个问题可以通过Map reduce来解决。首先把输入文件分成N个大小相等的块。然后每个块输出一行100个整数,如 2 4 6 8 10 ... 200
然后reducer接收每个mapper的输出结果,累加起来得到最终结果。

缺点是: 从mapper到reducer是需要DISK-IO及网络传输的。那么需要传输N*100个整数。当输入集的维数很大(每行有上百万个字节)的时候,很浪费。

spark很巧妙的引入了accumulator的概念。同一台机器上所有的task的输出,会先在这个机器上进行本地汇总,然后再发给reducer。这样就不再是task数量*维数,而是机器数量*维数。会节省不少。具体来说,在做机器学习的时候,大家很习惯的用accumulator来做这样的计算。

accumulator是被很careful设计的。比如,只有master节点能读取accumulator的值,worker节点不能。在“Performance and Scalability of Broadcast in Spark
”一文中,作者写到:“Accumulators can be defined for any type that has an “add” operation and a “zero” value. Due to their “add-only” semantics, they are easy to make fault-tolerant.” 。但真的是这样吗?并不是。

accumulator如果不是运行在运算的最后一环,那么正确性无法保证。因为accumulator不是map/reduce函数的输入或输出,accumulator是表达式求值中的side-effect。举个例子:

  val acc = sc.accumulator(0)  
data.map(x => acc += 1; f(x))  
data.count()  
// acc should equal data.count() here
data.foreach{...}  
// Now, acc = 2 * data.count() because the map() was recomputed.

这个问题被spark的创始人Matei标为Won't Fix。

那么是不是写代码小心点不要触发重复计算就行了呢?也不是。task是有可能fail-retry的,再或者因为某一个task执行的慢,所以同时有它的多个副本在跑。这些都可能会导致accumulator结果不正确。 Accumulators只能用在RDD的actions中,不能用在Transformations。举例来说:可以在reduce函数中用,但是不能在map函数中用。

如果不用accumlators,但又想节省网络传输,那么Matei说:“I would suggest creating fewer tasks. If your input file has a lot of blocks and hence a lot of parallel tasks, you can use CoalescedRDD to create an RDD with fewer blocks from it. ”

意思就是说,那你就把task划分大一点,把task的数量减少。比如每台机器只有1个task。 Downside其实也很明显,任务的执行容易不balance。

参考: https://issues.apache.org/jira/browse/SPARK-732
https://issues.apache.org/jira/browse/SPARK-3628
https://issues.apache.org/jira/browse/SPARK-5490

https://github.com/apache/spark/pull/228

相关 [spark 速度 计算] 推荐:

Spark的速度快是以丧失计算结果正确性为代价的

- - Changming
但是它不保证它算出的值是对的,哪怕你要做的只是简单的整数累加. Spark最著名的一篇论文是:《Spark: Cluster Computing with Working Sets》. 当你读它的时候你需要明白:文中代码不保证计算结果是正确的. 具体来说,它的Logistic Regression的代码在map阶段用到了accumulator.

LSH Spark 千万级用户/Item 相似度计算 cosine-lsh-join-spark: Approximate Nearest Neighbors in Spark

- -
This family of algorithms are very fast but might not give the exact solution and are hence called approximate nearest neighbours (ANN). This is an interface to find the k nearest neighbors from a data set for every other object in the same data set.

Spark:一个高效的分布式计算系统

- - IT技术博客大学习
标签:   Spark   分布式. Spark与Hadoop的对比. Spark的中间数据放到内存中,对于迭代运算效率更高. Spark更适合于迭代运算比较多的ML和DM运算. 因为在Spark里面,有RDD的抽象概念. Spark比Hadoop更通用. Spark提供的数据集操作类型有很多种,不像Hadoop只提供了Map和Reduce两种操作.

分布式计算框架-Spark初步理解

- - 互联网 - ITeye博客
    最开始关注Spark,是在csdn首页上看到一篇文件《Spark核心开发者:性能超Hadoop百倍,算法实现仅有其1/10或1/100》的,看着标题确实感觉比较年逼的. 后来稍微研究了一下,其实发现,这个描述有点问题. Spark是一个基于内存的纯计算框架,而hadoop是包括计算框架的mapreduce和分布式存储hdfs,所以应该描述为Spark性能超Hadoop的mapreduce计算性能百倍.

分布式计算系统 Spark 成为 Apache 顶级项目

- - 博客园_新闻
Apache 软件基金会今天宣布,Spark 项目已从孵化器毕业,成为 Apache 软件基金会的一个顶级项目. Spark 是一个高效的分布式计算系统,发源于美国加州大学伯克利分校 AMPLab 的集群计算平台. Spark 被称为“Hadoop 的瑞士军刀”,拥有非凡的速度和易用性. Spark 立足于内存计算,相比 Hadoop MapReduce,Spark 在性能上要高 100 倍,而且 Spark 提供了比 Hadoop 更上层的 API,同样的算法在 Spark 中实现往往只有 Hadoop 的1/10 或者1/100 的长度.

Spark:比Hadoop更强大的分布式数据计算项目

- - 标点符
Spark是一个由加州大学伯克利分校(UC Berkeley AMP)开发的一个分布式数据快速分析项目. 它的核心技术是弹性分布式数据集(Resilient distributed datasets),提供了比Hadoop更加丰富的MapReduce模型,可以快速在内存中对数据集进行多次迭代,来支持复杂的数据挖掘算法和图计算算法.

Kafka+Spark Streaming+Redis实时计算整合实践

- - 简单之美
基于Spark通用计算平台,可以很好地扩展各种计算类型的应用,尤其是Spark提供了内建的计算库支持,像Spark Streaming、Spark SQL、MLlib、GraphX,这些内建库都提供了高级抽象,可以用非常简洁的代码实现复杂的计算逻辑、这也得益于Scala编程语言的简洁性. 这里,我们基于1.3.0版本的Spark搭建了计算平台,实现基于Spark Streaming的实时计算.

实时流计算、Spark Streaming、Kafka、Redis、Exactly-once、实时去重

- - lxw的大数据田地
本文想记录和表达的东西挺多的,一时想不到什么好的标题,所以就用上面的关键字作为标题了. 在实时流式计算中,最重要的是在任何情况下,消息不重复、不丢失,即Exactly-once. 本文以Kafka–>Spark Streaming–>Redis为例,一方面说明一下如何做到Exactly-once,另一方面说明一下我是如何计算实时去重指标的.

【实践】Spark 协同过滤ALS之Item2Item相似度计算优化 - CSDN博客

- -
CF召回优化,自之前第一版自己实现的基于item的协同过滤算法. http://blog.csdn.net/dengxing1234/article/details/76122465,考虑到用户隐型评分的. 稀疏性问题,所以尝试用Spark ml包(非mllib)中的ALS算法的中间产物item的隐性向量,进行进一步item到item的余弦相似度计算.

Spark概览

- - 简单文本
Spark具有先进的DAG执行引擎,支持cyclic data flow和内存计算. 因此,它的运行速度,在内存中是Hadoop MapReduce的100倍,在磁盘中是10倍. 这样的性能指标,真的让人心动啊. Spark的API更为简单,提供了80个High Level的操作,可以很好地支持并行应用.