7. Batch and Distributed Data Processing

Introduction and Context

Big data systems are designed for datasets whose volume, velocity, variety, or computational complexity exceeds the practical capacity of a single machine. A central challenge is not merely storing such data, but transforming it reliably and efficiently. Tasks such as counting events, joining records, calculating aggregates, training models, and scanning historical logs must be divided across many machines and coordinated as one logical computation.

Batch and distributed data processing provide the foundations for this work. Batch processing operates on a bounded collection of data, usually accumulated before execution. Distributed processing divides computation and data across a cluster, allowing parallel execution and horizontal scalability. The combination is central to data lakes, enterprise reporting, recommendation systems, risk analysis, scientific computing, and machine-learning pipelines.

This chapter examines three closely related ideas. MapReduce provides a programming model for large-scale batch computation. Directed acyclic graph (DAG)-based engines represent computation as a sequence of dependent transformations and optimise execution across stages. Apache Spark extends these principles through in-memory processing, a rich programming model, SQL support, streaming capabilities, and machine-learning libraries. The emphasis is not simply on using a framework, but on making informed decisions about partitioning, caching, shuffling, resource allocation, fault tolerance, and cost.

Learning Objectives

After studying this chapter, students should be able to:

1. Explain the purpose and architecture of batch and distributed data processing.

2. Describe the MapReduce programming model and its execution stages.

3. Interpret DAG-based execution and distinguish narrow from wide transformations.

4. Explain Spark’s architecture, abstractions, APIs, and execution model.

5. Select suitable strategies for partitioning, caching, joins, aggregation, and resource allocation.

6. Diagnose common performance problems involving skew, excessive shuffling, serialization, and poor cluster utilisation.

7. Evaluate professional, governance, security, and operational considerations in distributed analytics.

8. Apply these concepts to the design of scalable data-processing solutions.

From Single-Machine Processing to Cluster Computation

Traditional data processing assumes that one computer can read the data, perform the computation, and write the result. This approach becomes unsuitable when the data cannot fit on one disk or when processing must be completed within a practical time window. A distributed system instead uses a cluster of machines, commonly called worker or executor nodes, coordinated by a control component.

Distributed processing introduces a fundamental trade-off. Parallelism increases capacity and reduces elapsed time, but coordination, network communication, task scheduling, replication, and failure recovery introduce overhead. A good design therefore seeks not merely to use more machines, but to minimise unnecessary communication while keeping the workers productively occupied.

A typical distributed job includes the following logical elements:

• Input data, stored in a distributed file system, object store, database, or message platform.
• A driver or coordinator, which constructs and submits the computation.
• Workers or executors, which perform tasks on partitions of data.
• A scheduler, which assigns tasks and handles dependencies.
• Intermediate data, which may remain in memory, be written locally, or be exchanged across the network.
• Output data, written to durable storage or passed to a downstream system.

The basic unit of parallelism is usually a partition. A partition is a logical subset of a dataset that can be processed by one task. If a dataset has too few partitions, available processors remain idle. If it has excessively many tiny partitions, scheduling and file-management overhead can dominate execution.

The MapReduce Model

MapReduce was developed as a programming model for processing large datasets across clusters. Its value lies in reducing a complex distributed computation to a small number of well-defined operations. The programmer specifies a map function and, usually, a reduce function; the framework manages task placement, intermediate data, retries, and much of the failure handling.

The canonical word-count example illustrates the model. Suppose the input consists of documents. The map function reads each record and emits pairs such as `(word, 1)`. The framework groups all values associated with the same word, producing records such as `(data, [1, 1, 1, ...])`. The reduce function sums each list and emits `(word, total)`.

The principal stages are:

1. Input splitting: Files are divided into input splits that become map tasks.

2. Mapping: Each mapper transforms input records into intermediate key-value pairs.

3. Optional combiner: A local partial aggregation reduces the amount of intermediate data transmitted.

4. Partitioning: Keys are assigned to reducers, commonly using a hash function.

5. Shuffle and sort: Intermediate records are transferred, grouped by key, and sorted or organised for reduction.

6. Reduction: Reducers aggregate values for each key.

7. Output: Results are written to durable storage.

