Skip to main content

Beyond MapReduce: Dataflow Engines and Graphs

Adapted from: Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), Chapter 10 — rewritten and condensed for teaching.

Joins in MapReduce covered how MapReduce actually computes things. This final lesson in the batch processing arc covers three remaining questions: what does a batch job's output actually become? How does MapReduce stack up against the MPP databases that predate it? And what replaced MapReduce once its rough edges started to matter?

What Batch Jobs Actually Produce​

A batch job's output is neither a transactional record nor an analyst's report — it's usually some other kind of derived structure, built once (or periodically) and then consumed elsewhere.

Search Indexes​

Google's original use for MapReduce was building search indexes, via a workflow of 5–10 chained jobs — mappers partition the document set, each reducer builds the index for its own partition, and the resulting files land on the distributed filesystem. Since querying a finished index is read-only, those index files are simply immutable once written. Handling updates to the underlying document set has two flavors: wholesale rebuild (rerun the entire indexing workflow, replace the old index files entirely — computationally wasteful for a tiny change, but conceptually dead simple: documents in, index out) or incremental updates (write new segment files and merge/compact them in the background — the same SSTable-style technique from Hash Indexes and LSM-Trees).

Key-Value Stores as Output​

Machine learning systems — spam filters, recommendation engines, "people you may know" — are the other major batch output pattern, and they typically need to be queried by a live web application afterward (by user ID, product ID, etc.). The tempting-but-wrong approach: write directly to the production database, one record at a time, straight from the mapper or reducer. Three concrete reasons this backfires:

  1. Throughput mismatch. A network write per record is orders of magnitude slower than a batch task's normal internal throughput, even with client-side batching.
  2. Overwhelming the target. Many parallel reducers hammering the same live database, all at once, at batch-job speed, can easily saturate it — degrading its normal query performance and causing knock-on problems elsewhere.
  3. Broken all-or-nothing semantics. MapReduce's clean guarantee — a job's output equals running every task exactly once, even after retries, or nothing at all if the whole job fails — depends on output staying inside the framework's control. Writing directly to an external database creates side effects the framework can no longer hide, exposing partial, in-progress results from tasks that haven't even finished yet.

The reliable pattern instead: build a brand-new database as output files in the job's own output directory (exactly like the search-index case), then bulk-load those immutable files into whatever server will handle read queries — Voldemort, Terrapin, ElephantDB, and HBase's bulk-loading feature all support this directly. Since these stores are effectively read-only once loaded, their internal structure can be much simpler than a general-purpose read/write store — no write-ahead log needed, for instance, since there's never a crash mid-write to recover from. Voldemort specifically keeps serving the old files while new ones copy over in the background, then atomically swaps to the new files once the copy finishes — and if anything goes wrong mid-swap, it can just as easily switch back, since the old files are still sitting there, untouched.

The Same Philosophy, One Level Up​

This is the exact same Unix philosophy from the first lesson in this arc, just applied at the scale of whole datasets: inputs stay immutable, outputs completely replace whatever came before, and there are no side effects beyond the declared output. That discipline pays off in ways that go well past raw performance:

  • Bugs become reversible. Ship broken mapper/reducer code, and the fix is: roll back the code, rerun the job. A live database that a buggy service wrote directly into offers no such undo button — rolling back the code does nothing to un-corrupt data that's already there. (This general property has a name: human fault tolerance — the ability to recover cleanly from a person's mistake.)
  • Retries are automatically safe. A failed map or reduce task just gets rescheduled and rerun on the same input — safe specifically because inputs are immutable and a failed task's output is always discarded, never left half-visible.
  • The same input can feed many purposes at once — including monitoring jobs that compare a run's output against the previous run's, watching for unexpected drift.
  • Logic stays decoupled from wiring, exactly as in Unix — one team builds a job that does one thing well; other teams independently decide when and where to actually run it.

Check: batch job outputs​

Quiz

Search indexes, key-value store outputs, and human fault tolerance

1 / 2

Why is it generally a bad idea for a MapReduce job to write directly, record-by-record, to a live production database from inside its mappers or reducers?

Pick an answer to see if you are right.

Hadoop vs. MPP Databases​

MapReduce wasn't actually new when Google published it — massively parallel processing (MPP) databases (Teradata, Tandem NonStop SQL, the Gamma database machine) had already implemented similar parallel join algorithms over a decade earlier. The real difference: MPP databases focus tightly on parallel SQL execution, while MapReduce plus a distributed filesystem behaves much more like a general-purpose operating system that happens to run arbitrary programs at scale.

