Distributed Processing - Apache Spark Engine

The first generation of distributed computing frameworks—epitomized by Apache Hadoop MapReduce—democratized batch processing across thousands of commodity machines by abstracting distributed coordination, failure recovery, and data partitioning behind simple functional primitives (map and reduce). However, MapReduce's computational execution model imposed severe systemic bottlenecks: every intermediate step in a multi-stage data pipeline was forced to materialize its state completely to physical disk (HDFS) and replicate it across the network before the subsequent stage could commence. For iterative algorithms (such as gradient descent in machine learning, graph traversals in PageRank, and exploratory SQL analysis), this disk-bound synchronization loop resulted in catastrophic performance degradation, with over 80% of execution time spent in disk I/O and object serialization.

Apache Spark revolutionized distributed computing by introducing in-memory distributed data abstractions coupled with lazy evaluation and coarse-grained deterministic lineage. Rather than persisting intermediate states to physical media, Spark retains data partitions in distributed RAM across a cluster of worker nodes. Powered by the Catalyst Optimizer for relational query synthesis and Project Tungsten for bare-metal memory management, Spark delivers processing throughput up to 100 times faster than classic MapReduce, serving as the computational backbone of modern enterprise data platforms.

1. Theoretical & Architectural Foundations#

Resilient Distributed Datasets (RDDs) and Coarse-Grained Lineage#

At the heart of Spark's theoretical architecture lies the Resilient Distributed Dataset (RDD): a read-only, horizontally partitioned collection of records distributed across cluster nodes that can be operated on in parallel.

Traditional distributed shared memory (DSM) systems provide fine-grained mutable access to shared state (allowing individual cells or variables to be updated in place). To achieve fault tolerance, DSM architectures must continuously record fine-grained write operations across the network or take costly global distributed checkpoints.

Spark rejects fine-grained mutations in favor of coarse-grained deterministic transformations:

• An RDD can only be created through deterministic transformations (e.g., map, filter, join) applied to either stable storage (HDFS, S3) or other existing RDDs.
• Instead of replicating data partitions across machines for fault tolerance, an RDD maintains an immutable Lineage Graph (a Directed Acyclic Graph - DAG) recording the exact mathematical sequence of transformations used to construct it from raw inputs.

+-----------------------------------------------------------------------------------+
|                        SPARK COMPUTATIONAL ARCHITECTURE                           |
+-----------------------------------------------------------------------------------+
|                            DRIVER PROGRAM                                         |
|   - SparkSession / SparkContext: Entry point & User Code Coordinator              |
|   - Catalyst Optimizer: AST -> Logical Plan -> Optimized Physical Plan            |
|   - DAGScheduler: Translates RDD DAG into Stages (Split at Shuffle Boundaries)    |
|   - TaskScheduler: Dispatches TaskSets to Cluster Manager (K8s / YARN)            |
+------------------------------------------+----------------------------------------+
                                           | RPC Task Dispatch & Block Tracking
         +---------------------------------+---------------------------------+
         |                                 |                                 |
         v                                 v                                 v
+------------------+             +-------------------+             +------------------+
| EXECUTOR JVM 1   |             | EXECUTOR JVM 2    |             | EXECUTOR JVM 3   |
+------------------+             +-------------------+             +------------------+
| - Thread Pool    |             | - Thread Pool     |             | - Thread Pool    |
| - BlockManager   |             | - BlockManager    |             | - BlockManager   |
| - Unified Memory |             | - Unified Memory  |             | - Unified Memory |
|   (Storage/Exec) |             |   (Storage/Exec)  |             |   (Storage/Exec) |
+------------------+             +-------------------+             +------------------+

If a physical worker node crashes and loses its in-memory partitions, the Spark Driver does not abort the entire job. It simply consults the lost partition's lineage sub-graph and recomputes only the missing partition on another active node in the cluster, completely avoiding global job rollbacks.