The shuffle is the defining cost centre of many MapReduce jobs. It involves network transfer, disk I/O, sorting, serialization, and coordination. A combiner can reduce traffic, but it must be safe to apply repeatedly and should therefore normally be associative and commutative, like summation or maximum. A combiner is an optimisation, not a replacement for the reducer.

MapReduce is attractive because tasks are generally isolated and intermediate results are materialised. If a task fails, the framework can rerun it. However, repeated materialisation makes iterative algorithms and multi-stage analytics expensive. Algorithms that repeatedly scan the same data, such as many machine-learning procedures, may perform poorly when every iteration reads from and writes to disk.

DAG-Based Execution

A directed acyclic graph represents computation as vertices and directed edges. In a data-processing DAG, vertices commonly represent transformations or stages, while edges represent data dependencies. Acyclic means that execution eventually moves forward; iterative algorithms are represented through repeated job submissions or specialised iterative abstractions rather than cycles in one DAG.

DAG execution separates the logical description of a program from its physical execution. An engine can inspect the entire computation and apply optimisations such as operator fusion, predicate pushdown, projection pruning, partition elimination, and selection of join strategies.

A useful distinction is between narrow and wide dependencies. In a narrow dependency, each output partition depends on a small number of input partitions, often one. Examples include filtering records, selecting columns, and applying a record-wise map. Narrow transformations can usually be pipelined within one stage because they do not require data to move between workers.

A wide dependency occurs when an output partition depends on many input partitions. Grouping by key, joining on a non-partition-aligned key, and global sorting commonly produce wide dependencies. They require a shuffle or an equivalent redistribution of data. The scheduler usually divides a DAG into stages at wide dependencies. Tasks within a stage can execute in parallel, while the next stage waits for the required shuffle data.

DAG-based systems are often more flexible than the original two-step MapReduce abstraction. They can express chains of transformations, interactive queries, graph computations, and iterative algorithms without forcing every logical step to write to durable storage. Nevertheless, DAG execution does not eliminate physical costs. A wide dependency remains expensive, and an apparently simple query may generate substantial network traffic if its partitioning is unsuitable.

Apache Spark as a Distributed Analytics Engine

Apache Spark is a general-purpose distributed processing engine designed to support batch analytics, SQL, streaming, machine learning, and graph processing. A Spark application normally includes a driver program and executor processes. The driver creates the execution plan and coordinates work; executors run tasks and may store cached data.

Spark applications are expressed using abstractions such as Resilient Distributed Datasets (RDDs), DataFrames, and Datasets. An RDD is a fault-tolerant distributed collection partitioned across a cluster. It records lineage: the sequence of transformations used to derive it. If a partition is lost, Spark can recompute it from lineage rather than requiring every intermediate result to be replicated.

DataFrames represent data in named columns and provide a higher-level interface. Spark SQL can analyse a DataFrame query, optimise it, and select physical operators. In many structured-data workloads, DataFrames are preferable to low-level RDD operations because the engine has more information with which to optimise execution. RDDs remain valuable when custom transformations, unstructured records, or fine-grained control are required.

Spark transformations are generally lazy. Operations such as `filter`, `select`, `map`, or `groupBy` build a logical plan but do not immediately execute it. An action, such as `count`, `collect`, `write`, or `save`, triggers execution. Laziness allows Spark to combine operations and avoid work whose result is never used. It also means that errors or expensive computation may not appear until an action is called.

A simplified example in PySpark is:

```python

sales = spark.read.parquet("/lake/sales")

result = (sales

.filter("sale_date >= '2025-01-01'")

.groupBy("region")

.sum("amount"))

result.write.mode("overwrite").parquet("/lake/output/region_sales")

```

The logical operations are reading, filtering, grouping, aggregating, and writing. The physical plan may push the filter into the scan, read only the required columns, perform partial aggregation, and choose a shuffle-based or broadcast join strategy when joins are present.

Partitioning, Locality, and Parallelism

Partitioning determines how records are distributed among tasks. A partitioning strategy should reflect both the structure of the data and the operations performed on it. Hash partitioning distributes records according to a key, while range partitioning assigns ordered key ranges. The former is common for grouping and equality joins; the latter can support ordering and range queries.

