Distributed Computation — Class Notes

1. Why Distributed Computation?

When data is distributed across many computers/nodes, we often need to perform computation or analysis on that data.

Example:

Node 1 → Data A
Node 2 → Data B
Node 3 → Data C
Node 4 → Data D
        ↓
   Distributed Data
        ↓
   Computation

Instead of moving all the data to one machine, we prefer to move the computation to where the data is located.

Key principle

Move the program to the data, rather than moving huge amounts of data to the program.

This is one of the most important ideas in distributed computation.

2. Scatter → Compute → Gather

A common distributed-computation paradigm is:

             SCATTER
                ↓
       ┌────────┼────────┐
       ↓        ↓        ↓
     Node 1   Node 2   Node 3
       ↓        ↓        ↓
    Compute   Compute   Compute
       ↓        ↓        ↓
       └────────┼────────┘
                ↓
             GATHER
                ↓
           Final Result

Three major steps

1. Scatter

Break the computation into smaller pieces and send them to multiple nodes.

2. Compute

Each node processes the computation, preferably using local data.

3. Gather

Collect the individual results and combine them into the final result.

This is commonly called the Scatter-Gather pattern.

3. Why Should Computation Be Near the Data?

Consider two computers connected through a network.

CPU ↔ Memory ↔ Disk
       |
       |
    Network
       |
       |
CPU ↔ Memory ↔ Disk

Even if the network is extremely fast, communication within a single computer is generally faster than communication across a network.

Why?

Inside a machine we have:

High-bandwidth memory buses
Very short physical distances
Fast CPU ↔ memory communication
Fast CPU ↔ local storage communication
Common system clock

Network communication introduces additional:

Network latency
Serialization/deserialization
Packet transmission
Network congestion
Remote data transfer overhead

Therefore:

Moving computation is often cheaper than moving large amounts of data.

This concept is called data locality.

4. Data Locality

Data locality means performing computation as close as possible to the data being processed.

For example:

Bad approach

10 TB Data
   ↓
Network
   ↓
One Computer
   ↓
Process

Moving 10 TB across the network can be expensive.

Better approach

Node 1: Data 2.5 TB → Process locally
Node 2: Data 2.5 TB → Process locally
Node 3: Data 2.5 TB → Process locally
Node 4: Data 2.5 TB → Process locally

                ↓

        Small Results
                ↓
        Central Aggregator

Only the relatively small computation results need to be transferred.

5. MapReduce

One of the most famous implementations of the Scatter-Gather idea is MapReduce.

MapReduce is a computational paradigm/pattern, not merely a single piece of code.

It became particularly well known through Hadoop.

The basic idea is:

Input Data
    ↓
   MAP
    ↓
Intermediate Results
    ↓
  REDUCE
    ↓
Final Result

MAP

Processes individual pieces of data in parallel.

REDUCE

Combines the intermediate results into a final answer.

6. Simple MapReduce Example

Suppose we have:

Node 1 → "Java Java Redis"
Node 2 → "Java Spark"
Node 3 → "Redis Spark Java"

Suppose we want to count each word.

Map phase

Each node 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

Shuffle/Group

Group identical keys:

Java  → [1,1,1,1]
Redis → [1,1]
Spark → [1,1]

Reduce

Add the values:

Java  → 4
Redis → 2
Spark → 2

So:

             MAP
              ↓
       Local computation
              ↓
          SHUFFLE
              ↓
       Group by key
              ↓
           REDUCE
              ↓
        Final result

7. Hadoop

Hadoop is a distributed computing ecosystem that became strongly associated with MapReduce.

Two important ideas in Hadoop are:

HDFS

Hadoop Distributed File System

Provides distributed storage.

Large File
   ↓
Split into blocks
   ↓
Node 1
Node 2
Node 3
Node 4

Data is distributed across multiple machines.

MapReduce

Provides distributed computation over that data.

HDFS
 ↓
Distributed Data
 ↓
MapReduce
 ↓
Distributed Processing
 ↓
Result

