Distributed Analytics

Every distributed system we have studied so far was, at heart, about managing state: naming it, synchronising it, replicating it, agreeing on it. This chapter changes the focus from managing state to processing data: distributed systems whose purpose is to run computations over volumes of data far too large for any single machine. The driving application is data science, extracting knowledge and insight from massive datasets, whether those datasets sit at rest on a distributed file system or arrive continuously in real time.

The central engineering question is deceptively simple: how do you design a distributed system that can process vast amounts of data? The answer that emerged in the mid-2000s, and that still underpins Spark, Flink, and their descendants, is a single conceptual shift: stop thinking in terms of a global mutable state and start thinking in terms of immutable data flowing through parallel transformations. This chapter develops that idea from its motivating example, through MapReduce, to the general dataflow model and its two execution architectures.

1. The Big Data Problem#

1.1 From compute-bound to data-bound#

Modern organisations collect enormous amounts of data and depend on it for decisions across nearly every domain: recommender systems for social media, streaming and e-commerce; genomics correlating genes with disease; health monitoring from wearable devices; real-time route optimisation in logistics; risk estimation in finance. What changed with this shift is where the bottleneck lives. Classical algorithm design assumes the cost is in the CPU. At this scale the cost is instead in reading the input and reading or storing the intermediate state. The problem is data-bound, not compute-bound.

The nature of the data is usually summarised by four V’s:

• Volume. Datasets are too large to fit in the memory, or even on the disk, of one machine. Already in 2008 Google was processing around 20 PB of data per day [Dean & Ghemawat, 2008]; volume has grown exponentially since.
• Velocity. Two distinct pressures. Ingestion rate: data arrives fast and continuously (every minute of 2024, millions of videos are watched, hundreds of millions of messages sent, and so on). Processing latency: in domains such as transportation, finance, and monitoring, fresh information is valuable and loses value as it ages, so results must be produced promptly.
• Variety. Data comes in many formats, versions, and sources. Unlike a classical relational database, a modern engine is designed to work over heterogeneous, semi-structured data.
• Veracity. Data is not always correct. This matters for algorithm design but is not our concern here.

1.2 The infrastructure that shaped the design#

These frameworks emerged around the mid-2000s, and their design reflects the hardware of that era. Storage meant spinning disks, where sequential reads are fast but random reads are painfully slow. Memory was limited, so datasets and intermediate state routinely did not fit in RAM. And the infrastructure was built on commodity hardware: clusters of hundreds to thousands of cheap, ordinary machines rather than dedicated supercomputers. Scaling out (many cheap nodes) was preferred over scaling up (few powerful nodes) because commodity hardware is inexpensive and easy to grow incrementally. Two consequences follow directly. First, in a rolling-update data centre the hardware is heterogeneous: some machines are new, some are years old. Second, with thousands of nodes, hardware failures during a long computation are statistically inevitable.

From these constraints the requirements for a data-processing framework fall out almost mechanically:

1. A clean, simple programming abstraction, so that domain experts (statisticians, mathematicians) can experiment without expertise in distributed systems.
2. Automatic parallelisation and distribution, hiding synchronisation and consistency from the programmer.
3. Fault tolerance, so that a single node or disk failure does not restart the entire job.
4. Monitoring and operational tooling, so that deployment and bottleneck detection are not the programmer’s problem.

2. From Mutable State to Data Flow#

2.1 The nearest-gas-station problem#

The motivating problem is this. A map is a graph: nodes are points of interest, edges are roads. Given a set of gas stations, precompute for every point the nearest gas station. This is a single-source shortest-path computation (Dijkstra) run outward from each gas station, at a cost of $O((N + E)\log N)$ per station, where $N$ is the number of nodes and $E$ the number of edges.

The naive approach runs shortest-paths from each gas station and, for each point, keeps the running minimum across all stations. It works on paper but makes assumptions that collapse at scale: that we can hold the entire input at once, that the state of the computation (all discovered paths, the current minimum per node) fits in memory or at least on one disk, and that random access to it is fast. At the scale of terabytes on a cluster of commodity nodes, none of these hold. If the input and the state do not fit on one machine we need a distributed solution, and then coordination and communication become the new bottleneck.