Partitioning affects two opposing concerns. More partitions can improve parallelism and reduce the amount of data processed by each task. However, too many partitions create scheduling overhead, small output files, and excessive task setup. Too few partitions cause long-running tasks and underutilised executors. The appropriate number depends on data volume, record size, available cores, workload complexity, and storage performance.

Partitioning can also reduce future shuffles. If two datasets are partitioned compatibly by the same join key, the engine may avoid redistributing both datasets. This benefit must be balanced against the cost of creating and maintaining the partitioning. Partitioning is therefore a workload-design decision rather than a universally beneficial operation.

Data skew is a particularly serious partitioning problem. If one key occurs far more frequently than others, hash partitioning may place a disproportionate amount of data in one partition. Most tasks finish while one task continues processing the dominant key. Techniques for mitigation include salting keys, splitting heavy keys, using broadcast joins where appropriate, adaptive query execution, and designing separate logic for exceptional values.

Shuffling and Join Strategies

A shuffle redistributes records between executors. It is needed when records with the same key must be brought together or when data must be repartitioned for a join or sort. Shuffle data may be written to local disk and transferred across the network, making it sensitive to bandwidth, disk throughput, serialization format, and partition sizes.

Several practices reduce shuffle cost:

• Filter rows and select columns before a shuffle.
• Aggregate locally before transferring data.
• Avoid unnecessary repartitioning.
• Choose an appropriate partition count.
• Use compact, columnar formats such as Parquet for analytical data.
• Inspect query plans rather than assuming that a transformation is inexpensive.

Join strategy is especially important. A broadcast join sends a small relation to each executor so that the large relation does not need to be shuffled. It is efficient when the broadcast relation fits safely within executor memory. A shuffle join repartitions both sides by the join key and is suitable when neither side is small enough to broadcast. A sort-merge join is often used for large relations because it scales better than building a very large in-memory hash table, although it still involves substantial shuffle and sorting.

Broadcasting an incorrectly sized table can cause executor memory pressure or failure. Conversely, refusing to broadcast a genuinely small dimension table can create an unnecessary large-scale shuffle. Join selection should therefore be based on measured data characteristics and execution plans.

Caching, Persistence, and Fault Tolerance

Caching is beneficial when a dataset is reused by multiple actions or branches of a computation. Without caching, Spark may recompute the same lineage each time it is needed. Persistence allows the application to retain partitions in memory, on disk, or in a combined storage level.

Caching is not automatically an optimisation. It consumes memory, may cause eviction of more useful data, and can introduce serialization or spill overhead. Caching a dataset used only once is generally wasteful. The decision should consider recomputation cost, reuse frequency, dataset size, and available memory. Cached data should be explicitly released when it is no longer required.

Spark’s lineage-based recovery differs from full replication of every intermediate result. If a lost partition can be recomputed cheaply, lineage is efficient. If recomputation is extremely expensive or the data is reused over a long period, checkpointing to reliable storage may be appropriate. Checkpointing truncates a long lineage and provides a stable recovery point, but it introduces durable-write overhead.

Fault tolerance also depends on idempotent output design. A failed task may be retried, and a failed application may be restarted. Data pipelines should avoid producing duplicate or partial outputs when retries occur. Transactional tables, temporary output locations followed by atomic commit, and deterministic transformations improve reliability.

Resource Management and Performance Engineering

Distributed performance is a systems problem, not merely a coding problem. Important resources include CPU, executor memory, memory overhead, local disk, network bandwidth, and the number of available cores. Allocating excessive resources to one application can reduce cluster sharing and create long scheduling delays; allocating too little increases spills, garbage collection, and task duration.

A practical optimisation process begins with measurement:

1. Establish a baseline using representative data.

2. Examine the logical and physical plan.

3. Identify the dominant stage or task.

4. Check input size, partition sizes, shuffle volume, spill, executor memory, and task skew.

5. Change one major factor at a time.

6. Re-run the workload and compare both performance and cost.

Common causes of poor performance include repeatedly calling actions that recompute a lineage, collecting large datasets to the driver, using Python-level row functions when built-in expressions are available, producing millions of tiny files, choosing an unsuitable partition count, and caching indiscriminately. The driver should coordinate work, not become a bottleneck by receiving large results.

