Batch Data Processing

Introduction

Batch data processing transforms a bounded collection of data through a planned sequence of computations. Unlike stream processing, which reacts continuously to arriving events, batch processing operates on data accumulated over a defined interval or on a complete historical dataset. It remains fundamental in data engineering because organizations routinely need to produce daily reports, rebuild analytical tables, train machine-learning models, reconcile transactions, and compute historical aggregates.

Modern batch systems must process data that may be terabytes or petabytes in size. A single-server program is usually inadequate because of limited storage, memory, processing capacity, and fault tolerance. Distributed batch engines divide data and computation across many machines, execute tasks in parallel, recover from failures, and write results to durable storage.

This chapter examines three closely related ideas: the MapReduce computation model, directed acyclic graph (DAG) execution, and Apache Spark. It then develops the engineering techniques required for efficient joins, aggregations, partitioning, caching, memory management, and compute utilization.

Learning Objectives

After completing this chapter, a learner should be able to:

1. Explain the architecture and execution logic of distributed batch processing.
2. Compare MapReduce, DAG-based execution, and Apache Spark.
3. Design pipelines containing transformations, shuffles, joins, and aggregations.
4. Select suitable partitioning, join, caching, and serialization strategies.
5. Diagnose data skew, excessive shuffling, memory pressure, and inefficient task utilization.
6. Evaluate batch pipelines using correctness, performance, cost, reliability, and governance criteria.

1. Foundations of Distributed Batch Processing

A batch job normally follows this pattern:

1. Read immutable or versioned input data.
2. Parse and validate records.
3. Transform records into an intermediate representation.
4. Repartition data when required by a computation.
5. Join, group, sort, or aggregate records.
6. Write durable output.
7. Record metadata, quality results, and operational metrics.

A distributed batch system separates logical computation from physical execution. The developer specifies transformations, while the engine decides how to distribute tasks, place them on workers, retry failed work, and materialize intermediate data.

Important terms include:

• Driver or coordinator: Process that constructs the execution plan and coordinates workers.
• Worker or executor: Process that performs computation on partitions.
• Partition: A logical subset of a dataset processed by one task at a time.
• Task: A unit of work scheduled on one worker.
• Stage: A set of tasks separated from another stage by a data redistribution boundary.
• Shuffle: Network exchange that redistributes records according to keys or ordering requirements.
• Lineage: A record of transformations from input data to a derived result.
• Materialization: Writing an intermediate or final result to storage.

For a dataset containing N records divided among P balanced partitions, the ideal computational work per partition is approximately:

Here, W_p is the number of records assigned to a partition. This approximation assumes uniform record sizes and balanced partitioning. In practice, processing time depends on record size, computation complexity, serialization, I/O, and data skew, so equal record counts do not guarantee equal task durations.

A simplified lower-bound model for elapsed execution time is:

The terms represent input reading, local computation, network redistribution, output writing, and scheduling or coordination overhead. The expression is not an exact performance law; it is a diagnostic model. Several components may overlap, and the actual time is often dominated by the slowest parallel stage rather than by a simple sum.

2. The MapReduce Model

MapReduce expresses a computation through two central functions. The map function transforms each input record into zero or more intermediate key–value pairs. The reduce function combines all values associated with the same key.

For input record x, a mapper produces:

The system then groups intermediate pairs by key and invokes the reducer:

The grouping phase is commonly called the shuffle and sort phase. It is essential because all values for a key must be brought together before reduction.

Word-count example

Suppose the input consists of documents. The mapper emits (word,1) for every word. The shuffle groups all values by word, and the reducer sums them:

The summation is over all occurrences of the word. A combiner can perform local partial sums before the shuffle, reducing network traffic. A combiner must be safe for repeated and partial application; addition is suitable because it is associative and commutative.

Strengths and limitations

MapReduce offers simple fault recovery, scalability, and a clear programming model. Intermediate results can be materialized, allowing failed tasks to be recomputed from durable data. However, repeated materialization makes iterative algorithms and multi-step pipelines expensive. A job containing many dependent MapReduce stages may read and write the same data repeatedly.

MapReduce is especially suitable for large, linear transformations, durable batch workflows, and environments where predictable fault recovery is more important than interactive latency. It is less suitable for algorithms requiring repeated access to the same intermediate dataset, such as iterative graph analysis or machine learning.