So Hadoop combines the concepts of:

Distributed Storage + Distributed Computation

8. Spark

Apache Spark is another distributed-computation technology.

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.

Conceptually:

Distributed Data
       ↓
      Spark
       ↓
Parallel Processing
       ↓
   Final Result

Hadoop MapReduce vs Spark — high level

Feature	Hadoop MapReduce	Spark
Computation	Distributed	Distributed
Main paradigm	Map → Shuffle → Reduce	Transformations + Actions
Programming model	More rigid	More flexible
Iterative processing	Relatively expensive	Generally much better
Interactive analytics	Less suitable	Better suited
Machine learning	Possible	Strong ecosystem
Streaming	Separate solutions commonly used	Strong streaming support

Important

Don't think:

Hadoop = storage and Spark = computation

The reality is more nuanced.

Hadoop commonly includes HDFS + MapReduce + resource-management components, while Spark is primarily a distributed computation engine and can work with different storage systems.

9. Hadoop vs Spark — How to Think About It

A useful mental model:

                Distributed Computation
                        |
              ┌─────────┴─────────┐
              ↓                   ↓
         Hadoop MapReduce       Spark
              ↓                   ↓
       Map → Shuffle → Reduce   Transformations
                                + Actions

Both distribute computation.

The difference is primarily in their execution model, programming model, performance characteristics, and use cases.

10. Apache Storm

Apache Storm addresses a different type of distributed-computation problem.

Hadoop MapReduce is traditionally associated with batch processing.

Storm is designed around event/stream processing.

Batch processing

Data is already stored:

Huge Data
   ↓
Distributed Storage
   ↓
Batch Processing
   ↓
Result

Example:

Analyze yesterday's 500 GB transaction data.

Event processing

Events continuously arrive:

Event → Event → Event → Event → Event
   ↓       ↓       ↓       ↓
        Storm
          ↓
   Real-time Processing

Example:

Detect suspicious transactions as they happen.

11. Batch vs Real-Time Processing

This is an important interview concept.

Batch Processing	Event/Stream Processing
Processes accumulated data	Processes incoming events
Higher latency acceptable	Low latency important
Large datasets	Continuous streams
Periodic computation	Continuous computation
Hadoop MapReduce is an example	Storm is an example

Example

Batch:

Every night calculate total sales for the day.

Real-time:

Immediately detect a suspicious credit-card transaction.

12. Lambda Architecture

Sometimes an application needs both batch processing and real-time processing.

This leads to the idea of Lambda Architecture.

Conceptually:

                    Incoming Data
                         |
              ┌──────────┴──────────┐
              ↓                     ↓
        Batch Layer             Speed Layer
              ↓                     ↓
       Historical Data         Real-time Data
              ↓                     ↓
              └──────────┬──────────┘
                         ↓
                    Serving Layer
                         ↓
                      Result

Batch Layer

Processes large amounts of historical data.

Advantages:

Accurate
Comprehensive
Can recompute historical results

Speed Layer

Processes new events quickly.

Advantages:

Low latency
Real-time results
Immediate updates

Serving Layer

Combines or exposes the results to applications/users.

13. Important Distributed Computation Concepts

1. Data Locality

Keep computation close to the data.

2. Parallelism

Multiple nodes process different portions of the workload simultaneously.

3. Scatter-Gather

Scatter → Process → Gather

4. MapReduce

Map → Shuffle → Reduce

5. Batch Processing

Process accumulated data periodically.

6. Stream/Event Processing

Process events continuously as they arrive.

7. Distributed Storage

Data is distributed across multiple machines so computation can happen close to it.

14. Big Picture

The entire topic can be remembered using this diagram:

              DISTRIBUTED DATA
                     |
                     ↓
          Move computation to data
                     |
                     ↓
             SCATTER-GATHER
                     |
          ┌──────────┼──────────┐
          ↓          ↓          ↓
        Node 1     Node 2     Node 3
          ↓          ↓          ↓
       Compute    Compute    Compute
          └──────────┼──────────┘
                     ↓
                   Gather
                     |
          ┌──────────┼───────────┐
          ↓          ↓           ↓
      MapReduce     Spark       Storm
          ↓          ↓           ↓
        Batch    Distributed   Real-time
                  Compute       Events
          \          |           /
           \         |          /
            └────────┼─────────┘
                     ↓
              Lambda Architecture
             Batch + Real-time