Columnar storage and compression have a major impact on analytical workloads. Column pruning avoids reading unused fields, while predicate pushdown avoids reading rows that fail a filter. Appropriate file sizes and periodic compaction reduce small-file overhead. These optimisations often provide greater benefit than simply increasing cluster size.

Practical Applications

Batch and distributed processing supports many professional tasks. Retail organisations aggregate transactions by product, store, and time period; banks calculate exposures and detect unusual patterns across historical events; telecommunications companies process call-detail records and network telemetry; manufacturers analyse sensor histories for maintenance planning; and public-sector organisations integrate administrative datasets for planning and service evaluation.

A typical data-lake pipeline may ingest raw files, validate schemas, remove duplicates, standardise fields, enrich records with reference data, aggregate business measures, and publish curated tables. The raw layer supports auditability, the transformed layer supports reuse, and the serving layer supports dashboards or downstream models. Distributed execution makes the transformation feasible, but governance determines whether the results can be trusted.

Spark is also used in feature engineering. Historical transactions can be transformed into customer-level features, such as counts, recency measures, and rolling aggregates. Care is required to prevent data leakage: features used to predict an outcome must be constructed only from information available before the prediction time.

Illustrative Case Study: Processing National Retail Transactions

Background

Consider a fictional retailer, Northstar Stores, operating an online and physical-store business. It receives several terabytes of transaction, product, customer, and inventory data each day. Management requires a daily report of regional sales, product-category performance, returns, and stock-outs.

Situation and Problem

The original pipeline ran on a single database server and frequently exceeded the morning reporting deadline. A direct migration to a distributed cluster produced little improvement because the job created many small files, joined the full transaction table with several reference tables, and grouped by a highly skewed product identifier. Executors also experienced memory pressure when intermediate data was cached indiscriminately.

Analysis

The engineering team examined the Spark UI and physical plans. The largest stage was a shuffle aggregation. One product category represented an unusually large proportion of records, creating a long-running task. The input scan read all columns even though the report needed only nine. A customer dimension was small enough for broadcasting, but the existing plan performed a shuffle join. The pipeline also recalculated the cleaned transaction dataset for three separate outputs.

Approach and Solution

The team adopted the following design:

• Store curated data in partitioned Parquet tables by transaction date and region.
• Select required columns and apply date and validity filters during the initial scan.
• Broadcast the small product and store reference tables after verifying their memory footprint.
• Persist the cleaned transaction dataset because it was reused by several reports.
• Replace a skewed group key with a two-stage aggregation that separates unusually frequent keys.
• Use local partial aggregation before the main shuffle.
• Compact small input files and establish a target range for output file sizes.
• Write results to temporary paths and publish them through an atomic completion step.
• Monitor shuffle bytes, spill, task duration, and output-file counts as operational metrics.

Outcome

The redesigned pipeline reduced unnecessary input reading and avoided two large shuffles. More importantly, its performance became predictable: the formerly dominant task no longer determined the entire job’s completion time. The team also improved recoverability because partial outputs were not exposed as completed reports.

Learning Points

The case demonstrates that distributed processing is not solved by adding machines. Performance depended on storage layout, column selection, join strategy, skew management, persistence, and reliable output handling. It also shows that technical optimisation must be connected to a business deadline and operational quality requirements.

Challenges, Risks, and Common Mistakes

Distributed systems introduce failure modes that are less visible in single-machine programs. Network interruptions, executor loss, disk exhaustion, incompatible schemas, corrupted files, and transient resource shortages can affect execution. Retrying a task improves availability but may increase load on an already stressed cluster.

Common mistakes include treating all transformations as equally expensive, assuming that caching always improves speed, broadcasting data without measuring its size, ignoring skew, using `collect()` on unbounded results, and creating a new output file for every small input fragment. Another error is optimising elapsed time while ignoring cloud cost, energy use, data quality, or reproducibility.

Schema evolution requires explicit policy. A newly added field may be harmless, while a changed data type or renamed column can silently corrupt downstream analysis. Pipelines should validate schemas, record data-quality metrics, and make incompatible changes visible.

Governance, Security, and Professional Responsibility

Distributed data processing often involves personal, financial, health, or commercially sensitive information. Access control should follow least privilege, and encryption should protect data in storage and transit. Sensitive fields may require masking, tokenisation, aggregation, or removal before data is shared with analysts.