Narrow vs. Wide Dependencies and Shuffle Boundaries#

Spark categorizes RDD transformations into two fundamentally distinct computational classes:

NARROW DEPENDENCY (No Shuffle, Pipelined):
[RDD A: Part 1] ------> [RDD B: Part 1]
[RDD A: Part 2] ------> [RDD B: Part 2]
[RDD A: Part 3] ------> [RDD B: Part 3]
Execution: Single Stage, Zero Network Exchange, Thread Pipelining (map, filter)

WIDE DEPENDENCY (Shuffle Boundary, All-to-All Network Transit):
[RDD A: Part 1] ---\ /--- [RDD B: Part 1]
[RDD A: Part 2] ----X---- [RDD B: Part 2]
[RDD A: Part 3] ---/ \--- [RDD B: Part 3]
Execution: Forces Stage Boundary, Disk Serialization, Network Shuffle (groupByKey, join)

1. Narrow Dependencies:

* Each partition of the parent RDD is consumed by at most one partition of the child RDD.

Examples*: map(), flatMap(), filter(), mapPartitions().

Optimization*: Transformations can be collapsed and pipelined in memory within a single CPU execution thread. Data stays in the CPU L1/L2 cache without requiring memory buffers, serialization, or network transit.

1. Wide Dependencies (Shuffle Operations):

* Multiple child partitions depend on data distributed across multiple parent partitions.

Examples*: groupByKey(), reduceByKey(), join(), distinct(), repartition().

Execution Cost: Forces a Shuffle Boundary*. All executing tasks in the upstream stage must write their output to local disk shuffle files, sort/bucket data by target partition key, and wait for downstream tasks to pull their assigned key blocks over the network (an all-to-all M × R network transfer, where M is map tasks and R is reduce tasks).

The Catalyst Query Optimizer#

When developers write queries using Spark SQL, DataFrames, or Datasets, operations are not executed naively as raw RDDs. Instead, they are passed to the Catalyst Optimizer, an extensible relational optimization framework implemented in Scala:

[Unresolved Logical Plan] (Parsed AST from SQL / DataFrame API)
           |
           v (Analysis: Catalog & Schema Resolution)
[Resolved Logical Plan]
           |
           v (Logical Optimization: Rule-Based Transformations)
[Optimized Logical Plan] (Predicate Pushdown, Projection Pruning, Constant Folding)
           |
           v (Physical Planning: Cost-Based Optimizer - CBO)
[Selected Physical Plan] (Choose Join Algorithm: Broadcast Hash Join vs. Sort-Merge)
           |
           v (Code Generation: Janino Compiler)
[Generated Java Bytecode] (Tungsten Whole-Stage Code Generation executed on bare metal)

Key Optimization Phases:

1. Analysis: Resolves table names, column identifiers, and data types against the metadata Catalog.
2. Logical Optimization: Applies rule-based transformations:

Predicate Pushdown*: Filters are pushed as close to the data source as possible (e.g., into Parquet/JDBC readers).

Projection Pruning*: Eliminates unreferenced columns before processing.

Null Propagation & Boolean Simplification*: Simplifies constant expressions (e.g., 1 = 1 or x AND false).

1. Physical Planning & CBO: Generates multiple candidate physical execution plans and uses Cost-Based Optimization (evaluating table row counts, size in bytes, and column histograms) to select the optimal physical plan (e.g., deciding between Broadcast Hash Join, Shuffle Hash Join, or Sort-Merge Join).
2. Whole-Stage Code Generation: Compiles the entire pipeline of physical operators within a stage into a single, clean Java while loop using the lightweight Janino compiler. This eliminates virtual function dispatch overhead, flattens execution stacks, and maximizes CPU instruction pipelining.

2. Project Tungsten: Bare-Metal Memory Architecture#

