Spark经典论文合集_spark论文资源-CSDN文库

共11个文件

pdf：11个

Spark,云计算

5星 · 超过95%的资源需积分: 49 44 浏览量 2016-09-07 07:20:33 上传评论 10 收藏 17.99MB ZIP 举报

资源推荐

资源详情

资源评论

收起资源包目录

spark.zip （11个子文件）

spark

Discretized Streams Fault-Tolerant Streaming Computation at Scale.pdf 739KB

Spark SQL Relational Data Processing in Spark.pdf 508KB

Discretized Streams An Efficient and Fault-Tolerant Model for Stream Processing on Large Clusters.pdf 265KB

Shark Fast Data Analysis Using Coarse-grained Distributed Memory.pdf 536KB

Spark Cluster Computing with Working Sets.pdf 205KB

Resilient Distributed Datasets A Fault-Tolerant Abstraction for In-Memory Cluster Computing.pdf 866KB

An Architecture for Fast and General Data Processing on Large Clusters.pdf 2.05MB

Shark SQL and Rich Analytics at Scale.pdf 650KB

GraphX Unifying Data Parallel and Graph Parallel.pdf 502KB

spark.pdf 8.94MB

大型集群上的快速和通用数据处理架构.pdf 5.53MB

Discretized Streams: An Efﬁcient and Fault-Tolerant Model for

Stream Processing on Large Clusters

Matei Zaharia, Tathagata Das, Haoyuan Li, Scott Shenker, Ion Stoica

University of California, Berkeley

Abstract

Many important “big data” applications need to process

data arriving in real time. However, current program-

ming models for distributed stream processing are rel-

atively low-level, often leaving the user to worry about

consistency of state across the system and fault recov-

ery. Furthermore, the models that provide fault recovery

do so in an expensive manner, requiring either hot repli-

cation or long recovery times. We propose a new pro-

gramming model, discretized streams (D-Streams), that

offers a high-level functional programming API, strong

consistency, and efﬁcient fault recovery. D-Streams sup-

port a new recovery mechanism that improves efﬁciency

over the traditional replication and upstream backup so-

lutions in streaming databases: parallel recovery of lost

state across the cluster. We have prototyped D-Streams in

an extension to the Spark cluster computing framework

called Spark Streaming, which lets users seamlessly in-

termix streaming, batch and interactive queries.

1 Introduction

Much of “big data” is received in real time, and is most

valuable at its time of arrival. For example, a social net-

work may want to identify trending conversation topics

within minutes, an ad provider may want to train a model

of which users click a new ad, and a service operator may

want to mine log ﬁles to detect failures within seconds.

To handle the volumes of data and computation they

involve, these applications need to be distributed over

clusters. However, despite substantial work on clus-

ter programming models for batch computation [6, 22],

there are few similarly high-level tools for stream pro-

cessing. Most current distributed stream processing sys-

tems, including Yahoo!’s S4 [19], Twitter’s Storm [21],

and streaming databases [2, 3, 4], are based on a record-

at-a-time processing model, where nodes receive each

record, update internal state, and send out new records

in response. This model raises several challenges in a

large-scale cloud environment:

• Fault tolerance: Record-at-a-time systems provide

recovery through either replication, where there are

two copies of each processing node, or upstream

backup, where nodes buffer sent messages and re-

play them to a second copy of a failed downstream

node. Neither approach is attractive in large clusters:

replication needs 2× the hardware and may not work

if two nodes fail, while upstream backup takes a long

time to recover, as the entire system must wait for the

standby node to recover the failed node’s state.

• Consistency: Depending on the system, it can be

hard to reason about the global state, because dif-

ferent nodes may be processing data that arrived at

different times. For example, suppose that a system

counts page views from male users on one node and

from females on another. If one of these nodes is

backlogged, the ratio of their counters will be wrong.

• Uniﬁcation with batch processing: Because the in-

terface of streaming systems is event-driven, it is

quite different from the APIs of batch systems, so

users have to write two versions of each analytics

task. In addition, it is difﬁcult to combine streaming

data with historical data, e.g., join a stream of events

against historical data to make a decision.

In this work, we present a new programming model,

discretized streams (D-Streams), that overcomes these

challenges. The key idea behind D-Streams is to treat a

