Spark RDD Implementation

pm jat @ daiict
 RDD Article [1]
• Here we are primarily discussing this article that appeared at a USENIX Conference
on Networked Systems Design and Implementation (NSDI) in 2012

28-Aug-23 Spark RDD Implementation 2

 RDD as Abstraction
• Partitioned collection of records/objects
• Can be created from storage or by transformations
• RDDs do not need to be materialized - instead “lineage graph” and realized by
executing on data on storage “whenever required”
• Users can control “persistence” and partitions

28-Aug-23 Spark RDD Implementation 3

 RDD programming interface
• Transformations
• Actions: count, collect, save
• Lazy evaluations

28-Aug-23 Spark RDD Implementation 4

 Comparison of RDDs with DSM [1]
Aspect RDDs DSM(Distributed Shared RAM)
Reads Coarse or fine-grained Fine-grained
Writes Coarse-grained Fine-grained
Consistency Trivial (immutable) Up to app / runtime
Fine-grained and low- Requires checkpoints and
Fault recovery
overhead using lineage program rollback
Straggler mitigation
Possible using backup tasks
(Dealing with Slow Difficult
on other replicas
Systems)
Automatic based on data Up to app (runtimes aim for
Work placement
locality transparency)
Behavior if not Similar to existing data flow
Poor performance (swapping?)
enough RAM
28-Aug-23
systems Spark RDD Implementation 5
 Advantages of RDD
• More efficient fault tolerance: because of coarse grain operations
• Since RDDs are read-only, it has a better ability to help slow nodes (stragglers) by
running backup copies of slow tasks
• Implements Improved Scheduling algorithm that uses a tradeoff between
“data locality” and “fairness” while scheduling tasks
• Able to better manage the situation of “insufficient RAMs”. RDDs degrade
gracefully when there is not enough memory to store them. May push to disk when
some are not used and keep only used one or so.

28-Aug-23 Spark RDD Implementation 6

 RDDs – Not suited for
• Main limitations of RDD is “Coarse grained”
• It is best suited for the same operations on all elements – “coarse-grained”
• Not suitable for applications requiring fine-grained updates to shared data
• For example storage System for
– Web applications
– Incremental web crawlers

28-Aug-23 Spark RDD Implementation 7

 Representing RDDs
• The article reports that deciding the appropriate representation of RDD, where
“fault tolerance is provided” while able to perform said set of operations in an
arbitrary manner.
• Spark uses a “lineage” based representation of RDD, where they maintain the
following information:
– set of partitions, which are atomic pieces of the dataset
– a set of dependencies on parent RDDs
– a function for computing the dataset based on its parents; and
– metadata about its partitioning scheme, and Data placement.

28-Aug-23 Spark RDD Implementation 8

 Representing RDDs

28-Aug-23 Spark RDD Implementation 9

 Representation of dependencies between RDDs

• Another challenge was to represent “dependencies”!

• Two types of Dependencies:
• Narrow and Wide dependencies
• Let RDDs be represented as shown here.
• An RDD has a set of partitions
– One or more partitions on a computer

28-Aug-23 Spark RDD Implementation 10

 Representation of dependencies between RDDs

28-Aug-23 Spark RDD Implementation 11

 Representation of dependencies between RDDs
• Narrow dependencies
– Where each partition of the parent RDD is used by at most one partition of the
child RDD
– For example: Map, Filter, Hash Partitioned Joins with same number of
partitioned (Consider a JOIN with Key=5)
– Narrow Transformations
– Dependencies where shuffling is not required
• Wide dependencies:
–…

28-Aug-23 Spark RDD Implementation 12

 Representation of dependencies between RDDs
• Narrow dependencies
–…
• Wide dependencies:
– Where multiple child partitions depend on a parent dependency
– In these dependencies, shuffling is required
– GroupBy, Join, etc.
– For example: Consider a JOIN with Key=5 (non hash partitioned)

28-Aug-23 Spark RDD Implementation 13

 Narrow and Wide Transformations

28-Aug-23 Spark RDD Implementation

[Link] 14
 Wide Dependency Concerns

• One, Shuffling is required

• Two, Reconstruction of a lost partition is expensive

28-Aug-23 Spark RDD Implementation 15

 Dependencies and Fault Tolerance
