Batch Processing · 1 of 1

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.

≈ 30 min

The whole idea

Press ← → to step, or Space to play and pause, whenever a diagram has focus.

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.log 
awk '{print $3}' 
sort 
uniq -c 
sort -rn 
head -n 3 
output of cat access.log8 lines
10.0.0.1 GET /home 20010.0.0.7 GET /cart 20010.0.0.1 GET /home 30410.0.0.9 GET /about 20010.0.0.7 GET /cart 20010.0.0.3 GET /home 20010.0.0.9 GET /pay 50010.0.0.2 GET /home 200
Each program reads lines and writes lines. None of them was written for this task.

Three 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.

≈ 150 sto grep 1 TB on about 1,800 machines in 2004, a minute of it start-up
891 sto sort 1 TB on the same cluster
20 PB / dayprocessed by about 100,000 MapReduce jobs a day at Google by 2008

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

map 1cat,1dog,1cat,1
map 2dog,1emu,1cat,1
map 3emu,1cat,1dog,1
reducer 0waiting for map output
reducer 1waiting for map output
Follow one ‘cat’ from the mapper that emitted it to the reducer that counts it.
  1. 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.
  2. 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.
  3. 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.
  4. 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

Because tasks are deterministic and inputs immutable, ‘run it again’ is always a correct recovery.
  • 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

MapReduce: a chain of jobsDataflow: one job, one graph
The same three steps. Only one of them pays for replicated intermediate files.

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.

up to 20×faster than Hadoop for iterative jobs, reported in the RDD paper (2012)
23 minfor Spark to sort 100 TB on 206 machines in 2014
72 minfor the previous record, Hadoop MapReduce on 2,100 machines

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

sort-merge joinover the network: 0 orders · 0 users
executor 1ordersa·u1b·u3c·u2usersu1u2u3 
executor 2ordersd·u2e·u1f·u1usersnone 
executor 3ordersg·u3h·u2i·u1usersnone 
Count what crosses the network. That's the cost that matters.

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

evenly spread keystask 1task 2task 3task 4task 5task 6task 7task 8stage endstime →other keyshot key
A stage is as slow as its slowest task. Bars show each task's share of the rows.

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())
query planaggregate: sum(amount) by countryfilter ts ≥ 2026-01-01join on user_id
scan events.parquetcolumns: all 40row groups: allscan users.parquetcolumns: all 12row groups: all
columns read: 52 · old row groups: read
The query is written in one order and executed in a better one.
  • 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.

4.2 hfor DuckDB to run TPC-H at scale factor 10,000 (≈ 10 TB) on a laptop, 2025
< 100 GBmedian data stored by heavy BigQuery customers, per a BigQuery founding engineer (2023)
857 s vs 300 sPageRank: Spark on 128 cores vs one laptop thread (COST, 2015)

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() or toPandas() 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

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.

Done with this lesson?

Mark it learned and the concepts it teaches will light up in your galaxy.

Batch Processing: roadmapBack to the roadmap