streaming computation as a series of deterministic batch

computations on small time intervals. For example, we

might place the data received each second into a new in-

terval, and run a MapReduce operation on each interval

to compute a count. Similarly, we can perform a running

count over several intervals by adding the new counts

from each interval to the old result. Two immediate ad-

vantages of the D-Stream model are that consistency is

well-deﬁned (each record is processed atomically with

the interval in which it arrives), and that the processing

model is easy to unify with batch systems. In addition, as

we shall show, we can use similar recovery mechanisms

to batch systems, albeit at a much smaller timescale, to

mitigate failures more efﬁciently than existing streaming

systems, i.e., recover data faster at a lower cost.

There are two key challenges in realizing the D-

Stream model. The ﬁrst is making the latency (interval

granularity) low. Traditional batch systems like Hadoop

and Dryad fall short here because they keep state on

disk between jobs and take tens of seconds to run each

job. Instead, to meet a target latency of several seconds,

we keep intermediate state in memory. However, sim-

ply putting the state into a general-purpose in-memory

storage system, such as a key-value store [17], would be

expensive due to the cost of data replication. Instead,

we build on Resilient Distributed Datasets (RDDs) [23],

a storage abstraction that can rebuild lost data without

replication by tracking the operations needed to recom-

pute it. Along with a fast execution engine (Spark [23])

that supports tasks as small as 100 ms, we show that

we can achieve latencies as low as a second. We be-

lieve that this is sufﬁcient for many real-world big data

applications, where the timescale of events monitored

(e.g., trends in a social network) is much higher.

The second challenge is recovering quickly from fail-

ures. Here, we use the deterministic nature of the batch

operations in each interval to provide a new recovery

mechanism that has not been present in previous stream-

ing systems: parallel recovery of a lost node’s state.

Each node in the cluster works to recompute part of the

lost node’s RDDs, resulting in faster recovery than up-

stream backup without the cost of replication. Paral-

lel recovery was hard to implement in record-at-a-time

systems due to the complex state maintenance protocols

needed even for basic replication (e.g., Flux [20]),

but is

simple with the deterministic model of D-Streams.

We have prototyped D-Streams in Spark Streaming,

an extension to the Spark cluster computing engine [23].

In addition to enabling low-latency stream processing,

Spark Streaming interoperates cleanly with Spark’s batch

and interactive processing features, letting users run ad-

hoc queries on arriving streams or mix streaming and his-

torical data from the same high-level API.

2 Discretized Streams (D-Streams)

The key idea behind our model is to treat streaming com-

putations as a series of deterministic batch computations

on small time intervals. The input data received during

each interval is stored reliably across the cluster to form

an input dataset for that interval. Once the time inter-

val completes, this dataset is processed via deterministic

parallel operations, such as map, reduce and groupBy,

to produce new datasets representing program outputs or

intermediate state. We store these results in resilient dis-

tributed datasets (RDDs) [23], an efﬁcient storage ab-

straction that avoids replication by using lineage for fault

recovery, as we shall explain later.

A discretized stream or D-Stream groups together a

series of RDDs and lets the user manipulate them to

through various operators. D-Streams provide both state-

less operators, such as map, which act independently on

each time interval, and stateful operators, such as aggre-

The one parallel recovery algorithm we are aware of, by Hwang et

al. [11], only tolerates one node failure and cannot mitigate stragglers.

t = 1:

t = 2:

pageViews ones counts

map reduce

. . .

Figure 1: Lineage graph for the RDDs in the view count pro-

gram. Each oblong shows an RDD, whose partitions are drawn

as circles. Lineage is tracked at the granularity of partitions.

gation over a sliding window, which operate on multiple

intervals and may produce intermediate RDDs as state.

We illustrate the idea with a Spark Streaming program

that computes a running count of page view events by

URL. Spark Streaming provides a language-integrated

API similar to DryadLINQ [22] in the Scala language.

The code for the view count program is:

pageViews = readStream("http://...", "1s")

ones = pageViews.map(event => (event.url, 1))

counts = ones.runningReduce((a, b) => a + b)

This code creates a D-Stream called pageViews by

reading an event stream over HTTP, and groups it into

1-second intervals. It then transforms the event stream to