Early iterations of Spark suffered from JVM inefficiencies: Java objects carry heavy memory overhead (a 4-byte string foo can consume 48 bytes in the JVM due to 16-byte object headers, 8-byte hash codes, and pointer alignments), and garbage collection (GC) pauses on 100 GB heaps routinely halted cluster operations for minutes.

Project Tungsten redesigned Spark's execution engine to manage memory directly, operating as close to bare metal as possible:

Off-Heap Memory Management via `sun.misc.Unsafe`#

Tungsten bypasses the standard JVM heap allocator by managing raw off-heap memory buffers directly using Java's internal sun.misc.Unsafe API:

• Data is stored in compact, C-style binary byte arrays.
• Records are referenced via 64-bit memory addresses (encoding a 32-bit object offset and a 32-bit base address), completely eliminating 64-bit JVM object pointer references.
• Because off-heap memory is managed manually by Spark's internal MemoryManager, it is completely invisible to the JVM Garbage Collector, eliminating "Stop-the-World" GC pauses entirely.

Cache-Aware Computation & Hardware Acceleration#

Modern CPU architectures access L1 cache in ≈ 1 ns, L2 cache in ≈ 4 ns, L3 cache in ≈ 10 ns, and main RAM in ≈ 100 ns. Traditional algorithms that traverse pointer-chasing linked lists suffer continuous CPU cache misses.

Tungsten designs cache-aware sorting algorithms:

• Instead of sorting arrays of pointers to full objects, Tungsten packs an 8-byte sort key prefix alongside an 8-byte memory pointer into contiguous 16-byte cache-line friendly arrays.
• CPU cores perform comparisons directly against the cache-resident 8-byte prefixes without fetching the full object from RAM. Only when prefixes are identical does the algorithm dereference the memory pointer.

3. Spark Unified Memory Management Architecture#

In modern Spark (versions 1.6+), executor heap memory is managed dynamically under a Unified Memory Manager, replacing static fixed memory partitions:

+-----------------------------------------------------------------------------------+
|                        TOTAL EXECUTOR JVM HEAP (e.g., 32 GB)                      |
+-----------------------------------------------------------------------------------+
|  Reserved Memory: 300 MB (Hardcoded internal system safety buffer)                |
+-----------------------------------------------------------------------------------+
|  User Memory: (Total - 300 MB) * (1 - spark.memory.fraction)                      |
|  - User data structures, internal metadata, UDF variables (default: 40%)          |
+-----------------------------------------------------------------------------------+
|  SPARK UNIFIED MEMORY POOL: (Total - 300 MB) * spark.memory.fraction (default 60%)|
|  +---------------------------------------+---------------------------------------+|
|  | STORAGE MEMORY POOL                   | EXECUTION MEMORY POOL                 ||
|  | - Cached RDDs, DataFrames (.cache())  | - Shuffle sort buffers, HashJoin maps ||
|  | - Broadcast variables                 | - Aggregations (reduceByKey buffers)  ||
|  | Default fraction: 50%                 | Default fraction: 50%                 ||
|  +---------------------------------------+---------------------------------------+|
|  <---------------- DYNAMIC BORROWING & EVICTION BOUNDARY ------------------------>|
+-----------------------------------------------------------------------------------+

Dynamic Borrowing and Eviction Rules#

The boundary between Storage Memory and Execution Memory is completely elastic:

1. Execution Borrows from Storage: If Execution needs memory for an active shuffle sort or hash join, and Storage has unallocated space, Execution borrows the space immediately.
2. Storage Borrows from Execution: If Storage needs memory to cache an RDD, and Execution has idle space, Storage borrows it.
3. Eviction Asymmetry:

If Execution requires memory that is currently occupied by Storage, Storage is evicted*: cached RDD blocks are dropped from RAM (spilled to local disk or simply discarded if the RDD lineage is preserved).

If Storage requires memory occupied by Execution, Execution is NEVER evicted*: Execution tasks cannot be preempted because an active shuffle or join cannot drop its working sort buffers without crashing. Storage must wait, or spill its new blocks directly to disk.

