Distributed Processing: MapReduce, Spark & Big Data

Processing data too big for one machine. Learn why we distribute (volume, parallelism), horizontal scaling and Amdahl's law, MapReduce (map, shuffle, reduce), Apache Spark (driver/executors, RDDs and DataFrames, lazy evaluation, DAG and stages, narrow vs wide transformations, the shuffle), partitioning and data skew, broadcast joins, caching, fault tolerance via lineage, cluster sizing, and alternatives (Dask, Ray, Flink, BigQuery, DuckDB) — with Python simulating MapReduce word count with hash partitioning and skew measurement.

When data reaches terabytes or petabytes, a single machine can't store or process it fast enough. Distributed engines split data into partitions and process them in parallel across many machines, then combine results.

The expensive part is moving data between machines (the shuffle); good distributed engineering minimises and balances it.

An analogy

Counting all the words in a library: give each volunteer a shelf (map), have them sort their tallies into bins by first letter and send each bin to one counter (shuffle), and each counter adds up their letters (reduce). If one bin is huge (skew), one counter becomes the bottleneck.

Why distribute?

Scale up (bigger machine) is simple but limited and expensive; scale out (many commodity machines) is nearly unlimited. Data is split into partitions processed in parallel. Amdahl's law limits speed-up: any serial part (driver work, final aggregation) caps the benefit, and coordination/shuffle costs grow with cluster size. Today, single-node engines (DuckDB, Polars) handle surprisingly large data — distribute only when needed.

Apache Spark

Key concepts:

Joins, skew and shuffles

Joins between large tables shuffle both sides by key (sort-merge join); joining a large table to a small one can broadcast the small table to every executor, avoiding the shuffle. Skew — a few keys with huge counts (a celebrity user, a 'null' key) — makes a few tasks run forever; fix with salting, adaptive query execution (AQE skew join), filtering nulls or pre-aggregating. Tune partition counts and avoid collecting large data to the driver.

Cluster design and the ecosystem

Size executors by memory per core and data per partition; use autoscaling and spot instances for batch; cache only reused data. Storage-compute separation (Spark on object storage, serverless warehouses) dominates the cloud. Alternatives: Flink (streaming-first), Dask and Ray (Python-native, ML workloads), Trino/Presto (interactive SQL), BigQuery/Snowflake (serverless MPP). Distributed systems face partial failures, stragglers, consistency trade-offs (CAP) and cost — observability and profiling (Spark UI) are essential.

Formulas

Worked example: Amdahl

Given: p = 0.95, N = 20

Find: Speed-up.

Answer: 10.3×

Worked example: Partition count

Given: 640 GB input, 128 MB partitions

Find: Partitions.

Answer: 5000 partitions

Worked example: Broadcast join

Given: 1 TB facts ⋈ 50 MB country table

Find: Strategy.

Answer: Broadcast the 50 MB table — no shuffle of the 1 TB

MapReduce word count with hash partitioning

from collections import defaultdict
import zlib
# MapReduce word count with hash partitioning across 3 reducers, and skew detection
docs = ["big data big pipelines", "data lakes and data warehouses", "big clusters process data"]
mapped = [(w, 1) for d in docs for w in d.split()]                       # map
partitions = defaultdict(list)
for w, c in mapped:                                                      # shuffle by stable hash
    partitions[zlib.crc32(w.encode()) % 3].append((w, c))
result = {}
for p in sorted(partitions):                                             # reduce
    counts = defaultdict(int)
    for w, c in partitions[p]:
        counts[w] += c
    result.update(counts)
    print(f"reducer {p}: {len(partitions[p])} records -> {dict(sorted(counts.items()))}")
print("top words:", sorted(result.items(), key=lambda kv: -kv[1])[:3])
sizes = [len(v) for v in partitions.values()]
print(f"skew ratio max/avg = {max(sizes)/(sum(sizes)/len(sizes)):.2f}")
# reducer 0: 2 records -> {'and': 1, 'pipelines': 1}
# reducer 1: 3 records -> {'clusters': 1, 'lakes': 1, 'process': 1}
# reducer 2: 8 records -> {'big': 3, 'data': 4, 'warehouses': 1}
# top words: [('data', 4), ('big', 3), ('pipelines', 1)]
# skew ratio max/avg = 1.85

Each word goes to the reducer chosen by its hash, so all counts for a word meet in one place. Reducer 2 receives 8 of 13 records because the hot keys 'data' and 'big' hash there — a skew ratio of 1.85 means that reducer takes nearly twice as long as average. In Spark, map-side combining (reduceByKey) and salting hot keys fix this.

Common mistakes

Applications

Key takeaways

Going further