Part III — Batch processing · Chapter 6

Apache Spark: RDDs, DAG and architecture

~42 min read6 interactive widgets4 plates

In this chapter

  1. Spark history
  2. The four innovations
  3. The RDD and its four properties
  4. Creating RDDs
  5. Transformations and actions
  6. Narrow and wide dependencies
  7. The DAG
  8. Stages and tasks
  9. Application, job, stage, task
  10. Persist and cache
  11. The architecture: driver, cluster manager, executors
  12. Running an application: shells, submits and deployment modes
  13. Test your knowledge

1. Spark history

Chapter 5 ended with a diagnosis: Hadoop MapReduce is slow because every job ends by saving results to HDFS, there is no possibility to keep data in RAM, and the paradigm is strict enough to make iterative and interactive work painful. Spark is the answer that stuck.

Editor’s note

The three original goals explain the whole design. Iterative programs demand that data stay in memory across passes. Interactive querying demands that the same dataset be queried repeatedly without re-reading it. Unifying real time and batch is why the same engine later grows a streaming module (Chapter 10) and a SQL module (Chapter 7). Spark is not a faster MapReduce; it is a different bet about where data lives between operations.

2. The four innovations

The deck lists four innovations, and they are worth stating as a block because each one removes a specific pain from Chapter 5:

InnovationWhat it saysWhich MapReduce pain it removes
The RDD
(Resilient Distributed Dataset)
Essentially a set of data items (of any format) that is automatically distributed. All operations are defined on RDDs. No more separation between Map and Reduce. The strict paradigm: you no longer have to bend every algorithm into two functions.
A rich set of APIs Easily develop pipelines. Depending on the type of operations, the system automatically defines the (map-style or reduce-style) tasks. The execution plan of a job takes the form of a DAG. Complex algorithms no longer mean hand-chaining multiple jobs.
Better usage of RAM Results are saved to disk only when the processing has finished. RDDs can be temporarily cached. The HDFS round-trip between every pair of stages.
Finer control over resource assignment Cores and memory are assigned explicitly. Under-exploited multi-core machines. This is the subject of Chapter 8.
Data processing in MapReduce versus Spark Above, each MapReduce iteration reads from and writes to HDFS. Below, Spark reads the input once and then keeps the working set in memory for all subsequent iterations and queries. MAPREDUCE — every iteration is an HDFS round trip Input iter. 1 iter. 2 ... HDFS read HDFS write + read slow due to data replication and disk I/O — every arrow crosses the disk and the network SPARK — read once, then stay in memory Input one-time processing iter. 1 iter. 2 query 3 result 1 result 2 result 3 10-100x faster than network and disk
Plate 6.1 — The same iterative workload under the two engines. MapReduce pays a full replicated write and a full read between every pair of iterations; Spark pays the read once and then works from memory, which is where the 10-100× figure comes from.

3. The RDD and its four properties

RDDs are immutable distributed collections of objects. Unpack the name:

Then four fundamental characteristics, mostly inherited from pure functional programming:

Immutable = it cannot change. Once created, an RDD cannot be modified. The slides put it as a++ (mutable) versus b = a+1 (immutable).

Pros: parallelization is easy — no race conditions, no need to implement locking; and immutability is what enables laziness and cacheability.
Cons: higher space occupation.

Lazy evaluation = do not compute transformations until you need them. With b = a+1, c = b+2, show c, everything executes at the third line.

Laziness requires immutability and absence of side effects — a side effect is when a function modifies a state or variable outside its scope.

Pros: job optimization and better performance; no need to separately create all RDDs.
Cons: you do not know there is an error until you compute.

Cachability = store it in RAM. Immutability means data can be cached for a long time, and it can be easily recreated on failure. It drastically improves the performance. See section 10 for the storage levels.

Type inference = the type is inferred by the compiler. It is actually a feature of Scala, and it is different from dynamic typing. It is smarter than Hadoop’s MapReduce and allows to anticipate programming errors.

Key idea — the properties are a chain, not a list

Immutability makes laziness safe (nothing can change under you between definition and execution), and laziness is what lets Spark see the whole pipeline before running any of it — which is what makes optimisation possible. Immutability also makes caching safe (a cached partition can never go stale) and resilience cheap (a lost partition can be recomputed from its lineage rather than replicated). Take immutability away and all four collapse.

4. Creating RDDs

