This is one of the most important ideas in distributed computation.
Break the computation into smaller pieces and send them to multiple nodes.
Collect the individual results and combine them into the final result.
Consider two computers connected through a network.
Even if the network is extremely fast, communication within a single computer is generally faster than communication across a network.
Moving 10 TB across the network can be expensive.
Only the relatively small computation results need to be transferred.
Processes individual pieces of data in parallel.
Combines the intermediate results into a final answer.
Suppose we want to count each word.
Provides distributed storage.
Data is distributed across multiple machines.
Provides distributed computation over that data.
Spark also follows the broad idea of distributing computation across multiple machines, but its programming model and data-processing approach differ significantly from traditional Hadoop MapReduce.
The reality is more nuanced.
Both distribute computation.
This is an important interview concept.
Processes large amounts of historical data.
Processes new events quickly.
Combines or exposes the results to applications/users.
Keep computation close to the data.
Multiple nodes process different portions of the workload simultaneously.
Process accumulated data periodically.
Process events continuously as they arrive.
Data is distributed across multiple machines so computation can happen close to it.
MapReduce — Class Notes
1. What is MapReduce?
MapReduce is primarily a computation pattern, not a programming language, product, or specific open-source project.
It is a mathematical/computational abstraction that helps us divide a large computation into pieces that can be executed across many machines.
Core idea
Break a large computation into smaller parallel computations, process data near where it is stored, then combine the results.
MapReduce became famous through Hadoop, but:
MapReduce ≠ Hadoop
2. Why MapReduce?
Suppose we have:
100 TB Data
↓
Distributed across
100 computers
A traditional program might try to bring the data to one machine:
100 TB
↓
Network
↓
One Server
↓
Process
That is inefficient.
MapReduce instead tries to do:
100 TB Data
↓
┌──────────┼──────────┐
↓ ↓ ↓
Node 1 Node 2 Node 3
↓ ↓ ↓
Map Map Map
↓ ↓ ↓
└──────────┼──────────┘
↓
Shuffle
↓
Reduce
↓
Final Result
The important principle is:
Move computation to the data, instead of moving the data to the computation.
3. MapReduce Gives Us Constraints
MapReduce can initially feel very restrictive.
Instead of writing an arbitrary program, we have to express our computation using two major functions:
MAP
↓
REDUCE
Why impose these restrictions?
Because those constraints make it much easier for a framework to:
Parallelize computation
Distribute work across machines
Handle huge datasets
Recover from failures
Execute work close to data
Scale from a few machines to hundreds or thousands
Important lesson
The limitation is actually a strength.
MapReduce sacrifices programming flexibility in exchange for massive scalability.
4. The Two Main Functions
MapReduce revolves around two functions:
Map
Input:
Key + Value
Output:
List of Key + Value pairs
Conceptually:
map(key, value)
↓
[(key1,value1), (key2,value2), ...]
Reduce
Input:
Key + List of Values
Output:
Key + Result
Conceptually:
reduce(key, [value1,value2,value3,...])
↓
(key,result)
5. Key-Value Pair
MapReduce commonly represents data as:
(Key, Value)
Almost anything can be represented this way.
Examples:
(1, "Hello World")
(2, "Java Redis")
(3, "Spark Hadoop")
The value could also represent:
Text
Image data
Sensor data
Serialized objects
Database records
Log entries
The key is important because MapReduce uses the key to determine how data should be grouped during shuffle.
6. Map Function
The mapper receives one key-value pair.
Mapper
↓
(Key, Value)
↓
List of Key-Value pairs
For example:
Input:
(1, "Java Java Redis")
Mapper might produce:
(Java, 1)
(Java, 1)
(Redis, 1)
The mapper doesn't necessarily have to produce many records.
It can produce just one:
Input:
(100, CustomerRecord)
↓ Mapper
(CustomerId, CustomerName)
So:
One input key-value pair → zero, one, or many output key-value pairs.
7. Shuffle — The Hidden but Critical Step
The complete pattern is actually:
MAP → SHUFFLE → REDUCE
People normally call it MapReduce, not MapShuffleReduce.
Why?
Because Shuffle is normally handled automatically by the framework.
The developer generally writes:
Mapper
Reducer
while the framework handles the shuffle.
8. What Does Shuffle Do?
This is one of the most important concepts in MapReduce.
Suppose different nodes produce:
Node 1:
(Java, 1)
(Redis, 1)
Node 2:
(Java, 1)
(Spark, 1)
Node 3:
(Redis, 1)
(Java, 1)
The framework needs to bring all identical keys together.
So shuffle produces:
Java → [1, 1, 1]
Redis → [1, 1]
Spark → [1]
Now all values belonging to the same key are together.
9. Why Shuffle Can Be Expensive
Suppose:
Node 1 → (Java,1)
Node 2 → (Java,1)
Node 3 → (Java,1)
Node 4 → (Java,1)
These records may initially exist on different machines.
To reduce them together, the framework may need to transfer data across the network.
Node 1 ─────┐
Node 2 ─────┤
Node 3 ─────┼──→ Network → Reducer
Node 4 ─────┘
Therefore:
Shuffle can become a major network and performance bottleneck.
This is one of the most important MapReduce optimization areas.
10. MapReduce Complete Flow
Remember this:
INPUT
↓
Key-Value Pairs
↓
┌────────┐
│ MAP │
└────────┘
↓
List of Key-Value Pairs
↓
┌─────────┐
│ SHUFFLE │
└─────────┘
↓
Group by Common Key
↓
Key + List of Values
↓
┌────────┐
│ REDUCE │
└────────┘
↓
Final Results
11. What Exactly Happens During Shuffle?
Suppose mapper outputs:
(A, 10)
(B, 20)
(A, 30)
(C, 40)
(B, 50)
Shuffle groups by key:
A → [10, 30]
B → [20, 50]
C → [40]
Then reducers receive:
Reducer(A, [10,30])
Reducer(B, [20,50])
Reducer(C, [40])
This grouping is the heart of the MapReduce model.
12. Reduce Function
The reducer receives:
Key + List of Values
Example:
(A, [10,30])
The reducer can aggregate:
10 + 30 = 40
Output:
(A, 40)
Similarly:
(B, [20,50])
↓
70
(C, [40])
↓
40
Final:
(A,40)
(B,70)
(C,40)
13. Canonical Example — Word Count
Word Count is the classic MapReduce example.
Input:
Java Java Redis
Java Spark
Redis Spark Java
Step 1 — Input
Imagine the data is distributed:
Node 1:
Java Java Redis
Node 2:
Java Spark
Node 3:
Redis Spark Java
Step 2 — Map
Each mapper processes its local data.
Node 1
(Java,1)
(Java,1)
(Redis,1)
Node 2
(Java,1)
(Spark,1)
Node 3
(Redis,1)
(Spark,1)
(Java,1)
14. Step 3 — Shuffle
The framework groups identical keys:
Java → [1,1,1,1]
Redis → [1,1]
Spark → [1,1]
Notice something important:
The Java values could have originated from different machines.
Shuffle brings them together logically for reduction.
15. Step 4 — Reduce
Reducer receives:
Java → [1,1,1,1]
and calculates:
1 + 1 + 1 + 1 = 4
Similarly:
Redis → [1,1] → 2
Spark → [1,1] → 2
Final result:
Java → 4
Redis → 2
Spark → 2
16. Word Count in One Diagram
INPUT
↓
"Java Java Redis"
"Java Spark"
"Redis Spark Java"
↓
MAP
↓
┌─────────────────────┐
│ (Java,1) │
│ (Java,1) │
│ (Redis,1) │
│ (Java,1) │
│ (Spark,1) │
│ (Redis,1) │
│ (Spark,1) │
│ (Java,1) │
└─────────────────────┘
↓
SHUFFLE
↓
┌─────────────────────┐
│ Java → [1,1,1,1] │
│ Redis → [1,1] │
│ Spark → [1,1] │
└─────────────────────┘
↓
REDUCE
↓
┌─────────────────────┐
│ Java → 4 │
│ Redis → 2 │
│ Spark → 2 │
└─────────────────────┘
17. Why Reduce Usually Produces Less Data
Imagine:
Input:
1 TB
Map might produce:
Several TB of intermediate key-value pairs
After grouping and aggregation:
Reduce output:
Few GB
or potentially much less.
Conceptually:
Huge Input
↓
MAP
↓
Huge Intermediate Data
↓
SHUFFLE
↓
Grouped Data
↓
REDUCE
↓
Smaller Aggregate Result
The goal is to turn a massive collection of raw records into useful aggregate information.
18. Map vs Shuffle vs Reduce
| Stage | Responsibility |
|---|
| Map | Process individual input records |
| Shuffle | Group records by key |
| Reduce | Aggregate/process values belonging to each key |
Easy memory trick
MAP = Create
Mapper creates intermediate key-value pairs.
SHUFFLE = Group
Framework groups values having the same key.
REDUCE = Combine
Reducer combines those values into a result.
19. Most Important Interview Concept — Shuffle
If you're preparing for distributed-system interviews, pay special attention to Shuffle.
Why?
Because Shuffle can involve:
Disk I/O
+
Network I/O
+
Serialization
+
Deserialization
+
Sorting
+
Data partitioning
Therefore:
MapReduce performance is often heavily influenced by how much data is generated and transferred during shuffle.
This is why MapReduce programming often feels restrictive: the constraints help the framework reason about how to distribute and execute the computation.
20. MapReduce Mental Model
Think of MapReduce as a data transformation pipeline:
LARGE DATA
↓
MAP
"Create key/value"
↓
INTERMEDIATE
DATA
↓
SHUFFLE
"Group by key"
↓
GROUPED DATA
↓
REDUCE
"Aggregate"
↓
RESULT
One-line definition
MapReduce is a distributed computation pattern where Map transforms input records into key-value pairs, Shuffle groups values by key, and Reduce aggregates those grouped values into final results.
⭐ Remember these 6 points
MapReduce is a computation pattern.
Map takes one key-value pair and produces zero/many key-value pairs.
Shuffle groups values having the same key.
Shuffle is generally handled by the framework.
Reduce receives a key and its list of values and produces a result.
The biggest hidden cost can be Shuffle because it may require substantial network data movement.
MapReduce — Class Notes: Word Count Example
This lecture explains the canonical MapReduce Word Count example using Edgar Allan Poe's The Raven. The important goal is not the poem itself, but understanding exactly what happens in Map → Shuffle → Reduce.
1. Input to the Mapper
MapReduce commonly works with key-value pairs.
In this example:
Key = File name
Value = Contents of the file
For example:
("The_Raven.txt", "Once upon a midnight dreary ...")
The entire text of The Raven is the value.
Important
The input doesn't have to be a poem.
The value could be:
Text file
Log file
Sensor data
JSON
Database record
Image metadata
Any serialized data
2. Mapper Tokenizes the Input
The mapper takes the value and tokenizes it.
Suppose the input contains:
"Once upon a midnight dreary"
The mapper breaks it into words:
Once
upon
a
midnight
dreary
But MapReduce requires the mapper to output key-value pairs, not just words.
So we need to decide:
What should the key and value represent?
Since our objective is word counting, the obvious choice is:
Key = Word
Value = 1
Therefore:
Once → 1
upon → 1
a → 1
midnight → 1
dreary → 1
Or as MapReduce key-value pairs:
(Once, 1)
(upon, 1)
(a, 1)
(midnight, 1)
(dreary, 1)
3. Why Does Mapper Output 1?
This is an important idea.
The mapper doesn't try to calculate the final word count.
It simply says:
"I found this word once."
For example:
(chamber, 1)
(pondered, 1)
(a, 1)
(a, 1)
(a, 1)
Each mapper has a very simple responsibility:
Input word
↓
"I saw this word"
↓
(word, 1)
This makes the computation highly parallelizable.
4. Why Is This Design Powerful?
Imagine we have 1 PB of text.
We don't want one machine to process everything.
Instead:
1 PB Data
↓
┌────────────┼────────────┐
↓ ↓ ↓
Node 1 Node 2 Node 3
↓ ↓ ↓
Mapper Mapper Mapper
↓ ↓ ↓
(word,1) (word,1) (word,1)
We can split the data into many chunks and have many mappers work simultaneously.
Each mapper only needs to understand its local piece of data.
5. Mapper Doesn't Need Global Knowledge
This is one of the most important MapReduce principles.
Suppose three different machines see the word raven.
Node 1 → (raven, 1)
Node 2 → (raven, 1)
Node 3 → (raven, 1)
None of them needs to know what the other machines are doing.
Each mapper simply says:
"I saw raven once."
This makes the mapper:
6. Map Phase
Suppose our input is:
"raven raven tapping"
The mapper produces:
(raven, 1)
(raven, 1)
(tapping, 1)
For a larger file:
FILE
↓
TOKENIZE
↓
┌──────────┼──────────┐
↓ ↓ ↓
word word word
↓ ↓ ↓
(word,1) (word,1) (word,1)
At the end of Map:
We have a large collection of (word, 1) pairs.
7. Shuffle Phase
Now comes one of the most important parts:
Shuffle groups identical keys.
Suppose mappers produce:
(raven, 1)
(a, 1)
(tapping, 1)
(raven, 1)
(a, 1)
(raven, 1)
Shuffle rearranges them:
raven → [1, 1, 1]
a → [1, 1]
tapping → [1]
The key is now:
word
and the values are:
list of counts
8. Shuffle May Move Data Across the Network
This is where data locality becomes important.
Suppose:
Node 1:
(raven,1)
Node 2:
(raven,1)
Node 3:
(raven,1)
All raven values need to reach the same reducer/group.
Therefore:
Node 1 ─────┐
│
Node 2 ─────┼──→ Network ──→ Reducer
│
Node 3 ─────┘
So when the lecture says the data may "move around", it can literally mean:
Data is transferred between machines over the network.
9. Why Take the Network Hit?
At first this seems contradictory.
We said:
Move computation to the data.
But Shuffle may move data across the network.
Why?
Because after moving the data, we get data locality for the next computation.
For example:
Before Shuffle:
Node 1 → raven = 1
Node 2 → raven = 1
Node 3 → raven = 1
After Shuffle:
Reducer Node:
raven → [1,1,1]
Now the reducer can efficiently process all raven values together.
Key principle
Sometimes we accept network cost during Shuffle to create locality for the Reduce computation.
10. Shuffle Output
The mapper produced:
(word, 1)
But the reducer doesn't receive individual pairs.
Instead, Shuffle converts them into:
(word, [values])
Example:
(raven, [1,1,1])
(a, [1,1])
(tapping, [1])
This is the input format expected by the reducer.
11. Why Are Some Lists Larger?
Suppose the word raven appears 100 times.
Shuffle could produce:
raven → [1,1,1,1,1,1,...]
with 100 values.
If a word appears only once:
dreary → [1]
So:
Word frequency Shuffle result
1 occurrence [1]
2 occurrences [1,1]
5 occurrences [1,1,1,1,1]
100 occurrences [1,1,1,.....100 times]
12. Reducer
Now the reducer receives:
Key + List of Values
For example:
raven → [1,1,1]
The reducer simply adds them:
1 + 1 + 1 = 3
Final output:
(raven, 3)
Similarly:
a → [1,1] → 2
tapping → [1] → 1
13. Complete Example
Let's put everything together.
Input
"The raven is raven"
Map
(the, 1)
(raven, 1)
(is, 1)
(raven, 1)
Shuffle
the → [1]
raven → [1,1]
is → [1]
Reduce
the → 1
raven → 2
is → 1
Final output
(the, 1)
(raven, 2)
(is, 1)
14. Multiple Reducers
A very important point from the lecture is that we don't necessarily need one reducer.
Suppose there are millions of words.
We could have:
SHUFFLE
↓
┌─────────┼─────────┐
↓ ↓ ↓
Reducer 1 Reducer 2 Reducer 3
↓ ↓ ↓
Results Results Results
For example:
Reducer 1:
a
b
c
d
Reducer 2:
e
f
g
h
Reducer 3:
i
j
k
l
The framework can partition the keys among reducers.
15. Reduce Can Also Be Performed in Stages
The lecture makes an interesting observation.
If there is too much data to process in one place, we can have multiple reduction stages.
Conceptually:
Shuffle
↓
┌─────────┼─────────┐
↓ ↓ ↓
Reduce Reduce Reduce
↓ ↓ ↓
└─────────┼─────────┘
↓
Further Reduce
↓
Final Result
This is another example of the functional and composable nature of MapReduce.
16. Why "Dumb" Functions Are Powerful
The lecture repeatedly describes the mapper/reducer as almost "dumb".
That is intentional.
Mapper:
"I saw this word once."
Reducer:
"Give me all values for this word; I'll add them."
Neither needs to understand the entire dataset.
Mapper
↓
Local view
Reducer
↓
Grouped view
This limited view allows the framework to distribute the work.
This is the big idea:
Simple functions + strict data flow = massive parallelism.
17. MapReduce Architecture — Mental Model
DISTRIBUTED FILES
↓
┌────────────────────┐
│ MAP PHASE │
└────────────────────┘
↓
(word, 1)
(word, 1)
(word, 1)
↓
┌────────────────────┐
│ SHUFFLE PHASE │
│ Group by key │
└────────────────────┘
↓
(word, [1,1,1,...])
↓
┌────────────────────┐
│ REDUCE PHASE │
│ Aggregate │
└────────────────────┘
↓
(word, count)
18. The Most Important Data Transformations
Memorize these three transformations:
Map
(K, V)
↓
[(K1,V1), (K2,V2), ...]
Shuffle
[(K,V), (K,V), (K,V)]
↓
(K, [V,V,V])
Reduce
(K, [V,V,V])
↓
(K, Result)
For Word Count:
Input:
File → Text
↓ MAP
(word, 1)
↓ SHUFFLE
(word, [1,1,1,...])
↓ REDUCE
(word, count)
19. Key Distributed-System Lessons
1. Parallelism
Large data can be divided among many machines.
2. Data locality
Try to process data near where it is stored.
3. Network cost
Shuffle can cause significant network traffic.
4. Simple computation
Map and Reduce functions are intentionally constrained.
5. Scalability
Because computation is split into independent pieces, the system can scale horizontally.
6. Fault tolerance
A distributed framework can detect failed work and execute it again on another node. This is one of the major benefits of having a framework manage the execution rather than manually coordinating machines.
20. Interview-Friendly Summary
| Stage | Input | Operation | Output |
|---|
| Map | (K,V) | Transform/tokenize | (K,V) pairs |
| Shuffle | Many (K,V) pairs | Group by key | (K,[V]) |
| Reduce | (K,[V]) | Aggregate | (K,Result) |
Word Count
"The raven raven"
↓
MAP
↓
(raven,1)
(raven,1)
↓
SHUFFLE
↓
raven → [1,1]
↓
REDUCE
↓
raven → 2
⭐ One-line exam answer
MapReduce is a distributed computation pattern in which the Map function converts input records into intermediate key-value pairs, Shuffle groups values having the same key—potentially moving them across the network—and Reduce aggregates each key's values to produce the final result.
⭐ The key insight from this lecture
Map is deliberately simple → Shuffle creates grouping/data locality → Reduce performs aggregation → the framework can execute all of this in parallel across many machines.
-------------------
Hadoop Architecture - Distributed Computation + Distributed Storage
Hadoop — Class Notes
1. What is Hadoop?
Hadoop is a distributed computing ecosystem/framework designed to process very large datasets across many machines.
It became one of the best-known open-source technologies for distributed computation and big-data processing.
A good mental model is:
HADOOP
|
┌──────────────┴──────────────┐
↓ ↓
Distributed Computation Distributed Storage
↓ ↓
MapReduce HDFS
So Hadoop is not just MapReduce.
Hadoop broadly provides:
MapReduce API
Job/workload management
HDFS — Hadoop Distributed File System
A large ecosystem of tools built around it
2. Hadoop vs MapReduce
This distinction is extremely important.
MapReduce
MapReduce is a computation pattern:
Map → Shuffle → Reduce
Hadoop
Hadoop provides an implementation/framework that allows distributed MapReduce jobs to actually run across a cluster.
MapReduce
↓
Hadoop MapReduce
↓
Cluster
↓
Multiple machines
Interview answer
MapReduce is a distributed computation model, whereas Hadoop is an ecosystem/framework that provides MapReduce execution, distributed storage through HDFS, and cluster/job management.
3. Hadoop MapReduce API
Hadoop provides APIs/interfaces through which developers can define:
Mapper
Reducer
Conceptually:
Input
↓
Mapper
↓
Shuffle
↓
Reducer
↓
Output
The developer writes the computation logic, while Hadoop takes care of much of the distributed execution.
4. Hadoop Job Management
One of Hadoop's major advantages is that you don't manually manage every machine.
Suppose we have:
Hadoop Cluster
|
┌────────────┼────────────┐
↓ ↓ ↓
Node 1 Node 2 Node 3
Hadoop can:
5. Failure Handling
Distributed systems assume that machines can fail.
Suppose:
Mapper Task
↓
Node 2
↓
FAILURE
Hadoop can detect the failure and arrange for the work to be executed again, potentially using another copy of the data.
Conceptually:
Node 1 → Task A ✓
Node 2 → Task B ✗
Node 3 → Retry Task B ✓
This is a major advantage of using a distributed framework rather than manually writing scripts for hundreds of machines.
6. HDFS
Hadoop also includes a distributed storage system:
HDFS = Hadoop Distributed File System
HDFS is designed to store very large files across many machines.
From a user's perspective, HDFS looks somewhat like a normal filesystem.
You can have:
/
├── data/
│ ├── sales.txt
│ ├── customers.txt
│ └── transactions.txt
└── logs/
├── app1.log
└── app2.log
You work with:
But underneath, the files are distributed across many machines.
7. HDFS Architecture — Basic Idea
A simplified model:
HDFS
|
┌──────────┴──────────┐
↓ ↓
NameNode DataNodes
Metadata Actual Data
| |
| ┌──────┼──────┐
| ↓ ↓ ↓
| Node1 Node2 Node3
|
File metadata
The important distinction:
NameNode
Manages metadata.
DataNodes
Store the actual data blocks.
8. NameNode
The NameNode is the central metadata manager of HDFS.
It keeps information such as:
File names
Directory structure
File paths
Which blocks belong to which files
Where those blocks are located
Other filesystem metadata
For example:
File:
customer-data.csv
Blocks:
B1
B2
B3
B4
NameNode knows:
customer-data.csv
|
┌────┼────┬────┐
↓ ↓ ↓ ↓
B1 B2 B3 B4
| | | |
Node1 Node3 Node2 Node4
It does not primarily store the actual file contents.
9. DataNodes
The actual blocks are stored on DataNodes.
Example:
DataNode 1:
Block A
Block C
DataNode 2:
Block B
Block D
DataNode 3:
Block A
Block B
The blocks are replicated for reliability.
10. Why Replication?
Suppose:
Block A
↓
Only Node 1
If Node 1 dies:
Node 1 💥
↓
Block A LOST
That's unacceptable.
So HDFS stores multiple copies:
Block A
/ | \
↓ ↓ ↓
Node 1 Node 2 Node 3
If Node 1 fails:
Node 1 💥
Block A still exists:
Node 2 ✓
Node 3 ✓
Therefore:
Replication provides fault tolerance.
11. HDFS Blocks
HDFS doesn't normally store a huge file as one giant object.
It divides it into large blocks.
For example:
1 GB file
↓
Block 1
Block 2
Block 3
Block 4
...
The lecture mentions a typical HDFS block size around 128 MB for the version being discussed.
So conceptually:
512 MB File
↓
┌─────────┐
│ 128 MB │ Block 1
├─────────┤
│ 128 MB │ Block 2
├─────────┤
│ 128 MB │ Block 3
├─────────┤
│ 128 MB │ Block 4
└─────────┘
Each block can be stored on a different machine.
12. Why Use Large Blocks?
Traditional operating systems may use relatively small blocks.
HDFS uses much larger blocks because it is designed for large-data workloads.
Imagine a 1 TB dataset.
Using tiny blocks would create an enormous number of blocks and therefore enormous metadata overhead.
Large blocks mean:
Huge File
↓
Fewer large blocks
↓
Less metadata
↓
Efficient distributed storage
This is one reason HDFS is designed for large files and large-scale data processing.
13. HDFS Is Designed for Large Files
HDFS is particularly suited for:
Large files
Large datasets
Sequential access
Batch processing
Distributed computation
It is not intended to behave like a traditional low-latency transactional database.
Think:
HDFS
↓
Big Data
↓
Large files
↓
Batch analytics
rather than:
HDFS
↓
Tiny records
↓
Millions of random updates
↓
OLTP
14. Immutable Blocks
One of the most important concepts in the lecture is:
HDFS blocks are immutable.
Once data is written, you generally don't modify the existing block in place.
Conceptually:
Write:
File A
↓
Blocks created
↓
Immutable
If you need changed content, you create new data rather than modifying the existing block in place.
15. Why Is Immutability Useful?
At first, immutability looks like a limitation.
Actually, it greatly simplifies distributed storage.
Imagine a replicated block:
Block A
/ | \
↓ ↓ ↓
Node 1 Node 2 Node 3
If you modify Block A in place, the system has to carefully coordinate:
Update Node 1
Update Node 2
Update Node 3
What happens if:
Node 1 updated ✓
Node 2 updated ✓
Node 3 fails ✗
Now replicas may temporarily contain different versions.
With immutable blocks:
Once created, the block doesn't change.
This makes replication and consistency much easier to manage.
16. Immutability = Simplification
A powerful distributed-systems lesson:
Whenever you can make data immutable, many distributed-system problems become easier.
With immutable data:
Replication is easier
Caching is safer
Concurrent reads are easier
Coordination is reduced
Version management becomes simpler
Failure recovery becomes easier
This idea appears in many modern distributed systems as well.
17. Hadoop Ecosystem
Because Hadoop became widely used, a large ecosystem developed around it.
The basic idea:
Hadoop
|
┌───────────────┼────────────────┐
↓ ↓ ↓
HDFS MapReduce Ecosystem
|
┌──────────┬──────────┬─────┴─────┐
↓ ↓ ↓ ↓
Hive Pig HBase Sqoop
The ecosystem exists partly because writing raw MapReduce jobs can be cumbersome.
18. Why Did the Hadoop Ecosystem Grow?
MapReduce is powerful but restrictive.
For simple Word Count:
Map → Shuffle → Reduce
is easy.
But imagine implementing:
Business analytics
SQL queries
Machine learning
Workflow management
Data ingestion
Logging
Database integration
using raw MapReduce.
It becomes painful.
Therefore, higher-level tools appeared.
High-Level Tool
↓
Abstracts
↓
MapReduce
↓
Hadoop
19. Important Hadoop Ecosystem Technologies
Hive
Provides a SQL-like query language for analyzing data stored in Hadoop.
Instead of writing complicated MapReduce code, users can express queries in a SQL-like manner.
SQL-like Query
↓
Hive
↓
Distributed Execution
Pig
Pig provides a higher-level data-analysis language.
It is useful for expressing data transformations without manually writing all the MapReduce logic.
HBase
HBase is a column-family NoSQL database designed to run on top of Hadoop/HDFS.
Conceptually:
HBase
↓
HDFS
↓
Distributed Storage
It provides database-like access patterns that are different from traditional relational databases.
Oozie
Oozie is associated with workflow/job management.
Instead of managing one MapReduce job, you may have:
Job A
↓
Job B
↓
Job C
↓
Job D
Workflow tools help coordinate these jobs.
ZooKeeper
ZooKeeper started as part of the broader Hadoop ecosystem but became useful as a general distributed coordination service.
It can help with things such as:
Important:
ZooKeeper is not simply "a Hadoop database"; it is a distributed coordination system used by many distributed applications.
Mahout
Apache Mahout was developed as a machine-learning project associated with the Hadoop ecosystem.
The important historical idea is:
Hadoop
↓
Distributed computation
↓
Machine Learning
↓
Mahout
Cascading
Provides a higher-level API for building data-processing workflows and makes writing MapReduce-style applications easier.
Sqoop
Used historically for moving data between:
Relational Database
↕
Hadoop
For example:
MySQL
↓
Sqoop
↓
HDFS
Flume / Scribe
These tools were associated with collecting and transporting log/event data into large-scale data systems.
Conceptually:
Application Logs
↓
Flume/Scribe
↓
Hadoop
↓
Analytics
20. Hadoop Ecosystem — Easy Memory Map
HADOOP
|
┌──────────────┴──────────────┐
↓ ↓
HDFS MapReduce
Distributed Storage Distributed Compute
|
|
┌───────┼──────────────────────────────┐
↓ ↓ ↓ ↓ ↓ ↓
HBase Hive Pig Sqoop Flume Oozie
↓ ↓ ↓ ↓ ↓ ↓
NoSQL SQL Analysis DB Logs Workflow
21. Hadoop Architecture — Big Picture
The lecture is essentially introducing this architecture:
HADOOP CLUSTER
|
┌──────────────┴──────────────┐
↓ ↓
HDFS MapReduce
| |
┌─────┴─────┐ ┌────┴────┐
↓ ↓ ↓ ↓
NameNode DataNodes Mapper Reducer
| | | |
Metadata Data Blocks Compute Aggregate
|
Replicated Blocks
The important relationship is:
HDFS stores the data; MapReduce processes the data.
And Hadoop's job-management mechanisms coordinate that processing.
22. How MapReduce Uses HDFS
This connects the previous class to this one.
Suppose HDFS contains:
File
↓
Block 1 → Node 1
Block 2 → Node 2
Block 3 → Node 3
MapReduce tries to execute:
Block 1 → Mapper on/near Node 1
Block 2 → Mapper on/near Node 2
Block 3 → Mapper on/near Node 3
This is data locality.
Instead of:
Node 1 data
↓
Network
↓
Central machine
↓
Compute
we prefer:
Node 1 → Local Mapper
Node 2 → Local Mapper
Node 3 → Local Mapper
That is a fundamental Hadoop design principle.
23. Critical Hadoop Concepts for Interviews
Q1. What is Hadoop?
Hadoop is a distributed computing ecosystem/framework for storing and processing very large datasets across clusters of commodity machines.
Q2. Is Hadoop the same as MapReduce?
No.
MapReduce = Computation model
Hadoop = Ecosystem/framework implementing distributed storage and computation
Q3. What is HDFS?
HDFS is Hadoop's distributed filesystem designed for storing very large files across multiple machines using large, replicated blocks.
Q4. What is a NameNode?
The NameNode manages HDFS filesystem metadata such as filenames, directories, file-to-block mappings, and block locations.
Q5. What is a DataNode?
A DataNode stores the actual HDFS data blocks.
Q6. Why are HDFS blocks replicated?
To provide fault tolerance when machines or disks fail.
Q7. Why are HDFS blocks large?
Large blocks reduce metadata overhead and are appropriate for large sequential data-processing workloads.
Q8. Why is immutability useful?
Immutable blocks reduce coordination and consistency complexity during replication and distributed processing.
24. The Most Important Mental Model
Keep these four concepts connected:
HADOOP
|
┌────────┴────────┐
↓ ↓
HDFS MapReduce
↓ ↓
Storage Computation
↓ ↓
Large Blocks Map → Shuffle → Reduce
↓ ↓
Replication Parallelism
└────────┬────────┘
↓
Distributed Processing
⭐ One-line summary
Hadoop combines distributed storage (HDFS), distributed computation (historically MapReduce), and cluster/job management, with a large ecosystem of higher-level tools that make large-scale data processing easier.
⭐ The 5 concepts to remember
HDFS → NameNode → DataNode → Blocks → Replication
And connect them with:
MapReduce → Data Locality → Map → Shuffle → Reduce
That gives you the foundation needed to understand the Hadoop architecture in the next class.
----------------------------
Hadoop Architecture — Class Notes
This class connects the two major sides of Hadoop:
HADOOP
├── HDFS → Distributed Storage
└── MapReduce → Distributed Computation
The most important thing to understand is how NameNode, DataNode, JobTracker, TaskTracker, Map, Shuffle and Reduce work together.
1. HDFS Architecture
The basic HDFS architecture has:
HDFS
|
NameNode
(File Metadata)
|
┌──────────┼──────────┐
↓ ↓ ↓
DataNode 1 DataNode 2 DataNode 3
↓ ↓ ↓
Blocks Blocks Blocks
2. NameNode
The NameNode is the master of HDFS metadata.
It maintains information about:
File names
Directory paths
File-to-block mapping
Locations of blocks
Filesystem metadata
For example:
/customer/data.txt
↓
Block A
Block B
Block C
The NameNode knows:
Block A → DataNode 1
Block B → DataNode 2
Block C → DataNode 3
Important
The NameNode does not normally contain the actual file data.
It contains the metadata describing where the data lives.
3. DataNodes
DataNodes store the actual HDFS blocks.
Example:
DataNode 1
├── Block A
├── Block D
└── Block F
DataNode 2
├── Block B
├── Block A
└── Block E
DataNode 3
├── Block C
├── Block B
└── Block F
The blocks are replicated across DataNodes.
4. Client → NameNode → DataNode
One of the most important architectural ideas is that the client does not send all file data through the NameNode.
Suppose the client wants to create a file.
Step 1 — Client contacts NameNode
Client
|
| "I want to create a file"
↓
NameNode
The NameNode determines where the blocks should be stored.
For example:
NameNode
↓
"Use DataNode 3"
Step 2 — Client sends actual data directly
Client
|
| Actual file data
↓
DataNode 3
This is important for scalability.
5. Why Doesn't Data Flow Through the NameNode?
Imagine 1,000 clients writing huge files.
If all data had to go through the NameNode:
Client 1 ─┐
Client 2 ─┤
Client 3 ─┤
Client 4 ─┼──→ NameNode ──→ DataNodes
... │
Client N ─┘
The NameNode would become a massive I/O bottleneck.
Instead:
NameNode
Metadata only
|
┌──────────┼──────────┐
↓ ↓ ↓
DataNode DataNode DataNode
↑ ↑ ↑
| | |
Client Client Client
The NameNode handles relatively small amounts of metadata traffic, while DataNodes handle the heavy data traffic.
6. Scalability Through DataNodes
This gives Hadoop substantial aggregate I/O capacity.
Suppose:
DataNode 1 → 1 GB/s
DataNode 2 → 1 GB/s
DataNode 3 → 1 GB/s
DataNode 4 → 1 GB/s
The cluster can potentially provide substantial aggregate throughput.
So HDFS scalability depends heavily on:
Network architecture
Number of DataNodes
Disk performance
Network interfaces
Cluster architecture
7. HDFS Replication
Suppose we have:
Block A
HDFS replicates it:
Block A
/ | \
↓ ↓ ↓
Node 1 Node 2 Node 3
The lecture mentions a typical replication factor of 3.
That means:
1 logical block
↓
3 physical copies
This protects against machine/disk failures.
8. NameNode Coordinates Replication
The NameNode keeps track of block replicas.
Conceptually:
NameNode
|
| "Block A needs replicas"
|
├──→ DataNode 1
├──→ DataNode 2
└──→ DataNode 3
The NameNode therefore maintains the metadata necessary to understand the state of the distributed filesystem.
9. What Happens When a DataNode Fails?
Suppose:
Block A
├── Node 1 ✓
├── Node 2 ✓
└── Node 3 ✗
Now the cluster has lost one replica.
HDFS can detect that the replication level has fallen below the desired level and arrange for another copy to be created.
Conceptually:
Block A
├── Node 1 ✓
├── Node 2 ✓
└── Node 3 ✗
↓
Replication
↓
Node 4 ✓
Now:
Block A
├── Node 1
├── Node 2
└── Node 4
The system has restored the desired replication level.
10. DataNode "Phones Home"
A DataNode periodically communicates with the NameNode.
Conceptually:
DataNode
|
| "Here I am"
↓
NameNode
If a DataNode was unavailable for some period and comes back, it can learn what state it needs to synchronize with the rest of the cluster.
This helps HDFS deal with entropy caused by failures and missing replicas.
11. HDFS Architecture Summary
Client
|
Metadata Request
↓
NameNode
|
Block Locations
↓
┌──────────┼──────────┐
↓ ↓ ↓
DataNode 1 DataNode 2 DataNode 3
↓ ↓ ↓
Block A Block A Block B
Remember:
NameNode = Metadata
DataNode = Actual Data
12. Now Distributed Computation
HDFS explains storage.
But Hadoop also needs to answer:
How do we run computation on this distributed data?
The classical Hadoop architecture introduced another master:
JobTracker
And worker-side processes:
TaskTrackers
The historical architecture looks like:
JobTracker
|
┌──────────────┼──────────────┐
↓ ↓ ↓
TaskTracker TaskTracker TaskTracker
+ DataNode + DataNode + DataNode
This is the classic Hadoop MapReduce architecture.
13. JobTracker
The JobTracker is responsible for managing MapReduce jobs.
A client submits a job:
Client
|
| Submit MapReduce Job
↓
JobTracker
The job contains the Map and Reduce logic.
Historically, this might be packaged as a JAR containing the application code.
14. TaskTracker
Each worker machine has a TaskTracker.
The TaskTracker executes the work assigned to that machine.
JobTracker
|
├─────────────┐
↓ ↓
TaskTracker TaskTracker
↓ ↓
Mapper Mapper
In the classic Hadoop model:
DataNode + TaskTracker
exist on the same worker machine.
This is important because it enables data locality.
15. Complete Hadoop Computation Flow
Let's connect everything.
Client
|
| Submit Job
↓
JobTracker
|
┌─────────────┼─────────────┐
↓ ↓ ↓
TaskTracker TaskTracker TaskTracker
| | |
DataNode DataNode DataNode
| | |
Local Data Local Data Local Data
↓ ↓ ↓
Mapper Mapper Mapper
↓ ↓ ↓
└─────────────┼─────────────┘
↓
Shuffle
↓
Reducer Tasks
↓
HDFS
16. Step-by-Step MapReduce Job
Suppose we want to count words in 100 TB of data.
Step 1 — Data already exists in HDFS
HDFS
|
├── Block 1 → DataNode 1
├── Block 2 → DataNode 2
├── Block 3 → DataNode 3
└── ...
Step 2 — Client submits MapReduce job
Client
↓
JobTracker
Step 3 — JobTracker distributes Map tasks
JobTracker
|
├──→ TaskTracker 1
├──→ TaskTracker 2
└──→ TaskTracker 3
17. Data Locality
This is one of the most important Hadoop concepts.
Suppose:
Block A
↓
DataNode 1
Hadoop tries to execute the mapper on or near DataNode 1.
DataNode 1
|
├── Block A
|
└── Mapper
Instead of:
Block A
↓
Network
↓
Remote Server
↓
Mapper
The computation moves to the data.
Remember:
Hadoop tries to bring computation to the data, not data to the computation.
18. What Does the Mapper Do?
Suppose:
Data:
"The Raven Raven"
Mapper produces:
(raven, 1)
(raven, 1)
These intermediate key-value pairs are generated locally.
19. Mapper Writes Intermediate Data
The mapper produces intermediate data that will eventually participate in the Shuffle phase.
Conceptually:
DataNode
|
↓
Mapper
|
↓
(raven,1)
(raven,1)
The framework then handles the Shuffle.
20. Shuffle
Now Hadoop groups identical keys.
Suppose:
Node 1 → (raven,1)
Node 2 → (raven,1)
Node 3 → (raven,1)
Shuffle may move the data:
Node 1 ────┐
Node 2 ────┼──→ Network → Reducer
Node 3 ────┘
Then:
raven → [1,1,1]
21. Reduce
Reducer receives:
raven → [1,1,1]
and calculates:
1 + 1 + 1 = 3
Result:
(raven, 3)
The final output can then be stored back into HDFS.
22. Full Hadoop Data Flow
HDFS
|
Distributed Data
↓
┌──────────────┐
│ JobTracker │
└──────┬───────┘
↓
┌─────────┼─────────┐
↓ ↓ ↓
Mapper Mapper Mapper
↓ ↓ ↓
└─────────┼─────────┘
↓
SHUFFLE
↓
┌─────────┼─────────┐
↓ ↓ ↓
Reducer Reducer Reducer
└─────────┼─────────┘
↓
HDFS
23. Why Hadoop Can Scale
The developer accepts constraints:
Map
+
Reduce
Hadoop then handles:
So the developer doesn't need to manually coordinate hundreds of machines.
24. Complex Real-World Jobs
Real applications may require many MapReduce jobs.
For example:
Job 1
↓
Job 2
↓
Job 3
↓
Job 4
↓
Job 5
This becomes difficult to manage manually.
That's why higher-level APIs and workflow systems became important.
25. Cascading
Cascading is an example of a higher-level API that makes complex MapReduce workflows easier to express.
Instead of manually thinking about every low-level MapReduce operation:
Map → Reduce
Map → Reduce
Map → Reduce
you can work at a higher abstraction.
The underlying execution still ultimately becomes distributed computation.
26. Hive
Another important Hadoop ecosystem technology is Hive.
Hive provides a SQL-like interface for querying Hadoop data.
Instead of writing low-level MapReduce code:
Mapper
Reducer
Shuffle
...
you can express an analysis using SQL-like syntax.
Conceptually:
SQL Query
↓
Hive
↓
Distributed Execution
↓
MapReduce / Hadoop
↓
Result
This is why Hive became important for analysts and developers who didn't want to write raw MapReduce programs.
27. Hadoop Distributions
Hadoop is open source and has historically been packaged and supported by companies providing:
Enterprise distributions
Support
Training
Management tools
Consulting
Examples historically included companies such as Cloudera and Hortonworks.
The important concept is not the vendor name but the fact that Hadoop developed a large commercial ecosystem around the open-source project.
28. When Should You Use Hadoop?
This is a very important design question.
Hadoop makes sense when you have:
1. Very large data
TB → PB → potentially beyond
2. Distributed processing requirements
You need many machines to process the data.
3. Batch-oriented workloads
You don't need every result immediately.
4. Relatively low data velocity
Data can be accumulated and processed in batches.
29. When Hadoop Is NOT a Good Choice
Case 1 — Data isn't very large
If your entire dataset fits comfortably on one machine:
100 MB / 10 GB / modest dataset
Using Hadoop may introduce unnecessary complexity.
Don't use distributed systems when you don't need distributed scale.
Case 2 — Very low latency requirements
Suppose:
User clicks
↓
System
↓
Result required in 10 ms
Traditional Hadoop MapReduce is not a good fit.
Why?
A MapReduce job has significant overhead:
Job setup
Scheduling
Task startup
Distributed coordination
Disk I/O
Shuffle
Result writing
So even a tiny computation can take considerably longer than the actual computation itself.
30. Hadoop Is a Batch System
Think:
HADOOP
↓
Large Dataset
↓
Batch Processing
↓
Final Result
Not:
Event
↓
10 milliseconds
↓
Result
For real-time/low-latency workloads, technologies such as Spark or stream-processing systems such as Storm may be more appropriate depending on the problem.
31. Hadoop vs Database
Suppose you have:
Scenario A
100 TB historical sales data
Analyze last 5 years
Hadoop can make sense.
Scenario B
Customer purchases product
↓
Transaction must be recorded immediately
↓
Customer expects immediate response
A traditional transactional database is usually more appropriate.
The distinction is:
Hadoop → Large-scale batch analytics
Database → Transactional / low-latency workloads
32. HBase vs Traditional Database
HBase sits on top of HDFS and provides a database-like layer.
But the lecture's key point is:
If you are starting from scratch, HBase isn't automatically the database you should choose just because you have Hadoop.
It tends to make more sense when there is already a strong HDFS/Hadoop commitment and you need its particular access model.
33. Hadoop vs Spark vs Storm
This connects to your previous class.
| Technology | Primary Strength |
|---|
| Hadoop MapReduce | Large-scale batch computation |
| Spark | General distributed computation, often faster/more flexible than classic MapReduce |
| Storm | Real-time stream/event processing |
| Traditional DB | Transactional and low-latency workloads |
| HDFS | Distributed large-file storage |
Simple mental model:
Huge Historical Data
↓
Hadoop
↓
Batch
Complex Distributed Analytics
↓
Spark
↓
Fast Distributed Processing
Continuous Events
↓
Storm
↓
Real-Time Processing
34. Hadoop Architecture — Final Mental Model
HADOOP
|
┌─────────────────┴─────────────────┐
↓ ↓
HDFS MapReduce
Distributed Storage Distributed Compute
| |
┌────┴────┐ JobTracker
↓ ↓ |
NameNode DataNodes ┌────────┼────────┐
| | ↓ ↓ ↓
Metadata Data Blocks TaskTracker ... TaskTracker
| | |
Replication Mapper Mapper
| |
└──────┬──────┘
↓
Shuffle
↓
Reduce
↓
HDFS
⭐ Interview Questions to Remember
1. Why doesn't the client send data through the NameNode?
Because the NameNode handles metadata, while DataNodes handle the heavy data transfer. Sending all data through the NameNode would create a bottleneck.
2. What is data locality?
Running computation on or close to the node where the required data is stored.
3. Why does Hadoop replicate blocks?
For fault tolerance and availability when DataNodes fail.
4. What does JobTracker do?
In the classic Hadoop MapReduce architecture, JobTracker manages MapReduce jobs, schedules tasks, monitors execution, and handles failures.
5. What does TaskTracker do?
In the classic architecture, TaskTracker runs Map/Reduce tasks on worker nodes.
6. What happens during Shuffle?
Intermediate key-value pairs are partitioned/grouped by key and may be transferred across the network to the appropriate reducers.
7. Why is Hadoop not suitable for low-latency applications?
Because traditional MapReduce has significant job setup, scheduling, task, I/O, and shuffle overhead.
8. When should Hadoop be used?
When you have very large datasets + distributed processing + batch-oriented workloads.
⭐ Most Important Takeaway
Remember this sequence:
HDFS stores → NameNode knows where → DataNodes hold blocks → JobTracker schedules → TaskTrackers execute → Mapper processes local data → Shuffle moves/groups data → Reducer aggregates → HDFS stores the result.
One important historical note for interviews: JobTracker/TaskTracker describes Hadoop MapReduce v1. Modern Hadoop uses YARN, where ResourceManager/NodeManager replace that classic job/task-management architecture.
