Deep Read · DDIA · Chapter 10

Batch Processing

Designing Data-Intensive Applications · Ch 10 · Martin Kleppmann · 2017

What is this chapter about?

The "recommended for you" list on a shopping app, the feed you scroll on a video app, the results Google hands back—behind all of them sits a kind of computation that runs quietly, at its own pace, often overnight: it gathers a whole day's worth of everyone's behavior and, in one big pass, computes "who might like what" and "which word maps to which web pages." This chapter is about that gather-a-big-batch-and-crunch-it-all-at-once kind of work, called batch processing, and its most classic move—MapReduce.

An analogy first

Batch processing is like doing a big load of laundry: you don't wash one shirt the moment it's dirty (that's an "online service," where a click should get an instant reaction). You wait until you have a full basket, then run the machine once—not chasing speed on any single shirt, but chasing "the whole load, done efficiently." It doesn't care whether you wait a second or an hour; it only cares how long the whole batch takes and how much it can chew through per hour.

Why the old world was hard

The hard part is that the data is enormous—too big for one machine's disk to hold, too big for one CPU to ever finish. You have to split the work across thousands of machines working together. But the moment you have a crowd, new headaches appear: how do you hand out the work fairly? What if a machine dies halfway through? Where do the half-finished results go? These "coordinate a swarm of machines" chores are the real source of pain.

The core mechanism, intuitively

The key idea of MapReduce is simply "tally in parallel, then group and total." Picture hundreds of people together counting how many books each author has in a giant library. Step 1 (Map)—each person takes a stack and writes every book onto a little card, "author name → 1." Step 2 (grouping)—line all the cards up by author name and pile them together, so every card for the same author naturally ends up next to each other. Step 3 (Reduce)—each author has one pile; count it and you have their book total. That "line up by name, gather the same-named ones into one pile" step is the heart of the whole machine—it's what lets the same kind of data, scattered across thousands of machines, finally meet up and be totaled.

What it gives you / how to choose

With this "tally then total" trick, engineers can chew through vast data on a pile of cheap machines: build a search engine's index, compute a recommendation list, train a model. Better still, it isn't afraid of failure—the input is read-only, so if a machine botches its share, just recompute that piece on another machine; even human coding mistakes can be fixed and the whole thing re-run cleanly, no lingering damage. One honest cost: it's a slow-and-steady creature by nature—you must wait for the whole batch to finish before you get results, so it only suits offline work that can wait; anything real-time needs the "stream processing" covered next chapter.

Remember one thing

Batch processing = gather a big batch of data and crunch it all at once, optimizing throughput (how much per hour), not speed. The move is MapReduce: tally in parallel (Map) → line up by name to gather like with like → total (Reduce), using "sort-and-gather" to make data from thousands of machines meet. Inputs are read-only and failed pieces just get recomputed—which is why it's so wonderfully tough.

Want the actual mechanisms, join strategies, and diagrams? → Switch to the deep read

In one sentence

This chapter is about batch processing: taking huge data as an immutable input, reading it in bulk, and computing derived results (search indexes, recommendations, reports), optimizing for throughput rather than response time. At its core it carries the old Unix wisdom (small tools + pipes) up onto thousands of machines—MapReduce: you write only map and reduce, and the framework uses one distributed sort to bring like data together. A counter-intuitive line to keep: you'd think the soul of batch processing is "computing fast"—it's actually the calm that "immutable input + determinism" buys you, the calm of "if it goes wrong, just run it again."

Glossary

Batch processing: gather a big batch of data and run it to completion in one pass, with no real-time requirement; its opposites are the "online service" (millisecond responses) and "stream processing" (compute as data trickles in—see next chapter).
Throughput: how much data gets processed per unit time (e.g. TB per hour), batch processing's number-one metric—versus an online service, which watches "response time."
Distributed filesystem (e.g. HDFS / GFS): splits one huge file into blocks, scatters them across hundreds or thousands of machines with several replicas each, yet looks like an ordinary filesystem. HDFS is the open-source counterpart of Google's GFS.
MapReduce: a batch-processing programming model—you write two functions: map (pull out "key→value" pairs from each record) and reduce (aggregate all values for one key); the framework spreads them across thousands of machines.
Key-value pair: one "name → content" record, e.g. (userID, one click). MapReduce shuttles key-value pairs from end to end.
Partition: split data into pieces by some rule (often a hash of the key) and hand each to a different machine to process in parallel.
Join: stitch two datasets together on a shared key, e.g. matching a "user activity log" to a "user profile table" on userID.
Skew / hot key: one key owns disproportionately much data (e.g. a celebrity with millions of followers), overloading one machine and dragging down the whole batch.
Lineage: recording "which inputs, through which operators, produced this piece of intermediate data," so on failure you recompute it rather than relying solely on stored replicas.

Where it sits

This chapter opens Part III, "Derived Data." Part II was about how to correctly store and read across many machines (replication, partitioning, transactions, consensus); Part III turns around and asks how to batch-compute new data from data you already have. The author first splits data systems into three kinds—online services, batch processing, stream processing; this chapter covers batch processing (offline, bounded data), while the next chapter (Ch 11) covers stream processing (unbounded, real-time). The two share one "immutable data + derivation" worldview. In the real world this maps to the Hadoop / Spark ecosystem, data-warehouse ETL, and offline feature and model training.

What problem this chapter solves

Suppose you run a site with hundreds of millions of users and want to do two things: ① sweep 10 TB of access logs every day to compute "how many times each page was visited, which are popular"; ② feed user behavior into a recommender to compute the "for you" list. What these share: the data is too big for one machine to hold or finish, yet it tolerates "run tonight, out by morning"—no real-time demand.

The hard part was never those two lines of counting logic; it's how to command a swarm of machines: how to slice the 10 TB, hand it fairly to a thousand machines to chew in parallel; how, when a machine dies mid-way, to avoid re-running the whole batch; where to put the intermediate scraps, and how to safely replace the old results wholesale with the new. Without solving these, you either hit a single-machine capacity wall, or you write a pile of brittle hand-rolled scripts where one machine crashing loses everything. What this chapter gives you is exactly a general skeleton that standardizes the dirty work—coordinating the fleet, fault tolerance, data flow.

The core, explained

1. The Unix philosophy: batch processing's ancestor

Don't jump to distributed yet. The author starts with a single-machine Unix example: from a web log, find the top 5 most-visited URLs, in one line: awk '{print $7}' access.log | sort | uniq -c | sort -rn | head. awk pulls out the URL column, sort lines them up (identical ones adjacent), uniq -c counts how often each appears, then sort -rn ranks by count descending and head takes the top few.

This pipeline hides three far-reaching design principles (the Unix philosophy, due to Doug McIlroy): ① each program does one thing, well (sort only sorts—but does it superbly, automatically using disk-based merge sort when data exceeds memory); ② one program's output can be another's input (chained with the pipe |); ③ a uniform interface—everyone reads and writes plain text line streams, so any two tools compose. MapReduce is almost the distributed translation of this philosophy: swap "uniform interface = text streams, composition = pipes" for "uniform interface = HDFS files, composition = a chain of jobs."

2. MapReduce: "sort-and-gather" spread over thousands of machines

MapReduce lets you write just two pure functions; the fleet scheduling, fault tolerance, and data shuffling are all handled by the framework:

Map: the framework calls your map once per input record; you pick out and emit some (key, value) pairs. E.g. read one log line, emit (url, 1).
Shuffle (done automatically by the framework): sort all the key-value pairs emitted by mappers by key, and gather all values for one key together—this step moves data across machines and is MapReduce's engine.
Reduce: the framework calls your reduce once per distinct key, handing you the run of values under that key to aggregate. E.g. (url, [1,1,1,…]) → sum → (url, total).

The thing to grasp: "sort by key, gather like keys" is the heart of the model. A mapper partitions its output by target reducer (usually hash(key) mod R, where R is the reducer count), sorts locally, and writes to disk; each reducer then pulls its own partitions from every mapper and merges them—so the same key, scattered across a thousand machines, is guaranteed to meet at one reducer. How big can this go? Open-source Hadoop has sorted data at the petabyte scale on thousands of machines, powered by exactly this mechanism.

Fig 1 · MapReduce data flow: Map emits key-value pairs per record → sort/partition by key → Shuffle moves data across machines so every "same key" meets at one reducer → Reduce aggregates. The sort-and-gather is the whole engine.

A single MapReduce job can only express a simple "one in, one out" transform; real tasks (like a recommender) often chain dozens of jobs into a workflow—one job's output directory becomes the next job's input, orchestrated by schedulers like Airflow or Oozie. A complex flow at Google chained around 50 or more MapReduce jobs.

3. Joins: where batch processing earns its keep

Recommendation and analytics almost always need a join: you have a "user activity log" (who clicked what, huge) and want to stitch on a "user profile table" (age, region, relatively small) to compute "what each age group likes." In batch processing you can't query the profile table remotely, record by record, the way an online database does—hundreds of millions of network round-trips would be glacial and would crush the database. Hence several very different join strategies:

Reduce-side join (sort-merge join): feed both datasets into Map with userID as key; once the framework shuffles, a user's activity records and profile record naturally gather at the same reducer, where you stitch them. The upside is it assumes nothing about the inputs—fully general; the cost is that both datasets must be fully sorted and shuffled, which is expensive.

Map-side join: if the small table (profiles) is small enough to fit in memory, skip the shuffle—a broadcast hash join loads the whole small table into a hash table, copies it to every mapper, and the mapper streams the big table while looking up and stitching, no reduce at all. If both datasets are already partitioned the same way, use a partitioned hash join, where each mapper loads only the matching slice of the small table. Map-side joins are far faster but have strict prerequisites (one side small, or both sides aligned on partitions).

Fig 2 · Two joins: reduce-side is general but needs both sides sorted and shuffled; map-side broadcast hash copies the small table into every mapper's memory and streams the big table, skipping the shuffle—at the cost of the small table having to fit.

The hot-key trap: if one user is a mega-celebrity with a mountain of activity records, the reducer owning that key gets crushed and drags down the whole batch (data skew). The fix is a "sharded / skewed join": randomly split the hot key's records across several reducers to compute in parallel, replicating the other side to match—the same line of thinking as handling hot spots in the partitioning chapter (Ch 6).

4. The philosophy of batch outputs: immutable input + determinism = composure

A batch task's output is usually: building a search index (e.g. generating Lucene inverted-index files for a whole corpus), or bulk-building a key-value store (packaging computed recommendations or ML models into read-only files loaded wholesale into a serving store, like LinkedIn's early Voldemort read-only stores). Here lies the chapter's most important idea, echoing the Unix philosophy directly:

Input is immutable, read-only: a job never modifies its input in place, only writes new output to a new directory. So you can re-run and debug freely, never fearing you'll pollute the source.
Operators are deterministic, side-effect-free: given the same input, the output is necessarily the same, and the job won't secretly mutate a database or send emails. So any failed task can just be recomputed on another machine by the framework (this is also what makes "speculative execution"—launching a backup for a slow task in parallel—possible).
Human fault tolerance: wrote buggy code? Fix it and re-run the whole batch, or just switch back to the previous output—because the old input is still there and the old output was never overwritten. That "roll-back-able" luxury is hard to have in online systems.

In a sentence: cleanly separate "computation logic" from "read/write wiring," keeping the data flow crisp—that discipline is exactly what buys batch systems their trademark toughness and maintainability.

5. Beyond MapReduce: dataflow engines and iterative computation

MapReduce reigned for years, but has one hard flaw: every job writes its full intermediate result back to HDFS (with replicas), and the next job reads it back. A workflow dozens of jobs deep therefore does "write-to-disk, read-from-disk" dozens of times over; worse, a later step must idly wait for the whole earlier step to finish before it can start. This is materialization of intermediate state—robust, but slow and wasteful.

Dataflow engines (Spark, Tez, Flink) treat the entire workflow as one operator graph (DAG) submitted at once, so they can: skip sorting where it isn't needed; skip HDFS and instead pipeline data straight to the next operator (or keep it in memory), with an operator starting the moment it has input. Fault tolerance? No longer "replicate everything," but recompute from lineage—remember how each piece of intermediate data was computed (Spark's RDD lineage), and if it's lost, recompute it (as long as operators are deterministic). In published benchmarks, iterative jobs (computing over the same data for many rounds—ML, graph algorithms) can run an order of magnitude faster than MapReduce by keeping data in memory.