Data lineage is important for explaining how a report or model was produced. Systems should record source locations, processing versions, schema changes, execution dates, and quality checks. Retention policies should limit storage of data that is no longer necessary. Audit logs should capture administrative and data-access activity without exposing sensitive values unnecessarily.

Engineers should also consider fairness and representativeness when distributed pipelines prepare data for automated decisions. A technically efficient pipeline can still produce harmful results if it systematically excludes populations, encodes historical discrimination, or permits unauthorised use. Reproducibility, documentation, review, and responsible access are therefore part of professional data engineering.

Current Developments and Best Practices

Modern engines increasingly use adaptive query execution, which can revise aspects of a physical plan after observing runtime statistics. Examples include coalescing shuffle partitions, changing join strategies, and mitigating some forms of skew. Lakehouse technologies add transactions, schema enforcement, time travel, and incremental processing to object-storage architectures.

The boundary between batch and streaming is also becoming less rigid. Many platforms support incremental or micro-batch execution, allowing the same transformations to operate on newly arriving data. Nevertheless, event-time semantics, late data, duplicate events, state management, and exactly-once claims require careful interpretation.

Effective practice can be summarised as follows:

• Design transformations around data locality and minimise wide dependencies.
• Use DataFrame or SQL expressions when their optimiser can improve execution.
• Partition according to access patterns, not habit.
• Measure before and after performance changes.
• Treat shuffle, skew, and small files as first-class operational concerns.
• Cache only reused and expensive intermediate results.
• Keep large data away from the driver.
• Validate schemas and data quality at pipeline boundaries.
• Separate raw, curated, and serving data products where appropriate.
• Make outputs idempotent, auditable, and safe under retries.

Chapter Summary

Batch processing applies computation to bounded datasets, while distributed processing divides data and work across a cluster. MapReduce established a robust key-value programming model based on mapping, shuffling, and reducing, but repeated materialisation can make iterative workloads expensive. DAG-based engines represent dependencies explicitly and can pipeline narrow transformations while placing stage boundaries at wide dependencies.

Apache Spark uses lazy transformations, actions, lineage, RDDs, DataFrames, and a physical execution plan to support scalable analytics. Performance depends heavily on partitioning, data locality, shuffle volume, join strategy, caching, skew management, storage format, and resource allocation. Broadcast joins can avoid large shuffles, whereas unsuitable partitioning and data skew can create bottlenecks. Fault tolerance relies on recomputation, checkpointing when appropriate, and reliable output design.

In professional environments, technical performance must be combined with cost control, data quality, security, privacy, lineage, governance, and responsible use. The best distributed solutions are measured, explainable, operationally reliable, and aligned with the business purpose of the computation.

Key Terms

Batch processing: Execution of computation over a bounded collection of accumulated data.

Distributed processing: Coordinated computation performed across multiple networked machines.

MapReduce: A programming model based on mapping records to intermediate key-value pairs and reducing grouped values.

Mapper: A function or task that transforms input records into intermediate records.

Reducer: A function or task that aggregates values associated with a key.

Shuffle: Redistribution of intermediate data across workers according to keys or partitions.

Combiner: An optional local aggregation step that reduces mapper output before shuffling.

DAG: A directed acyclic graph representing computation and its dependencies.

Narrow dependency: A dependency in which an output partition depends on a limited number of input partitions.

Wide dependency: A dependency requiring data from multiple input partitions, usually involving a shuffle.

Partition: A logical subset of distributed data processed by one task.

Data skew: Uneven distribution of records or keys that causes some tasks to process much more data than others.

RDD: A fault-tolerant, partitioned distributed collection with lineage information.

DataFrame: A distributed table-like data abstraction with named columns and engine-level optimisation.

Lazy evaluation: Delaying computation until an action requires a result.

Caching: Retaining a computed dataset for possible reuse.

Broadcast join: A join that copies a small relation to executors to avoid shuffling the large relation.

Lineage: The record of transformations from which a distributed dataset can be recomputed.

Checkpointing: Writing an intermediate state to reliable storage to provide a recovery point and shorten lineage.

Predicate pushdown: Applying filters as close as possible to the data source to reduce data read.

Review Questions

Short Answer Questions

1. What is the purpose of the shuffle stage in MapReduce?