RDDs can be created in two ways: by loading an external dataset or by distributing a collection of objects (e.g., a list or set).

From objects

Existing collections of data can be copied to an RDD in order to enable parallel computations. This requires the entire collection in memory on one machine first:

val data = Array(1, 2, 3, 4, 5)
val rddData = sc.parallelize(data)

// the number of partitions can be set manually
sc.parallelize(data, 10)
// a synonym for parallelize is makeRDD
data = [1, 2, 3, 4, 5]
rddData = sc.parallelize(data)

From external datasets

Spark can create RDDs from any storage source supported by Hadoop — local file system, HDFS, Cassandra, HBase, Amazon S3 — and supports text files, SequenceFiles and any other Hadoop InputFormat.

val rddFile = sc.textFile("data.txt")

sc.textFile("/my/directory")        // the first argument can be a directory
sc.textFile("/my/directory/*.gz")   // wildcards are supported

Beyond plain text:

MethodWhat it reads
sc.wholeTextFilesA directory containing multiple small text files, returning each of them as (filename, content) pairs. In contrast, textFile returns one record per line in each file.
sc.sequenceFile[K, V]SequenceFiles, where K and V are the types of key and values in the file; these should be subclasses of Hadoop’s Writable interface, like IntWritable and Text.
sc.hadoopRDDOther Hadoop InputFormats; takes an arbitrary JobConf, an input format class, a key class and a value class.

Files on HDFS are accessed by their URI, hdfs://master:port/path:

val rddCapra = sc.textFile("hdfs:/bigdata/dataset/capra/capra.txt")
val rddDc = sc.textFile("hdfs:/bigdata/dataset/divinacommedia")
val rddWeather = sc.textFile("hdfs:/bigdata/dataset/weather")
Watch out

RDDs are not computed until an action is performed. If something was wrong in the URI — a typo, a missing directory — you would realise it only when firing the action (rdd1.first(), rdd1.count(), rdd1.collect()). This is the practical face of the “you do not know there is an error until you compute” con of lazy evaluation.

The number of partitions

When creating RDDs, one important parameter is the number of partitions to cut the dataset into: Spark runs one task for each partition.

If not specified, Spark sets the number automatically: for objects it is based on the cluster; for external datasets it is one partition for each block (128 MB in HDFS). Note the constraint from the lab: it is not allowed to have fewer partitions than blocks. Chapter 8 turns this into concrete tuning rules.

Complex and key-value RDDs

RDDs are collections of unnamed elements, and elements can be of arbitrary complexity: RDD[String], RDD[(String, String)], RDD[(String, String, String, ...)], RDD[((String, String), String)].

Key-value RDDs are important as they expose dedicated operations — counting up reviews for each product, grouping together data with the same key, and grouping together two different RDDs. They are created from simple RDDs by mapping the original values to a key-value pair:

val rddData = sc.parallelize( Array("A 1", "B 2", "A 3") )

val rddDataKV1 = rddData.map(x => ( x.split(" ")(0), x.split(" ")(1) ) )
// RDD[(String, String)]: the key is the letter, the value is the number

val rddDataKV2 = rddData.zipWithIndex()
// RDD[(String, Integer)]: the original element is associated to a 0-based index

// to define functions over a multi-valued RDD
val rddData2V = rddDataKV1.map( { case (k,v) => (k, v, v) } )
val rddData2V = rddDataKV1.map( x => (x._1, x._2, x._2) )

5. Transformations and actions

RDDs offer two types of operations, and the distinction is the single most important thing in this chapter:

TransformationsActions
What they doConstruct a new RDD from a previous oneCompute a result that is either returned to the driver program or saved to an external storage system (e.g., HDFS)
Examplesmap, flatMap, filter, reduceByKey, groupByKey, join, sortByKeycollect, count, first, take, reduce, saveAsTextFile
When they runNever on their own — they are lazyImmediately, triggering everything upstream

