Early big data tools such as MapReduce were great for a single pass over huge files. But many useful jobs go over the same data again and again: machine learning that refines a model, graph algorithms that repeat until they settle, or an analyst who asks one question after another. Re-reading from disk each time is slow.
The obvious fix is to keep the data in the memory of the cluster. But memory is lost when a machine dies, and a cluster has many machines. The 2012 paper on resilient distributed datasets, or RDDs, shows how to keep data in memory and survive failures without copying everything. It is the idea behind Apache Spark.
An RDD is a read-only, partitioned collection of records that can only be built by transformations such as map and filter. Because Spark remembers each dataset's recipe, called its lineage, a lost partition is rebuilt by replaying the recipe on just that piece of data. No replication of the data is needed.
A dataset that remembers its recipe
The paper defines an RDD as a read-only, partitioned collection of records. RDDs can only be created through deterministic operations on data in stable storage or on other RDDs. These operations are called transformations. Examples are map, filter and join.
An RDD does not need to be fully stored at all times. It holds enough information about how it was derived from other datasets, its lineage, to compute its partitions again from stable storage. Nothing is actually computed until an action, such as counting or saving the result, asks for an answer.