4. Common Antipatterns & Production Pitfalls#

Antipattern 1: Using `groupByKey()` Instead of `reduceByKey()`#

// CATASTROPHIC ANTIPATTERN: Massive shuffle spill and OOM!
val wordCounts = pairs.groupByKey().mapValues(values => values.sum)

// HIGH-PERFORMANCE PRODUCTION PATTERN: Map-side combine!
val wordCounts = pairs.reduceByKey(_ + _)

• groupByKey(): Transmits every single raw record across the network over the shuffle link before performing aggregation on the reducer. If key "error" appears 10 million times, all 10 million instances are serialized and sent across the network, overflowing reducer memory buffers.
• reduceByKey(): Executes an automated Map-Side Combine within each mapper before shuffling. If key "error" appears 10 million times across 100 mappers, each mapper sums its local subset, emitting only one single integer per mapper across the network, reducing network shuffle volume by > 99.9\%.

Antipattern 2: Severe Data Skew in Joins#

In distributed joins, data is partitioned by hash code of the join key:

partition\_id = hash(key) mod{num\_partitions}

If a single key (e.g., null or a generic enterprise customer ID) represents 40\% of all rows, a single executor task receives 40\% of the entire cluster's workload while the other 99 executors finish in seconds and sit idle. The job hangs at "Stage 99% Complete" for hours, eventually crashing with java.lang.OutOfMemoryError: Java heap space.

Production Remediation (Salting):

Append a random integer suffix (key + "_" + random(0, 9)) to the skewed key in the primary table, and replicate the corresponding lookup key across all 10 salted variations in the secondary table, redistributing the single massive partition evenly across 10 distinct executors.

5. University-Grade Checkpoint Practice Problems#

Problem 1: Spark Unified Memory Manager Partitioning & Spill Sizing#

Context: An enterprise Spark executor is allocated a JVM heap of H_{total} = 32 GB (32,768 MB).

Spark Memory Configuration Parameters:

• Hardcoded reserved memory: M_{reserved} = 300 MB.
• spark.memory.fraction = 0.60 (60\% allocated to Spark Unified Pool; 40\% to User Memory).
• spark.memory.storageFraction = 0.50 (baseline 50\% storage / 50\% execution split within the unified pool).

Workload Profile:

• A machine learning pipeline caches an iterative feature matrix DataFrame requiring S_{cache} = 12,000 MB of storage memory.
• Simultaneously, a massive shuffle sort stage executes, requiring E_{req} = 14,000 MB of execution memory for internal shuffle hash aggregations.

Task:

1. Calculate the exact size (in MB) of the User Memory Pool.
2. Calculate the total size (in MB) of the Spark Unified Memory Pool.
3. Calculate the baseline protected Storage Memory limit M_{storage, base} and baseline Execution Memory limit M_{exec, base}.
4. Given the workload demands (12,000 MB storage, 14,000 MB execution), determine the exact dynamic memory allocation, calculate the volume of cached data evicted from RAM (if any), and compute the volume of execution data spilled to disk (if any).

Solution:

1. User Memory Pool Sizing:

* Usable heap after subtracting hardcoded reserve:

H_{usable} = H_{total} - M_{reserved} = 32,768 MB - 300 MB = 32,468 MB

* User memory fraction = 1 - spark.memory.fraction = 1 - 0.60 = 0.40:

M_{user} = 0.40 × 32,468 MB = 12,987.2 MB

1. Spark Unified Memory Pool Sizing:

M_{unified} = 0.60 × 32,468 MB = 19,480.8 MB

1. Baseline Pool Allocations:

* Storage fraction R_{storage} = 0.50:

M_{storage, base} = 0.50 × 19,480.8 MB = 9,740.4 MB

* Execution baseline:

M_{exec, base} = M_{unified} - M_{storage, base} = 9,740.4 MB

