Spark's fault tolerance doesn't come from replicating data across machines -- it comes from LINEAGE. Every RDD remembers its parent RDD and the transformation that produced it from that parent. If a cached partition is lost (an executor crashes), Spark doesn't need a replica: it recomputes that partition by walking the lineage graph backward, recursively recomputing whatever ancestor data isn't available either, all the way back to the original source if nothing in between was cached.

Implement RDD.compute(partition_id):

• If this RDD is persist()-ed and partition_id is already in self.cache, return the cached value -- no recomputation.
• Otherwise, actually compute the partition:
  • Base RDD (self.parent is None): read it from self.source_data[partition_id] (raise KeyError if missing).
  • Derived RDD: recursively call self.parent.compute(partition_id), then apply self.transform to that result.
• Either way, bump self.compute_count by 1 -- it counts actual work done, not cache hits.
• If this RDD is persisted, store the freshly computed result in self.cache[partition_id] before returning it.

evict(partition_id) (already implemented) simulates losing a cached partition -- just removes it from self.cache. The next compute() call for that partition must transparently recompute it via lineage.

Example

base = RDD("base", source_data={0: [1, 2, 3]})
doubled = RDD("doubled", parent=base, transform=lambda xs: [x * 2 for x in xs])
doubled.persist()
plus1 = RDD("plus1", parent=doubled, transform=lambda xs: [x + 1 for x in xs])

plus1.compute(0)          # -> [3, 5, 7]; doubled.compute_count == 1, base.compute_count == 1
plus1.compute(0)          # plus1 isn't persisted -> recomputes, but doubled IS cached
                           # -> doubled.compute_count stays 1, base.compute_count stays 1

doubled.evict(0)          # simulate losing the cached partition
plus1.compute(0)          # -> still [3, 5, 7] -- recovered by recomputing from base
                           # -> doubled.compute_count is now 2, base.compute_count is now 2

Constraints

• An unpersisted RDD never populates self.cache -- every call is a fresh computation (that's what makes it "nothing to lose": losing an RDD's own data that was never cached in the first place is a no-op, the parent chain just gets walked again).
• compute_count only increases on real work, never on a cache hit.

Real-world grounding

• The original RDD paper: Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J. Franklin, Scott Shenker, Ion Stoica. "Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing," NSDI 2012.
• Spark's RDD class, where lineage (the dependencies graph) and caching (persist/StorageLevel) are actually implemented: core/src/main/scala/org/apache/spark/rdd/RDD.scala

Real Spark also checkpoints RDDs with very long lineage chains (writing materialized data to reliable storage, truncating the lineage) so recovery never has to replay an unbounded chain of transformations -- this exercise implements the core lineage-walk recovery mechanism both are built on.