Diversity of Storage​

A database forces data into a specific model (relational, document) before it ever gets stored. A distributed filesystem stores plain byte sequences — could be database-style records, but equally well text, images, sensor readings, genome sequences, anything. This lets you dump data into HDFS first and figure out how to process it later — a strategy sometimes called the data lake approach, or (more colorfully) the sushi principle: raw data is better. MPP databases, by contrast, demand careful schema design before import — which produces cleaner data to work with, but measurably slows down the simple act of getting disparate data into one place where it can finally be joined together at all.

This is schema-on-read territory, already covered from the document-database angle back in Graph-Like Data Models — dumping data raw shifts the burden of interpreting it from the producer onto the consumer, which is a real win specifically when producer and consumer are different teams with genuinely different priorities (and maybe even different, mutually incompatible ideal views of the same underlying data).

Diversity of Processing Models​

MPP databases are monolithic — storage layout, query planning, scheduling, and execution are all tightly co-designed and tuned together, buying excellent performance for the specific query shapes SQL is built to express, plus accessibility to non-programmers via graphical BI tools. But plenty of real workloads simply don't map onto SQL cleanly — machine learning feature engineering, full-text relevance ranking, image analysis — these need genuine, arbitrary code, not just queries.

MapReduce's real contribution was giving engineers a direct path to run their own arbitrary code over huge datasets — which is also exactly why SQL engines (Hive) and many other, non-SQL processing models could all eventually be built independently on the same underlying Hadoop platform, all sharing the same cluster and the same files on the same filesystem — no need to copy data into several separately specialized systems just to support different processing styles. The Hadoop ecosystem's coexistence of HBase (random-access OLTP-style access) and Impala (MPP-style analytics) — neither of which even uses MapReduce, but both of which sit directly on HDFS — is the clearest illustration of this flexibility in practice.

Designing for Frequent Faults​

A third real design gap: how each system handles faults. Most MPP databases simply abort the entire query on a node crash mid-execution — acceptable, since a typical query runs seconds to minutes, so a full retry is cheap. MapReduce instead tolerates individual task-level failure without derailing the whole job, retrying just that one task.

Why the different philosophy? At Google's own mixed-use datacenters, low-priority batch jobs and high-priority online services share the same machines — and a higher-priority process can preempt (forcibly terminate) a lower-priority one to reclaim resources on demand. This lets Google overcommit resources for genuinely better overall utilization, since spare capacity can always be reclaimed the moment something more important needs it. The real cost: at Google, an hour-long MapReduce task faced roughly a 5% chance of preemption — over ten times higher than the rate of failure from actual hardware problems. With enough tasks in a job, that adds up fast: 100 tasks running 10 minutes each faced better than even odds that at least one would get preempted before finishing. MapReduce's aggressive task-level retry design isn't a hedge against unreliable hardware at all — it's a direct, deliberate consequence of a scheduling philosophy that deliberately sacrifices individual low-priority tasks in exchange for markedly better cluster-wide utilization.

Check: Hadoop vs. MPP databases​

Quiz

Storage diversity, processing diversity, and fault philosophy

1 / 3

What does "schema-on-read" mean in the context of dumping raw data into a distributed filesystem before deciding how to model it?

Pick an answer to see if you are right.

Beyond MapReduce: Dataflow Engines​

MapReduce's biggest structural weakness: every job fully materializes its output to the distributed filesystem before the next job can even start — replicated across multiple nodes, exactly like any other HDFS file, even when that data is really just disposable, temporary intermediate state on its way to the very next job in a chain.