get a D-Stream of (URL, 1) pairs called ones, and per-

forms a running count of these using the runningReduce

operator. The arguments to map and runningReduce are

Scala syntax for a closure (function literal).

Finally, to recover from failures, both D-Streams and

RDDs track their lineage, that is, the set of deterministic

operations used to build them. We track this information

as a dependency graph, similar to Figure 1. When a node

fails, we recompute the RDD partitions that were on it by

rerunning the map, reduce, etc. operations used to build

them on the data still in the cluster. The system also peri-

odically checkpoints state RDDs (e.g., by replicating ev-

ery ﬁfth RDD) to prevent inﬁnite recomputation, but this

does not need to happen for all data, because recovery is

often fast: the lost partitions can be recomputed in par-

allel on separate nodes, as we shall discuss in Section 3.

D-Stream Operators D-Streams provide two types of

operators to let users build streaming programs:

• Transformation operators, which produce a new D-

Stream from one or more parent streams. These can

be either stateless (i.e., act independently on each in-

terval) or stateful (share data across intervals).

• Output operators, which let the program write data to

external systems (e.g., save each RDD to HDFS).

D-Streams support the same stateless transformations

available in typical batch frameworks [6, 22], including

map, reduce, groupBy, and join. We reused all of the op-

words interval

counts

sliding

counts

t-1

t+1

t+2

t+3

t+4

(a) Na

ıve evaluation

words interval

counts

sliding

counts

t-1

t+1

t+2

t+3

t+4

–

(b) Incremental evaluation

Figure 2: Comparing the na

ıve variant of reduceByWindow (a)

with the incremental variant for invertible functions (b). Both

versions compute a per-interval count only once, but the second

avoids re-summing each window. Boxes denote RDDs, while

arrows show the operations used to compute window [t, t + 5).

erators in Spark [23]. For example, a program could run

a canonical MapReduce word count on each time interval

of a D-Stream of sentences using the following code:

words = sentences.flatMap(s => s.split(" "))

pairs = words.map(w => (w, 1))

counts = pairs.reduceByKey((a, b) => a + b)

In addition, D-Streams introduce new stateful opera-

tors that work over multiple intervals. These include:

• Windowing: The window operator groups all of the

records from a range of past time intervals into a

single RDD. For example, in our earlier code, call-

ing pairs.window("5s").reduceByKey(_+_) yields

a D-Stream of word counts on intervals [0, 5), [1, 6),

[2, 7), etc. Window is the most general stateful oper-

ator, but it is also often inefﬁcient, as it repeats work.

• Incremental aggregation: For the common use case

of computing an aggregate value, such as a count or

sum, over a sliding window, D-Streams have several

variants of a reduceByWindow operator. The simplest

one only takes an associative “merge” operation for

combining values. For example, one might write:

pairs.reduceByWindow("5s", (a, b) => a + b)

This computes a per-interval count for each time in-

terval only once, but has to add the counts for the past

ﬁve seconds repeatedly, as in Figure 2a. A more efﬁ-

cient version for invertible aggregation functions also

takes a function for “subtracting” values and updates

state incrementally (Figure 2b).

• Time-skewed joins: Users can join a stream against

its own RDDs from some time in the past to compute

trends—for example, how current page view counts

compare to page views ﬁve minutes ago.

Finally, the user calls output operators to transfer re-

sults out of D-Streams into external systems (e.g., for dis-

play on a dashboard). We provide two such operators:

save, which writes each RDD in a D-Stream to a stor-

age system,

and foreach, which runs a user code snippet

(any Spark code) on each RDD in a stream. For example,

a user can print the counts computed above with:

counts.foreach(rdd => println(rdd.collect()))

Uniﬁcation with Batch and Interactive Processing

Because D-Streams follow the same processing model

as batch systems, the two can naturally be combined.

Spark Streaming provides several powerful features to

unify streaming and batch processing.

First, D-Streams can be combined with static RDDs

computed, for example, by loading a ﬁle. For example,

one might join a stream of incoming tweets against a pre-

computed spam ﬁlter, or compare it with historical data.

Second, users can run a D-Stream program as a batch

job on previous historical data. This makes it easy com-

pute a new streaming report on past data as well.

Third, users can attach a Scala console to a Spark