2.2 A two-stage parallel solution#

The way out is to partition the data under a mild assumption: every point on the map lies within a fixed radius (say 50 km) of some gas station. Draw one overlapping circle around each station; together they cover every point. This unlocks a two-stage structure.

Stage 1 (partitioned by station). Split the graph into overlapping sub-graphs, each centred on a gas station, and assign each to a node. Each node loads only its local sub-graph (which fits in memory) and computes shortest paths from its station to every point in its radius. This is embarrassingly parallel: no synchronisation across nodes.

Stage 2 (partitioned by point). A point may fall inside several circles, so the partial results must be reorganised. The data is repartitioned by point: each node now receives every distance estimate for the points it owns, and independently computes the minimum, i.e. the nearest station. Again no synchronisation is needed. The communication between the two stages can travel over a distributed filesystem, direct messages (TCP), or a queue such as Apache Kafka.

2.3 The key insight#

The two-stage solution abandons a global mutable state in favour of a model built on sequences of transformations over immutable data. Data flows through stages, is reorganised (first by station, then by point) and transformed at each step; no node holds everything, and intermediate results move as messages. Each transformation is independent and can run in parallel, and the computation is specified only once (the same code ships to every node). This is exactly the trick of functional programming, immutable data flowing through pure functions, and it is why these systems are called dataflow platforms.

3. MapReduce#

3.1 Map, shuffle, reduce#

The two-stage pattern generalises into the programming model Google introduced in the mid-2000s: MapReduce. The names come from two higher-order functions of functional programming.

The map function applies a computation independently to each element of a partitioned dataset and emits a list of (key, value) pairs. In the gas-station example: input is a station and its sub-graph, the computation is shortest-paths, and each output pair is (point of interest, distance from this station). Every mapper runs the same code on its own partition, fully in parallel, with no coordination.

Between map and reduce the framework performs a shuffle: it collects all intermediate pairs from every mapper, groups them by key, and delivers all values sharing a key to the same reducer. This step moves data across the network and is managed entirely by the runtime; the developer never implements it. Implementing the reliable movement of terabytes of intermediate data by hand is precisely the kind of complexity the framework exists to hide.

The reduce function receives a key and an iterator over all values for that key, and computes an aggregated result. In the example: input is a point and the list of distances to it from every nearby station, the computation is the minimum, and the output is the nearest station.

3.2 Word count#

The canonical example is counting word occurrences across a large document collection. Take the lyrics of a short song, split into lines, one line per map task:

Each mapper is stateless: its output depends only on its own input. It builds a local dictionary and emits one pair per distinct word:

# key: document name   value: document contents
def map(key, value):
    count = {}
    for w in value:
        count[w] = count.get(w, 0) + 1
    for w in count:
        emit(w, count[w])

The shuffle guarantees that all pairs with the same key reach the same reducer. Each reducer then folds its values into a total:

# key: a word          values: an iterator of counts
def reduce(key, values):
    result = 0
    for v in values:
        result += v
    emit(result)

The reducer for a-h receives <all, [1,1,1,1]> and <is, [1,1,1,1]> and emits <all, 4>, <is, 4>; the i-p reducer emits <love, 5>, <need, 4>; the q-z reducer emits <you, 4>.

3.3 Why reducers receive an iterator, not a list#

A subtle but deliberate choice: reduce receives an iterator over its values rather than a materialised list. The abstraction forces the developer to visit the data in sequence, once, and this is dictated by the infrastructure. First, intermediate results may not fit in memory; an iterator streams them from disk one element at a time, keeping memory bounded, and it also avoids inviting the developer to jump around in memory and thrash the cache. Second, on spinning disks sequential reads are far faster than random reads, so an iterator enforces the access pattern the hardware rewards. The developer is therefore expected to write reducers that process data in a single streaming pass, holding only a small accumulator (for word count, a running sum).

3.4 The batch storage assumption#

In the classic MapReduce scenario the data is pre-loaded into a replicated distributed file system before the computation starts. Ingestion is not the bottleneck: the typical use case is a large, stable dataset that data scientists query repeatedly with different analyses. Nor does processing need to be real time; an overnight batch job is acceptable. This is the batch processing model. Streaming, where data must be processed with low latency as it arrives, needs different machinery, covered in Section 7.

