Lesson 10: Batch Processing

Lesson 0010 — 50 min read

Part III shifts from theory to practice. Chapters 5–9 built the distributed systems vocabulary (replication, partitioning, transactions, failure models, consensus). Now we see how real systems actually crunch data at scale. Chapter 10 covers batch processing — the oldest form of computation, from punch cards to MapReduce to Spark.

The central insight: batch processing turns the distributed systems nightmare on its head. Instead of worrying about individual request latencies, you treat the cluster as a single machine that reads input, runs a deterministic job, and writes output. The framework handles partitioning, fault tolerance, and scheduling — your code is just a pure function over records.

The Three System Types

Kleppmann gives us a clean taxonomy. Every data system falls into one of three categories:

The web (and HTTP/REST in general) has made the request/response model so dominant that we forget the other two. But batch processing is how Google built its search index, how LinkedIn computes "People You May Know", how Netflix generates recommendations, and how every credit card company detects fraud overnight.

Batch Processing with Unix Tools

Kleppmann starts with a deceptively simple example: analyzing an nginx access log. A single log line looks like:

216.58.210.78 - - [27/Feb/2015:17:55:11 +0000] "GET /css/typography.css HTTP/1.1" 200 3377 "http://martin.kleppmann.com/" "Mozilla/5.0 ..."

To get the five most popular URLs:

cat /var/log/nginx/access.log |
  awk '{print $7}' |
  sort             |
  uniq -c          |
  sort -rn         |
  head -n 5

This chain of Unix commands — awk, sort, uniq -c, sort -rn, head — processes gigabytes of logs in seconds on a single machine. It's the prototype for MapReduce. The key insight: sort is the workhorse that brings related data together. uniq -c then counts adjacent duplicates — which is exactly what a reducer does.

Sorting vs In-Memory Aggregation

The Ruby equivalent keeps a hash table in memory: counts[url] += 1. Which is better? It depends on the working set (number of distinct keys):

• Small distinct keys: in-memory hash table wins — fast, simple, linear scan.
• Large distinct keys (bigger than RAM): sort-based approach wins — GNU sort automatically spills to disk using mergesort (same pattern as LSM-Trees from Chapter 3), and parallelizes across CPU cores.

The Unix Philosophy

The Unix pipe model is the conceptual ancestor of MapReduce. Four principles from Doug McIlroy (1964):

1. Do one thing well. sort is a better sorting implementation than most language standard libraries (it spills to disk, uses multiple threads).
2. Expect output to become input. Don't clutter output. Avoid binary formats.
3. Build quickly, iterate, throw away clumsy parts. Sounds like Agile/DevOps decades before they had names.
4. Use tools over unskilled help. Automate everything.

Uniform Interface — Files and ASCII Text

In Unix, everything is a file descriptor — a sequence of bytes. An actual file, a pipe, a device driver (/dev/audio), a TCP socket — they all share the same interface. This is what makes composition possible.

By convention, records are separated by \n (newline). Fields are split by whitespace. This is ugly but universal — it's why awk, sort, and head can interoperate even though they're written by different people.

Contrast with today: you can't pipe your email into a spreadsheet and post the result to a social network. Data balkanization is the norm, not the exception.

Separation of Logic and Wiring

A Unix program reads stdin and writes stdout. It doesn't know or care where input comes from or output goes to. This is loose coupling / inversion of control. The shell user wires things up.

Transparency and Experimentation

Four properties make Unix tools great for exploration:

• Immutable inputs — you can rerun with different options safely.
• Inspect at any stage — pipe to less anywhere in the pipeline.
• Materialize intermediate stages — write output to a temp file and restart the later stage without re-running everything.
• No side effects — the program produces output; it doesn't modify input or talk to external systems.

The biggest limitation: Unix tools run on a single machine. Hadoop/MapReduce extends this model to thousands of machines.

MapReduce and Distributed Filesystems

MapReduce is Unix tools, distributed. A MapReduce job is like a Unix process: it takes immutable inputs, produces outputs, and has no side effects. The key difference: instead of stdin/stdout, MapReduce reads and writes files on a distributed filesystem — HDFS (Hadoop Distributed File System, an open-source implementation of Google File System / GFS).

HDFS Architecture

HDFS scales to tens of thousands of machines with hundreds of petabytes. The key to scale: data is stored on the same machines that process it — computation near data (also called locality optimization). If erasure coding is used, locality advantage is lost because data from multiple machines must be combined to reconstruct a file.