2. Distinguish between a narrow dependency and a wide dependency.

3. Why does Spark use lazy evaluation?

4. What is data skew, and why does it harm performance?

5. When is caching an intermediate dataset likely to be useful?

Long Answer Questions

1. Explain the complete MapReduce execution process, including the role and limitations of a combiner.

2. Describe Spark’s driver, executor, partition, lineage, transformation, and action concepts and show how they interact during job execution.

3. Compare broadcast joins, shuffle joins, and sort-merge joins, including the conditions under which each is appropriate.

4. Discuss how partitioning, file format, predicate pushdown, and column pruning influence the performance of a batch pipeline.

5. Explain how fault tolerance, checkpointing, idempotent outputs, and schema validation contribute to reliable distributed data processing.

Analytical / Application Questions

1. A Spark job has 2,000 tasks, but one task runs for 40 minutes while the others finish in two minutes. Analyse the likely cause and propose at least three remedies.

2. A daily report repeatedly uses the same cleaned transaction dataset for four outputs. Should the dataset be cached, checkpointed, recomputed, or written to a curated table? Justify your decision using workload and reliability considerations.

3. A large fact table is joined with a dimension table that has grown beyond executor memory. Explain why a broadcast join may no longer be suitable and design an alternative strategy that controls shuffle and skew.

22. Multiple Choice Questions with Answers

Question 1

Which operation most directly causes a wide dependency in a distributed data-processing engine?

A. Filtering records using a row predicate

B. Selecting a subset of columns

C. Grouping records by key

D. Applying a deterministic function to each record

Correct Answer: C. Grouping records by key

Question 2

What is the primary purpose of a combiner in MapReduce?

A. To replace the reducer completely

B. To reduce intermediate data transferred during the shuffle

C. To replicate all mapper outputs for fault tolerance

D. To assign input files to worker nodes

Correct Answer: B. To reduce intermediate data transferred during the shuffle

Question 3

A small dimension table is joined with a very large fact table. Which strategy will usually avoid shuffling the fact table?

A. Broadcast join

B. Global sort before joining

C. Random repartitioning of both tables

D. Writing both tables to separate output files

Correct Answer: A. Broadcast join

Question 4

Why can caching a dataset that is used only once reduce performance?

A. Caching prevents transformations from being executed

B. Caching always forces a global sort

C. It consumes memory and may add persistence overhead without reuse

D. Cached datasets cannot be partitioned

Correct Answer: C. It consumes memory and may add persistence overhead without reuse

Question 5

Which statement best describes Spark lazy evaluation?

A. Spark never executes transformations

B. Transformations build a plan and execution begins when an action is invoked

C. Every transformation is immediately written to durable storage

D. Only streaming applications use delayed execution

Correct Answer: B. Transformations build a plan and execution begins when an action is invoked

Question 6

One key appears in 60 percent of a dataset, causing one task to run much longer than the others. What problem is illustrated?

A. Schema evolution

B. Data skew

C. Predicate pushdown

D. Column pruning

Correct Answer: B. Data skew

Question 7

Which practice most directly reduces the amount of data read from a columnar data source?

A. Calling collect on the driver

B. Selecting only required columns and pushing filters to the source

C. Increasing the number of output files

D. Disabling task retries

Correct Answer: B. Selecting only required columns and pushing filters to the source

Question 8

What is the main recovery mechanism provided by Spark lineage?

A. Recomputing a lost partition from its preceding transformations

B. Sending every record to the driver

C. Broadcasting all intermediate datasets

D. Preventing executor failure entirely

Correct Answer: A. Recomputing a lost partition from its preceding transformations

Question 9

Why are DAG stage boundaries commonly associated with wide dependencies?

A. Wide dependencies require redistribution of data between partitions

B. Narrow transformations cannot be executed in parallel

C. DAGs cannot contain actions after a shuffle

D. Wide dependencies eliminate the need for scheduling

Correct Answer: A. Wide dependencies require redistribution of data between partitions

Question 10

A pipeline creates millions of tiny output files. Which consequence is most likely?

A. Reduced metadata and scheduling overhead

B. Improved compression in every case

C. Excessive file-management and task overhead

D. Automatic elimination of data skew

Correct Answer: C. Excessive file-management and task overhead