Batch pipelines are everywhere: a job that reads logs and produces a report, or reads a database and builds an index. Most start as a single periodic job and grow into a chain of them. This chapter explains why periodic pipelines become unreliable as they scale, and describes Google Workflow, which runs pipelines as continuously operating systems with strong guarantees about work being done exactly once.

The chapter uses the Shakespeare indexing job as its running example and introduces a vocabulary, thundering herd and Moiré load patterns, that interviewers may use.

In one minute

• A simple pipeline reads input, transforms, writes output, in one stage. A multiphase pipeline chains stages, each stage's output feeding the next, and is typically run periodically (daily, hourly).
• Periodic pipelines work until data grows or the environment gets busy. Drawbacks: uneven work distribution (one worker gets the big shard, so the whole job waits), resource contention in a shared cluster (batch jobs get preempted by serving jobs), cascading failures when one stage is late and the next starts on partial data, and startup and monitoring overhead proportional to the number of runs.
• Thundering herd: too many workers start at once and overwhelm a shared service such as a storage system. Moiré load pattern: two or more pipelines with overlapping periods interfere and periodically coincide, creating spikes.
• Google Workflow replaces the periodic model with a leader-based continuous system. A Task Master holds the state of all work units; workers claim units, do the work, and commit results; the pattern is model-view-controller, where the Task Master is the model, workers are the views, and the controller handles scaling, snapshots and other out-of-band operations.
• Correctness comes from four guarantees: a worker's output is only accepted if the lease it holds is still valid, each task holds one exclusive lease, the Task Master validates configuration version on each commit, and workers write output to a uniquely named location so that two workers cannot overwrite each other.
• Business continuity: the Task Master is a replicated Paxos-based state store, and a snapshot of the whole pipeline can be restored in another datacenter.

Origin of the pipeline design pattern

The idea comes from Unix pipes and from MapReduce: a program reads, processes and writes, and a chain of such programs produces the result. It is simple to write and easy to reason about, so almost every batch system starts this way.

Initial effect of big data on the simple pipeline pattern

The simple pattern breaks in two ways with large data. One stage's input is too large for one machine, which is why MapReduce shards it. And one stage's duration becomes long enough that failures within it matter, so the stage has to be restartable. Multiphase pipelines inherit both problems and multiply them by the number of stages.

Challenges with the periodic pipeline pattern

A periodic pipeline is judged by whether it finishes in its period. Google's experience is that as data grows, these pipelines become fragile. Shards are uneven because the data is skewed, and the stage ends when the largest shard does; a few hot keys can double the run time. In a shared cluster, batch work runs at low priority and can be preempted or starved during busy periods, so a daily job that used to take an hour takes six, misses its window and starts stacking. When one stage is late and the next one starts on time, it reads incomplete data and propagates the problem.

Trouble caused by uneven work distribution and problems in shared, distributed environments

The hanging chunk problem is when a few shards take far longer than the rest, leaving most workers idle. Dynamic repartitioning, where idle workers steal work from busy ones, addresses it but is not natural in a periodic batch model. In a shared environment the pipeline also has to deal with the cluster manager's decisions: preemption mid-task, machines disappearing, quotas changing.

Monitoring problems in periodic pipelines

Each run has to be monitored separately, and an alert that a run is late is usually too late to do anything about it. Alerting on run duration against a baseline helps, but the deeper fix is to make the pipeline continuous so that lag is a quantity you can measure and alert on at any moment.

Thundering herd problems and Moiré load pattern

When a periodic pipeline starts, it launches all its workers at once, and they all hit the same storage or RPC backend. A big enough pipeline, or several that start at the same time, can take down shared infrastructure. The Moiré pattern is the subtler version: pipelines with different periods periodically align, so a 30-minute job and a 45-minute job collide every 90 minutes and the backend sees a spike with no obvious cause. The fix is to spread start times and to rate-limit workers, and the deeper fix is again to be continuous rather than periodic.

Introduction to Google Workflow

Workflow is a system for running multiphase pipelines continuously. Instead of a job that starts at midnight, there is a running system that always has a queue of work units in each stage. The Task Master knows every unit of work and its state (unclaimed, leased to a worker, completed). Workers ask for work, receive a unit with a lease, do it, and commit the result back. Stages are connected because the output of one stage becomes work units for the next.

Workflow as model-view-controller. The Task Master is the model: it owns the state and is the only authority. Workers are stateless views: they can be added, removed and restarted without losing anything. The controller is an optional component for things like autoscaling the worker pool, snapshotting the Task Master, and rolling the pipeline configuration forward.

Stages of execution in Workflow. A pipeline is a chain of stages, each with its own Task Master instance or namespace, and each can be scaled independently. The Task Master itself is sharded for large pipelines.

Workflow correctness guarantees. Workers are unreliable; they get preempted, duplicated, or run on slow machines. Workflow stays correct through leases (a worker's commit is rejected if its lease has expired, which rules out a slow worker overwriting a fast one), exclusivity (one lease per task at a time), configuration versioning (a worker running old code cannot commit into a pipeline that has moved on), and uniquely named outputs (two workers that did the same unit write to different places and only the lease holder's output is linked in). Together these give exactly-once semantics for each unit of work.

Ensuring business continuity

The Task Master's state lives in a Paxos-replicated store, so it survives machine failure. For datacenter loss, Workflow can snapshot the Task Master and restore the pipeline elsewhere, since workers are stateless and the inputs are in a distributed filesystem. The pipeline resumes from the last committed unit rather than from the beginning of the day.

Summary and concluding remarks

Periodic pipelines are fine until they are not, and the failure comes slowly: longer runs, missed windows, mysterious load spikes. Converting to a continuous, leader-based system with explicit leases turns a fragile batch job into a service that can be monitored like any other, scaled by adding workers, and recovered from a snapshot.