4. Inside MapReduce#

4.1 Master/worker architecture#

MapReduce runs on a master/worker architecture. A single master allocates tasks, tracks worker state, and periodically pings workers to detect failures; many workers execute the map and reduce tasks.

The input is divided into M map tasks, each covering one or more data blocks. Blocks are large, typically 64 MB or multiples of it, far larger than a local filesystem block (about 4 KB), because the distributed filesystem is optimised for large sequential reads. The reduce phase is partitioned into R reduce tasks by hash(key) mod R, which guarantees that all values for one key land on one reducer. The values of $M$ and $R$ follow from the resources provisioned at startup (say, 128 machines of 8 cores each), and tasks are assigned to workers dynamically at runtime, not fixed in advance.

4.2 Data locality#

Moving large volumes of data across the network is expensive, so MapReduce sends the computation to the data, not the reverse. The master knows the network topology and, from the filesystem, which node holds which block. Its scheduling policy is:

1. Assign a map task to the same machine that holds its block (reads come from local disk).
2. If that machine is busy, assign it to a node in the same rack, minimising cross-rack traffic.
3. Only if neither is available does the task run on a remote node, stealing the block over the network.

As workers finish and free up, new tasks are assigned under the same locality-aware policy, maximising input throughput.

4.3 The distributed file system#

The reference implementation stored data in the Google File System (GFS), open-sourced as HDFS in Apache Hadoop. Each block is stored with three replicas, typically two close together and one further away for disaster recovery. Beyond durability, replication has a direct scheduling benefit: with several nodes holding each block, the master has more candidate workers and a higher chance of achieving data locality.

4.4 Fault tolerance#

Fault tolerance in MapReduce is straightforward precisely because map and reduce are stateless, deterministic transformations: the same input always yields the same output, and there is no shared mutable state. If a node crashes mid-computation, some partial results are lost, but since they are deterministic they can simply be recomputed.

Worker failure. The master detects it through missing heartbeats. Map tasks that were running on the failed node are rescheduled elsewhere, regardless of progress. Crucially, completed map tasks must also be re-executed: their output sat on the failed node’s local disk and is now unreachable. (Completed reduce tasks need no re-execution: their output went to the distributed filesystem.) The master does not need to confirm the node is truly dead before rescheduling. If the original node later recovers, there may be duplicate results, but duplicates are harmless because the computation is deterministic, so they are simply discarded.

This is the whole point: restarting is cheap and always correct, so no consensus protocol among workers is needed. All the machinery of agreement from earlier chapters is unnecessary here, because a task can be run any number of times without changing the answer.

Master failure. The master holds only metadata (task assignments, which blocks are complete, worker availability), never the actual data. It can be recovered from a checkpoint or a standby, since the real results live safely on the distributed filesystem.

4.5 Stragglers#

A straggler is a worker that falls badly behind: slow hardware, a failing disk, or an unusually heavy partition (a dense urban area has far more roads than a rural one). The cure mirrors fault tolerance: when a job is nearly done but a few tasks lag, the master speculatively reschedules them on free workers in parallel, and whichever copy finishes first wins while the other is discarded. This simple trick, again enabled entirely by immutability, stops one slow node from bottlenecking the whole job.

4.6 Composing jobs#

A single map-then-reduce pass is often not enough. MapReduce supports chaining: the output of one job (on the distributed filesystem) becomes the input of the next, so arbitrarily complex analyses are expressed as a directed sequence of MapReduce jobs. The classic example is PageRank, an iterative graph algorithm: each iteration is one MapReduce job, and a small aggregation after each iteration (a single convergence number brought back to the master) decides whether to launch another. Iterative computation is thus possible even within the rigid two-stage model.

4.7 Strengths and limitations#

The strengths follow from the abstraction. Developer simplicity: two functions, with parallelisation, distribution, synchronisation, fault tolerance, load balancing, and communication all hidden. Scalability to thousands of nodes and petabytes. Flexibility through composition, including iterative algorithms. And rapid prototyping: because an analysis is often run only once or twice before being revised, fast development matters more than execution-time optimisation, which is exactly what lets domain experts run large experiments without infrastructure expertise.