The lab lists them in full. Transformations: map(func), filter(func), flatMap(func), mapPartitions(func), mapPartitionsWithIndex(func), sample(withReplacement, fraction, seed), union(otherDataset), intersection(otherDataset), distinct([numTasks]), groupByKey([numTasks]), reduceByKey(func, [numTasks]), aggregateByKey(zeroValue)(seqOp, combOp, [numTasks]), sortByKey([ascending], [numTasks]), join(otherDataset, [numTasks]), cogroup(otherDataset, [numTasks]), cartesian(otherDataset), pipe(command, [envVars]), coalesce(numPartitions), repartition(numPartitions), repartitionAndSortWithinPartitions(partitioner). Actions: reduce(func), collect(), count(), first(), take(n), takeSample(withReplacement, num, [seed]), takeOrdered(n, [ordering]), saveAsTextFile(path), saveAsSequenceFile(path), saveAsObjectFile(path), countByKey(), foreach(func). Some are available on any RDD, others only on key-value RDDs.

The workhorses

OperationSemanticsExample from the lab
map(func)Return a new RDD formed by passing each element of the source through a functionrddCapra.map( x => x.split(" ") ) — each record becomes an array of words; rddDc.map( x => x.length ) — each record becomes the length of the line
flatMap(func)Similar to map, but each input item can be mapped to 0 or more output items (so func should return a Seq rather than a single item)rddCapra.flatMap( x => x.split(" ") ) — the new RDD contains one record for every word in every line
filter(func)Return a new RDD formed by selecting those elements on which func returns truerddCapraWords.filter( x => x.indexOf("c")==0 ) — keep only words beginning with c
groupByKey()On an RDD of (K,V) pairs, returns (K, Iterable<V>) pairs — creates a list with the values sharing the same keyrddCapraKvLength.groupByKey() — group words by their length
reduceByKey(func)On an RDD of (K,V) pairs, returns (K,V) pairs where the values for each key are aggregated with func. The function should be commutative and associative so it can be computed correctly in parallel, and must be of type (V,V) => VrddCapraKvCount.reduceByKey( (x,y) => x + y ) — count the occurrences of each word
sortByKey([ascending])Returns (K,V) pairs sorted by keys. K must implement OrderedrddCapraKvLength.sortByKey(false) — order words by decreasing length
join(other)On datasets of type (K,V) and (K,W), returns (K,(V,W)) pairs with all pairs of elements for each key. Outer joins via leftOuterJoin, rightOuterJoin, fullOuterJoinrddCapraKvCount.join(rddCapraKvCount2)
For the exam

The commutativity and associativity requirement on reduceByKey is the same requirement as the one for MapReduce combiners in Chapter 4, for the same reason: the function is applied partially on each partition before the shuffle. If your aggregation is an average or an ordered concatenation, reduceByKey is as wrong as a combiner was.

The actions in practice

rddCapraWords.map(x => x.length).reduce((x,y) => x+y)
rddCapraWords.map(x => x.length).reduce(_+_)

val result = rddCapraWords.
  map(x => (x.length,1)).
  reduce((v1,v2) => (v1._1 + v2._1, v1._2 + v2._2))
val avgWordLength = result._1 / result._2

And the writers: saveAsTextFile(path) (Spark calls toString on each element to convert it to a line of text), saveAsSequenceFile(path) (available on RDDs of key-value pairs implementing Hadoop’s Writable; Spark includes conversions for basic types like Int, Double, String), saveAsObjectFile(path) (Java serialization, loadable with SparkContext.objectFile()). Remember: authentication on HDFS is performed by checking the OS user.

Lazy evaluation: nothing happens until it must

Add transformations to the pipeline and watch nothing execute. Then fire an action and watch the whole lineage run at once.

6. Narrow and wide dependencies

Each operation expresses a dependency A→B from an RDD A (input) to an RDD B (output), and there are exactly two kinds. This distinction drives everything the scheduler does.

Narrow dependencyWide dependency
DefinitionThe data from partition ai of A ends up in one partition bj of BThe data from partition ai of A ends up in many (possibly every) partition of B
Examplesmap, filtergroupByKey, reduceByKey
ExecutionAllow for pipelining on one cluster node (more optimized execution)Cannot be pipelined, as they require data shuffling
On failureRequire less partitions to be recomputedRecovery is more expensive: many parent partitions feed each lost child
Narrow versus wide dependencies On the left, each parent partition feeds exactly one child partition, so the chain can be pipelined on one node. On the right, every parent partition feeds every child partition, which requires a shuffle across the network. NARROW — pipelined on one node a1 a2 a3 b1 b2 b3 map, filter no network, and one lost partition costs one recomputation WIDE — requires a shuffle a1 a2 a3 b1 b2 b3 groupByKey, reduceByKey every arrow may cross the network, and this is where a stage must end
Plate 6.2 — The two dependency shapes. Everything the DAG scheduler does follows from this picture: narrow edges are collapsed into a single pipelined stage, and every wide edge becomes a stage boundary, because the child cannot start until every parent partition has produced its share.

