Unit V — Applications of Parallel Computing

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 key

Map

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 3

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

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.

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.

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.