⭐ Interview Takeaways

Why distributed computation?
To process very large datasets using multiple machines in parallel.
Why move computation to data?
Network transfer is usually more expensive than local computation.
What is data locality?
Processing data on or near the node where it is stored.
What is Scatter-Gather?
Scatter computation → process in parallel → gather results.
What is MapReduce?
A distributed computational paradigm consisting primarily of Map, Shuffle/Group, and Reduce stages.
What is Hadoop?
A distributed-data ecosystem historically centered around HDFS and MapReduce.
What is Spark?
A general-purpose distributed computation engine with a different programming/execution model from classic MapReduce.
What is Storm?
A distributed stream/event-processing system designed for low-latency processing.
Batch vs real-time?
Batch processes accumulated data; real-time processing handles events as they arrive.
Lambda Architecture?
A design combining batch processing and real-time processing to provide both comprehensive and low-latency results.

--------------------------------

Map Reduce - 1

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

MapReduce → computation pattern
Hadoop MapReduce → an implementation of that pattern

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 - 2

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:

Simple
Stateless in the conceptual model
Easy to parallelize
Easy to distribute

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:

Distribute computation
Schedule tasks
Monitor tasks
Detect failures
Retry failed tasks
Run work on nodes containing the required data
Manage execution across the cluster

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:

Files
Directories
Paths

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:

Coordination
Configuration
Leader election
Distributed synchronization

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:

NameNode
DataNodes
Clients

                    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:

Distribution
Scheduling
Data locality
Task execution
Failure recovery
Intermediate data movement
Result storage

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.

Sunday, 23 August 2026

Distributed Computations -

Distributed Computation — Class Notes

1. Why Distributed Computation?

Key principle

2. Scatter → Compute → Gather

Three major steps

3. Why Should Computation Be Near the Data?

Why?

4. Data Locality

Bad approach

Better approach

5. MapReduce

MAP

REDUCE

6. Simple MapReduce Example

Map phase

Shuffle/Group

Reduce

7. Hadoop

HDFS

MapReduce

8. Spark

Hadoop MapReduce vs Spark — high level

Important

9. Hadoop vs Spark — How to Think About It

10. Apache Storm

Batch processing

Event processing

11. Batch vs Real-Time Processing

Example

12. Lambda Architecture

Batch Layer

Speed Layer

Serving Layer

13. Important Distributed Computation Concepts

1. Data Locality

2. Parallelism

3. Scatter-Gather

4. MapReduce

5. Batch Processing

6. Stream/Event Processing

7. Distributed Storage

14. Big Picture

⭐ Interview Takeaways

MapReduce — Class Notes

1. What is MapReduce?

Core idea

2. Why MapReduce?

3. MapReduce Gives Us Constraints

Important lesson

4. The Two Main Functions

Map

Reduce

5. Key-Value Pair

6. Map Function

7. Shuffle — The Hidden but Critical Step

8. What Does Shuffle Do?

9. Why Shuffle Can Be Expensive

10. MapReduce Complete Flow

11. What Exactly Happens During Shuffle?

12. Reduce Function

13. Canonical Example — Word Count

Step 1 — Input

Step 2 — Map

Node 1

Node 2

Node 3

14. Step 3 — Shuffle

15. Step 4 — Reduce

16. Word Count in One Diagram

17. Why Reduce Usually Produces Less Data

18. Map vs Shuffle vs Reduce

Easy memory trick

19. Most Important Interview Concept — Shuffle

20. MapReduce Mental Model

One-line definition

⭐ Remember these 6 points

MapReduce — Class Notes: Word Count Example

1. Input to the Mapper

3. Why Does Mapper Output `1`?