3. DAG Execution and Apache Spark

A directed acyclic graph represents computations as vertices and dependencies as directed edges. Acyclicity means that execution eventually progresses toward completion rather than returning to an earlier operation. A batch pipeline can therefore be represented as:

Figure: A simplified DAG showing local transformations followed by a shuffle boundary.

A narrow dependency occurs when each output partition depends on a small number of input partitions. Filtering and many map operations are narrow. A wide dependency occurs when an output partition depends on many input partitions, as in grouping by key or joining on a key. Wide dependencies usually require a shuffle and define stage boundaries.

Apache Spark uses DAG scheduling to optimize a sequence of transformations. Common abstractions include:

• RDD (Resilient Distributed Dataset): An immutable, partitioned collection with lineage-based recovery.
• DataFrame: A distributed table with named columns and schema information.
• Dataset: A typed distributed abstraction available in selected Spark language APIs.
• Transformation: Lazy operation that creates a new dataset, such as filter, select, or join.
• Action: Operation that triggers execution, such as count, collect, or write.

Spark transformations are lazy. The engine can inspect the complete logical plan before execution, eliminate unnecessary work, push filters toward data sources, select efficient join strategies, and combine compatible operations. DataFrames and SQL generally permit more optimization than untyped low-level operations because the engine understands their schemas and expressions.

Spark does not mean that all data remains in memory. It may use memory, disk, or a combination depending on storage level and available resources. Persisting data can improve repeated access, but caching is not automatically beneficial.

4. Stages, Tasks, and Scheduling

A scheduler converts a DAG into stages. A stage generally contains operations that can execute without a shuffle. When a shuffle is required, the preceding stage produces partitioned intermediate data and the following stage fetches it.

The number of tasks in a stage is related to the number of input or shuffle partitions. Too few partitions underuse the cluster and create large tasks. Too many partitions increase scheduling, serialization, and file overhead. A practical target depends on data volume, cluster size, and task complexity; therefore, partition counts should be measured rather than copied from a universal rule.

The slowest task often determines stage completion. If task durations are t₁, t₂, …, tₙ, the stage's final task completion time is approximately:

This explains why a job may show most tasks complete while one task continues for a long time. The cause may be skew, a slow host, garbage collection, or an unusually large partition.

5. Partitioning and Data Locality

Partitioning determines where records reside. A hash partitioner assigns a key to a partition using a hash function. Conceptually:

where k is the key and P is the number of partitions. A range partitioner assigns records according to ordered key ranges and is useful for sorted outputs and range queries. Hash partitioning is usually effective for equality joins and aggregations, while range partitioning can support ordering but requires careful boundary selection.

Two datasets with the same partitioner and compatible partition count may be joined with less data movement. This is called partitioner compatibility. Repartitioning is expensive because it generally causes a shuffle.

Partitioning must also account for skew. If one key appears far more frequently than others, hash partitioning sends most records for that key to one partition. Techniques include:

• salting hot keys with a controlled random or bucket suffix;
• processing exceptionally frequent keys separately;
• using a broadcast join when one side is small;
• increasing parallelism only when the workload can actually be divided;
• using adaptive query execution where supported.

Salting requires a two-step aggregation. The first step aggregates by (key,salt), and the second removes the salt and aggregates by the original key. This adds complexity and must preserve correctness.

6. Aggregations and Joins

Aggregations

A full group operation transfers every value to a reducer. A more efficient aggregation uses local combiners or map-side aggregation. For an associative and commutative operation ⊕:

and

Local partial results can be combined safely before the global aggregation. Sum, count, minimum, and maximum meet these conditions. Average requires care because independently averaging averages is generally incorrect unless weighted by group counts. A correct distributed average maintains sum and count, then computes:

For a group with values x₁ through xₙ, the mean is:

The denominator must be the total number of observations.

Join strategies

A join combines records according to a matching key. Important strategies include:

A broadcast join sends a small relation to workers holding partitions of the large relation. It avoids shuffling the large dataset, but the broadcast object must fit within safe executor memory on every worker. “Small” is therefore relative to available memory, concurrent tasks, serialization overhead, and object representation.

For an inner join, only matching keys are returned. A left outer join retains every record from the left side and adds nulls when no right-side match exists. Engineers must explicitly choose join semantics; changing an inner join to a left join can materially alter counts and downstream decisions.