The limitations are equally direct. High overhead from scheduling, shuffle, and speculative re-execution makes it unsuitable for latency-sensitive or high-performance workloads; raw performance is well below a dedicated HPC system tuned for one problem. The rigid two-stage structure does not fit every problem, and each step must complete before the next begins. Above all, there is one hard prerequisite:

5. The Dataflow Model#

5.1 Generalising MapReduce#

MapReduce was foundational but very fixed: exactly two stages, always map then reduce, nothing else. The generalisation is the dataflow programming model. The core idea is unchanged, functional transformations over immutable data, but the constraints are lifted:

• Any number of transformation steps, not exactly two.
• The steps form an arbitrary directed acyclic graph (DAG) of operators, not a fixed linear pair.
• A rich operator set: map, filter, join, group-by, and many more, not just map and reduce.
• A unified abstraction for both batch and stream processing.

As a developer you write something that looks like Java Streams or a functional pipeline: operators chained together, each consuming data and producing data, with no mutable shared state.

5.2 Operators, stages, and tasks#

Three levels of terminology, easy to confuse and worth pinning down, connect the program the developer writes to what actually runs on the cluster.

In one line: operators are what the programmer writes, stages are what the framework builds by fusing operators between shuffles, and tasks are how stages are parallelised and scheduled onto machines.

6. Two Execution Architectures#

Given the same logical DAG, engines differ fundamentally in how they handle tasks. There are many platforms, but two extremes bracket the design space.

Scheduling of tasks (representative: Apache Spark). Tasks are scheduled stage by stage. A master waits for all tasks of one stage to finish, materialises their output (in memory or on disk), and only then schedules the next stage. Independent branches of the DAG may be scheduled concurrently, but a data dependency forces sequential execution. This is MapReduce generalised to arbitrary DAGs. Spark, from the mid-2010s, is today’s de-facto standard for large-scale analytics; a decade of cheaper memory means it caches intermediate results in memory by default (spilling to disk only when memory is exhausted), which is safe precisely because lost in-memory data can be recomputed, and dramatically faster than MapReduce’s disk round-trips, especially for iterative algorithms.

Pipelining of tasks (representative: Apache Flink). All tasks across all stages are instantiated up front when the job is submitted, connected by ephemeral network channels (typically TCP). As soon as a task produces output it sends it directly downstream, where the next task can begin without waiting for the upstream stage to finish. This gives inter-stage parallelism: multiple stages are active at once, data flowing continuously. In word count, a mapper can emit a tuple per word as it reads, without finishing the document, while the aggregator downstream already counts.

The pivotal difference is decoupling. In scheduling, A produces into non-ephemeral storage and B consumes later; the storage may be a distributed filesystem (MapReduce), memory or disk (Spark), or a queue. Because the two stages are decoupled, all of scheduling’s advantages, and its one cost, follow.

6.1 Advantages of scheduling#

Dynamic, data-aware load balancing. A pipeline instantiates every task before any data is seen, so it must guess the number of tasks per stage and split the data in advance, usually assuming a uniform distribution. If the real data is skewed, some tasks are overloaded with no way to rebalance at runtime. A scheduler, by contrast, can observe the actual data distribution before launching a stage and assign tasks accordingly, also accounting for data locality, hardware heterogeneity, and current load, all runtime information a pipeline cannot use.

Elasticity. A pipeline fixes the machine count at job start; changing it means tearing down and rebuilding the whole topology. A scheduler can add or remove resources between stages: fewer machines if a stage produced less data than expected, more if the job is running behind. Each stage is independent, so resizing between stages is cheap.

Fine-grained fault tolerance via lineage. If intermediate results are lost, the scheduler reschedules the affected tasks. If those tasks’ inputs were also lost (they were in memory), it traces the lineage, the chain of transformations that produced the data, and recomputes only the minimal necessary subset upstream, going back step by step just far enough to regenerate what was lost, independently and without disturbing other tasks.

6.2 The cost of scheduling, and the advantages of pipelining#

Latency overhead. Starting a new stage costs the master a scheduling decision, task provisioning, and a load from intermediate storage. This is fine for batch workloads, where throughput dominates and the overhead is amortised over huge data volumes, but it makes scheduling ill-suited to continuously updated, low-latency results.

