Skip to content
LumenaryAcademy
Foundations 80 min

Batch processing and MapReduce

The 2004 idea that made thousand-machine jobs routine — build a small engine, break it in instructive ways, and see why Spark came next.

Code tested · 6AI-draftedAwaiting review by a data engineer

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

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.

History & global context

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.

DefinitionsH

The model, precisely

Definition— MapReduce job

A map function takes one input record (k1,v1)(k_1, v_1) and returns a list of intermediate pairs (k2,v2)(k_2, v_2). A partition function assigns each intermediate key to one of RR reduce tasks, usually hash(k2) mod R\text{hash}(k_2) \bmod R. 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 k2k_2 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.

input splitsmap taskslocal diskshufflereduce tasksoutput filessplit 1split 2split 3mapmapmapreduce 0reduce 1output 0output 1r0r1r0r1r0r1
The flow of a MapReduce job with three map tasks and two reduce tasks. Each map task writes one bucket per reducer to its local disk; in the shuffle, every reducer fetches its bucket from every map task.

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 v1⊕v2⊕⋯⊕vnv_1 \oplus v_2 \oplus \cdots \oplus v_n for an operation ⊕\oplus that is associative and commutative (with an identity element for the empty case), and the combiner computes the same ⊕\oplus 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 V1,…,VmV_1, \dots, V_m whose union is the full multiset VV. The combiner replaces each VjV_j by the single value cj=⨁Vjc_j = \bigoplus V_j. The reducer computes c1⊕⋯⊕cmc_1 \oplus \cdots \oplus c_m. By associativity this equals ⨁\bigoplus of all values of V1V_1 followed by all values of V2V_2, and so on; by commutativity the order of the values does not matter; so the result is ⨁V\bigoplus V, 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 (sum,count)(\text{sum}, \text{count}) 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.

ComputationC

A small MapReduce engine

The engine below keeps the essential structure: input partitions as lists, a map phase in which each map task writes RR 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.

python
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)
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

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.

ComputationC

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.

python
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}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

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.

ComputationC

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.

python
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")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

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.

ComputationC

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).

python
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'}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

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.

ExplanationH

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):

python
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 misconceptionsH

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

Exercises

1. Batch processing and MapReduce

Warm-upHuman

In 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.

Choose all that apply

2. Batch processing and MapReduce

CoreHuman

Four 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

CoreHuman

During 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?

Choose one

4. Batch processing and MapReduce

CoreComputational

The 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.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

5. Batch processing and MapReduce

StretchComputational

Write 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.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

6. Batch processing and MapReduce

CoreHuman

The 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?

Choose one

7. Batch processing and MapReduce

Warm-upHuman

The 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