MapReduce Job Execution

A MapReduce job has four steps, which exactly mirror our Unix pipeline:

1. Input format — break input files into records (e.g., lines in a log file).
2. Mapper — extract key + value from each record. Stateless callback. Called once per record. Produces any number of KV pairs (including zero).
3. Shuffle + Sort — the only thing the framework does automatically. Partitions by key (hash of key → reducer partition), sorts by key, merges. This is the sort step from our Unix pipeline, now distributed.
4. Reducer — called once per key with an iterator over all values for that key. Produces output records.

Distributed Execution Details

• Map tasks — one per input file block (typically 128–256 MB). Framework tries to run each mapper on a machine that stores a replica of the input block (data locality).
• Reduce tasks — configurable number (not tied to input size). All KV pairs with the same key go to the same reducer via hash partitioning.
• Shuffle — each mapper writes sorted output files to local disk, partitioned by reducer. Reducers then fetch (pull) their partitions from each mapper. This is the bottleneck in most MapReduce jobs.
• Merge — reducer merges the sorted files from all mappers into a single sorted stream, then calls the reducer function.

MapReduce Workflows

A single MapReduce job is rarely enough. For the "top 5 URLs" example:

• Job 1: count page views per URL (mapper: extract URL, reducer: sum counts)
• Job 2: sort by count descending, take top 5 (mapper: swap key/value, reducer: take top N)

Jobs are chained via directory names in HDFS. Job 1 writes to /output/intermediate/, Job 2 reads from it. This is materialization — writing intermediate state to durable storage. It's like Unix pipes writing to temp files instead of using in-memory buffers.

