Batch Processing, Designing Data-Intensive Applications Notes

10.1Chapter Thesis

A dataset that doesn't fit in one machine's memory, or takes too long for one machine's CPU, still needs to be processed completely and correctly. Batch processing solves this by breaking the job into small, independent, re-runnable pieces distributed across many machines - the central design problem is not parallelism itself, but making failure of any one piece cost only that piece's work, not the whole job.

10.2First Principles

Sorting is what makes joins scale past memory

A join between two large datasets can't rely on an in-memory hash table if neither side fits in RAM. Sorting both datasets by the join key and then scanning them in lockstep (a sort-merge join) turns an unbounded-memory problem into a sequential-scan problem, using disk to hold what memory can't - external sorting is the specific mechanism that makes this possible at any scale.

Determinism is what makes re-execution safe

If a worker fails partway through a task, the simplest recovery is to just re-run that task elsewhere. This is only safe if the task is a pure function of its input - no reliance on external mutable state, no side effects beyond its declared output. Batch frameworks enforce this constraint structurally, not by convention, precisely because fault tolerance depends on it.

The shuffle is where all the actual cost lives

Mapping is embarrassingly parallel - each input record is processed independently. The expensive part is the shuffle: grouping all intermediate output by key so that every value for a given key ends up at the same reducer, which requires moving data across the network between every mapper and every reducer.

10.3Mechanism

The map phase transforms each input record independently into zero or more key/value pairs. The shuffle phase groups all emitted pairs by key, regardless of which mapper produced them. The reduce phase receives, for each key, every value ever emitted for it, and combines them into a final result. The correctness of the whole pipeline rests entirely on the shuffle grouping being complete - a reducer only sees a correct answer if every value for its key from every mapper has actually arrived.

10.4Build It Yourself

mini-mapreduce.ts

mapReduce<In, K, V, Out>(
  input: In[],
  mapFn: (item: In) => [K, V][],
  reduceFn: (key: K, values: V[]) => Out
): Map<K, Out> {
  // map: independent, parallelizable per input record
  const emitted = input.flatMap(mapFn);

  // shuffle: explicit grouping-by-key - this is the
  // step that costs network I/O in a real cluster.
  const grouped = new Map<K, V[]>();
  for (const [key, value] of emitted) {
    const list = grouped.get(key) ?? [];
    list.push(value);
    grouped.set(key, list);
  }

  // reduce: one call per key, over every value ever emitted for it
  const result = new Map<K, Out>();
  for (const [key, values] of grouped) {
    result.set(key, reduceFn(key, values));
  }
  return result;
}

// example: word count over log lines
const counts = mapReduce(
  logLines,
  (line) => line.split(" ").map((word) => [word, 1]),
  (_word, values) => values.reduce((a, b) => a + b, 0)
);

Tip

Level 3 (Failure) would re-run mapFn on a subset of inputs and assert the output is byte-identical every time - the property the entire re-execution recovery strategy depends on.

10.5Failure Modes

Condition	Resulting state
A map function has a side effect or reads mutable external state	Re-running it after a worker failure can produce different output the second time, silently corrupting the job's result without any error being raised.
One key has vastly more values than any other (skew)	The reducer handling that key becomes a straggler - the entire job's completion time is bound by that one slow reducer, regardless of how many other reducers finished instantly.
A worker crashes mid-shuffle	Partial output for the tasks it owned may already have been read by downstream reducers; the job must either re-run the entire task from a known-clean checkpoint or track exactly which output was consumed to avoid double-counting.

10.6Tradeoffs

Approach	Benefit	Cost	When it makes sense
Materialize intermediate results to disk (classic MapReduce)	Simple, robust fault tolerance - any stage can be re-run independently	Extra disk I/O between every stage of a multi-stage pipeline	Very large, infrequent batch jobs where robustness matters more than latency
Pipeline intermediate results in memory (Spark/Flink-style)	Much lower latency for multi-stage pipelines	Failure recovery requires re-computing further back through the pipeline	Iterative or multi-stage jobs run frequently enough that latency matters

10.7Production Perspective

Production frameworks (Hadoop MapReduce, Spark) generalize this exact map/shuffle/reduce shape across thousands of machines, adding speculative execution (re-running suspiciously slow tasks on a different machine in parallel, keeping whichever finishes first) specifically to blunt the straggler problem this chapter's failure modes describe.

Batch Processing