1. Workload Contention, Eviction, and Spill Analysis:

Step 1: Initial Caching*:

* Storage requests 12,000 MB.

* Because Execution was initially idle, Storage was allowed to borrow from Execution:

Borrowed Space = 12,000 - 9,740.4 = 2,259.6 MB

Storage successfully occupied 12,000 MB in RAM.

Step 2: Execution Demand Arrives*:

* Execution now requires E_{req} = 14,000 MB.

* Under Spark's eviction rules, Execution has absolute priority to reclaim its baseline allocation (M_{exec, base} = 9,740.4 MB).

Therefore, the 2,259.6 MB that Storage borrowed from Execution is forcibly evicted*:

Storage Evicted to Disk / Dropped = 2,259.6 MB

* Storage is compressed down to its strict baseline:

M_{storage, remaining} = 12,000 - 2,259.6 = 9,740.4 MB

Step 3: Execution Memory Allocation*:

* Execution reclaims its full baseline of 9,740.4 MB.

Can Execution evict any of Storage's baseline (9,740.4 MB)? No*. Execution can only reclaim borrowed space; it cannot evict data residing within Storage's protected baseline.

* Execution requires 14,000 MB, but only has 9,740.4 MB available in RAM.

* The remaining deficit must spill to local disk:

Execution Disk Spill = 14,000 MB - 9,740.4 MB = 4,259.6 MB

Summary*:

* RAM Storage Memory: 9,740.4 MB (with 2,259.6 MB evicted).

* RAM Execution Memory: 9,740.4 MB.

* Execution Spilled to Disk: 4,259.6 MB.

Problem 2: Data Skew Salting Mathematics & Execution Equalization#

Context: A daily e-commerce clickstream dataset contains N = 1,000,000,000 (1 billion) records totaling 200 GB of data.

The dataset is partitioned by user_id across P = 100 reducer partitions during an aggregation stage.

Telemetry reveals severe key skew:

• Unauthenticated guest traffic shares a dummy key user_id = "GUEST", representing 30\% of all records (300,000,000 records, 60 GB).
• The remaining 70\% of records (700,000,000 records, 140 GB) are uniformly distributed across 70,000,000 distinct authenticated user IDs.

In standard hash partitioning:

partition = hash(key) mod{100}

All 300,000,000 guest records hash to a single reducer partition (Partition 42), while the other 99 partitions share the remaining 140 GB.

Task:

1. Calculate the data volume and record count assigned to Partition 42 vs. the average volume assigned to each of the other 99 partitions under standard execution.
2. Compute the skew ratio R_{skew} = V_{max} / V_{avg}.
3. Design a Salting Key Strategy using S = 20 salt buckets to redistribute the guest traffic.
4. Calculate the new maximum partition volume and prove how salting eliminates executor memory bottlenecks.

Solution:

1. Baseline Skew Evaluation:

* Partition 42 receives:

* All guest records: 300,000,000 records (60.0 GB).

* Its normal share (1\%) of authenticated traffic:

(700,000,000 / 100) = 7,000,000 records (1.4 GB)

* Total on Partition 42:

V_{part 42} = 60.0 GB + 1.4 GB = 61.4 GB (307,000,000 records)

* Each of the remaining 99 partitions receives:

V_{normal} = (140 GB - 1.4 GB / 99) = (138.6 GB / 99) = 1.40 GB (7,000,000 records)

1. Skew Ratio Calculation:

* Average partition volume across all 100 partitions:

V_{avg} = (200 GB / 100) = 2.0 GB

* Skew Ratio:

R_{skew} = (V_max / V_avg) = (61.4 GB / 2.0 GB) = 30.7×

* Partition 42 processes over 30× more data than the average partition, causing straggler tasks and OOM crashes.

1. Salting Key Implementation:

* In the transformation pipeline, inspect the key:

new\_key = {

"GUEST_" + random(0, 19) if user_id = "GUEST"

user_id otherwise

}

