Big Data & Parallel Processing
Session 14 • 2311CSC501J — Hadoop, MapReduce & Spark
What You'll Learn
- Why some data is too big for any one machine
- Hadoop = HDFS + MapReduce + YARN
- Map → Shuffle → Reduce, traced end-to-end
- Why Spark's in-memory model is 10–100× faster
"Move the computation to the data, not the data to the computation."
— The one idea behind big data
Too Big For One Machine
This whole course, we made one machine faster
- More cores (Unit II) · better algorithms (Unit III) · OpenMP / MPI / CUDA (Unit IV)
- But some data is too big for any single machine — no amount of cores fits it.
Google, 2004: index the entire web — petabytes across thousands of disks. No computer you can buy holds that. Disks fail, machines crash. So how do you process it?
Scale UP (old way)
Buy a bigger machine. Stops working — the biggest box still isn't big enough, and it's absurdly expensive.
Scale OUT (the answer)
Buy a thousand cheap machines and make them cooperate. This session is how.
Move the Code, Not the Data
1,000 GB of logs on 100 machines (10 GB each). You want to count something across all of it.
Move data → code
Copy all 1,000 GB over the network to one big machine. The network is the slowest thing in the building. Dead on arrival.
Move code → data
Send your 5 KB program OUT to all 100 machines. Each processes its own local 10 GB. Only the tiny result comes back. This scales.
Data locality: run the computation where the data already lives. A program is kilobytes; the data is terabytes — always move the small thing.
This is just data parallelism (Session 01) — but the "cores" are now whole machines.
Hadoop: The Full Stack
Open-source (2006), built from two Google papers. Three parts — storage, compute, scheduling.
| Layer | Name | Job |
|---|---|---|
| Storage | HDFS | Store one giant file, split + replicated across many machines |
| Compute | MapReduce | The model + engine that runs your job in parallel across the cluster |
| Resource mgmt | YARN | The scheduler — decides which machine runs which task |
That's the whole stack. Everything else is detail. YARN even tries to place each task on the machine that already holds its data — data locality, automatically.
HDFS: Split & Replicate
HDFS chops a huge file into blocks (~128 MB) and keeps 3 copies of each on different machines.
A 512 MB file in HDFS (4 blocks, replication factor 3)
Block 1 Block 2 Block 3 Block 4
Node A [B1] [B3]
Node B [B1] [B2] [B4]
Node C [B2] [B3]
Node D [B1] [B2] [B4]
Node E [B3] [B4]
Every block lives on 3 machines. A disk dies -> the data survives.Why replicate? In a cluster of thousands of cheap machines, something is always broken. With 3 copies, a dead disk is a non-event — Hadoop reads another copy and quietly makes a fresh third one.
At this scale, fault tolerance isn't a feature. It's survival.
MapReduce: Just Two Functions
You write only map and reduce. The framework does all the parallelism, distribution, and failure recovery for free.
INPUT --> MAP (parallel) --> SHUFFLE & SORT --> REDUCE (parallel) --> OUTPUT
emit (k,v) group by key combine per keyMap
Each record → (key, value) pairs. Runs in parallel on every chunk. Data-parallel.
Shuffle & Sort
Framework groups all values by key across the cluster. The network-heavy step.
Reduce
One key + all its values → combine. Runs in parallel. The reduction from S03/S10.
The restriction IS the point: every job has the same shape, so the framework solves the hard distributed-systems problems once, for everyone.
Word Count, Traced End-to-End
Input: "the cat sat the mat the cat" — the "hello world" of MapReduce.
1) SPLIT Mapper 1: "the cat sat the" Mapper 2: "mat the cat"
2) MAP M1: (the,1)(cat,1)(sat,1)(the,1) M2: (mat,1)(the,1)(cat,1)
(just tag each word with a 1 -- no counting yet)
3) SHUFFLE cat -> [1,1] mat -> [1] sat -> [1] the -> [1,1,1]
& SORT (group every pair by its key)
4) REDUCE cat -> 2 mat -> 1 sat -> 1 the -> 3
(sum the list of 1s per word)
OUTPUT cat 2 mat 1 sat 1 the 3The magic: the exact same two functions work on one sentence or on ten petabytes across 5,000 machines. You wrote map & reduce; the framework did everything else. (See the 01-mapreduce-wordcount demo.)
Worked Example: The Shuffle Is the Whole Cost
Word count on 1 TB of text — roughly 170 billion words — across 1,000 mappers. The map and reduce functions are trivial. So where does the time go?
WITHOUT a combiner:
map emits ("the",1) ("the",1) ("the",1) ... once per word occurrence
intermediate pairs: 170,000,000,000
at ~12 bytes each: ~2 TB must cross the network in the shuffle
WITH a combiner (aggregate locally before sending):
each mapper emits ("the", 4,213,905) — ONE pair per distinct word
~1,000,000 distinct words x 1,000 mappers x 12 bytes
~12 GB crosses the network| Stage | No combiner | With combiner |
|---|---|---|
| Read 1 TB from HDFS (local disks, parallel) | ~100 s | ~100 s |
| Map: split into words | ~60 s | ~60 s |
| Shuffle across the network | ~2,000 s | ~12 s |
| Reduce: add up the counts | ~20 s | ~5 s |
| Total | ~36 minutes | ~3 minutes |
Without a combiner, 92% of the job is the shuffle. The actual counting — the thing the program is for — is a rounding error. Everything else is moving data between machines.
A combiner is just your reducer, run on the mapper's own output before it leaves the machine. Usually one line:
job.setCombinerClass(SumReducer.class); // the same class as the reducerOne line, 12× faster job. That is the highest-leverage line of code in this entire unit.
The catch, and it's a real one: a combiner is only valid if your reduce operation is associative and commutative — if combining in any grouping gives the same answer.
| Operation | Combiner safe? |
|---|---|
| sum, count, min, max | Yes — grouping never changes the answer |
| average | No! avg(avg(1,2), avg(3,4,5)) ≠ avg(1,2,3,4,5). Emit (sum, count) pairs instead and divide at the very end. |
| median, distinct count | No — need the full set (or an approximate algorithm like HyperLogLog) |
The average trap catches people constantly, and it produces plausible-looking wrong numbers rather than an error. Notice it's the same associativity requirement as OpenMP's reduction clause in Session 03 — same maths, three units and a thousand machines apart.
Watch: MapReduce Explained
Watch someone else run the same map → shuffle → reduce trace. Repetition locks it in.
The only two functions you write are map and reduce. The framework handles the split, the shuffle, the parallel execution, and recovery when a machine dies.
Hadoop's Flaw: The Disk
MapReduce writes to disk between every step. Map → disk. Shuffle reads disk. Reduce → disk.
An iterative job (e.g. 3 passes over the data):
DISK -> Map -> Reduce -> DISK -> Map -> Reduce -> DISK -> Map -> Reduce -> DISK
'--- full disk round-trip between every stage -- the killer ---'For one pass, fine. But most analytics — and all machine learning — loop over the same data 20–30 times. That's 30 rounds of writing gigabytes to disk and reading them back. The job crawls.
Recall Unit II: RAM is roughly 100× faster than disk. That number is about to become the whole plot.
Apache Spark: Keep It In Memory
Keep the working data in RAM across steps instead of writing to disk between stages. RAM is ~100× faster → 10–100× faster than Hadoop on iterative jobs.
Spark, the same iterative job:
DISK -> [ load once ] Map -> Reduce -> Map -> Reduce -> Map -> Reduce -> DISK
'------- all in memory, no disk between -------'RDD
Dataset split across the cluster's memory; rebuildable if a machine dies. Wrapped by DataFrames (a distributed SQL table).
Lazy DAG
Transformations build a task graph (S07); Spark optimizes the whole plan, then runs only when you ask for a result.
Same model
Still map & reduce underneath — minus the disk trips, plus a far nicer API.
Worked Example: Why Spark Won (Honestly)
Run 10 iterations of an algorithm like PageRank or k-means over a 100 GB dataset. Per iteration: 10 s of computing, and 100 GB to move.
| Hadoop MapReduce | Spark | |
|---|---|---|
| Iteration 1: read the data | 60 s from disk | 60 s from disk |
| Iteration 1: compute | 10 s | 10 s |
| Iteration 1: write the result | 60 s back to HDFS | 0 — kept in RAM |
| Each of iterations 2–10 | 130 s (read + compute + write) | ~12 s (RAM + compute) |
| Total for 10 iterations | 1,300 s ≈ 22 min | 178 s ≈ 3 min |
7× faster — and notice Spark's computation is not faster at all. Both do 10 seconds of arithmetic per iteration. Spark wins entirely by not writing the intermediate result to disk and reading it straight back, nine times over.
Hadoop's model has no memory between jobs: every MapReduce job begins by reading HDFS and ends by writing HDFS. That was a deliberate 2004 choice — it makes fault tolerance almost free, because every intermediate result is already durable on disk. A fine trade for one job. Ruinous for ten in a loop.
About the "100× faster than Hadoop" on Spark's website — be sceptical, and know exactly why. Look at the shape of it:
speedup ~ (disk I/O + compute) x iterations
---------------------------------------
one initial load + compute x iterationsThe advantage grows with the number of iterations and shrinks as the compute per iteration grows. So:
- 100 iterations, light compute → genuinely 50–100×. That's where the marketing number comes from, and it is real.
- A single pass, heavy compute → roughly 1×. For a one-shot ETL job Spark buys you nicer APIs, not speed.
- Data larger than cluster RAM → Spark spills to disk and most of the advantage evaporates.
And here's what Spark had to invent to make RAM safe. If an intermediate result lives only in memory and a node dies, the data is simply gone. Spark's answer is lineage: it stores the recipe that produced each partition, not the partition. Lose one, and it recomputes just that one from its parents.
That's the elegant bit worth remembering: Hadoop gets fault tolerance by storing everything; Spark gets it by storing how to rebuild anything. Both are correct. One of them is seven times faster on a loop.
Spark vs Hadoop MapReduce
| Dimension | Hadoop MapReduce | Apache Spark |
|---|---|---|
| Data between steps | Written to disk | Kept in memory (RAM) |
| Speed (iterative) | Baseline | 10–100× faster |
| API | Just map + reduce (verbose) | SQL, DataFrames, Python, MLlib |
| Evaluation | Eager, stage by stage | Lazy — optimizes a DAG first |
| Best for | Huge one-pass batch; low memory | Iterative ML, interactive queries |
The honest nuance: Hadoop isn't dead — HDFS is still a common storage layer, and giant single-pass jobs still suit MapReduce. But for iterative and interactive work, Spark won.
Where It Runs & Why It Matters
You rent a cluster; you don't build one
- AWS EMR, Google Dataproc, Databricks — managed Hadoop/Spark by the hour.
- BigQuery, Snowflake, Redshift (Session 13) — the same massively-parallel ideas under plain SQL.
Twenty years of one idea
Google MapReduce paper (2004) -> Hadoop (2006) -> Spark (2014) -> cloud data platforms
split the data -> map in parallel -> shuffle by key -> reduce in parallel
(getting faster and easier the whole way)Map is data parallelism; reduce is the reduction. This is fan-out / fan-in — the same shape as an MPI Scatter → compute → Reduce, at data-center scale.
Quick Check: Is This a MapReduce Job?
The test: can you express it as independent work on each record, then grouped combining? Shout it out.
1. Count how many times each error code appears in 50 TB of logs
Perfect fit. Map → (code, 1). Reduce → sum. Combiner safe. This is word count wearing a different hat, and most real MapReduce jobs are.
2. Sort 100 TB of records
Yes — and famously so. Map partitions by key range, the shuffle does the global ordering, reduce sorts locally. Hadoop held the world sort record for years doing exactly this.
3. Train a neural network for 10,000 steps
Terrible fit. Every step depends on the previous one — 10,000 sequential job launches, each paying full HDFS round-trip. This exact pain is why Spark exists, and why AI training uses MPI-style all-reduce instead.
4. Find the median salary across 1 billion records
Possible, awkward. Median isn't associative — no combiner, so the full dataset shuffles. In practice you sort first, or accept an approximate answer. Some questions are just expensive to ask.
5. The one people get wrong: "Fetch one user's profile by ID, in under 10 ms"
Absolutely not — and this is the most valuable answer of the five. MapReduce launches JVMs, schedules containers and scans partitions; the startup alone is tens of seconds. It is a batch throughput engine, built to process petabytes over hours. For a single-record lookup you want a database index — a millisecond, on one machine.
Session 01's latency-versus-throughput distinction, one last time. Everything in Unit V buys throughput. None of it buys latency. Reaching for "big data" tooling on a small-data problem is one of the most expensive mistakes in the industry — and it's the same category error as the toll booth on day one.
Recap & What's Next
Key Takeaways
- Some data is too big for one machine → scale out and move the code to the data.
- Hadoop = HDFS (replicated blocks) + MapReduce (compute) + YARN (scheduling).
- MapReduce: write only map + reduce; framework does shuffle, distribution, recovery. Word count is the trace.
- Spark keeps data in memory → 10–100× faster; largely superseded raw MapReduce.
Homework
- Explain to a non-technical friend why counting words in all of Wikipedia needs a thousand computers.
- Re-draw the word-count trace from memory after watching a MapReduce video.
- Come ready: "How can you train an AI across millions of phones without collecting their data?"
Next session: Real-Time Systems & Recent Trends (+ Course Wrap-Up)
Federated learning, the computing frontier, and tying the whole course together.