Workflow schedulers (Oozie, Azkaban, Luigi, Airflow, Pinball) manage dependencies between jobs. Complex workflows (e.g., LinkedIn's recommendation system) use 50–100 MapReduce jobs per run.

Reduce-Side Joins and Grouping

MapReduce has no indexes — it does full table scans. For analytic queries over large datasets, this is acceptable (and often desirable, since sequential I/O is fast). But it means joins must be implemented differently than in an OLTP database.

Sort-Merge Join

The classic reduce-side join. Example: joining user activity events with user profiles.

1. Mapper sets — two sets of mappers extract user ID as key:
• Activity events mapper: key = user ID, value = event data
• User profiles mapper: key = user ID, value = profile (e.g., date of birth)
2. Shuffle + Sort — all records with the same user ID are sent to the same reducer and sorted by key.
3. Secondary sort — arrange records so the profile comes first, then events in timestamp order. The reducer can then store the profile in a local variable and iterate over events.
4. Reducer — outputs (viewed_url, viewer_age) pairs. Subsequent jobs can compute age-group distributions.

Key insight: mappers "send messages" to reducers. The key is the destination address. All messages with the same key arrive at the same reducer. This separates physical network communication from application logic — the application never deals with partial failures, retries, or network issues.

GROUP BY / Sessionization

Same mechanism as a join, but only one input dataset. Use cases:

• Counting records per group (COUNT, SUM)
• Sessionization — group all activity events for a user by session ID to reconstruct the sequence of clicks. Used for A/B testing, funnel analysis, marketing attribution.

Handling Skew (Hot Keys)

The "all same key → same reducer" pattern breaks for hot keys (linchpin objects, e.g., a celebrity with millions of followers). One reducer gets swamped while others sit idle. Solutions:

• Skewed join (Pig) — sample first to find hot keys. For join input, send hot key records to random reducers. Replicate the other input to all those reducers.
• Sharded join (Crunch) — same idea, but hot keys specified explicitly.
• Hive skewed join — store hot key records in separate files; use map-side join for those.
• Two-stage aggregation — first stage sends hot key records to random reducers (partial aggregation), second stage combines per-key results.

Map-Side Joins

Reduce-side joins are general but expensive (sorting + shuffling + merging). If you can make assumptions about the input, map-side joins avoid the reduce phase entirely. Each mapper reads one input file block and writes one output file — no sorting, no shuffling.

Broadcast Hash Join

The simplest map-side join. One input must be small enough to fit in memory on each mapper machine. The mapper loads the small input into a hash table, then scans the large input and looks up each record.

• Broadcast — every mapper reads the entire small input.
• Hash — uses an in-memory hash table for lookups.
• Supported by Pig (replicated join), Hive (MapJoin), Cascading, Crunch.
• Alternative: store small input in a local read-only index (PalDB) — almost as fast as an in-memory hash table, without requiring the data to fit in memory.

Partitioned Hash Join (Bucketed Map Join)

Both inputs are partitioned the same way (same key, same hash function, same number of partitions). Each mapper loads only its partition of the small input. This allows larger inputs than a broadcast join, because each mapper loads less data.

Map-Side Merge Join

Both inputs are partitioned and sorted the same way. The mapper reads both inputs incrementally (like merging two sorted lists) and produces the join output. No hash table needed — works for arbitrarily large inputs.

The Output of Batch Workflows

Why run all these jobs? Batch output is usually not a report for humans. It's data for other systems.

Search Indexes

Google's original use case for MapReduce. A workflow of 5–10 MapReduce jobs builds the inverted index: mappers extract terms from documents, reducers build postings lists. The output is an immutable set of index files. To update: rerun the entire workflow (or use incremental indexing with Lucene segment files).

Key-Value Stores as Output

Batch jobs often build databases: recommendation models (people you may know), classifiers (spam filters), related products.

Don't write to an external database from inside a mapper/reducer! Three problems: (1) network overhead kills throughput; (2) parallel writes overwhelm the target database; (3) partial job failures leave externally-visible side effects, breaking the all-or-nothing guarantee.

Correct approach: build the database files themselves inside the batch job and output them to HDFS. Then load them in bulk into a read-only serving layer (Voldemort, Terrapin, ElephantDB, HBase bulk loading). The files are immutable once written. Voldemort atomically switches: copy new files to serving nodes, then swap in one operation. If anything fails, old files are still there.

Philosophy of Batch Output

Batch processes follow the Unix philosophy:

• Immutable inputs — you can rerun safely.
• New output replaces old output entirely — no partial writes.
• No side effects — the job only writes to its output directory.

This enables human fault tolerance: if you deploy buggy code that produces wrong output, you roll back the code and rerun. You don't need to "fix the data" as you would with a database that has read-write transactions. This makes Agile development of data pipelines feasible — mistakes aren't irreversible.

Comparing Hadoop to Distributed Databases

MapReduce wasn't new — MPP databases (Teradata, Gamma, Tandem NonStop SQL) had parallel join algorithms a decade earlier. The differences:

Diversity of Storage: The Data Lake

Hadoop's "dump data first, model later" approach is called the data lake (or enterprise data hub). It's the opposite of the careful schema-on-write of traditional data warehouses. The sushi principle: "raw data is better."

This shifts the burden of interpretation from producer to consumer (schema-on-read). It enables ETL: dump transactional data into HDFS, then MapReduce jobs clean and transform it into relational form for an MPP data warehouse.

Diversity of Processing Models

SQL can't express everything: machine learning feature engineering, natural language models, image analysis, recommendation algorithms. MapReduce gave engineers the ability to run arbitrary code over large datasets. This led to an explosion of processing models on top of the same HDFS data: Hive (SQL), HBase (random access), Impala (MPP-style), Spark (in-memory), Flink (streaming), Mahout (ML), Giraph (graphs) — all accessing the same files. This is the Hadoop ecosystem's killer feature.

Designing for Frequent Faults

Why is MapReduce so eager to write to disk and so tolerant of task failures?

At Google, MapReduce tasks run at low priority in mixed-use datacenters. Production services and batch jobs share machines. If a higher-priority task needs resources, a low-priority batch task can be preempted (killed) at any time. A task that runs for an hour has ~5% risk of being preempted. A 100-task job with 10-minute tasks has >50% chance of at least one preemption.

Key insight: MapReduce's design is optimized for frequent task termination caused by resource overcommitment, not hardware failures. This allows better cluster utilization by "picking up scraps under the table."

Beyond MapReduce

MapReduce is robust but slow — especially because of materialization of intermediate state: every job writes to HDFS and the next job reads it back. This has three problems:

1. Straggler delay — all tasks in the first job must complete before the second job starts. One slow task holds up the entire pipeline.
2. Redundant mappers — the next job's mapper is often just re-reading what the previous reducer just wrote and re-partitioning.
3. Over-replication — intermediate state is replicated 3x in HDFS, but it's temporary data that will be discarded.

Dataflow Engines (Spark, Tez, Flink)

Dataflow engines fix materialization by treating the entire workflow as one job, with explicit DAGs of operators. They're like Unix pipes (streaming intermediate data through memory or local disk) instead of Unix temp files.

Fault Tolerance in Dataflow Engines

Since intermediate state isn't in HDFS, failures require recomputation. Spark uses RDDs (Resilient Distributed Datasets) — an abstraction that tracks the lineage (how each partition was computed). If a partition is lost, it's recomputed from the original input or a prior checkpoint.

Determinism matters: operators must be deterministic for correct recovery. Non-deterministic sources (random numbers, system clock, hash table iteration order) must be handled carefully. Nondeterminism cascades — if a restored operator produces different output, downstream operators must also be killed and re-run.

Graphs and Iterative Processing

Many graph algorithms (PageRank, shortest paths, transitive closure) are iterative: they repeat until convergence. MapReduce can't express this efficiently — it would read the entire input dataset on every iteration, even if only a small part changed.

Pregel (BSP Model)

The Bulk Synchronous Parallel model (popularized by Google's Pregel paper) is designed for iterative graph processing. Implementations: Apache Giraph, Spark GraphX, Flink Gelly.

• Think like a vertex: a function is called for each vertex with messages sent to it in the previous iteration. The vertex sends messages along its edges.
• Supersteps: iterations are synchronized — all messages from superstep N are delivered in superstep N+1.
• Stateful: vertices remember state across iterations (unlike mappers, which are stateless per record).
• Fault tolerance: checkpoint all vertex state at the end of each superstep. If a node fails, roll back to the last checkpoint.

Caveat: graph algorithms often have high network overhead (message passing). If a graph fits on a single machine, a single-threaded algorithm will likely outperform a distributed Pregel job. The COST (Configuration that Outperforms a Single Thread) paper makes this point forcefully.

High-Level APIs and Languages

Raw MapReduce is too laborious (you implement join algorithms from scratch). Higher-level APIs emerged:

• Pig — dataflow scripting (Latin-like syntax)
• Hive — SQL on Hadoop (declarative queries → MapReduce jobs)
• Cascading / Crunch / FlumeJava — Java dataflow APIs
• Spark DataFrames / Flink Table API — declarative APIs with cost-based optimizers

The trend is toward declarative query languages. Cost-based optimizers choose join algorithms automatically (sort-merge v/s broadcast hash v/s partitioned hash). Declarative operators enable columnar storage optimizations (Parquet) and vectorized execution (tight inner loops over CPU cache-friendly data).

Meanwhile, MPP databases are becoming more flexible (user-defined functions, support for ML libraries like MADlib). The two worlds are converging.

Summary: What to Remember

Chapter 10 builds a bridge from Unix pipes to distributed batch processing. The key ideas:

1. Distributed batch processing = Unix philosophy at scale. Immutable inputs, deterministic computation, composable jobs, no side effects.
2. Partitioning brings related data together. Sorting is the mechanism; the framework handles it.
3. Fault tolerance is the framework's job. Your code is a pure function over records — the framework retries, recovers, and guarantees exactly-once output.
4. MapReduce is a learning tool, not the final answer. Dataflow engines (Spark, Flink, Tez) fix its materialization overhead and provide more flexible operators.
5. Batch output is not for humans. It builds databases, search indexes, and ML models — immutable artifacts consumed by other systems.
6. The Hadoop v/s MPP divide is narrowing. Batch engines add declarative SQL optimizers; MPP databases add flexibility. Both end up in the same place.

Quiz

Select the correct answer for each question.

Notes

Primary source: Kleppmann, M. (2017). Designing Data-Intensive Applications, Chapter 10: “Batch Processing.” O'Reilly Media.
Recommended supplements: Dean & Ghemawat's original MapReduce paper (OSDI 2004), the Hadoop: The Definitive Guide (Tom White), the Spark paper (Zaharia et al., NSDI 2012), the COST paper (McSherry et al., HotOS 2015), the Pregel paper (Malewicz et al., SIGMOD 2010), and the FlumeJava paper (Chambers et al., PLDI 2010).

Ask follow-up questions to drill into: how HDFS NameNode handles metadata at scale, the exact format of the shuffle (partition, sort, spill, merge), how Spark RDD lineage enables fault recovery, why Pregel supersteps act as global barriers, the difference between at-most-once/at-least-once/exactly-once in batch processing, or how the sushi principle ("raw data is better") actually plays out in production data lakes.