Pipelining trades exactly this away. Immediate processing: a downstream task starts on the first bytes it receives, so resources are never idle waiting for a whole stage. No scheduling overhead: no master decisions, no writes to storage between stages, no waiting for a stage to complete. Data flows continuously from task to task, which is why pipelining is ideal for stream processing and low end-to-end latency. The price is the loss of dynamic load balancing and elasticity (the fixed topology), and a harder fault-tolerance story.

6.3 Fault tolerance in a pipeline: distributed snapshots#

In a scheduling system each task runs to completion independently; if it fails, its output simply does not exist yet, so restart it. In a pipeline the tasks are live and continuously communicating: if task A fails midway it may already have sent half its output to B, and there is no clean boundary at which to restart. Restarting everything from scratch is wasteful, and there is no synchronisation telling us how much A had already sent.

The solution is distributed snapshots, a slightly simplified Chandy-Lamport algorithm (simplified because the topology is a known acyclic graph). It is the same snapshot mechanism seen in the synchronisation chapter, reused here to checkpoint a running pipeline.

Step by step: sources periodically inject markers into the stream. When a task receives a marker on one input, it stops reading that channel but continues on the others. When markers have arrived on all inputs, the task snapshots its current state to durable storage, forwards a marker on all outputs, and resumes. The marker propagates until every task has snapshotted. On failure, the entire pipeline is stopped, the snapshot is reloaded, and processing resumes from that point, replaying all data that arrived after the snapshot (which the ingestion layer, Section 7.4, has retained). Snapshot frequency is a tunable trade-off: frequent snapshots shorten recovery but add overhead; infrequent ones do the opposite. The same mechanism also implements elasticity: snapshot, stop, redistribute the state across more or fewer partitions, and restart, more disruptive than a scheduler’s incremental resizing.

6.4 Summary of the trade-off#

Both architectures can technically run both kinds of workload, but each was born for, and is optimised for, one of them.

7. Stream Processing#

7.1 Batch vs. stream: the nature of the problem#

Everything so far assumed batch processing: a static dataset, fully available on disk, is computed over once to produce a static result. Stream processing is a different beast. Data arrives continuously over time, and the system must produce continuously updated results as new data comes in. The input is a stream and so is the output.

From static data, on-demand query to static query, dynamic data.

The running example: compute the average temperature of each room in a building, updated as new sensor readings arrive.

Streaming introduces a fundamental difficulty: semantic ambiguity. Even “the average temperature over the last hour” leaves open how often to update the result, what to do if no reading arrives for several minutes, and what happens over a gap longer than an hour. Natural language does not specify a streaming computation; a precise, formal construct is needed.

7.2 Windows#

The primary construct is the window. A window formally specifies two things: what data to consider (which stream elements feed one instance of the computation) and when to trigger (how often a new result is emitted). It is parameterised by:

• Size: how much data, or time, the window spans.
• Slide: how often a new window starts and a new result is produced.

When slide = size, consecutive windows are disjoint: tumbling windows. When slide < size, they overlap and each element contributes to several windows: sliding windows.

Count-based windows express size and slide as numbers of elements; time-based windows express them as durations. The room query becomes precise as a time-based sliding window of size 1 hour, slide 5 minutes: every 5 minutes, compute over the last hour of readings. Each system attaches a precise semantics to the corner cases; many, for instance, emit nothing for a window that received no elements.

Windows are the reason streaming operators are stateful: the operator must remember which elements fall inside the current window in order to compute over them. This is a sharp departure from stateless map and reduce, where each element is handled independently, and it complicates both fault tolerance (the state must be snapshotted and recoverable) and semantics (boundaries, gaps, late data).

7.3 The problem of time: processing time vs. event time#

A window of “size 1 hour” hides a deep question we have met before: in a distributed system there is no single clock. Who owns time?

Processing time was the early approach (including early Spark): each machine uses its own local wall clock. It is simple but problematic. Results become non-deterministic: they depend on how fast each machine runs and how well clocks are synchronised, not only on the data. This breaks fault tolerance (replaying data after a failure gives different results, since the local clock has moved on), produces inconsistent window boundaries across drifting machines, and, with multiple sources, makes the processing order depend purely on network delays.