Fig 3 · Materialization vs pipelining: MapReduce writes each intermediate result back to HDFS then reads it out (robust but slow); dataflow engines keep intermediate state in memory / stream it straight to the next operator, tolerating faults via "recompute from lineage."

Two more specializations exist: iterative / graph computation uses the Pregel model (a.k.a. bulk synchronous parallel, BSP)—each vertex sends messages to its neighbors and iterates round by round to convergence, a natural fit for PageRank and shortest-path algorithms that repeatedly sweep a graph. And high-level APIs—nobody wants to hand-write map/reduce daily, so Hive, Pig, Spark SQL, and Flink Table let you write declarative SQL-like queries, with a query optimizer automatically choosing the join algorithm and planning execution (echoing Ch 2's theme, "declarative beats imperative").

Key trade-offs and how to choose

Choosing in batch processing is essentially a trade-off among generality, speed, fault-tolerance cost, and ease of use. Three tables pull out the most-tested, most-useful comparisons.

Table 1 · MapReduce vs dataflow engines (Spark / Tez / Flink)

	MapReduce	Dataflow engine
Intermediate results	Materialized to HDFS (with replicas), repeated disk I/O	Pipelined / in memory, avoids disk where possible
Unit of execution	A pile of independent jobs; later step idly waits for the whole earlier step	One operator graph submitted at once; an operator starts on first input
Fault tolerance	Via replicas of intermediate results; on crash, resume from disk	Via recompute from lineage (needs deterministic operators), or checkpoint on demand
Speed	Baseline; multi-stage workflows dragged by disk writes	Iterative / multi-stage jobs often an order of magnitude faster
Toughness	Extremely robust—a giant job can die mid-way and resume	Long recompute chains get costly; giant jobs need checkpoints as a backstop
Best for	Very large, very long, fault-tolerance-first batch jobs	Iterative (ML / graph), interactive, speed-hungry

Table 2 · How to choose among three join strategies

Strategy	How	Prerequisite	Cost / when to pick
Reduce-side sort-merge	Feed both sides into Map keyed on the join key; after shuffle, same keys gather at one reducer to stitch	None, most general	Full sort + shuffle on both sides, slowest; pick when both sides are big and can't be pre-partitioned
Map-side broadcast hash	Load whole small table into every mapper's memory hash; stream big table, look up and stitch	One side small enough for memory	No shuffle, fastest; first choice for a big-small join
Map-side partitioned hash	Both sides partitioned the same way; each mapper loads only the matching slice	Both sides already partitioned on the join key	Saves memory and skips the shuffle; pick when both tables are already aligned by partition in the pipeline

Table 3 · Three kinds of data system: where batch sits

	Online service	Batch	Stream (Ch 11)
Input	Requests processed as they arrive	Bounded: a fixed big batch	Unbounded: a never-ending event stream
Primary metric	Response time (p99)	Throughput	Throughput + end-to-end latency
Result freshness	Real-time	"Run tonight, out by morning"	Seconds / sub-second
Typical systems	Web services, OLTP databases	Hadoop MapReduce, Spark	Kafka + Flink / Storm

Why it matters / real systems

Batch processing is the bedrock of the whole big-data ecosystem. Google's MapReduce + GFS (two papers, 2003–2004) directly spawned open-source Hadoop (HDFS + MapReduce), turning "chew through PB-scale data on a pile of cheap machines" from Google's secret art into infrastructure anyone can use. From there came Hive (SQL-on-Hadoop), Spark (a dataflow engine), and Flink, layer upon layer; today's data-warehouse ETL, offline feature engineering, and offline training pipelines for recommendation / ads are, at heart, this chapter's ideas. In interviews, "what does MapReduce's shuffle do," "how do you choose between reduce-side and map-side join," and "why is Spark faster than MapReduce" are near-mandatory questions for data roles—and the answers are all in this chapter.

INDUSTRY EVIDENCE · claims from companies' / authors' own published papers

Google, in the MapReduce paper, argued: let engineers write just two functions, map/reduce, and hand parallelization / fault tolerance / data distribution entirely to the framework, and you can process TB–PB data on thousands of cheap machines—founding the whole batch-processing paradigm. J. Dean & S. Ghemawat, "MapReduce", OSDI 2004 ↗
Google itself moved beyond MapReduce: the FlumeJava paper admits "writing chains of MapReduce directly is tedious and hard to optimize," switching to high-level data-parallel pipelines auto-fused and optimized by the framework—the very forerunner of this chapter's "beyond MapReduce, toward dataflow + declarative." Chambers et al., "FlumeJava", PLDI 2010 ↗
Spark (UC Berkeley) used RDDs + recompute-from-lineage to show: keeping intermediate data in memory and tolerating faults via lineage rather than on-disk replicas lets iterative jobs run an order of magnitude faster than MapReduce—validating the value of the "materialization → pipelining" step. Zaharia et al., "Resilient Distributed Datasets", NSDI 2012 ↗

Pitfalls and controversies

"MapReduce = big data" is a dated impression: it pioneered the paradigm, but because of repeated disk writes and weak expressiveness, in most scenarios it's now displaced by dataflow engines like Spark / Flink—even Google turned to successor systems long ago. Learn it for the ideas, not as tech to ship.
Treating the shuffle as trivial: beginners think the bottleneck is the map/reduce logic; in fact the shuffle (cross-machine sort and transfer) is often the most expensive part, and where data skew (hot keys) most easily explodes.
Picking the wrong join: when one side is small enough to fit in memory yet you use a reduce-side sort-merge, you pay for a whole extra round of sort and shuffle for nothing—a big-small join should prefer broadcast hash.
Thinking batch can do real-time: it's bounded and latent by nature (you wait for the whole batch). "Compute as data trickles in" needs stream processing (Ch 11). The two are complementary, not substitutes—the famous Lambda architecture tried to use both batch and stream at once, but drew criticism for maintaining two sets of logic.
Period limits: this chapter was written in 2017; since then cloud object storage (S3) has displaced self-hosted HDFS, Spark / Flink have matured further, and unified batch-stream (Flink, and data lakes like Iceberg / Delta) has become the new trend—yet the "immutable input + derived result" worldview holds up to this day.

Takeaways

① One sentence: batch processing = read in a bounded, immutable mountain of data in bulk and compute derived results, optimizing throughput, not speed.

② Three kinds of system: online service (watches response time), batch (watches throughput), stream (unbounded, real-time)—this chapter is batch, next is stream.

③ The idea is rooted in the Unix philosophy: small tools that do one thing well + pipe composition + a uniform interface; MapReduce is its distributed translation.

④ MapReduce = Map (emit key-value pairs per record) → sort/shuffle by key (the engine) → Reduce (aggregate per key); the same key always meets at one reducer.

⑤ Three joins: reduce-side sort-merge (general, slowest), map-side broadcast hash (big-small, fastest), partitioned hash (both sides same partitioning); hot keys are tamed by a sharded join.

⑥ The soul is immutable input + deterministic operators + no side effects → recompute on failure, roll-back-ability, human fault tolerance all flow from this.

⑦ Beyond MapReduce: dataflow engines (Spark/Tez/Flink) shift intermediate state from materialized-to-disk to pipelined / in-memory + recompute-from-lineage, iterative jobs an order of magnitude faster; plus Pregel (graphs) and high-level declarative APIs (Hive/Spark SQL).

⑧ In practice: Google MapReduce/GFS → Hadoop → Hive/Spark/Flink, propping up the whole data warehouse and offline pipeline; a high-frequency interview topic.