Streaming program to run ad-hoc queries on D-Streams

interactively, using Spark’s existing fast interactive

query capability [23]. For example, the user could query

the most popular words in a time range by typing:

counts.slice("21:00", "21:05").topK(10)

The ability to quickly query any state in the system is

invaluable for users troubleshooting issues in real time.

3 Fault Recovery

Classical streaming systems update mutable state on a

per-record basis and use either replication or upstream

backup for fault recovery [12].

The replication approach creates two or more copies

of each process in the data ﬂow graph [2, 20]. Support-

ing one node failure therefore doubles the hardware cost.

Furthermore, if two nodes in the same replica fail, the

system is not recoverable. For these reasons, replication

is not cost-effective in our large-scale cloud setting.

In upstream backup [12], each upstream node buffers

the data sent to downstream nodes locally until it gets an

acknowledgement that all related computations are done.

When a node fails, the upstream node retransmits all un-

acknowledged data to a standby node, which takes over

the role of the failed node and reprocesses the data. The

disadvantage of this approach is long recovery times, as

the system must wait for the standby node to catch up.

To address these issues, D-Streams employ a new

approach: parallel recovery. The system periodically

checkpoints some of the state RDDs, by asynchronously

replicating them to other nodes. For example, in a view

count program computing hourly windows, the system

We can use any storage system supported by Hadoop, e.g., HDFS

or HBase, by calling into Hadoop’s I/O interfaces to these systems.

0.5

1.5

2.5

0 0.2 0.4 0.6 0.8 1

Recovery time(min)

System Load (Before Failure)

Upstream Backup

Parallel Recovery N = 5

Parallel Recovery N = 10

Parallel Recovery N = 20

Figure 3: Recovery time for parallel recovery vs. upstream

backup on N nodes, as a function of the load before a failure.

could checkpoint results every minute. When a node

fails, the system detects the missing RDD partitions and

launches tasks to recover them from latest checkpoint.

Many ﬁne-grained tasks can be launched at the same

time to compute different RDD partitions on different

nodes. Thus, parallel recovery ﬁnishes faster than up-

stream backup, at a much lower cost than replication.

To show the beneﬁt of this approach, we present re-

sults from a simple analytical model in Figure 3. The

model assumes that the system is recovering from a

minute-old checkpoint and that the bottleneck resource

in the recovery process is CPU. In the upstream backup

line, a single idle machine performs all of the recov-

ery and then starts processing new records. It takes a

long time to catch up at high system loads because new

records for it continue to accumulate while it is rebuild-

ing old state.

In the other lines, all of the machines

partake in recovery, while also processing new records.

With more nodes, parallel recovery catches up with the

arriving stream much faster than upstream backup.

One reason why parallel recovery was hard to perform

in previous streaming systems is that they process data

on a per-record basis, which requires complex and costly

bookkeeping protocols (e.g., Flux [20]) even for basic

replication. In contrast, D-Streams apply deterministic

transformations at the much coarser granularity of RDD

partitions, which leads to far lighter bookkeeping and

simple recovery similar to batch data ﬂow systems [6].

Finally, beside node failures, another important con-

cern in large clusters is stragglers [6]. Fortunately, D-

Streams can also recover from stragglers in the same

way as batch frameworks like MapReduce, by execut-

ing speculative backup copies of slow tasks. This type of

speculation would again be difﬁcult in a record-at-a-time

system, but becomes simple with deterministic tasks.

For example, when the load is 0.5, the standby node ﬁrst has to

spend 0.5 minutes to recompute the 1 minute of state lost since the

checkpoint, then 0.25 minutes to process the data that arrived in those

0.5 minutes, then 0.125 minutes to process the data in this time, etc.

Note that when the system’s load before failure is high enough, it

can never recover because the load exceeds the available resources.

0.5

1.5

2.5

0 20 40 60

Cluster Throughput (GB/s)

# of Nodes in Cluster

Grep

1 sec

2 sec

0.5

1.5

2.5

0 20 40 60

Cluster Throughput (GB/s)

# of Nodes in Cluster

WordCount

1 sec

2 sec

Figure 4: Performance of Grep and sliding WordCount on dif-

ferent cluster sizes. We show the maximum throughput attain-

able under an end-to-end latency below 1 second or 2 seconds.