Event time is the modern answer: time is attached to the data by the source. Each element carries a timestamp of when the event actually occurred, and the processing network never consults its own clock, it only reads timestamps. This buys determinism (same input, same timestamps, same result, however many times it is run), replay safety (stored data reprocesses consistently), and decoupling (responsibility for time accuracy sits with the sources, not the processors).

7.4 Watermarks and the ingestion layer#

Event time raises a new question: how does a processor know it has seen all the data for a window, given that data can arrive out of order or late? It cannot just close a window at wall-clock time $T$. The answer is the watermark: a marker injected into the stream that declares

“no future record will carry a timestamp earlier than $T$.”

When a processor has received a watermark for time $T$ on all its input channels, it knows every event up to $T$ has arrived and can safely fire any window closing at or before $T$; it then propagates the watermark downstream, preserving ordered processing through a multi-stage pipeline. Watermarks are distinct from Chandy-Lamport snapshot markers: their purpose is to advance the notion of time, not to checkpoint state.

In practice, physical sensors are not wired directly to the processing network. An intermediate ingestion layer, typically a distributed queue such as Apache Kafka, sits between them. It receives data from external sources and stores it durably for a configurable period, buffers and reorders it, generates and injects the watermarks, and replays stored data to the processors after a failure. The event-time contract is therefore not between a flaky edge sensor and the processor, but between Kafka and the processing framework, a guarantee that is practical and enforceable inside the data centre.

7.5 Implementing stream processing#

How the two architectures realise streaming differs, and it is here that their fit shows.

In a pipeline (Flink). Streaming is natural. Tasks are always running, data flows through continuously, and a stateful window operator keeps the last hour of readings per room in memory, updating with each element and emitting a new average every 5 minutes. On failure, the Chandy-Lamport snapshot restores the operator’s state and Kafka replays from the last snapshot.

In a scheduling system (Spark): microbatches. A scheduler cannot natively process an infinite stream, it schedules discrete stages to completion. The trick is microbatching: cut the stream into small fixed intervals (a few hundred milliseconds up to seconds) and run each as an ordinary batch job, repeating continuously to produce a stream of outputs.

Microbatching has a latency floor. Because starting a stage carries scheduling overhead, microbatches cannot shrink below a few hundred milliseconds; sub-millisecond requirements leave pipelining as the only option. The harder problem is state: a 1-hour window spans many 5-minute microbatches, so each microbatch must account for the accumulated state, not just the new data. The elegant solution is to treat state as data. At the end of each microbatch the updated state is written to the intermediate storage alongside the output; at the start of the next microbatch it is reloaded, merged with the new input, and the computation proceeds. This keeps the model functional and stateless in spirit, the state is an externalised persistent artifact rather than a live in-process value, and using in-memory storage keeps the load/store overhead small.

7.6 Choosing an architecture for streaming#

For example, an e-commerce platform hit by a spike (Black Friday) needs to scale up fast. If second-level latency is acceptable, Spark’s microbatching allows elastic provisioning of extra machines between microbatches; the same scaling in a pipeline requires a disruptive snapshot-and-restart cycle.

8. Dataflow as a Compilation Target#

In practice, developers rarely write raw dataflow programs today. Spark, Flink, and their peers act as execution targets for higher-level abstractions: SQL for structured data, DataFrames (pandas-like APIs) for tabular manipulation, graph-processing libraries, and machine-learning libraries. These compile automatically into dataflow DAGs that the engine executes. The developer works at the abstraction that matches the domain, and the distributed execution underneath is transparent.

The through-line of the chapter is a single conceptual shift: from mutable shared state, which does not scale in a distributed setting, to immutable data flowing through parallel transformations. It is this shift that lets failures, stragglers, and variable load all be handled gracefully, without coordination between tasks, and it is the idea on which every system from MapReduce to Spark and Flink is built.

9. Exam Questions#

The questions below are drawn from past exam papers. The professor does not publish official solutions; the worked answers here are unofficial.

One question on this topic recurs, essentially verbatim, across several sessions.

10. Glossary#

Compiled from G. Cugola's lectures (A.Y. 2025/26), slides + class transcriptions. Not official course material.