Narrow or wide?

Classify each operation. The verdict explains what the answer implies for pipelining, shuffling and failure recovery.

7. The DAG

Based on the user application and on the lineage graphs, Spark computes a logical execution plan in the form of a DAG, which is later transformed into a physical execution plan.

The DAG (Directed Acyclic Graph) is a sequence of computations performed on data:

The acyclicity is not a technicality — it is immutability again, seen from the graph. Since no transformation can modify an existing RDD, no edge can ever point backwards, and a graph with no cycles is a graph you can schedule in one pass and replay deterministically after a failure.

Building the word count DAG

The deck builds it one line at a time. Each line adds exactly one node:

Which yields the chain:

textFile  →  flatMap  →  map  →  reduceByKey  →  saveAsTextFile

8. Stages and tasks

The execution plan is compiled into physical stages, and the rule is exactly one sentence long:

Key idea

Stages’ boundaries are defined by shuffle operations. Operations with narrow dependencies are pipelined as much as possible.

In the word count DAG, textFile, flatMap and map are all narrow, so they collapse into Stage 1; reduceByKey is wide, so it opens Stage 2.

Then the unit of execution: a task is created for each partition in the new RDD. Tasks are scheduled and assigned to the worker nodes based on data locality (the same principle as Chapter 5), and the scheduler can run the same task on multiple nodes in case of stragglers — slow nodes.

The word count DAG compiled into stages and tasks The chain textFile, flatMap, map, reduceByKey is split into two stages at the shuffle boundary; stage 1 runs four tasks, one per input partition, and stage 2 runs three tasks, one per output partition. Stage 1 — narrow, pipelined Stage 2 — after the shuffle textFile flatMap map reduceByKey saveAsText SHUFFLE Task 1 Task 2 Task 3 Task 4 one task per partition of the input RDD Task 5 Task 6 Task 7 one task per partition of the new RDD tasks are assigned by data locality; the scheduler may re-run a task elsewhere to beat a straggler application > job > stage > task
Plate 6.3 — From DAG to execution. The wide edge cuts the plan in two; inside each stage the narrow operations are fused so a record passes through flatMap and map without ever being materialised, and the number of tasks is simply the number of partitions.

9. Application, job, stage, task

Four words, four scopes. Getting them right is worth easy marks:

LevelDefinition from the slides
ApplicationA single instance of SparkContext that stores data processing logic and schedules a series of jobs, sequentially or in parallel.
JobA complete set of transformations on RDD that finishes with an action or data saving, triggered by the driver application.
StageA set of transformations that can be pipelined and executed by a single independent worker.
TaskThe basic unit of scheduling: executes the stage on a single data partition.

The conceptual picture in the deck makes the relationship visible: a chain of transformations builds RDDs lazily; then counts.collect() is one action producing a value, and counts.saveAsTextFile("hdfs://...") is another action producing a second job over the same lineage.

An iterative example: logistic regression

The goal is to find a line separating two sets of points. This is the workload that motivated Spark in the first place:

val data = spark.textFile(...).map(readPoint).cache()
var w = Vector.random(D)

for (i <- 1 to ITERATIONS) {
  val gradient = data
    .map(p => (1 / (1 + exp(-p.y*(w dot p.x))) - 1) * p.y * p.x)
    .reduce(_ + _)
  w -= gradient
}

println("Final w: " + w)
For the exam

Look at .cache() on the first line. Without it, every iteration would recompute textFile(...).map(readPoint) from HDFS, because RDDs are recomputed each time an action is called on them — and reduce is an action, fired once per iteration. One method call is the difference between the top and the bottom half of Plate 6.1.

10. Persist and cache

Spark recomputes an RDD each time an action is called on it. This is especially expensive for iterative algorithms, and the trivial example in the lab is doing a count() and then writing out the same RDD: the whole lineage runs twice.

When you persist an RDD x, each node stores in memory the partitions of x that it computes and reuses them in other actions on x. Three properties to remember:

RDDs can be persisted with persist() or cache(): persist() allows to specify the storage level, while cache() uses MEMORY_ONLY.

