Batch Processing

Fullscreen

Because inputs are immutable and there are no side effects, a buggy run is fixed by rolling back the code and rerunning (object stores and open table formats support time travel), a property called human fault tolerance that read/write databases lack. Batch jobs run for minutes to days, are often scheduled periodically, and are measured by throughput. Their natural home is data integration / ETL.

History: MapReduce (Google, 2004) drove the "big data" movement and was implemented in Hadoop, CouchDB, MongoDB, but it's a low-level model, now largely obsolete (no longer used at Google). Today batch runs on Spark, Flink, and cloud warehouse engines (BigQuery, Snowflake); orchestration moved from Oozie/Azkaban to Airflow, Dagster, Prefect; storage moved from HDFS to object stores (S3).

---

Batch Processing with Unix Tools

The classic example: find the five most-requested URLs in an NGINX access log.

Fullscreen

It processes gigabytes in seconds, is trivially modifiable, and composes via pipes. A Python equivalent is readable too, but the deeper difference is the execution model.

Sorting vs in-memory aggregation. The Python script keeps an in-memory hash table (working set = number of distinct URLs). The Unix pipeline sorts instead. If the working set fits in memory, the hash table wins; if it's larger than memory, sorting wins because it can spill to disk and use sequential access (mergesort). GNU sort automatically spills to disk and parallelizes across cores, so the pipeline scales to large datasets, bottlenecked only by disk read rate. Unix tools' limit: a single machine, which is where distributed frameworks come in.

---

Batch Processing in Distributed Systems

A distributed batch framework is a distributed operating system with the same components as the single-machine pipeline.

Fullscreen

Distributed filesystems

A local filesystem layers: block device drivers → page cache → filesystem (inodes/dirs; ext4/XFS) → VFS (common API). A DFS mirrors this:

Fullscreen

Larger blocks mean less metadata (critical at petabyte scale) and lower seek overhead; partial last blocks are allowed (a 900MB file = seven 128MB blocks + one 4MB block). Data nodes expose a daemon that serves blocks; the page-cache equivalent caches hot blocks. The S3 API is a de facto standard (MinIO, R2, Tigris, B2); POSIX access via FUSE/NFS (EFS, Archil). DFSs are shared-nothing (commodity machines + ordinary network), unlike shared-disk NAS/SAN (custom appliances, Fibre Channel).

Object stores

Fullscreen

