Jobs that run while the city sleeps
Much of the world's computing happens in batches. Every night a national statistics office recomputes regional price indices from millions of scanned receipts; a power company turns a day of smart-meter readings into tomorrow's bills; a search engine rebuilds part of its index; a genomics lab aligns the day's sequencing runs. Each job reads a large, fixed input, computes, writes a result, and stops.
Lumenary CS's batch and stream processing lesson introduced the model that made such jobs routine on thousands of machines: MapReduce. This lesson goes inside it. You will build a small engine, run three classic jobs on it, and then break it in the ways real clusters break — skewed keys, slow machines, dead machines, and code that is not quite deterministic — to see which design decisions keep the answers right. MapReduce itself is rarely written by hand any more, but its ideas run every Spark job, every warehouse query that shuffles data, and the pipelines in the rest of this elective.
The 2004 idea
By the early 2000s Google ran hundreds of special-purpose programs over its crawled web pages and logs: counting, indexing, building link graphs, summarising queries. Each was simple at heart, but each had to be parallelised over hundreds of machines, and each had to cope with machines failing mid-run, data unevenly spread, and the occasional slow disk. The parallel plumbing dwarfed the actual logic, and every team rewrote it.
Jeffrey Dean and Sanjay Ghemawat noticed that most of these programs had the same shape. They first transformed each input record into intermediate key–value pairs, then combined all the values that shared a key. Those two steps echo the map and reduce (fold) operations of Lisp and other functional languages. If programmers wrote only those two functions, a library could do everything else: split the input, schedule tasks near their data, move intermediate data between machines, re-run what failed, and work around slow machines. Their 2004 paper described the library and its use inside Google. Underneath sat the Google File System (2003), which stored files in large replicated chunks across the same machines that computed on them, so the scheduler could usually send a map task to a machine that already held its input — moving computation to the data, not data to the computation.
The paper's lasting contribution was less the two functions than the contract behind them: write deterministic functions without side effects, and the system guarantees the same output as a sequential run, however many machines fail.
The model, precisely
Definition— MapReduce job
A map function takes one input record and returns a list of intermediate pairs . A partition function assigns each intermediate key to one of reduce tasks, usually . The shuffle delivers to each reduce task every intermediate pair whose key it owns, grouped by key and sorted. A reduce function takes a key with the list of all its values and returns a list of output values. Map tasks run in parallel over input splits; reduce tasks run in parallel over partitions of the key space.
An optional combiner runs reduce-like logic on each map task's output before the shuffle, so that a mapper which saw "the" ten thousand times sends one pair instead of ten thousand. When is that safe?
Theorem— Combiners are safe for commutative monoids
Suppose the reduce function for each key computes for an operation that is associative and commutative (with an identity element for the empty case), and the combiner computes the same over any subset of a key's values. Then applying the combiner to each map task's values, in any grouping, and reducing the partial results, gives the same output as reducing all the original values.
Proof
The values of one key are split among map tasks as disjoint sub-multisets whose union is the full multiset . The combiner replaces each by the single value . The reducer computes . By associativity this equals of all values of followed by all values of , and so on; by commutativity the order of the values does not matter; so the result is , the reduction of the original values. ∎
∎
Sum, count (as a sum of ones), minimum and maximum qualify. The mean does not: the mean of per-mapper means is wrong when mappers saw different numbers of values. The fix is to change what flows through the shuffle — emit pairs, which add component-wise, and divide only in the final reduce. Medians and exact distinct counts have no such small summary, which is why engines offer mergeable approximate sketches for them, such as t-digest for quantiles and HyperLogLog for distinct counts.
A small MapReduce engine
The engine below keeps the essential structure: input partitions as lists, a map phase in which each map task writes local buckets, a shuffle as a dictionary of lists per reducer, and reducers that see their keys in sorted order. It counts the records that cross the shuffle, which often dominate the cost of a real job. Three classic jobs run on it: word count (with and without a combiner), an inverted index, and a reduce-side join, in which records from two inputs are tagged with their source, meet at the reducer that owns their key, and are paired up there.
import re
import zlib
from collections import defaultdict
def partition(key, R):
"""Every map task must send a key to the same reducer: use a hash that is stable across machines."""
return zlib.crc32(repr(key).encode()) % R
def run_job(splits, mapper, reducer, R=3, combiner=None):
"""A MapReduce job. splits: list of input partitions (lists of (key, value) records)."""
# Map phase: map task m turns its split into R buckets, one per reducer (on its local disk).
buckets = []
for split in splits:
local = [defaultdict(list) for _ in range(R)]
for k, v in split:
for k2, v2 in mapper(k, v):
local[partition(k2, R)][k2].append(v2)
if combiner: # run reduce logic early, per map task
local = [{k: [out for _, out in combiner(k, vs)] for k, vs in b.items()} for b in local]
buckets.append(local)
shuffled = sum(len(vs) for local in buckets for b in local for vs in b.values())
# Shuffle: reducer r fetches bucket r from every map task and groups the values by key.
output = []
for r in range(R):
groups = defaultdict(list)
for local in buckets:
for k, vs in local[r].items():
groups[k].extend(vs)
for k in sorted(groups): # each reducer sees its keys in sorted order
output.extend(reducer(k, groups[k]))
return sorted(output), shuffled
docs = {1: "the night train to Mombasa leaves at seven",
2: "tea and bread on the train",
3: "the harbour at Mombasa at night",
4: "seven ships and the night tide"}
splits = [[(1, docs[1]), (2, docs[2])], [(3, docs[3]), (4, docs[4])]] # two map tasks
def words(text):
return re.findall(r"[a-z]+", text.lower())
# 1. Word count.
wc_map = lambda doc, text: [(w, 1) for w in words(text)]
wc_reduce = lambda w, counts: [(w, sum(counts))]
counts, plain = run_job(splits, wc_map, wc_reduce)
_, combined = run_job(splits, wc_map, wc_reduce, combiner=wc_reduce)
print("top words:", sorted(counts, key=lambda kv: -kv[1])[:4])
print(f"records shuffled: {plain} without a combiner, {combined} with one")
# 2. Inverted index: word -> the documents that contain it.
ii_map = lambda doc, text: [(w, doc) for w in set(words(text))]
ii_reduce = lambda w, ids: [(w, sorted(ids))]
index, _ = run_job(splits, ii_map, ii_reduce)
print("index:", [kv for kv in index if kv[0] in ("mombasa", "night", "train")])
# 3. Reduce-side join: tag each record with its source; the reducer pairs them up per key.
stations = [("MSA", ("station", "Mombasa")), ("NBO", ("station", "Nairobi")), ("VOI", ("station", "Voi"))]
trips = [(101, ("trip", "NBO", 3)), (102, ("trip", "MSA", 5)), (103, ("trip", "NBO", 2)), (104, ("trip", "KSM", 1))]
def join_map(key, rec):
if rec[0] == "station":
yield key, ("S", rec[1]) # station code -> name
else:
yield rec[1], ("T", rec[2]) # station code -> passengers on one trip
def join_reduce(code, tagged):
names = [v for tag, v in tagged if tag == "S"]
loads = [v for tag, v in tagged if tag == "T"]
for name in names: # inner join: needs both sides
if loads:
yield name, len(loads), sum(loads)
joined, _ = run_job([stations[:2] + trips[:2], stations[2:] + trips[2:]], join_map, join_reduce)
print("trips and passengers per destination:", joined)The combiner cuts the shuffle from 26 records to 21 here; on real text, with words repeated thousands of times per split, the reduction is usually far larger. The inverted index is the core data structure of a search engine, built in two short functions. The join keeps only stations with trips and trips with known stations — an inner join — so Voi (no trips) and the trip to KSM (no station row) drop out. A reduce-side join works for inputs of any size, but it shuffles both of them; when one input is small, a map-side join loads it into every map task's memory instead, the broadcast join of Analytical databases.
Notice one deliberate detail: the partition function uses zlib.crc32 rather than Python's built-in hash, which is randomised per process for strings. Every map task must send a given key to the same reducer, so the hash must be identical on every machine.
Skew
A reduce task's work is proportional to the number of records it receives, and keys are rarely equally popular. Word frequencies, city sizes, product sales and website traffic all follow heavy-tailed distributions in which a few keys are enormous. With hash partitioning, whichever reducer owns the most popular key does the most work — and the job waits for its slowest reducer.
The block simulates 200,000 search queries from 40 map tasks, with query popularity roughly following Zipf's law, and counts the records each of 8 reducers receives under three strategies: no combiner, salting the two hottest keys (appending a random suffix 0–3, so each is spread over up to four reducers), and a combiner.
import random
import zlib
from collections import Counter
rng = random.Random(5)
# Search queries from 40 map tasks. Query popularity is heavily skewed (roughly Zipf-like):
# the k-th most popular query is about k times rarer than the most popular one.
vocab = [f"q{k}" for k in range(1, 5001)]
weights = [1 / k for k in range(1, 5001)]
M, R = 40, 8
splits = [rng.choices(vocab, weights, k=5000) for _ in range(M)]
def reducer_of(key, R):
return zlib.crc32(key.encode()) % R
def loads(records_per_mapper):
"""Records arriving at each reducer, given what each map task emits."""
load = Counter()
for emitted in records_per_mapper:
for key, _ in emitted:
load[reducer_of(key, R)] += 1
return [load[r] for r in range(R)]
plain = [[(q, 1) for q in split] for split in splits] # one record per query
combined = [list(Counter(split).items()) for split in splits] # combiner: one per key per task
salted = [[(f"{q}#{rng.randrange(4)}", 1) if q in ("q1", "q2") else (q, 1) for q in split] for split in splits]
top = Counter(q for s in splits for q in s).most_common(3)
print(f"{M * 5000:,} queries; most common: {top}")
for name, emitted in [("no combiner", plain), ("hot keys salted x4", salted), ("with combiner", combined)]:
load = loads(emitted)
print(f"{name:20s} records per reducer: {load} max/mean = {max(load) / (sum(load) / R):.2f}")Without help, the reducer owning the top query receives 1.56 times the average load. Salting the two hottest keys brings that down to 1.16; the price is a second, small aggregation step to add q1#0 to q1#3 back into q1, and the need to know which keys are hot (from a sample, or from the previous run). For an aggregation that has a combiner, the combiner fixes skew almost entirely: each map task sends at most one record per key, so the hottest key costs its reducer 40 records, not 21,980. Skew is hardest for operations without a compact partial result — joins on a hot key, or collecting all of a key's values — which is where salting, splitting hot keys and the adaptive skew handling of modern engines such as Spark's adaptive query execution earn their keep.
Stragglers and failures
On a few thousand commodity machines, something is always wrong: a disk retrying reads, a machine sharing its processor with another job, a network card negotiated down to a tenth of its speed, a machine that dies outright. MapReduce's coordinator (the paper calls it the master) handles both slowness and death with one tool: running tasks again.
- Backup tasks. When the map or reduce phase is nearly finished, the coordinator launches backup copies of the tasks still running and takes whichever copy finishes first. This costs a few per cent more computation and protects the job from its single slowest machine. Hadoop calls it speculative execution.
- Re-execution after failure. The coordinator pings workers. If one stops answering, its in-progress tasks are rescheduled elsewhere — and so are its completed map tasks, because their output lived on that machine's local disk and is now unreachable. Completed reduce tasks are safe: their output was written to the replicated file system.
The block is an event-driven simulation of one map phase — 60 tasks of about 10 seconds on 10 workers — under a slow worker, with and without backup tasks, and under a worker crash at two different moments.
import heapq
import random
def simulate(slow=(), crash=None, backups=False, tasks=60, workers=10, seed=1):
"""Event-driven simulation of a map phase. Returns (finish time, task executions started).
slow: workers that run 4x slower. crash: (worker, time) at which a worker dies."""
rng = random.Random(seed)
work = [10 + rng.uniform(0, 2) for _ in range(tasks)] # seconds on a healthy worker
pending, running, output_on, alive = list(range(tasks)), {}, {}, set(range(workers))
events, runs = [], 0 # heap of (time, worker, task, run id)
def start(w, task, now):
nonlocal runs
runs += 1
end = now + work[task] * (4 if w in slow else 1)
running[w] = (task, end, runs)
heapq.heappush(events, (end, w, task, runs))
def dispatch(now):
for w in sorted(alive - set(running)):
if pending:
start(w, pending.pop(0), now)
elif backups: # near the end: back up stragglers
copies = [t for t, _, _ in running.values()]
late = [(end, t) for t, end, _ in running.values() if copies.count(t) == 1]
if late and max(late)[0] > now + work[max(late)[1]]: # a fresh copy would finish sooner
start(w, max(late)[1], now)
if crash:
heapq.heappush(events, (crash[1], crash[0], None, 0))
dispatch(0.0)
while len(output_on) < tasks:
now, w, task, run = heapq.heappop(events)
if task is None: # worker w crashes
alive.discard(w)
lost = [t for t, where in output_on.items() if where == w] # finished map output, on its disk
if w in running:
lost.append(running.pop(w)[0])
for t in lost:
output_on.pop(t, None)
if t not in pending and all(t != r[0] for r in running.values()):
pending.insert(0, t) # re-execute elsewhere
elif running.get(w, (None, None, None))[2] == run: # ignore copies already killed
del running[w]
if task not in output_on:
output_on[task] = w
for other, (t, _, _) in list(running.items()): # kill the losing copy, if any
if t == task:
del running[other]
dispatch(now)
return now, runs
print("60 map tasks of about 10 s on 10 workers")
for label, kw in [("all workers healthy", {}),
("worker 7 runs four times slower", dict(slow={7})),
("worker 7 slow, with backup tasks", dict(slow={7}, backups=True)),
("worker 3 crashes at t = 25 s", dict(crash=(3, 25.0))),
("worker 3 crashes at t = 55 s", dict(crash=(3, 55.0)))]:
t, runs = simulate(**kw)
print(f" {label:34s} finishes at {t:5.1f} s after {runs} task executions")At the scale of a real cluster, these effects are everywhere: Dean and Barroso's later essay "The Tail at Scale" generalises the lesson to every large system — when a request touches hundreds of machines, the rare slow one becomes the common case, and redundancy is cheaper than perfection. A failure of the coordinator itself was rare enough that the original implementation simply aborted the job and let the client retry; later systems replicate the coordinator's state, using consensus of the kind in Lumenary CS's replication and consensus lesson.
Why determinism matters
Re-execution is correct only if running a task again produces the same output. Suppose reducer 0 has already fetched its bucket from map task 2 when task 2's machine dies; task 2 is re-executed elsewhere, and reducer 1 fetches its bucket from the new attempt. If the map function is deterministic, both attempts produced identical buckets and nobody can tell the difference. If it is not — it samples records with a random generator seeded from the clock, or reads a value that changes, such as the current time or an external service — reducer 0 has seen one version of the task and reducer 1 another.
The block runs exactly that scenario. The map function samples about 30% of events and emits both a per-country count (owned by reducer 0) and a grand total (owned by reducer 1).
import random
import zlib
from collections import Counter
rng = random.Random(0)
events = [(i, rng.choice(["Chile", "Ghana", "Japan", "Poland"])) for i in range(2000)]
splits = [events[m::4] for m in range(4)] # four map tasks
def map_task(split, attempt, deterministic):
"""Sample about 30% of events; emit a per-country count and a grand-total count.
Reducer 0 receives the per-country keys, reducer 1 the grand total."""
clock = random.Random(attempt) # stands in for seeding from the clock
buckets = [Counter(), Counter()]
for event_id, country in split:
if deterministic:
keep = zlib.crc32(str(event_id).encode()) % 10 < 3 # decided by the record itself
else:
keep = clock.random() < 0.3 # decided by luck, differently per attempt
if keep:
buckets[0][country] += 1
buckets[1]["TOTAL"] += 1
return buckets
def run(deterministic):
outputs = [map_task(s, attempt=1, deterministic=deterministic) for s in splits]
result = Counter()
for out in outputs: # reducer 0 fetches its buckets...
result.update(out[0])
# ...then the machine holding map task 2's output fails, and the task is re-executed elsewhere.
outputs[2] = map_task(splits[2], attempt=2, deterministic=deterministic)
for out in outputs: # reducer 1 fetches its buckets afterwards
result.update(out[1])
countries = sum(v for k, v in result.items() if k != "TOTAL")
return countries, result["TOTAL"]
for deterministic in (True, False):
countries, total = run(deterministic)
print(f"{'deterministic' if deterministic else 'nondeterministic':16s} map: per-country counts sum to "
f"{countries}, grand total says {total}{'' if countries == total else ' <- inconsistent'}")With a deterministic map — the sampling decision is a hash of the event's id, so every attempt makes the same choice — the per-country counts add up to the grand total. With a nondeterministic one, they add up to 628 while the grand total says 613: the output corresponds to no single run of the program. The original paper states the guarantee precisely: with deterministic functions, the distributed output is what a sequential run without failures would produce; with nondeterministic ones, each reducer's output matches some sequential run, but different reducers may match different runs.
From Hadoop to Spark
Hadoop, begun in 2006 by Doug Cutting and Mike Cafarella and developed at scale at Yahoo, brought the two Google papers to everyone as open source: the Hadoop Distributed File System (HDFS) and Hadoop MapReduce, written in Java, with Hadoop Streaming allowing mappers and reducers in any language that reads standard input. An ecosystem grew around it — Apache Hive (from Facebook) compiled SQL into MapReduce jobs, Apache Pig offered a dataflow language, HBase a Bigtable-like store — and Hadoop 2 (2013) separated resource management into YARN so other engines could share the cluster. Not everyone was persuaded: in 2008–2010 database researchers, notably Michael Stonebraker and David DeWitt, argued that MapReduce re-invented parallel databases without their schemas, indexes and optimisers, and published comparisons showing parallel databases much faster on many queries, while Dean and Ghemawat replied that MapReduce's flexibility and fault tolerance served different needs. Both sides were partly right, and the systems that followed borrowed from each.
MapReduce's weakness was the boundary between jobs. Real pipelines chain many steps, and each MapReduce job wrote its entire output to the replicated file system for the next job to read back. Iterative algorithms — PageRank, k-means clustering, training a model by gradient descent — re-read the same input from disk on every iteration. Interactive questions waited for job start-up.
Apache Spark, started by Matei Zaharia at UC Berkeley's AMPLab in 2009 and described in a 2012 paper, kept MapReduce's model of deterministic transformations over partitioned data but represented a whole pipeline as a graph of resilient distributed datasets (RDDs), kept intermediate data in memory where possible, and replaced replication of intermediate results with lineage: the recipe to recompute any lost partition from its parents — re-execution again, now at the level of partitions. Word count in Spark's original API (not run here: it needs a Spark cluster):
from pyspark.sql import SparkSession
spark = SparkSession.builder.appName("word-count").getOrCreate()
counts = (spark.sparkContext.textFile("s3a://example-bucket/books/*.txt")
.flatMap(lambda line: line.lower().split()) # the map step
.map(lambda word: (word, 1))
.reduceByKey(lambda a, b: a + b) # shuffle; also combines before it
.sortBy(lambda kv: -kv[1]))
counts.saveAsTextFile("s3a://example-bucket/word-counts/")reduceByKey takes the associative, commutative operation of the theorem above and applies it on each partition before the shuffle as well as after: the combiner, built in. Most Spark code today uses the higher-level DataFrame and SQL APIs instead, whose optimiser plans shuffles, joins and pruning much as an analytical database does; Distributed processing takes up Spark in depth.
As of 2026, few new systems are built on Hadoop MapReduce. Many organisations still run Hadoop clusters, especially on premises, but new platforms mostly keep data in object storage and process it with Spark, Flink, Apache Beam (on Google Cloud Dataflow, Flink or Spark) or the cloud warehouses — available as managed services such as Amazon EMR, Google Cloud Dataproc, Databricks and Alibaba Cloud E-MapReduce, each billed by the machine-hour or by usage. The ideas of this lesson are in all of them: partitioned data, a shuffle keyed by hash, combiners, backup tasks, and recovery by deterministic re-execution.
Common misconceptions
Misconception
"MapReduce is obsolete, so its ideas no longer matter." The programming interface has been superseded, but the shuffle is still where Spark, Flink and warehouse queries spend much of their time and money, and skew, stragglers and deterministic re-execution are still how those systems fail and recover.
Misconception
"Any reducer can be used as a combiner." Only one that computes an associative, commutative operation whose output has the same form as its input. A mean of means is wrong; so is a count computed as the length of the value list (the reducer would count partial results, not records). Change what is emitted — (sum, count) pairs, or ones to be summed — and it works.
Misconception
"More reduce tasks always make a job faster." More reducers spread work only if the keys spread; a single hot key still lands on one reducer. Past a point, more tasks also mean more scheduling overhead and more, smaller output files.
Misconception
"Re-execution makes the job's effects happen exactly once." It makes the job's output files correct. Every side effect inside a task can happen several times, through retries and backup tasks, and must be made idempotent.
Exercises
1. Batch processing and MapReduce
Warm-upHumanIn each job below, the mapper emits (key, x) pairs with a number x, and the reducer shown is also used, unchanged, as the combiner. For which jobs does the combiner leave the output unchanged? Select all that apply.
2. Batch processing and MapReduce
CoreHumanFour workers A, B, C, D run 8 map tasks, numbered 1–8. Each task takes 10 s on A, B or C, but 50 s on D, whose disk is failing. Whenever a worker is idle it takes the lowest-numbered unassigned task (ties go to A, then B, then C, then D). Once no unassigned tasks remain, an idle worker instead starts a backup copy of a running task that has no copy yet, if the copy would finish earlier; a task is done when its first copy finishes.
At what time, in seconds, is the whole map phase finished?
3. Batch processing and MapReduce
CoreHumanDuring the reduce phase of a MapReduce job, a worker dies. It had completed 3 map tasks and 1 reduce task, and was in the middle of a second reduce task. Under the original design (map output on local disk, reduce output in the replicated file system), which tasks are re-executed?
4. Batch processing and MapReduce
CoreComputationalThe starter computes the mean temperature per station with the tiny engine run_job (do not change it). Its combiner computes a mean of each map task's values — so with the combiner switched on, the answers are wrong.
Rewrite mapper, combiner and reducer so that the job gives the exact mean per station both with and without the combiner. The combiner's output must have the same form as the mapper's values, so that it could be applied any number of times.
5. Batch processing and MapReduce
StretchComputationalWrite join_map and join_reduce for a reduce-side join of customers with their orders, run on the engine run_job from the starter. Input records are (record_id, record) where record is either ("C", (customer_id, name)) or ("O", (order_id, customer_id, amount)).
The job must output one tuple (customer_id, name, number_of_orders, total_amount) for every customer, including customers with no orders (a left outer join). Orders whose customer does not exist are dropped.
6. Batch processing and MapReduce
CoreHumanThe lesson's engine partitions keys with zlib.crc32(repr(key).encode()) % R instead of Python's built-in hash(key) % R. Why does that matter in a real, multi-machine MapReduce?
7. Batch processing and MapReduce
Warm-upHumanThe MapReduce paper calls them backup tasks: duplicate copies of still-running tasks launched near the end of a phase, the first to finish winning. What name does Hadoop use for this technique? (Two words.)
Further reading and resources
- MapReduce: Simplified Data Processing on Large Clusters · Jeffrey Dean and Sanjay Ghemawat · 2004The OSDI paper. Short and readable; its sections on fault tolerance, locality and backup tasks repay close study.
- The Google File System · Sanjay Ghemawat, Howard Gobioff and Shun-Tak Leung · 2003The replicated file system MapReduce read from and wrote to.
- Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing · Matei Zaharia et al. · 2012The paper behind Apache Spark.
- MapReduce and Parallel DBMSs: Friends or Foes? · Michael Stonebraker, Daniel Abadi, David DeWitt, Samuel Madden, Erik Paulson, Andrew Pavlo and Alexander Rasin · 2010Communications of the ACM; database researchers' comparison, published alongside Dean and Ghemawat's reply, "MapReduce — A Flexible Data Processing Tool".
- The Tail at Scale · Jeffrey Dean and Luiz André Barroso · 2013Why a few slow components dominate large systems, and the techniques, including hedged and backup requests, that tame them.
- Apache Hadoop
- Apache Spark: RDD programming guide