Storage levelMeaning
MEMORY_ONLYDefault when using cache()
MEMORY_AND_DISKSpills to disk if there is too much data to fit in memory
MEMORY_ONLY_SER, MEMORY_AND_DISK_SERStore a serialized representation in memory: more efficient, but more CPU-intensive
DISK_ONLYOnly on disk
[storage_level]_2Replicate the data on 2 machines

Which storage level is best? The four rules from the lab:

Which storage level?

Answer three questions about your RDD and get the level the course rules point to.

Watch out

Chapter 8 adds the counterweight to this section in three words: do not cache unless necessary. Cached partitions occupy executor heap that the shuffle machinery also needs, so caching an RDD that is read once buys nothing and can cost a great deal.

11. The architecture: driver, cluster manager, executors

Spark uses a master/slave architecture with one central coordinator, the driver, and many distributed workers, the executors. The driver and each executor are independent Java processes; together they form a Spark application. The architecture is independent of the cluster manager that Spark runs on.

Spark architecture The driver holding the SparkContext requests resources from the cluster manager, which assigns them; the driver then sends tasks and data directly to the executors, which exchange shuffled data between themselves. Driver SparkContext DAG → physical plan schedules tasks, webUI Cluster Manager standalone or YARN Executor Task Task caches RDDs in JVM heap Executor Task Task lives for the whole application resources request resources assignment tasks and data tasks and data data shuffling
Plate 6.4 — The three components. The cluster manager is on the control plane only: it hands out containers and steps aside. Tasks and data flow driver↔executor, and shuffled data flows executor↔executor — the same “master off the data plane” discipline as the HDFS NameNode in Chapter 3.
ComponentResponsibilities
Cluster Manager The component responsible for assigning and managing the cluster’s resources (memory, processor time). It can be either the Spark standalone manager or any other compatible manager (e.g., YARN). Launches executor processes on behalf of the driver.
Executor A process responsible for executing the received tasks. Each Spark application can have (and usually has) multiple executors, and each worker node can host many executors. Typically runs for the entire duration of the application. Stores (caches) RDD data in JVM heap. Tasks are the smallest unit of work and are carried out by executors.
Driver Program Each Spark application can only have one driver (the entry point of the Spark shell). It converts the user program into tasks: creates the SparkContext — the object that handles communications — computes the logical DAG of operations and converts it into a physical execution plan. It schedules tasks on executors: it has a complete view of the available executors, and stores metadata about RDDs and their partitions. It also launches a webUI.

Anatomy of a run

  1. The SparkContext connects to the Cluster Manager.
  2. The Cluster Manager allocates executors on worker nodes based on the driver’s requests — number of executors, number of cores per executor, amount of memory per executor. Executors typically stay up for the whole duration of the application, and each executor can run more tasks in multiple threads.
  3. The SparkContext sends tasks to the executors to run.

Spark on YARN

The mapping onto Chapter 5 is exact, and worth memorising:

Spark conceptYARN conceptNote
Driver Program≅ ApplicationThe driver can be internal to the AMP (e.g., for production jobs) or run in an external process (e.g., spark-shell)
Executor< ContainerEach executor runs in its own container, which is run and monitored by the Node Manager
Cluster Manager= Resource Manager

Spark vs MapReduce

MapReduceSpark
JobConsists of two tasks: a map and a reduceCan consist of more stages; each stage can consist of more tasks
Executor / ContainerRuns one task (either map or reduce), then diesCan run more (concurrent) tasks and stays active for the whole job
Data is read from / written to HDFSData can be cached and used by different tasks
Parallelization is driven by the number of tasks in the clusterParallelization is driven by the number of tasks in the executors

And the consequence for resource negotiation: in MapReduce, the application asks YARN’s Resource Manager to allocate containers to run tasks — many communications with YARN, and the availability of containers may change during job execution. In Spark, the driver asks the RM to allocate containers to run executors: the assignment of tasks to executors is done by the driver, and containers are allocated only once.

For the exam

That last paragraph is the crispest one-sentence answer to “why is Spark faster than MapReduce?” that does not mention memory. MapReduce negotiates with the cluster manager per task; Spark negotiates once per application and then schedules internally. Long-lived executors are also what makes caching possible at all — a container that dies after one task has nowhere to keep a cached partition.

12. Running an application: shells, submits and deployment modes