Many-to-many joins can produce unexpectedly large outputs. If a key has m records on one side and n on the other, that key can produce m × n output pairs. This multiplication is a major source of data explosion. Before joining, profile key cardinalities and determine whether duplicate records should be removed or aggregated.

7. Memory, Serialization, and Compute Utilization

Distributed engines manage several memory demands: execution memory for sorting and joins, storage memory for cached data, user objects, shuffle buffers, and operating-system overhead. A job can fail even when the input file is modest because in-memory objects may be substantially larger than their serialized representation.

Best practices include:

• select only required columns before joins;
• filter early, provided the predicate is correct;
• use compact, columnar formats such as Parquet for analytical workloads;
• choose compression according to CPU and storage trade-offs;
• avoid repeatedly converting between inefficient object representations;
• prefer built-in SQL functions over row-by-row user-defined functions when possible;
• release or unpersist datasets no longer needed;
• avoid collecting distributed data to the driver.

A rough utilization measure is:

Both terms must refer to the same interval and same resource scope. High CPU utilization does not prove that a job is efficient; it may reflect expensive serialization or redundant computation. Low utilization may indicate I/O waits, insufficient parallelism, skew, or a bottleneck outside the CPU.

Serialization affects network traffic and memory. A compact binary format often performs better than verbose text, but compatibility, schema evolution, and debugging requirements must also be considered. Columnar formats store values by column and can enable projection and predicate pushdown, reducing bytes read.

8. Caching and Persistence

Caching is valuable when the same derived dataset is reused by multiple downstream actions or iterative stages. It is usually wasteful when a dataset is read once, when recomputation is cheaper than storage, or when the cache displaces more useful data.

A rational caching decision compares:

This is a qualitative decision model rather than a precise accounting identity. The costs should include CPU, network, disk, memory, latency, and operational complexity.

Caching does not guarantee permanence. Cached partitions may be evicted or recomputed, depending on the storage level. If a result is an important recovery boundary or a product consumed by other systems, write it to durable storage with appropriate metadata rather than relying only on cache.

9. Reliability, Correctness, and Data Governance

Distributed batch jobs fail because of machine loss, corrupt records, network interruptions, executor memory exhaustion, software defects, and external-system errors. Reliable pipelines use deterministic transformations, idempotent output procedures, checkpointing or durable intermediate results where appropriate, retries, and clear failure handling.

An idempotent operation can be safely repeated without creating an incorrect additional effect. A common design is to write output to a temporary location, validate it, and atomically publish a versioned result. This avoids exposing a partially written dataset.

Data quality checks should include schema validation, null-rate thresholds, uniqueness constraints, referential integrity, record counts, range checks, and reconciliation against trusted totals. A useful reconciliation relationship is:

This identity applies only when categories are mutually exclusive and collectively exhaustive. The pipeline should document exceptions and late-arriving data.

Governance concerns include access control, encryption, retention, lineage, auditability, data minimization, and protection of personally identifiable information. Batch outputs may be copied into warehouses, feature stores, and reports; therefore, access permissions must follow the data rather than ending at the initial storage layer.

10. Worked Example: Daily Retail Sales Pipeline

Assume a retailer receives 240 million sales records each day. Each record contains transaction ID, customer ID, product ID, store ID, timestamp, quantity, unit price, and status. The objective is to produce daily revenue by store and product category.

First, invalid records are rejected: missing transaction IDs, negative quantities where not permitted, unknown products, and malformed timestamps. Valid records are filtered to the business date and joined with a product dimension containing product category.

The design is:

1. Read only required columns from columnar storage.
2. Filter by date and valid status.
3. Broadcast the product dimension if its serialized size fits safely in executor memory.
4. Compute line revenue:

The units are, for example, items × currency/items = currency.

1. Aggregate by store and category using local partial aggregation.
2. Write partitioned output by business date, with controlled file sizes.
3. Publish quality metrics and a versioned success marker.

If the product dimension is too large for safe broadcasting, both datasets should be repartitioned by product ID and joined through a shuffle-based strategy. If one store is responsible for a disproportionately large share of sales, store-level skew should be measured. A hot store may require specialized salting or separate processing.

Suppose a group contains quantities 2, 3, and 5 sold at a unit price of 10 currency units. Its revenue is:

This calculation assumes the same unit price applies to all three records. If prices differ, each line must be multiplied separately before summation.

The pipeline should be tested with duplicate transactions, missing products, late records, currency changes, and reruns. A rerun for the same business date should replace or reconcile the previous version rather than append a duplicate result.

11. Illustrative Case: Detecting a Slow Daily Pipeline

Background. A financial institution's regulatory report normally completes in 45 minutes but recently requires four hours.

Problem. The scheduler shows that 95% of tasks finish quickly, while a small number run for a long time. Executor logs also show high shuffle spill and garbage collection.

Analysis. Key-frequency profiling reveals that a small number of corporate accounts generate most transactions. Hash partitioning sends these hot keys to a few reducers. The job also joins a large transaction table with a customer table using a generic repartitioned join, although the customer table is small enough for controlled broadcasting.

Approach. Engineers first filter columns and records before the join, broadcast the dimension after measuring serialized size, and use map-side partial aggregation. They then isolate exceptionally hot accounts and apply a two-stage salted aggregation. Partition counts are adjusted after examining task size and cluster capacity. The output is written to a temporary versioned location and published only after reconciliation checks pass.

Outcome. The dominant long-tail tasks disappear, shuffle volume falls, and the report returns to an acceptable completion window. More importantly, the team adds key-skew monitoring and a regression benchmark to prevent recurrence.

Learning points. Performance tuning should begin with evidence from the execution plan, task distribution, shuffle metrics, and data profiles. Increasing cluster size alone may not solve a skewed or poorly planned computation. Correctness controls must remain active during optimization.

12. Contemporary Developments and Best Practices

Current batch platforms increasingly combine declarative SQL, adaptive query execution, cost-based optimization, columnar storage, elastic clusters, and open table formats supporting schema evolution and transactional updates. Adaptive systems can change join strategies, coalesce partitions, and mitigate skew using runtime statistics. These features improve resilience but do not eliminate the need for data modeling and observability.

AI can assist with anomaly detection in task durations, automatic query-plan recommendations, and prediction of resource requirements. Such recommendations must be validated because training data may reflect historical bias, changing workloads, or incomplete cost information. Human review remains necessary for regulated data and material business decisions.

A professional batch engineering checklist is:

• define input and output contracts;
• choose formats and partition columns based on access patterns;
• minimize data before wide transformations;
• inspect the physical execution plan;
• measure partition sizes and key skew;
• select joins using size, cardinality, and memory evidence;
• cache only reused datasets;
• control output file counts and sizes;
• make retries and reruns safe;
• monitor data quality, cost, latency, and resource utilization;
• document lineage, ownership, retention, and access controls.

Chapter Summary

Batch processing applies bounded data transformations at scale. MapReduce provides a durable map–shuffle–reduce model, while DAG engines represent multi-stage computations and optimize dependencies. Apache Spark uses lazy evaluation, lineage, distributed partitions, and optimized DataFrame or SQL plans to execute batch workloads efficiently.

Narrow transformations generally preserve partition locality; wide transformations require shuffles and often create stage boundaries. Partitioning, aggregation strategy, join selection, memory management, serialization, and caching strongly affect performance. Broadcast joins are useful for safely small dimensions, whereas large relations commonly require partitioned or sort-merge joins. Skew can dominate elapsed time even when average resource utilization appears healthy.

Reliable pipelines are deterministic, observable, rerunnable, and governed. They validate schemas and data quality, protect sensitive information, publish outputs atomically, and measure both technical and business outcomes. Effective optimization is evidence-based: inspect plans, profile data, identify bottlenecks, apply the least complex improvement, and verify correctness after every change.

Key Terms

MapReduce: A distributed programming model based on map, shuffle, and reduce phases.

DAG: A directed acyclic graph representing computation dependencies.

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

Task: A unit of computation scheduled on a worker.

Stage: A group of operations separated from another group by a shuffle boundary.

Shuffle: Network redistribution of records among partitions.

Narrow dependency: A dependency in which an output partition reads limited input partitions.

Wide dependency: A dependency requiring records from multiple input partitions.

RDD: An immutable, partitioned, fault-tolerant distributed collection.

DataFrame: A distributed dataset organized into named columns and a schema.

Lineage: The transformation history used to reconstruct derived data.