4 Results

We implemented a prototype of Spark Streaming that ex-

tends the existing Spark runtime and can receive streams

of data either from the network or from ﬁles periodically

uploaded to HDFS. We brieﬂy evaluated its scalability

and fault recovery using experiments on Amazon EC2.

We used nodes with 4 cores and 15 GB RAM.

Scalability We evaluated the scalability of the sys-

tem through two applications: Grep, which counts in-

put records matching a pattern, and WordCount, which

performs a sliding window word count over 10 second

windows. For both applications, we measured the max-

imum throughput achievable on different-sized clusters

with an end-to-end latency target of either 1 or 2 seconds.

By end-to-end latency, we mean the total time between

when a record enters the system and when it appears in

a result, including the time it waits for its batch to start.

We used a batching interval of 0.5s and 100-byte records.

Figure 4 plots the results. We see that the system can

process roughly 40 MB/second/node (400K records/s/n-

ode) for Grep and 20 MB/s/node (200K records/s/node)

for WordCount at sub-second latency, as well as slightly

more data if we allow 2s of latency. The system also

scales nearly linearly to 50 nodes. The scaling is not per-

fect because there are more stragglers with more nodes.

Parallel Recovery We evaluated parallel fault recov-

ery using two applications, both of which received 10

MB/s of data per node on 10 nodes, and used 2-second

batching intervals. The ﬁrst application, MaxCount, per-

formed a word count in each 2-second interval, and com-

puted the maximum count for each word over the past 30

seconds using a sliding window. Because max is not an

invertible operation, we used the na

ıve reduceByWindow

that recomputes every 2s. We ran this application both

without any checkpointing (except for replication of the

input data). Each interval took 1.66s to process be-

fore the failure, whereas the average processing time of

the interval during which a failure happened was 2.64s

Failure Happens

0.0

0.5

1.0

1.5

2.0

0 15 30 45 60 75

Interval Processing

Time (s)

Figure 5: Processing time of intervals during one run of the

WordCount job. After a failure, the jobs for the next 30s (shown

in red) can take slightly longer than average because they may

need to recompute the local counts from 30s ago.

(std.dev. 0.19s). Even though results dating back 30 sec-

onds had to be recomputed, this was done in parallel,

costing only one extra second of latency.

The second application performed a sliding word

count with a 30s window using the the incremen-

tal reduceByWindow operator, and checkpointed data

every 30s. Here, a failure-free interval took 1.47s,

while an interval with a failure took on average 2.31s

(std.dev. 0.43s). Recovery was faster than with Max-

Count because each interval’s output only depends on

three previous RDDs (the total count for the previous in-

terval, the local count for the current interval, and the

local count for 30 seconds ago). However, one interest-

ing effect was that any interval within the next 30s after

a failure could exhibit a slowdown, because it might dis-

cover that part of the local counts for the interval 30s

before it were lost. Figure 5 shows an example of this,

where the interval at 30s, when the failure occurs, takes

2.26s to recover, but the intervals at times 32, 34, 46 and

48 also take slightly longer. We plan to eagerly recom-

pute lost RDDs from the past to mitigate this.

5 Related Work

The seminal academic work on stream processing was in

streaming databases such as Aurora, Borealis, Telegraph,

and STREAM [4, 2, 3, 1]. These systems provide a SQL

interface and achieve fault recovery through either repli-

cation (an active or passive standby for each node [2, 13])

or upstream backup [12]. We make two contributions

over these systems. First, we provide a general program-

ming interface, similar to DryadLINQ [22], instead of

just SQL. Second, we provide a more efﬁcient recovery

mechanism: parallel recomputation of lost state. Parallel

recovery is feasible due to the deterministic nature of D-

Streams, which lets us recompute lost partitions on other

nodes. In contrast, streaming DBs update mutable state

for each incoming record, and thus require complex pro-

tocols for both replication (e.g., Flux [20]) and upstream

backup [12]. The only parallel recovery protocol we are

aware of, by Hwang et al [11], only tolerates one node

failure, and cannot handle stragglers.

In industry, most stream processing frameworks use a

lower-level message passing interface, where users write

stateful code to process records in a queue. Examples in-

clude S4, Storm, and Flume [19, 21, 7]. These systems

