I Spent 5 Hours Reading the Original White Paper on Spark and RDDs: Here’s What I Learned

Understanding the origins of Apache Spark and the power of in-memory data processing.

A Retrospective on Spark and Resilient Distributed Datasets (RDDs)

In 2012, researchers at the UC Berkeley AMP Lab, led by Matei Zaharia, introduced a groundbreaking concept in data processing called Resilient Distributed Datasets (RDDs). This innovation was aimed at overcoming significant inefficiencies in existing data processing frameworks like MapReduce, particularly for iterative and interactive workloads. The importance and impact of this innovation were recognized when the paper detailing RDDs and Spark won the Best Paper Award at the USENIX NSDI conference in 2012.

The Performance Bottlenecks of Early Data Processing Models

In the early 2010s, MapReduce was the leading model for processing large datasets. However, while MapReduce was effective for batch-processing tasks, it struggled with more complex, iterative, and interactive applications, such as machine learning algorithms and interactive data mining. These applications required running multiple stages of processing where data needed to be efficiently shared across stages.

MapReduce's reliance on stable storage solutions like distributed file systems (e.g., Hadoop Distributed File System - HDFS) introduced significant performance bottlenecks. Each job required data to be written to disk at the end of each stage and read back from disk at the start of the next, causing substantial I/O and network overhead. For instance, every write operation to HDFS involved replicating data across three machines to ensure fault tolerance, a process that was inherently slow.

To illustrate the inefficiency, consider that typical disk I/O speeds on distributed systems were around 100 MB/s, while network speeds were about 1 Gbps (125 MB/s). Moving data to and from disk under these conditions could add significant delays. For example, writing and replicating a 1 GB dataset across three machines could take up to 80 seconds, assuming optimal network and disk performance.

The Introduction of Resilient Distributed Datasets (RDDs)

The Berkeley team recognized the need for a more efficient data processing abstraction that could alleviate these bottlenecks. They introduced RDDs, a distributed memory abstraction designed to enable fault-tolerant, in-memory cluster computing. RDDs were designed to take advantage of memory speeds, which were significantly faster than disk and network speeds.

Internal memory bandwidth on servers was typically around 10 GB/s, vastly outpacing network speeds of 1 Gbps and disk I/O speeds of 100 MB/s. By enabling data to be shared in memory across jobs, RDDs reduced the need for slow disk I/O, allowing for much faster data processing. This was a game-changer for applications that required low-latency access to data, such as iterative machine learning algorithms and interactive queries.

How RDDs Transformed Data Processing Efficiency

RDDs offered a new approach to data processing by introducing a set of powerful transformations and actions that operate on datasets in a distributed manner:

• Transformations: These are operations that are applied to an RDD to create a new RDD. They are lazy in nature, meaning they do not immediately compute the results. Instead, transformations build up a lineage of operations, which Spark uses to optimize and execute the tasks efficiently. Common transformations include map(), filter(), flatMap(), groupByKey(), and reduceByKey(). These operations allow users to perform a wide range of data manipulation tasks while keeping the data in memory.

• Actions: Actions trigger the execution of the transformations that have been previously specified. They perform computations on the RDD and return results to the driver program or write the data to an external storage system. Examples of actions include collect(), count(), saveAsTextFile(), and reduce(). Actions are essential for extracting the computed results from Spark.

By using RDDs, data could be kept in memory across multiple processing stages, eliminating the need for repeated disk access. This in-memory data sharing was not only faster but also more efficient in terms of resource utilization. The lineage information (a record of the transformations applied to build the dataset) allowed RDDs to quickly recompute lost data without replicating it across the network, further enhancing performance.

The impact of this approach was profound. Various benchmarks demonstrated the significant performance improvements achievable with RDDs:

1. Interactive Query Performance: On a 50 GB dataset of Wikipedia data spread across 20 machines, a full-text search took about 20 seconds using traditional disk-based systems like Hadoop. With Spark and RDDs, the same query completed in under 1 second. This 20x improvement highlighted the potential of in-memory computing to drastically reduce query response times.

2. Iterative Algorithms: For iterative algorithms like PageRank, which required multiple stages of computation over the same dataset, the benefits of RDDs were even more pronounced. Running PageRank on 30 machines, Spark achieved a 3x speedup by keeping data in memory and an additional 3x speedup by optimizing data partitioning to minimize network shuffles, resulting in an overall 8x speedup compared to disk-based systems.

3. Scalability: Spark's scalability was demonstrated with a 1 TB dataset across 100 machines. Full-text search on this dataset took about 3 minutes using disk-based storage but was reduced to just 5 seconds with in-memory storage using Spark, showing a speedup of over 30x.

Spark: The Engine Behind RDDs

To harness the power of RDDs, the Berkeley team developed Spark, a flexible, in-memory cluster computing engine. Spark provided a simple programming interface in languages like Scala, Python, and Java, allowing developers to interact with RDDs directly and perform a wide range of data processing tasks interactively.

Spark's design focused on optimizing data locality and minimizing unnecessary data movement. By using delay scheduling and other techniques to keep data local to where it was processed, Spark could achieve nearly 100% data locality, maximizing the benefits of in-memory processing.

Additionally, Spark introduced several optimizations to enhance performance:

• In-Memory Persistence: Spark allows users to persist RDDs in memory across operations, which is crucial for iterative algorithms that repeatedly access the same dataset. This significantly reduces I/O overhead and speeds up processing.

• Controlled Partitioning: By allowing users to control the partitioning of RDDs, Spark minimizes the amount of data shuffled across the network. This is particularly beneficial for operations like joins, which can be performed locally on each machine if the data is partitioned appropriately.

• Fault Tolerance: Spark's fault tolerance is built into the RDD model. If a node fails, Spark can recompute the lost partitions using the lineage information, ensuring data reliability without the need for replication.

Real-World Applications and Industry Impact

Since its release, Spark has become a widely adopted tool in both academia and industry, thanks to its ability to combine SQL, machine learning, and graph processing on the same in-memory dataset.

Numerous companies have leveraged Spark to achieve significant performance gains:

• Conviva reported that it could run some of its reports up to 40 times faster using Spark's in-memory capabilities compared to traditional disk-based systems.

• Yahoo! used Spark to analyze 1.5 billion events daily, achieving better performance and reduced costs by leveraging Spark's in-memory data processing capabilities.

Conclusion

The introduction of RDDs and Spark marked a significant leap forward in data processing technology. By focusing on in-memory computation and leveraging coarse-grained transformations and actions, Spark and RDDs provided a scalable, fault-tolerant solution that dramatically improved the speed and efficiency of large-scale data analytics. The metrics and benchmarks demonstrate the substantial gains in performance: from 20x improvements in interactive query response times to over 30x speedups in processing large datasets, Spark and RDDs set a new standard for data processing performance. Today, their influence continues to be seen in the evolving landscape of distributed computing systems, as the principles of fast, efficient, and scalable data processing remain at the forefront of innovation.

References

• Original white paper

• Paper presentation with video and slides

Watch Our Session Recording

We're excited to share the recording of our recent session where we read and discussed key papers on Kafka, Spark, and Spark Streaming. This session is part of our ongoing series aimed at deepening our understanding of these powerful technologies through collaborative reading and discussion.

After the readout, we hold a lively Q&A session where participants asked insightful questions about any data topic. For privacy concerns, I do not publish the Q&A section of the meeting.

If you're interested in joining us for future sessions, where we explore more papers on Kafka, Spark, Spark Streaming, and other cutting-edge technologies, you can find the next session on LinkedIn or Discord. It's a great opportunity to learn, ask questions, and connect with others in the community!

Video Recording Of The Session