This costs real time and I/O:

  • A job can't start until every task in every job it depends on has finished — and stragglers (slower-than-average tasks caused by skew or an overloaded machine) directly delay the whole chain.
  • Mappers in a chained job are frequently pure overhead — reading back the exact same data a previous reducer just finished writing, purely to re-prepare it for another round of partitioning and sorting that could often have been folded directly into that previous reducer instead.
  • Replicating genuinely temporary, single-use intermediate data across several nodes (HDFS's normal replication behavior) is often complete overkill for data nobody will ever need again after the very next job consumes it.

Dataflow engines — Spark, Tez, Flink — fix this by treating an entire multi-job workflow as one single job, rather than a chain of fully independent ones. They generalize map and reduce into more flexible operators, connectable in several ways: repartition-and-sort (exactly like MapReduce's shuffle, still needed for sort-merge joins), repartition without sorting (cheaper, and sufficient for hash joins, where partition membership matters but order doesn't), or broadcast an operator's entire output to every downstream partition (broadcast hash joins).

The wins compound: sorting only happens where it's genuinely required, not by default between every single stage; a scheduler that can see the entire workflow's declared data dependencies up front can make real locality decisions (placing a consuming task on the same machine as its producer, trading a network copy for a shared memory buffer); intermediate state can often just live in memory or local disk rather than being written through the full replicated-HDFS path; and downstream operators can start consuming data the instant it's ready, rather than waiting for an entire preceding stage to fully finish. The exact same job logic — written once, in a high-level API like Pig or Hive — can often switch from running as classic MapReduce to running on Tez or Spark with nothing more than a configuration change.

Fault Tolerance Looks Different Without Full Materialization​

MapReduce's durability story is simple because everything gets written through HDFS: a failed task just restarts and re-reads the same durable input. Dataflow engines that skip that full write-through need a different answer: recompute any lost intermediate data from whatever's still available — a prior stage's still-durable output if one exists, or the very original input data if not. Spark tracks exactly how each piece of data was derived via its RDD (resilient distributed dataset) abstraction; Flink instead periodically checkpoints operator state directly, so a failed operator can resume from its last checkpoint rather than recomputing from scratch.

This recomputation strategy has one real precondition: determinism. If an operator can produce genuinely different output from the exact same input on a retry, and some of its (now-invalidated) original output already propagated downstream before the failure, reconciling old and new output becomes extremely difficult — usually forcing every downstream operator to be killed and rerun too, cascading the fault outward. Nondeterminism sneaks in more easily than it sounds: unordered hash-table iteration in many languages, any explicit use of randomness, or reading the system clock or any external data source, are all classic, easy-to-miss sources — which is exactly why building genuinely deterministic operators (e.g., seeding any pseudorandom generator with a fixed value) matters far more here than it would in an ordinary single-threaded program.

Check: dataflow engines​

Quiz

Materialization, operators, and recomputation-based fault tolerance

1 / 3

What specific inefficiency does full materialization of intermediate state (writing every job's output to HDFS before the next job starts) introduce into chained MapReduce workflows?

Pick an answer to see if you are right.

Graphs and Iterative Processing​

Some algorithms don't fit the "one pass over the data" shape MapReduce assumes at all. PageRank — estimating a web page's importance from which other pages link to it — is the canonical example: it works by repeatedly propagating information along graph edges until some convergence condition is met (no more edges left to follow, or the values stop changing meaningfully between rounds).

Running this kind of algorithm as literal, repeated, independent MapReduce jobs (an external scheduler runs one pass, checks a completion condition, and if not done, runs another full pass) technically works — but it's wasteful, since each full pass re-reads and reprocesses the entire graph from scratch, even when only a small corner of it actually changed since the last round.

The Pregel Model​

The bulk synchronous parallel (BSP) model — popularized under the name Pregel, after Google's paper on the topic, and implemented by Apache Giraph, Spark's GraphX, and Flink's Gelly — is purpose-built for exactly this iterative graph shape. The core idea genuinely echoes MapReduce's "mapper sends a message to a reducer call" pattern, but with one crucial upgrade: each vertex keeps its own state in memory, persisting from one iteration (called a "superstep") to the next, and a vertex's per-iteration function only has to process new incoming messages — if no messages arrive anywhere in some part of the graph, that part of the graph simply does zero work that round.

It resembles the actor model (recall Modes of Dataflow) if you picture each vertex as its own actor — except Pregel additionally guarantees vertex state and inter-vertex messages are both fault-tolerant and durable, and processing proceeds in strict, fixed rounds: every message sent during one superstep is guaranteed delivered at the very start of the next, a much stronger timing guarantee than actors typically offer.

Fault Tolerance and Parallelism in Pregel​

Because vertices can only communicate via message passing — never by directly querying each other — messages can be batched efficiently, and there's comparatively little waiting beyond the natural boundary between one superstep finishing and the next one starting. Durability comes from periodic checkpointing of every vertex's full state at the end of a superstep; if a node fails, the simplest recovery is rolling the entire computation back to the last checkpoint (a more surgical option — recovering only the lost partition — is possible for deterministic algorithms with logged messages, echoing the same recomputation idea from dataflow engines above).

Parallelizing Pregel means partitioning the graph across machines — and a vertex genuinely has no idea which physical machine it's actually running on; it just addresses messages to a destination vertex ID, leaving routing entirely to the framework. In principle, an ideal partitioning would colocate vertices that message each other heavily on the same machine — but computing a good partitioning like that is itself a genuinely hard problem, so in practice, graphs are commonly partitioned by nothing more than an arbitrarily assigned vertex ID, with no attempt at grouping related vertices together at all. The direct consequence: heavy cross-machine message traffic, and often more total data moving between machines than the original graph itself contained. Worth remembering as a sanity check: if a graph fits in memory on one machine, a single-machine (even single-threaded) algorithm frequently beats a "properly" distributed one — distribution only pays for itself once a graph is genuinely too large for any single machine to hold.

Practice: one Pregel superstep​

Implement a single BSP superstep directly: given each vertex's current value and a set of incoming messages, compute each vertex's new value and the messages it sends onward — the core "propagate the max value along edges" pattern several real graph algorithms are built from.

Check: Pregel and graph processing​

Quiz

The Pregel / BSP model

1 / 3

What is the key difference between Pregel's per-vertex processing and a plain MapReduce reducer call?

Pick an answer to see if you are right.

High-Level APIs and Declarative Features​

Hand-writing raw MapReduce jobs is genuinely laborious — implementing every join algorithm from scratch, by hand, every time. Higher-level languages (Pig, Hive, Cascading, Crunch) exist specifically to abstract this away, expressing computations with relational-style building blocks (join, group, filter, aggregate) that compile down to the appropriate low-level join/grouping algorithm underneath — with the added, non-obvious benefit that the exact same job logic can move from classic MapReduce onto Tez or Spark via a configuration change alone, no rewrite required.

Expressing joins declaratively (rather than hand-coding a specific join algorithm) lets the framework's own query optimizer pick the best strategy automatically — Hive, Spark, and Flink all include cost-based optimizers that choose join algorithms and even reorder joins to minimize intermediate data size, the exact same idea behind SQL query optimization, just now applied to batch dataflow jobs. But these frameworks deliberately don't go fully declarative like SQL: user-defined mapper/reducer-style callback functions remain central, which is precisely what lets a job freely pull in the vast existing ecosystem of libraries for parsing, natural language processing, image analysis, or numerical computing that a purely declarative query language could never accommodate as naturally. Even simple, common operations (a plain filter, a field projection) benefit from being expressed declaratively where possible — it lets the underlying engine skip a full function-call overhead per record and exploit column-oriented storage layouts directly, an optimization no hand-written callback function can access from the outside.

The overall trend: batch frameworks are steadily gaining more declarative, MPP-database-like optimization smarts, while MPP databases are simultaneously becoming more extensible and programmable — the two categories are visibly converging toward the same destination from opposite starting points. Domain-specific reusable libraries have followed the same path: Mahout implements machine learning algorithms on top of MapReduce/Spark/Flink, while MADlib implements comparable functionality inside a relational MPP database — genuinely different architectures converging on the same underlying algorithmic territory.

Key takeaways
  • Batch job output is rarely a report — it's usually a derived structure (a search index, a read-only key-value store) built as immutable files and bulk-loaded, never written record-by-record straight into a live production database.
  • Treating input as immutable and output as a full replacement, with no other side effects, buys real reliability properties — safe automatic retries, and crucially, "human fault tolerance": a buggy job's damage can be undone just by rolling back code and rerunning it.
  • MapReduce and MPP databases differ along three real axes: storage diversity (raw files vs. enforced schema), processing diversity (arbitrary code vs. SQL-only), and fault philosophy (frequent task-level retry, driven by Google's preemption-heavy scheduling, vs. abort-and-restart-the-whole-query).
  • Dataflow engines (Spark, Tez, Flink) treat an entire workflow as one job instead of independently chained ones, skip unnecessary sorting and full materialization, and recover from failures by recomputing lost data — which only works correctly for genuinely deterministic operators.
  • Pregel/BSP adapts the MapReduce message-passing idea for graphs specifically, letting each vertex retain state across iterations and process only new incoming messages — though a poor graph partitioning can still make cross-machine communication the dominant cost.
  • High-level APIs let batch frameworks borrow declarative query optimization from the SQL world while keeping the ability to run arbitrary user code — pulling batch processing and MPP databases visibly closer together over time.

Further Reading​