• Re-computing missing partitions is fast for narrow
dependencies but slower for wider dependencies

28-Aug-23 Spark RDD Implementation 16

 Dependencies and Optimization
• Internal Optimization for narrow and wider dependencies

28-Aug-23 Spark RDD Implementation 17

 Spark Job and Stages
• RDDs are represented as Directed Acyclic
Graph called “Lineage Graph”
• A request for “Action” on RDD triggers a Job.
• A Job is a pipeline of “Stages”
• Stages are executed by assigning tasks for A task is on a
partition
each partition.
• “Determining Stages” could be very crucial
in efficient execution of a Spark Job.
• The Query Optimizer should be playing a role
here.

28-Aug-23 Spark RDD Implementation 18

 Stages in a Spark Job
• Each stage contains many pipelined
transformations with narrow
dependencies as possible.
• The boundaries of the stages are the
shuffle operations required for wide
dependencies
• To run an action on RDD G, we build
stages at wide dependencies and
pipeline narrow transformations inside
each stage.
• In this case, stage 1’s output RDD is
already in RAM, so we run stage 2
and then 3.

28-Aug-23 Spark RDD Implementation 19

 Task Scheduling – considerations
• Our scheduler assigns tasks to machines based on data locality using “delay
scheduling”[4] – basically a delay in scheduling a task to ensure better locality
– Locality here means, writing output on the same machine where the input is.
– In a nutshell, it waits for a local machine (if not already free) to schedule the task
locally. Sometimes may kill existing jobs, etc.
• If a task needs to process a partition that is available in memory on a node, we send
the process to that node. Otherwise,
• If a task processes a partition for which the containing RDD provides preferred
locations (e.g., an HDFS file), we send it to those.
• …

28-Aug-23 Spark RDD Implementation 20

 Stages: How many stages it would require

28-Aug-23 Spark RDD Implementation 21

 Stages: How many stages it would require

28-Aug-23 Spark RDD Implementation 22

 Stages: How many stages it would require
• “Group By” and “Join” forms stage boundaries!

28-Aug-23 Spark RDD Implementation 23

 API Note!

• .dependencies()
• .toDebugString()

28-Aug-23 Spark RDD Implementation 24

 Evaluation Reports [1]
• The article presents an evaluation for the following three tasks: logistic regression, k-
means, page-rank
• They compared three systems
– Hadoop: The Hadoop 0.20.2 stable release.
– HadoopBinMem: A Hadoop deployment that converts the input data into a low-
overhead binary format in the first iteration to eliminate text parsing in later
ones, and stores it in an in-memory HDFS instance.
– Spark: their implementation of RDDs.
• Here is evaluation summary:

28-Aug-23 Spark RDD Implementation 25

 Logistic Regression and K-Means
• 100 GB Data, 10 iterations on
100 machines
• Logistic Regression:
– In the first iteration: Spark is
moderately faster than Hadoop
– In later iterations, the spark is
25.3x and 20.7x faster than
Hadoop and HadoopBinMem
• K-means:
– Faster in the range
of 1.9 to 3.2

28-Aug-23 Spark RDD Implementation 26

 Page Rank
• We compared the performance of Spark with
Hadoop for PageRank using a 54 GB Wikipedia
dump.
• We ran 10 iterations of the PageRank algorithm
to process a link graph of approximately 4 million
articles.
• in-memory storage alone provided spark with a
2.4x speedup over Hadoop on 30 nodes.
• Where in an improved algorithm (where
partitioning of RDD is controlled) improves the
speedup to 7.4x.
• The results also scaled nearly linearly to 60
nodes.

28-Aug-23 Spark RDD Implementation 27

 References / Further Readings
[1] Zaharia, Matei, et al. "Resilient distributed datasets: A fault-tolerant abstraction for in-memory
cluster computing." Proceedings of the 9th USENIX conference on Networked Systems Design and
Implementation. USENIX Association, 2012.
[2] Advanced Apache Spark Training - Sameer Farooqui (Databricks)
[Link]
[3] [Link]
[Link]
[4] Zaharia, Matei, et al. "Delay scheduling: a simple technique for achieving locality and fairness in
cluster scheduling." Proceedings of the 5th European conference on Computer systems. 2010.

28-Aug-23 Spark RDD Implementation 28