Spark supports three languages (Scala, Java, Python) and provides two main approaches to run applications, plus notebooks:

The spark-submit utility deploys the application, and different parameters can be configured — deployment mode, memory, CPU cores. There are three deployment modes:

The driver process runs directly on a node in the cluster, and the driver is run within the AMP.

Pro: data transfer from driver to executors (and vice versa) is fast.
Con: the driver takes away computing resources from the cluster.

The driver process runs on a machine that does not belong to the cluster, decoupled from the AMP.

Pro: the driver leaves all computing resources to the cluster.
Con: the driver cannot request specific computing resources for the executors.

Both driver and executors run on the same machine. Mainly used for testing and debugging purposes.

Keep this in mind when reading Chapter 8: in the local environment only the driver is created, so --executor-memory and --executor-cores have nothing to act on.

Key idea — where the chapter lands

You now have the whole picture of a Spark job: you write transformations (lazy, immutable), the driver builds a DAG, wide dependencies cut it into stages, each partition becomes a task, and long-lived executors run those tasks and hold the cache. Chapter 7 adds a schema and an optimiser on top of this machinery; Chapter 8 tunes the two numbers that decide everything — how many partitions, and how much shuffling.

Test your knowledge

What are Spark’s four innovations with respect to Hadoop MapReduce?

1. The RDD (Resilient Distributed Dataset): a set of data items of any format that is automatically distributed; all operations are defined on RDDs and there is no more separation between Map and Reduce. 2. A rich set of APIs to easily develop pipelines: depending on the type of operations the system automatically defines the map-style or reduce-style tasks, and the execution plan takes the form of a DAG. 3. Better usage of RAM: results are saved to disk only when the processing has finished, and RDDs can be temporarily cached. 4. Finer control over resource assignment (cores and memory).

What does “resilient” mean in Resilient Distributed Dataset, and what makes it possible?

Resilient means automatically rebuilt on failure. It is possible because RDDs are immutable and the transformations that produced them are recorded as a lineage (a DAG that is directed and acyclic). A lost partition can therefore be recomputed deterministically by replaying its lineage, instead of being recovered from a replica. This is also why narrow dependencies are cheaper to recover than wide ones: fewer parent partitions are needed to rebuild a lost child.

State the four RDD characteristics and the pros and cons of the first two.

Immutable (once created it cannot be modified) — pros: parallelization is easy, with no race conditions and no need to implement locking, and immutability enables laziness and cacheability; con: higher space occupation. Lazily evaluated (do not compute transformations until you need them; requires immutability and absence of side effects, where a side effect is a function modifying state outside its scope) — pros: job optimization and better performance, and no need to separately create all RDDs; con: you do not know there is an error until you compute. Cacheable (can persist in memory, spilling to disk if necessary). Type inference (the type is inferred by the compiler; a Scala feature, different from dynamic typing, which allows anticipating programming errors).

How many partitions does Spark create if you do not say, and why does the number matter?

For in-memory datasets it is based on the cluster; for external datasets it is one partition for each block (128 MB in HDFS), and it is not allowed to have fewer partitions than blocks. It matters because Spark runs one task for each partition: too few partitions and some CPU cores will not be used; too many and there is excessive overhead in managing many small tasks.

Distinguish transformations from actions, and give three examples of each.

Transformations construct a new RDD from a previous one and are lazy — examples: map, flatMap, filter, reduceByKey, join. Actions compute a result that is either returned to the driver program or saved to an external storage system, and they trigger the computation — examples: collect, count, first, take, reduce, saveAsTextFile. Until no action is fired, the data to be processed is not even accessed: in the example from the slides, Spark simply scans the file until it finds the first matching line when the action is first().

What is the difference between map and flatMap?

map(func) returns a new RDD formed by passing each element of the source through a function, so it is one input element to exactly one output element. flatMap(func) is similar, but each input item can be mapped to 0 or more output items, so func should return a Seq rather than a single item. Splitting lines into words is the canonical case: rddCapra.map(x => x.split(" ")) gives an RDD of arrays, whereas rddCapra.flatMap(x => x.split(" ")) gives an RDD with one record per word.

Define narrow and wide dependencies and give the four consequences of the distinction.