Broadcast join: A join that replicates a small relation to workers.

Sort-merge join: A join strategy that partitions and sorts both relations by key.

Data skew: Uneven distribution of records or keys across partitions.

Combiner: A local pre-aggregation operation that reduces shuffle volume.

Caching: Retaining a derived dataset for possible reuse.

Serialization: Encoding objects for storage or network transfer.

Idempotence: The property that repeating an operation does not create an incorrect additional effect.

Predicate pushdown: Applying filters near the data source to reduce data read.

Columnar storage: A format that stores values by column to support efficient analytical access.

Review Questions

Short Answer Questions

1. What is the purpose of the shuffle phase in MapReduce?
2. Distinguish between a narrow dependency and a wide dependency.
3. Why can a broadcast join reduce network traffic?
4. What is data skew, and how can it affect task completion time?
5. Why is caching not automatically beneficial in a batch pipeline?

Long Answer Questions

1. Explain MapReduce execution from input reading through reduce output, including the role of combiners.
2. Describe how Apache Spark converts a logical DAG into stages and tasks.
3. Compare broadcast, partitioned hash, sort-merge, and bucketed joins.
4. Discuss memory, serialization, caching, and partition-count decisions in a large batch job.
5. Explain how correctness, idempotence, data quality, and governance should be integrated into batch engineering.

Analytical / Application Questions

1. A join contains a very small product dimension and a multi-terabyte sales table. Recommend a join strategy and identify the operational conditions that must be verified first.
2. One reducer processes 40% of all records while the remaining reducers finish quickly. Diagnose the likely cause and propose two technically different remedies.
3. Design a rerunnable daily revenue pipeline. Specify its transformations, aggregation strategy, output-publication method, quality checks, and metrics for evaluating success.

Multiple Choice Questions with Answers

Question 1

Which phase groups all intermediate values associated with the same key in MapReduce?

A. Input validation

B. Shuffle and sort

C. Final output publication

D. Driver initialization

Correct Answer: B. Shuffle and sort

Question 2

Which operation normally creates a wide dependency?

A. Filtering records

B. Selecting columns

C. Joining records by key

D. Parsing a timestamp

Correct Answer: C. Joining records by key

Question 3

A broadcast join is most appropriate when:

A. Both datasets are larger than executor memory

B. One dataset is safely small enough to replicate to workers

C. The join has no key

D. The output must be globally sorted

Correct Answer: B. One dataset is safely small enough to replicate to workers

Question 4

If a dataset has 120 records and is evenly divided into 6 partitions, the ideal records per partition are:

A. 12

B. 20

C. 60

D. 720

Correct Answer: B. 20

Question 5

Which property is required for safe local pre-aggregation with a simple combiner?

A. The operation must be associative; commutativity is also generally needed for arbitrary order

B. The operation must always produce text

C. The operation must require global sorting

D. The operation must be performed only at the driver

Correct Answer: A. The operation must be associative; commutativity is also generally needed for arbitrary order

Question 6

What is the main risk of collecting a large distributed dataset to the driver?

A. Reduced schema visibility

B. Driver memory exhaustion

C. Automatic data encryption

D. Elimination of all shuffles

Correct Answer: B. Driver memory exhaustion

Question 7

For values 4, 6, and 10, what is the arithmetic mean?

A. 5

B. 6

C. 20/3

D. 10

Correct Answer: C. 20/3

Question 8

Which technique directly addresses a highly frequent hot key?

A. Salting the key and performing a second aggregation

B. Removing all partitioning

C. Collecting the complete dataset to the driver

D. Disabling validation

Correct Answer: A. Salting the key and performing a second aggregation

Question 9

Why are DataFrame or SQL plans often easier for Spark to optimize than arbitrary row-level code?

A. They expose schema and relational expressions to the optimizer

B. They never use memory

C. They eliminate the need for workers

D. They guarantee zero network traffic

Correct Answer: A. They expose schema and relational expressions to the optimizer

Question 10

Which design best supports safe reruns of a daily batch output?

A. Appending blindly to the same unmanaged directory

B. Writing to a temporary versioned location, validating, and atomically publishing

C. Ignoring duplicate transaction IDs

D. Writing only to executor memory

Correct Answer: B. Writing to a temporary versioned location, validating, and atomically publishing