* The single GUEST key is converted into 20 distinct synthetic keys (GUEST_0, GUEST_1, ..., GUEST_19), each containing approximately:

(300,000,000 / 20) = 15,000,000 records (3.0 GB)

1. Post-Salting Workload Distribution:

* Because there are 100 partitions and 20 uniformly distributed guest keys, the 20 guest keys distribute across 20 distinct partitions.

* The maximum partition now holds:

V_{max, salted} = 3.0 GB (salted guest chunk) + 1.4 GB (normal authenticated traffic) = 4.4 GB

* New maximum partition volume: 4.4 GB (reduced from 61.4 GB).

* The maximum partition size is slashed by:

(1 - (4.4 / 61.4)) × 100\% = (1 - 0.07166) × 100\% ≈ 92.83\%

* Every executor easily accommodates 4.4 GB in memory without spilling to disk or triggering GC thrashing.

Problem 3: Broadcast Hash Join vs. Sort-Merge Join Network I/O Math#

Context: A Spark SQL application joins two tables residing in an S3 data lake:

• Table A (Fact Table: Web Event Telemetry):

* Size: S_A = 1.6 TB = 1,600 GB uncompressed.

* Number of partitions: P_A = 1,600 partitions.

• Table B (Dimension Table: Product Metadata):

* Size: S_B = 1.2 GB uncompressed (240 MB compressed in Parquet; 400 MB serialized in memory).

* Number of partitions: P_B = 4 partitions.

Cluster Architecture:

• The cluster consists of N = 40 worker nodes running 160 executors.
• By default, spark.sql.autoBroadcastJoinThreshold is set to 10 MB (10,485,760 bytes). Because Table B (1.2 GB) exceeds 10 MB, Catalyst selects Sort-Merge Join (SMJ).

Task:

1. Calculate the total network shuffle write and shuffle read volume (in GB) incurred by the default Sort-Merge Join across both tables.
2. If the lead data engineer overrides the configuration by setting:

spark.sql.autoBroadcastJoinThreshold = "2GB"

or forces a Broadcast Hash Join (BHJ) via broadcast(tableB), calculate the total network data transmitted from the Driver to all executors.

1. Calculate the absolute network bandwidth saved and explain the execution speedup.

Solution:

1. Sort-Merge Join (SMJ) Network Traffic:

* In a Sort-Merge Join, both tables must be co-partitioned across the cluster by hash of the join key:

* Table A is read by mappers, partitioned into R = 200 shuffle buckets, and written to local disk. Downstream reducers fetch all 1,600 GB across the network.

* Table B is read, partitioned into 200 shuffle buckets, and written to disk. Downstream reducers fetch all 1.2 GB across the network.

* Total shuffle network transit:

V_{shuffle, SMJ} = S_A + S_B = 1,600 GB + 1.2 GB = 1,601.2 GB

* Additionally, Sort-Merge Join forces both tables to be sorted by key on disk, incurring 2 × 1,601.2 = 3,202.4 GB of local disk I/O.

1. Broadcast Hash Join (BHJ) Network Traffic:

In a Broadcast Hash Join, Table A is never shuffled*. Mappers read Table A locally from S3 and stream rows directly through an in-memory hash table.

* The Driver fetches Table B (1.2 GB uncompressed; 400 MB serialized = 0.40 GB), constructs a compact hash table, and broadcasts it to every worker executor using a BitTorrent-like peer-to-peer distribution protocol.

* Network data transmitted across the cluster:

V_{broadcast} = N_{executors} × S_{B, serialized} = 160 × 0.40 GB = 64.0 GB

1. Performance Comparison:

* Absolute network traffic saved:

Δ V = V_{shuffle, SMJ} - V_{broadcast} = 1,601.2 GB - 64.0 GB = 1,537.2 GB saved

* Percentage reduction in network transit:

(1 - (64.0 / 1,601.2)) × 100\% = (1 - 0.03997) × 100\% ≈ 96.0\%

Result*: Over 1.5 TB of network shuffle is eliminated. Furthermore, because sorting of the 1.6 TB fact table is bypassed, job completion time typically drops from 45 minutes to under 4 minutes.

Problem 4: Lineage DAG Reconstruction vs. Periodic Checkpointing Recovery#

Context: A distributed graph analytics job executes an iterative PageRank algorithm across a cluster for K = 60 iterations.

Operational Metrics:

• Each iterative transformation step i takes T_{iter} = 45 seconds to compute.
• Because each iteration builds on the previous iteration's RDD:

RDD_i = f(RDD_{i-1})

the logical lineage graph depth grows by 1 on every iteration.

• At iteration step k = 54, an executor hosting a critical partition suffers a fatal hardware kernel panic, destroying the partition in RAM.

We evaluate two fault-recovery architectures:

• Strategy A (Pure Lineage Recomputation): Zero checkpointing. When the partition is lost at step 54, Spark traces the lineage graph back to the original raw graph input (RDD_0) on HDFS and recomputes the partition from iteration 1 to 54.
• Strategy B (Periodic Reliable Checkpointing): The application invokes rdd.checkpoint() every C = 10 iterations (persisting the RDD state to HDFS and truncating the lineage graph).

* Writing a checkpoint to HDFS incurs a temporal penalty of T_{check} = 60 seconds during the checkpoint iteration.

Task:

1. Calculate the total baseline execution time for all 60 iterations under Strategy A assuming zero failures.
2. Calculate the total baseline execution time for all 60 iterations under Strategy B assuming zero failures.
3. Calculate the time lost to recomputation when the failure occurs at iteration 54 under Strategy A.
4. Calculate the time lost to recomputation when the failure occurs at iteration 54 under Strategy B.
5. Compute the total wall-clock time from start to completion for both strategies in the presence of this failure, and determine which strategy is superior.

Solution:

1. Baseline Time under Strategy A (No Failures):

T_{base, A} = 60 × T_{iter} = 60 × 45 s = 2,700 seconds (45.0 minutes)

1. Baseline Time under Strategy B (No Failures):

* Checkpoints occur at iterations 10, 20, 30, 40, and 50 (5 total checkpoints).

* Total checkpoint writing overhead:

T_{check, total} = 5 × 60 s = 300 seconds

* Total baseline time:

T_{base, B} = (60 × 45 s) + 300 s = 2,700 s + 300 s = 3,000 seconds (50.0 minutes)

1. Failure Recomputation Time under Strategy A:

* Because lineage was never truncated, the lost partition must be recomputed from RDD_0 up to RDD_{54} (54 iterations):

T_{recompute, A} = 54 × 45 s = 2,430 seconds (40.5 minutes)

1. Failure Recomputation Time under Strategy B:

* The most recent stable checkpoint exists at iteration 50 (RDD_{50}).

* Spark truncates lineage at RDD_{50}; therefore, recomputation only needs to execute iterations 51, 52, 53, and 54 (4 iterations):

T_{recompute, B} = (54 - 50) × 45 s = 4 × 45 s = 180 seconds (3.0 minutes)

1. Total Wall-Clock Time Comparison with Failure:

* Strategy A Total Time:

T_{total, A} = T_{base, A} + T_{recompute, A} = 2,700 s + 2,430 s = 5,130 seconds = 85.5 minutes

* Strategy B Total Time:

T_{total, B} = T_{base, B} + T_{recompute, B} = 3,000 s + 180 s = 3,180 seconds = 53.0 minutes

Conclusion: Strategy B completes in 53 minutes compared to 85.5 minutes for Strategy A, saving 32.5 minutes* (38\% faster). In deep iterative workloads, periodic checkpointing is strictly required to prevent catastrophic lineage graph explosion and prolonged recovery times.