Narrow: the data from partition ai of A ends up in one partition bj of B (e.g., map, filter). Wide: the data from partition ai ends up in many, possibly every partition of B (e.g., groupByKey, reduceByKey). Consequences: narrow dependencies allow pipelining on one cluster node, giving more optimized execution; wide dependencies cannot be pipelined because they require data shuffling; in case of failure narrow dependencies require fewer partitions to be recomputed; and stage boundaries in the physical plan are defined exactly by the wide dependencies.

What is the DAG, and why must it be acyclic?

Based on the user application and on the lineage graphs, Spark computes a logical execution plan in the form of a Directed Acyclic Graph, later transformed into a physical execution plan. Nodes are RDDs, edges are operations on RDDs. It is directed because transformations go from an RDD A to an RDD B; it is acyclic because transformations cannot return an old RDD — which is immutability restated at the graph level. Acyclicity is what makes the plan schedulable in one pass and deterministically replayable after a failure.

How is a DAG compiled into stages and tasks?

Stages’ boundaries are defined by shuffle operations, and operations with narrow dependencies are pipelined as much as possible. Then a task is created for each partition in the new RDD; tasks are scheduled and assigned to worker nodes based on data locality, and the scheduler can run the same task on multiple nodes in case of stragglers, i.e. slow nodes. In the word count example, textFile, flatMap and map form Stage 1 and reduceByKey opens Stage 2.

Define application, job, stage and task.

Application: a single instance of SparkContext that stores data processing logic and schedules a series of jobs, sequentially or in parallel. Job: a complete set of transformations on RDD that finishes with an action or data saving, triggered by the driver application. Stage: a set of transformations that can be pipelined and executed by a single independent worker. Task: the basic unit of scheduling, which executes the stage on a single data partition.

What does persist() do, how does it differ from cache(), and which level would you pick?

Spark recomputes an RDD each time an action is called on it, which is especially expensive for iterative algorithms. When you persist an RDD, each node stores in memory the partitions of it that it computes and reuses them in other actions; persisting does not trigger the computation, and unpersist() releases it. persist() allows specifying the storage level while cache() uses MEMORY_ONLY. The levels are MEMORY_ONLY, MEMORY_AND_DISK (spills to disk if too much data), MEMORY_ONLY_SER / MEMORY_AND_DISK_SER (serialized: more space-efficient but more CPU-intensive), DISK_ONLY, and any level with the _2 suffix to replicate on 2 machines. Rules: stay in memory as much as possible; serialization makes objects much more space-efficient; spill to disk only if the dataset is computed via expensive functions; use replication only if you want fast fault recovery.

Describe the three components of the Spark architecture and what each one does.

Driver: one per application, the entry point of the Spark shell; creates the SparkContext, converts the user program into tasks by computing the logical DAG and turning it into a physical execution plan, schedules tasks on executors with a complete view of them, stores metadata about RDDs and their partitions, and launches a webUI. Cluster Manager: assigns and manages the cluster resources (memory, processor time); can be the Spark standalone manager or another compatible manager such as YARN; launches executor processes on behalf of the driver. Executor: a process that executes the received tasks; there are usually several per application and a worker node can host many; it typically runs for the entire duration of the application and caches RDD data in the JVM heap. Driver and executors are independent Java processes and together form the Spark application.

Map the Spark architecture onto YARN.

Driver Program ≅ Application: the driver can be internal to the Application Master Process (e.g., for production jobs) or run in an external process (e.g., spark-shell). Executor < Container: each executor runs in its own container, which is run and monitored by the Node Manager. Cluster Manager = Resource Manager.

Why does Spark talk to the resource manager less often than MapReduce?

In MapReduce the application asks YARN’s Resource Manager to allocate containers to run tasks, which means many communications with YARN, and the availability of containers may change during job execution. In Spark the driver asks the RM to allocate containers to run executors: the assignment of tasks to executors is then done by the driver, and containers are allocated only once. This is also what allows an executor to stay active for the whole job, run several concurrent tasks, and hold cached data between them — whereas a MapReduce container runs one task and dies.

Compare the three deployment modes of spark-submit.

Cluster mode: the driver process runs directly on a node in the cluster, within the AMP — data transfer between driver and executors is fast, but the driver takes computing resources away from the cluster. Client mode: the driver runs on a machine that does not belong to the cluster, decoupled from the AMP — it leaves all computing resources to the cluster, but cannot request specific computing resources for the executors. Local mode: both driver and executors run on the same machine, mainly for testing and debugging.