Batch Processing
Take a pile of data that has stopped changing, run a pure function over all of it on as many machines as you like, and replace the old answer. From Unix pipes to MapReduce to Spark and DataFrames, how bulk computation works, and where it hurts.
The whole idea
What batch processing is
Most of the systems in earlier lessons are online: a request arrives, and someone is waiting for the answer. Latency is the measure that matters. A batch job is the other kind. It takes a large, bounded input, a day’s logs or last night’s database snapshot, runs a computation over all of it, and produces an output. Nobody waits on it interactively; it runs for minutes or hours, often on a schedule, and the measure that matters is throughput: how much data per hour, at what cost.
Batch jobs build search indexes and recommendation features, train and score ML models, compute daily reports, reconcile payments, and turn raw event logs into the warehouse tables from the analytics lesson. They have one property that makes them unusually easy to reason about: the input doesn’t change while the job runs, and a job only reads its input and writes a new output. That makes a batch job a pure function from input to output, which is what makes everything else in this lesson possible: parallelism without locks, and failure recovery by simply running a piece again.
The Unix philosophy
The design ideas behind batch processing are older than any cluster. In 1978 Doug McIlroy, who proposed the Unix pipe, and his co-authors wrote down the maxims Unix builders had settled on, starting with:
Make each program do one thing well. To do a new job, build afresh rather than complicate old programs by adding new “features.”
Expect the output of every program to become the input to another, as yet unknown, program.
A shell pipeline is a batch job on one machine. Here’s a classic: find the most requested pages in a web server’s log.
Six small tools, one job
cat access.log8 linesThree ideas make this work, and every distributed batch system has inherited them:
- A uniform interface. Every program reads and writes a stream of lines, so any program can feed any other. In distributed systems the uniform interface became files in a distributed file system, and later self-describing columnar files like Parquet.
- Logic separated from wiring. awk doesn’t know where its input comes from or where its output goes; the shell decides. The same programs can be recombined for a new question in seconds.
- Immutable inputs, experimental workflow. Running the pipeline never changes
access.log, so you can run it, look at the output, tweak a stage and run it again. You can stop at any stage and inspect what it emits.
The approach also scales further than it looks. sort handles inputs bigger than memory by sorting chunks,
spilling them to disk and merging them. In 1986 Jon Bentley asked Donald Knuth to write a program printing the k
most frequent words in a text; Knuth wrote a careful literate program with its own data structure.
McIlroy’s review replied with six piped commands (tr, tr, sort, uniq -c, sort -rn, sed) that, he
noted, “worked on the first try”. The limit is that a pipeline runs on one machine.
MapReduce
In 2004 Jeff Dean and Sanjay Ghemawat published MapReduce, Google’s answer to running that pipeline over thousands of machines. You write two functions and the framework does everything else:
- map(record) → (key, value) pairs. Called once per input record, independently. It extracts what you care about, like awk.
- reduce(key, values) → output. Called once per key, with every value emitted for that key, like
uniq -c.
Between them the framework does what sort did: it brings all values for a key together, across machines. The
input lives in a distributed file system (GFS at Google, HDFS in Hadoop), split into chunks (16 to 64 MB in Google’s 2004 setup; Hadoop defaults to the 128 MB HDFS block). The scheduler starts one map task per split, preferably on a machine that already stores a replica of it,
so that the computation moves to the data instead of the data moving to the computation.
Hadoop brought the model to everyone else. Doug Cutting and Mike Cafarella split its distributed file system and MapReduce out of the Nutch search engine in 2006, and Yahoo became its biggest user: in 2010 Yahoo engineers reported Hadoop clusters spanning 25,000 servers and 25 PB of data, the largest a single 3,500-server cluster. Hadoop 2 later separated cluster resource management into YARN, so engines other than MapReduce could share the same machines.
The shuffle
The step between map and reduce, the shuffle, is where most of a batch job’s cost and most of its failure modes live. It’s a distributed sort.
Inside the shuffle
- Each map task partitions its output into R buckets, one per reducer, usually by
hash(key) mod R. Every occurrence of a key goes to the same bucket number on every mapper. - It sorts each bucket by key and writes it to its own local disk, spilling and merging if the output doesn’t fit in memory.
- Each reducer fetches its bucket from every mapper: M × R transfers in total, which is why shuffles are network-heavy and why the number of reducers matters.
- The reducer merges the sorted runs and calls reduce once per key, with all of that key’s values.
That is how Hadoop and Spark do it. Google’s original sorted on the reduce side instead: mappers only partitioned their output, and each reducer sorted what it fetched, with an external sort if it didn’t fit in memory. Either way, the shuffle is a distributed sort.
A combiner cuts the traffic: a mini-reduce that runs on the mapper’s output before it’s sent, so a mapper
ships (cat, 2) instead of two (cat, 1) pairs. It only works for operations that can be applied in parts,
like sum, count or max.
At scale, the shuffle is the bottleneck. LinkedIn found that blocks in its Spark shuffles averaged only tens of kilobytes, read billions of times a day, and that around 15% of its Spark compute was wasted waiting on shuffle I/O. Its fix, push-based shuffle (Magnet, VLDB 2020), has mappers push blocks to remote services that merge them into large per-reducer files. It shipped in Spark 3.2, and by 2021 it served all of LinkedIn’s roughly 15 to 18 PB of daily shuffle data.
Surviving failure
With thousands of machines, something fails during almost every large job; Google’s August 2004 statistics average more than one worker death per job. MapReduce’s answer is not to prevent failure but to make re-execution cheap and correct.
Dead workers and stragglers
- Dead workers. The master pings workers. When one stops answering, its tasks are rescheduled, including completed map tasks, because their output was on the dead machine’s local disk. Completed reduce output is already in the replicated file system and stays.
- Stragglers. A job finishes only when its last task does, and one sick machine can hold everyone up. The paper’s example is a disk with correctable errors that slowed reads from 30 MB/s to 1 MB/s. Near the end of a job, the master launches backup copies of the remaining in-progress tasks and marks the task done as soon as either copy finishes. On its terabyte sort, disabling backups made the job 44% slower; killing 200 of 1,746 workers mid-sort slowed it by only 5%.
- Atomic output. A reduce task writes to a temporary file and atomically renames it on success, and the master ignores a second completion of a map task, so a task that ran twice still produces exactly one output.
This only works if tasks are deterministic and free of side effects outside their output. A mapper that calls an external API, or reads the clock, or picks random numbers without a fixed seed, can produce different output on rerun, and the “exactly one output” guarantee silently breaks.
Dataflow engines
MapReduce has a rigid shape: one map, one shuffle, one reduce. Real pipelines are dozens of steps, so they became chains of jobs, each writing its full output to the distributed file system, three-way replicated, before the next could start. Google’s own FlumeJava paper (2010) reported one pipeline of 207 MapReduce stages that its optimizer fused into a single stage.
Chained jobs vs one dataflow graph
Dataflow engines (Dryad, Tez, Apache Spark, Apache Flink) treat the whole pipeline as one directed acyclic graph of operators. Seeing the whole graph lets them:
- Fuse steps that don’t need a shuffle (map, filter, parse) into a single pass, a stage.
- Keep intermediate data in memory or on local disk, not replicated in the distributed file system.
- Sort only when needed, and choose join strategies based on the data.
Spark’s core abstraction, the resilient distributed dataset (RDD; Zaharia et al., NSDI 2012), made fault tolerance cheap without replicating intermediates. Each dataset records its lineage: which operator produced it from which parents. If a partition is lost, Spark recomputes just that partition from its parents. Operations split into narrow dependencies, where each input partition feeds at most one output partition (map, filter), so steps can be pipelined and recomputed locally, and wide ones, where an input partition feeds many output partitions, which needs a shuffle. Spark cuts stages at the wide ones and keeps shuffle output on local disk, so a lost task re-reads it instead of replaying history.
Google moved on too. FlumeJava’s deferred, optimised pipelines replaced hand-written MapReduce chains internally, and, with the MillWheel streaming system, led to Cloud Dataflow and Apache Beam. In 2014 Urs Hölzle told the Google I/O audience that Google didn’t really use MapReduce any more. Hadoop the project lives on (version 3.5.0 shipped in April 2026), but Cloudera and Hortonworks, its two main vendors, merged in January 2019, and most new batch work runs on Spark, often on Kubernetes and object storage rather than YARN and HDFS. Pinterest, for one, has been moving its Hadoop batch platform onto Spark on Kubernetes.
Joins at scale
Joining two large datasets is the most common expensive thing a batch job does: enrich events with user attributes, match orders to payments, attach features to training examples. In a cluster, the problem is locality. Rows that match on the join key usually live on different machines.
Two ways to join
The three strategies every engine has:
- Sort-merge join (reduce-side join): shuffle both inputs by the join key, sort each partition, and merge them like a zipper. It works for any sizes and spills gracefully, but it shuffles both sides. It’s Spark’s default for large equi-joins.
- Broadcast hash join (map-side join): if one side is small, copy it whole to every executor, build an
in-memory hash table from it, and stream the big side past it in place. No shuffle of the big side at all.
Spark broadcasts automatically when a side is under
spark.sql.autoBroadcastJoinThreshold, 10 MB by default. - Shuffle hash join: shuffle both sides, then build a hash table from the smaller side of each partition instead of sorting. It skips the sort but needs each partition’s build side to fit in memory.
A fourth trick avoids the shuffle by planning ahead: bucketing. If both tables were written partitioned and sorted by the join key into the same number of buckets, matching rows are already co-located, and the join is a local merge.
Choosing between them needs the sizes of the inputs after filters, which an optimizer often guesses wrong before the job runs. Spark’s adaptive query execution (AQE), on by default since Spark 3.2, re-plans at each shuffle boundary using real statistics: it converts a sort-merge join into a broadcast join when one side turns out to be small, coalesces many tiny post-shuffle partitions into fewer, and splits skewed ones. Databricks reported up to 8× speed-ups on TPC-DS queries when it was introduced.
Data skew
Hash partitioning spreads keys evenly. It does not spread rows evenly. If one key is far more common than the rest, every row for it lands in one partition, and that task does all the work.
One hot key
Skew is the batch version of a hot spot, and the usual culprits are predictable: a NULL or empty-string key, a
default like user_id = 0, a bot or test account, a celebrity, one giant customer. Symptoms are distinctive: a
stage stuck at 199 of 200 tasks for an hour, one executor spilling gigabytes or dying of out-of-memory errors,
and the rest of the cluster idle. Facebook engineers described joins in which non-skewed partitions finished in minutes to a few hours while skewed ones took hours to days, and skew could delay hundreds of downstream pipelines.
The fixes, roughly in the order you should reach for them:
- Filter the junk. If the hot key is NULL, drop or handle those rows separately; they often don’t join to anything.
- Broadcast the small side, if there is one. A broadcast join has no shuffle, so a hot key can’t pile up on one reducer.
- Let AQE split it. Spark treats a join partition as skewed when it’s over 5× the median partition and over 256 MB, splits it into several tasks and replicates the matching partition of the other side.
- Salt the key by hand: append a random suffix 0..N−1 to the hot key on the big side, and replicate the other side’s matching rows N times, once per suffix. The hot key’s rows now spread over N tasks. For aggregations, aggregate per salted key first, then combine.
- Pre-aggregate with a combiner or a two-phase group-by, so the hot key’s millions of rows become one partial result per mapper before the shuffle.
DataFrames
Writing map and reduce functions by hand is low-level. Most batch code today uses a DataFrame: a table of
named, typed columns with operations like select, filter, join, group-by and aggregate. The model comes from
R’s data.frame; Wes McKinney started pandas in 2008 to bring it to Python, and Spark added a DataFrame API
in 2015, inspired by both.
The important difference between DataFrame engines is eager vs lazy. pandas runs each operation the moment you call it, so a filter written after a join runs after the join. Spark’s DataFrames and Polars’ lazy API instead record each call into a logical plan and run nothing until you ask for a result. That lets an optimizer rewrite the plan exactly like a SQL query planner does.
What a lazy plan buys you
events = pl.scan_parquet("events/*.parquet") users = pl.scan_parquet("users.parquet") (events.join(users, on="user_id") .filter(pl.col("ts") >= date(2026, 1, 1)) .group_by("country") .agg(pl.col("amount").sum()) .collect())
- Predicate pushdown moves filters as close to the data as possible, into the scan, where Parquet’s row-group statistics skip data without reading it.
- Projection pushdown reads only the columns the query uses, the columnar storage win.
- Join reordering, constant folding, common-subplan elimination and the rest of the optimizer toolkit.
On an aggregation benchmark in the Spark SQL paper, the DataFrame version beat hand-written RDD code by 2× in Scala and 12× in Python, mainly because the plan runs as generated JVM code: no per-record object allocation, and no calls into Python per record.
The other big shift is how much fits on one machine. A laptop now has a dozen cores and tens of gigabytes of RAM, and a cloud VM has hundreds of cores and terabytes. DuckDB (an in-process, vectorized analytic SQL engine; 1.0 in June 2024) and Polars (a Rust DataFrame engine built on Arrow’s columnar layout; 1.0 in July 2024) exploit that with columnar, multi-threaded execution and spilling to disk.
The honest lesson of the last decade: distributed processing has a large fixed cost in coordination, serialization and shuffles. McSherry, Isard and Murray’s 2015 paper “Scalability! But at what COST?” found that a single laptop thread beat several published graph-processing systems running on 128 cores. Reach for a cluster when the data or the compute truly doesn’t fit one machine, not before.
What batch jobs produce
The output of a batch job is usually not a report someone reads. It’s data that another system serves:
- Search indexes, the original MapReduce use case: Google rebuilt its web index with a sequence of MapReduce jobs.
- Derived tables for a warehouse or lakehouse: cleaned, joined, aggregated facts.
- Features and models for machine learning, and the scores they produce, bulk-loaded into a key-value store that online services query.
- Compacted data: merging change logs into current-state tables, the job Amazon began moving from Spark to Ray in 2024.
The rule for all of them: don’t write into a live database from inside the job, one record at a time. Thousands of tasks making network calls swamp the database, and a retried task writes twice. Instead, write complete new output files (or a new table snapshot), then switch readers over atomically. A failed or wrong run leaves the old output untouched, and the job stays idempotent.
Trade-offs
| Unix pipeline | MapReduce | Dataflow engine (Spark, Flink) | Single-node (DuckDB, Polars) | |
|---|---|---|---|---|
| Scale | one machine | thousands of machines | thousands of machines | one big machine |
| Intermediate data | pipes, memory | replicated files between jobs | memory and local disk | memory, spill to disk |
| Fault tolerance | rerun everything | rerun failed tasks | recompute lost partitions from lineage | rerun the query |
| Programming model | text streams | map and reduce functions | DataFrames, SQL, operators | DataFrames, SQL |
| Fixed overhead | none | high (job start-up, disk) | moderate | very low |
| Join strategy | Moves over the network | Memory needed | Best when |
|---|---|---|---|
| Sort-merge | both sides | small (streams) | both sides large |
| Broadcast hash | small side × executors | whole small side per executor | one side small (≤ 10 MB by default in Spark) |
| Shuffle hash | both sides | build side per partition | sides similar, partitions fit in memory |
| Bucketed | nothing | small | tables pre-bucketed on the join key |
In the real world
- Google ran about 29,000 MapReduce jobs in August 2004 and about 100,000 a day by 2008, processing over 20 PB daily, before replacing it internally with FlumeJava and Dataflow.
- Yahoo ran Hadoop on tens of thousands of servers by 2010, which made it the default for big data across the industry for a decade.
- LinkedIn built push-based shuffle for Spark: its paper reported nearly 30% shorter runtimes for production jobs, and after rollout, 16% less compute overall.
- Amazon’s Business Data Technologies team runs a compaction job that merges change-data inserts, updates and deletes into current tables. In 2024 Amazon wrote that, for the tables it had started moving from Spark to Ray, Ray gave 82% better cost efficiency per GiB, on over 1.5 EiB of Parquet input in one quarter, worth more than $120 million a year at on-demand prices. The same post is candid that Ray’s first-attempt job success rate (99.15%) was still below Spark’s (99.91%).
Pitfalls
- Non-deterministic tasks. Random numbers without a fixed seed,
now(), or external calls inside a map make retries and speculative backups produce different results. Keep tasks pure. - Side effects from inside the job. Writing to a database or calling an API per record turns retries into duplicates and the job into a denial-of-service attack. Write files, then publish.
- Ignoring skew. “199 of 200 tasks done” for an hour is skew, not slowness. Look at the partition-size distribution before adding machines.
- Too few or too many partitions. Spark’s default of 200 shuffle partitions is wrong for both a 1 GB and a 100 TB job; AQE coalescing helps, but set it deliberately for big jobs.
- Collecting to the driver.
collect()ortoPandas()on a large DataFrame pulls everything onto one machine and kills it. - Small files. Thousands of tiny output files slow every downstream reader. Repartition or compact before writing.
- Defaulting to a cluster. If the data fits on one machine, DuckDB or Polars will usually be faster, cheaper and simpler.
Recall
Go deeper
- Dean & Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters” (OSDI 2004): the model, the shuffle, failure handling and backup tasks, with real cluster numbers.
- Zaharia et al., “Resilient Distributed Datasets” (NSDI 2012): lineage, narrow vs wide dependencies, and why Spark doesn’t replicate intermediates.
- Chambers et al., “FlumeJava” (PLDI 2010): deferred evaluation and stage fusion, the idea behind Beam, Dataflow and lazy DataFrames.
- Armbrust et al., “Spark SQL” (SIGMOD 2015): the Catalyst optimizer, and why DataFrames beat hand-written RDD code.
- Spark SQL performance tuning: join strategies, broadcast thresholds and adaptive execution, with every default.
- Shen, Zhou & Singh, “Magnet: Push-based Shuffle Service” (VLDB 2020): what actually goes wrong in a shuffle at petabytes a day.
- McSherry, Isard & Murray, “Scalability! But at what COST?” (HotOS 2015): a short reality check on scaling out.
- Amazon’s exabyte-scale migration from Apache Spark to Ray (AWS, 2024): a rare migration write-up with real costs and honest caveats.
Keep going
The atomic notes for this lesson live in the knowledge graph:
Next on the map: Message Brokers & Logs and Stream Processing, where the input is unbounded and never stops arriving.