generally guarantee at-least-once message delivery, but

unlike D-Streams, they require the user to manually han-

dle state recovery on failures (e.g., by keeping all state in

a replicated database) and consistency across nodes.

Several recent research systems have looked at on-

line processing in clusters. MapReduce Online [5] is a

streaming Hadoop runtime, but cannot compose multiple

MapReduce steps into a query or recover stateful reduce

tasks. iMR [15] is an in-situ MapReduce engine for log

processing, but does not support more general computa-

tion graphs and can lose data on failure. CBP [14] and

Comet [10] provide “bulk incremental processing” by

running MapReduce jobs on new data every few minutes

to update state in a distributed ﬁle system; however, they

incur the high overhead of replicated on-disk storage. In

contrast, D-Streams can keep state in memory without

costly replication, and achieve order of magnitude lower

latencies. Naiad [16] runs computations incrementally,

but does not yet have a cluster implementation or a dis-

cussion of fault tolerance. Percolator [18] performs in-

cremental computations using triggers, but does not offer

consistency guarantees across nodes or high-level opera-

tors like map and join.

Finally, our parallel recovery mechanism is conceptu-

ally similar to recovery techniques in MapReduce, GFS,

and RAMCloud [6, 9, 17], which all leverage repartition-

ing. Our contribution is to show that this mechanism can

be applied on small enough timescales for stream pro-

cessing. In addition, unlike GFS and RAMCloud, we re-

compute lost data instead of having to replicate all data,

avoiding the network and storage cost of replication.

6 Conclusion

We have presented discretized streams (D-Streams), a

stream programming model for large clusters that pro-

vides consistency, efﬁcient fault recovery, and power-

ful integration with batch systems. The key idea is to

treat streaming as a series of short batch jobs, and bring

down the latency of these jobs as much as possible. This

brings many of the beneﬁts of batch processing models

to stream processing, including clear consistency seman-

tics and a new parallel recovery technique that we be-

lieve is the ﬁrst truly cost-efﬁcient recovery technique

for stream processing in large clusters. Our implemen-

tation, Spark Streaming, lets users seamlessly intermix

streaming, batch and interactive queries.

In future work, we plan to use Spark Streaming to

build integrated systems that combine these types of

processing [8], and to further explore the limits of D-

Streams. In particular, we are interested in pushing the

latency even lower (to about 100 ms) and in recovering

from failures faster by providing approximate results.

评论收藏

内容反馈

ychnnnzy

2018-11-13

不错太好了
xuxiaoliang

2018-03-05

好东西，值得阅读，多谢分享
wuwenzhe456

2017-10-14

原版论文，免得自己找，很全了，基本组件都包含
杨鑫newlfe

2017-05-18

很不错，适合耐心读一读
Zonda_HM

2016-09-12

资源很有用，现在国内的资料都是错漏百出，还是看英文原版比较好

前往

页

黑白尤文

粉丝: 5
资源: 10

Spark经典论文合集

spark的论文

Spark论文资料

基于spark的大数据论文资料

spark streaming相关15篇论文，包含几篇硕士论文，包含几篇期刊论，有的结合自然语言处理

spark RDD 论文 中文版

基于Spark的大数据分析工具Hive的研究(毕业论文).caj

【spark论文】大型集群上的快速和通用数据处理架构（修正版）

基于Spark的数据处理分析系统的设计与实现

毕业设计PPT答辩（终期）

Hadoop经典技术书籍合集(Spark, Kafka, HBase, etc.)

spark rdd 论文翻译_中文_spark老汤

spark RDD 论文

spark全面资料合集

Spark RDD 论文原文

spark 奠基者博士论文（中文版）

毕业设计（论文）-基于物联网的智能家居设计

基于SpringBoot+Neo4j+Spark实现的论文智能分析问答系统（采用朴素贝叶斯分类器）.zip

基于SpringBoot+Neo4j+Spark实现的论文智能分析问答系统源码（采用朴素贝叶斯分类器）.zip

论文研究-基于Spark框架的CNM算法并行研究 .pdf

spark并行计算论文集合

一种基于Spark的语义推理引擎实现及应用-浙大硕士论文.pdf

MIT 6.824论文合集.zip

最新资源

spark RDD 论文中文版