Listing by prefix behaves like a recursive ls -R; deleting all children makes the "directory" vanish (hence zero-byte placeholder objects). Object stores optimize for large, less-frequent reads (vs key-value stores' small, frequent ones), though S3 Express One Zone now offers single-ms latency. The big architectural difference: object stores separate storage from compute (more bandwidth, but independent scaling) while HDFS offers data locality (run compute where the data lives).

Distributed job orchestration

Fullscreen

The orchestrator (Kubernetes, YARN) is the distributed OS kernel. Resource allocation is hard: gang scheduling can leave nodes idle or deadlock; waiting for capacity risks starvation; preemption wastes work by killing tasks. Optimal allocation is NP-hard, so schedulers use heuristics.

Scheduling workflows. Output of one job feeds others → a workflow / DAG of jobs (here "workflow" means a chain of batch jobs, distinct from the RPC durable-execution workflows of Ch. 3). Like Unix pipes (which apply backpressure via a small buffer), Spark/Flink can pass output task-to-task; but more commonly a job writes to the DFS and the next reads from there (decoupling, run at different times). Per-job schedulers (YARN, Spark) don't manage whole DAGs, workflow schedulers (Airflow, Dagster, Prefect) do, and 50-100-job workflows are common.

Handling faults. Long jobs with many tasks will hit failures (hardware, network, or deliberate preemption of low-priority spot/preemptible instances, cheaper but killed more often). Because batch jobs regenerate output from scratch, a failed task's partial output is discarded and the task retried elsewhere, at task granularity (not whole-job). For intermediate data between stages: MapReduce writes it to the DFS (safe but I/O-heavy); Spark keeps it in memory (spilling to local disk) and recomputes from lineage if lost; Flink uses periodic checkpointing.

---

Batch Processing Models

MapReduce

Fullscreen

Four steps: read+split records (input format parser; Parquet/Avro on HDFS/S3), map (your code: extract key-value per record, stateless, parallel), sort by key (implicit, the framework's job), reduce (your code: iterate all values for a key). Need a second sort? Chain a second job. The model comes from functional programming (map/reduce/fold); avoiding mutable state is what enables parallel execution and safe retries. Downsides: the raw API is laborious (joins coded from scratch) and slow (file-based I/O prevents pipelining).

Dataflow engines (Spark, Flink)

Fullscreen

Dataflow engines model the entire workflow as one job with flexible operators (join, group-by, filter, aggregate) beyond strict map/reduce alternation. Based on Dryad/Nephele, their advantages: sort only where needed, fuse consecutive same-sharding operators, exploit locality, keep intermediate state in memory, pipeline (start before the previous stage finishes), and reuse processes (no per-task JVM).

Shuffling data

Fullscreen

A shuffle is the distributed sort that underlies joins and aggregations; "shuffle" is a misnomer, it produces sorted, not random, order. Number of map tasks = number of input shards; number of reduce tasks is configurable.

Joins and grouping

Fullscreen

A sort-merge join: both sides are mapped to the same key (user ID), the shuffle co-locates them, and the reducer joins them, keeping only one user record in memory and making no network requests. Secondary sort arranges the DB record to arrive first. A second job then shuffles by URL to group and aggregate.

Query languages and DataFrames

• SQL is the lingua franca of batch processing now (warehouses used it; analysts know it; enables interactive/exploratory querying). Query engines (Hive, Trino, Spark, Flink) compile SQL → operators with cost-based optimizers that pick join algorithms and reorder joins to minimize intermediate state. Niche languages: Pig, Morel, jq/JMESPath; graph traversal via Gremlin.
• Batch and cloud warehouses are converging: batch frameworks added SQL + columnar formats (Parquet); warehouses (BigQuery, Snowflake) added cloud scalability + the same shuffle/fault-tolerance techniques, plus DataFrame libraries (BigQuery DataFrames, Snowpark). But not all jobs fit SQL (PageRank, ML, multimodal AI), and warehouses can be costlier/less efficient for row-by-row work, most large enterprises run several systems.
• DataFrames (R/Pandas model) brought to distributed engines (Spark, Flink, Daft). Caveat: local DataFrames are indexed/ordered, distributed ones generally are not. Pandas executes eagerly; Spark builds a lazy query plan and optimizes before running. Apache Arrow gives a shared columnar model.

---

Batch Use Cases

Batch shines wherever there's a lot of data and freshness isn't critical: accounting/inventory reconciliation, demand forecasting, recommendation-model training, and most of the US banking network.

• ETL / ELT, extract from production DBs, transform, load to a warehouse. Embarrassingly parallel (filter, project), well-served by robust workflow schedulers (Airflow has built-in connectors), and easy to debug/rerun. Data mesh / data contract / data fabric practices let teams safely publish data org-wide; pipelines and analytics increasingly share engines (SparkSQL, Trino, DuckDB).
• Analytics (OLAP), SQL over a data lakehouse (object store + table formats like Iceberg + catalogs like Unity). Two styles: pre-aggregation (OLAP cubes / data marts, pushed to Druid/Pinot, on a schedule) and ad hoc (interactive, response-time sensitive). Integrates with Tableau, Power BI, Looker, Superset.
• Machine learning, feature engineering, model training (data in → weights out), and batch inference. Tools: Spark MLlib, Flink FlinkML. Graph processing via the bulk synchronous parallel (BSP) / Pregel model (Giraph, GraphX, Gelly). LLM data prep (extract text, dedupe, tokenize/embed) on Kubeflow, Flyte, Ray (OpenAI uses Ray for ChatGPT training). Data scientists explore in notebooks (Jupyter, Hex).
• Serving derived data, get batch output (recommendations, reports, ML features) into a serving DB/KV/search engine.

Fullscreen

Writing directly to a production DB record-by-record is slow, can overwhelm it, and breaks the all-or-nothing guarantee (partial/duplicate output). Better: push to a stream (Kafka) that downstream systems (Elasticsearch, Pinot, Druid, ClickHouse, Venice) ingest, sequential writes, buffering/throttling, multiple consumers, and a DMZ boundary. The all-or-nothing gap is closed by a completion notification (keep data invisible like an uncommitted read-committed transaction until the job signals done). Alternatively, build a new database in the job and bulk-load it (SST files), enabling fast atomic version swaps.

---

Real-world examples and analogies

• Immutable inputs / human fault tolerance, keeping the recipe's raw ingredients. If a dish comes out wrong, you don't try to "un-cook" it; you throw it out and re-cook from the same untouched ingredients with a corrected recipe. A read/write database is like cooking directly in the only bowl of ingredients you have, a mistake there is permanent.
• Throughput over latency, a freight train vs a courier bike. Batch is the freight train: slow to depart and arrive, but it moves an enormous load per trip. You don't use it to deliver one urgent envelope (that's streaming/online).
• Unix pipeline, an assembly line. Each station does one thing (extract, sort, count, rank, trim) and hands its output to the next. Simple parts, powerful whole.
• Sorting vs in-memory aggregation, counting votes. If there are few candidates, keep a tally sheet in your head (hash table). If there are millions of distinct write-ins, it's easier to stack the ballots in sorted piles and count each pile (sort + spill to disk).
• Distributed filesystem, a library with many branches. A huge book (file) is split into chapters (blocks) copied across branches (data nodes) for resilience; a central catalog (NameNode) knows where each chapter lives; you request chapters over the network.
• Object store vs DFS, a coat check vs your own closet. An object store is a coat check: you hand over a whole coat (object), get it back whole, can't reach in and adjust a sleeve (no seek/partial update), and "folders" are just label conventions. HDFS is your closet at home, where you can work right next to where things are stored (data locality).
• Job orchestrator, an airport control tower. It tracks every gate and runway (resource manager), decides which plane uses which (scheduler), and the ground crews (executors) carry it out and radio back status (heartbeats).
• Shuffle, sorting mail by zip code. Many sorting clerks (mappers) each pre-sort their pile into per-destination bins; each delivery office (reducer) collects its bin from every clerk and merges them, so all mail for one address ends up together, in order. It's deliberate sorting, not card-shuffling.
• Sort-merge join, merging two sorted guest lists. Sort both the RSVP list and the dietary-preferences list by name, then walk them together; matching names line up adjacently with no random lookups.
• Serving derived data via a stream, a loading dock, not the storefront. A batch job shouldn't dump pallets straight onto the sales floor (production DB) mid-shift. It delivers to the loading dock (Kafka), where staff bring goods out at a safe pace and only put them on shelves once the whole shipment is checked in (completion notification).

---

Cheat-sheet flashcards

Cover the answer and recall it.

• What defines batch processing? → Bounded, immutable input → output, no side effects.
• Key performance metric for batch? → Throughput.
• What is time travel in batch? → Rerunning/restoring output from a prior version after a bug.
• What is human fault tolerance? → Recovering from buggy code by rolling back and rerunning.
• Two main batch challenges? → Whole job must finish; any input change reprocesses everything.
• Origin and status of MapReduce? → Google 2004; now largely obsolete (Spark/Flink/warehouses replaced it).
• The canonical Unix log pipeline? → cat | awk | sort | uniq -c | sort -r -n | head.
• Sorting vs in-memory aggregation, when does sorting win? → When the working set exceeds memory (spills to disk).
• What is the working set here? → The number of distinct keys needing random access.
• Limitation of Unix tools? → Single machine.
• A batch framework is analogous to what? → A distributed operating system.
• HDFS default block size vs ext4? → 128 MB vs 4 KB.
• What are data nodes and the NameNode? → Block-serving daemons / the cluster metadata service.
• Two DFS redundancy methods? → Replication or erasure coding (Reed-Solomon).
• Shared-nothing vs shared-disk? → Commodity machines + network vs central appliance (NAS/SAN).
• Object store object model? → Immutable objects, put/get, bucket + key; no seek/partial update.
• Are object-store directories real? → No, slashes in keys; prefix listing is recursive; no empty dirs.
• Object store vs HDFS on compute? → Storage/compute separated vs data locality.
• Three orchestrator components? → Scheduler, resource manager, task executors.
• Where is cluster state stored? → ZooKeeper (YARN) / etcd (Kubernetes).
• Why is resource allocation hard? → NP-hard; needs heuristics (FIFO, DRF, bin-packing).
• What is gang scheduling? → Running a job only when all its needed cores are free at once.
• What are spot/preemptible instances? → Cheap VMs that may be preempted at any time.
• Workflow / DAG schedulers? → Airflow, Dagster, Prefect (manage job dependencies).
• How do MapReduce/Spark/Flink handle intermediate-data faults? → DFS write / in-memory + lineage recompute / checkpointing.
• The four MapReduce steps? → Read+split, map, sort (implicit), reduce.
• Mapper vs reducer? → Stateless per-record key-value extractor / iterates all values per key.
• MapReduce's programming-model origin? → Functional programming (map/reduce/fold).
• Two MapReduce weaknesses? → Laborious raw API; slow file I/O, no pipelining.
• What is a dataflow engine? → Spark/Flink: whole workflow as one job with flexible operators.
• Four dataflow advantages over MapReduce? → Sort only when needed, operator fusion, in-memory state, pipelining/process reuse.
• What is a shuffle? → A distributed sort (not random) underlying joins/aggregations.
• How does MapReduce shuffle work? → Mappers write sorted per-reducer files by key hash; reducers copy + mergesort.
• What is a sort-merge join? → Map both sides to the same key, shuffle, reducer merges co-located records.
• What is a secondary sort? → Ordering values so one record (e.g. the DB row) arrives first.
• Lingua franca of batch query? → SQL.
• What do cost-based optimizers do? → Pick join algorithms and reorder joins to minimize intermediate state.
• Local vs distributed DataFrames? → Indexed/ordered vs generally not; eager (Pandas) vs lazy plan (Spark).
• Four batch use cases? → ETL, analytics, machine learning, serving derived data.
• What is a data lakehouse? → Object store + table formats (Iceberg) + catalogs for SQL analytics.
• BSP / Pregel model? → Bulk synchronous parallel graph processing (Giraph, GraphX, Gelly).
• Why not write batch output directly to a prod DB? → Slow, overwhelms it, breaks all-or-nothing (partial/duplicate).
• Better ways to serve derived data? → Push to a stream (Kafka) or bulk-load a freshly built DB.

---

Common interview questions

1. What makes batch processing distinctive, and what benefits flow from immutable inputs? (Bounded input/no side effects; time travel, human fault tolerance, reuse, efficiency.)
2. When does sorting beat an in-memory hash table for aggregation? (When the working set exceeds memory; sorting spills to disk sequentially.)
3. Why is a distributed batch framework like an operating system? (Filesystem + scheduler + programs → DFS + orchestrator + tasks.)
4. Compare distributed filesystems and object stores. (Blocks/data nodes/locality vs immutable objects/keys/separated compute.)
5. What does a job orchestrator do, and why is scheduling hard? (Scheduler/resource manager/executors; NP-hard allocation, gang scheduling, preemption.)
6. Explain the MapReduce model and its weaknesses. (Read/map/sort/reduce; laborious API, slow file I/O, no pipelining.)
7. How do dataflow engines improve on MapReduce? (One job, flexible operators, in-memory state, pipelining, fusion, locality.)
8. What is a shuffle, and why isn't it random? (Distributed sort co-locating equal keys; underlies joins/aggregations.)
9. Walk through a sort-merge join in MapReduce. (Map both sides to the join key, shuffle, reducer merges; secondary sort.)
10. How do batch jobs handle task failures and preemption? (Discard partial output, retry at task granularity; DFS/lineage/checkpointing for intermediate data.)
11. How have batch frameworks and cloud warehouses converged? (SQL + columnar both ways; DataFrame libs; shared engines; when each still wins.)
12. How should batch output be served to production systems, and why not write directly? (Stream via Kafka or bulk-load; direct writes are slow, overwhelming, and break all-or-nothing.)

---

Key terms glossary

---

Forward links (where these ideas return)

• Stream processing (unbounded inputs, the contrast to batch) → Chapter 12
• Serving derived data via Kafka streams, change ingestion → Chapter 12
• Sharding and parallel execution → Chapter 7
• Columnar storage, Parquet, query compilation/vectorization, cloud warehouses → Chapter 4
• Event sourcing, deterministic replay, durable execution workflows → Chapters 3, 9, 10
• Star schemas, fact/dimension tables, data warehousing/ETL → Chapter 3