Hadoop HDFS and MapReduce

1 Introduction to HDFS
A Distributed File System (DFS) enables programs to store and access files as though they were local,
despite the files being physically distributed across a network of interconnected servers. Two of the most
critical aspects of designing a robust DFS (such as the Hadoop Distributed File System or Google File
System) are the physical organization of the hardware and the logical organization of the data at scale.

Figure 1: HDFS 2.0

The diagram illustrates the HDFS High Availability (HA) architecture introduced in Hadoop 2.0 to
solve the single point of failure.

1.1 The Masters Tier (Metadata Management)

• Active NameNode: This is the primary master server. It receives all HDFS requests from the Client
(as shown by the downward arrow). It manages the file system namespace, tracks the directory
tree, and knows exactly which DataNodes hold which blocks of data.
• Standby NameNode: This is the hot backup. It does not handle client traffic directly. Instead,
its sole purpose is to stay perfectly synchronized with the Active NameNode so it can take over
instantly if the Active node crashes.

• Shared Edit Logs: Situated between the two NameNodes, this is the synchronization mechanism.
When a Client writes data, the Active NameNode logs this transaction (the ”Write” arrow) to the
Shared edit logs. The Standby NameNode constantly consumes these logs (the ”Read” arrow) to
update its own internal state to match the Active node.

1.2 The Slaves Tier (Physical Storage)

• DataNode: These are the worker daemons responsible for physically storing the data blocks on the
machine’s hard drives.
• The V-Shaped Lines (Block Reporting): Notice the black lines connecting the DataNodes to both
the Active and Standby NameNodes. In HDFS 2.0, DataNodes must send their heartbeats and
block reports to both master nodes simultaneously. This ensures that if a failover occurs, the

1
 Standby NameNode immediately knows where all the data is located without needing to scan the
cluster.

1.3 The Storage Limitations of HDFS 1.0

HDFS 2.0 was designed specifically to fix the critical storage limitations of the 1.0 architecture:
• Single Point of Failure (SPOF): HDFS 1.0 allowed for only one NameNode. If that server suffered
a hardware failure, the metadata was unavailable, and the entire file system went offline.

• No High Availability: HDFS 1.0 had a ”Secondary NameNode,” but it was not a failover node. It
only performed housekeeping tasks (merging logs). If the primary NameNode died, an administra-
tor had to manually provision a new one, resulting in significant downtime.
• Namespace Bottleneck: Because a single NameNode had to hold the entire file system metadata
in its RAM, the maximum size of an HDFS 1.0 cluster was severely bottlenecked by the physical
memory limit of that single master machine.

1.4 What was Added in HDFS 3.0? (Storage Focus)

HDFS 3.0 retained the High Availability architecture shown in your diagram but introduced major
features to optimize storage efficiency and fault tolerance.
• Erasure Coding (EC): HDFS 1.0 and 2.0 achieved fault tolerance by replicating every data block
three times (a 200% storage overhead). HDFS 3.0 introduced Erasure Coding, which uses mathe-
matical parity to provide the same level of fault tolerance with only a 50% storage overhead. This
drastically reduces hardware costs for storing data.

• Support for Multiple Standby NameNodes: While the HDFS 2.0 diagram shows exactly one Active
and one Standby NameNode, HDFS 3.0 allows you to configure multiple Standby NameNodes.
This provides even greater resilience against consecutive hardware failures.
• Intra-DataNode Disk Balancer: In HDFS 2.0, data could become unevenly distributed across the
various hard drives within a single DataNode, leading to localized bottlenecks. HDFS 3.0 added a
dedicated balancer to evenly distribute data across all physical disks mounted on a specific node.

2 Physical Organization of Compute Nodes in HDFS

The physical infrastructure of a large-scale DFS is engineered for fault tolerance, high throughput, and
massive horizontal scalability, almost exclusively utilizing commodity hardware.

2.1 Hierarchical Cluster Topology

To optimize network traffic and isolate hardware failures, nodes are organized into a strict physical
hierarchy:

• Nodes (Servers): The fundamental compute/storage unit. Each node typically consists of stan-
dard CPUs, RAM, and multiple directly attached disk drives (HDDs or SSDs).
• Racks: Nodes are grouped into physical racks, usually containing 20 to 40 nodes. Nodes within the
same rack communicate via a Top-of-Rack (ToR) switch. Intra-rack communication is extremely
fast and has high bandwidth.
• Clusters: Multiple racks are aggregated to form a cluster. The ToR switches are connected
to core switches or spine switches. Cross-rack communication is subject to higher latency and
oversubscription, making it slower than intra-rack communication.

2
2.2 Division of Roles
While hardware may be similar, compute nodes are logically and physically assigned distinct roles to
optimize resource allocation:
• Master/Metadata Nodes: Highly reliable, specialized servers that maintain the file system’s
namespace and track where data is located. Because metadata is kept in memory for speed, these
nodes require massive amounts of RAM and fast persistent storage for transaction logs, but less
raw disk space.
• Worker/Storage Nodes: The vast majority of the cluster. These nodes store the actual data
and execute local compute tasks. They require dense, high-capacity storage configurations.

3 Large-Scale File-System Organization in HDFS

Traditional local file systems (like ext4 or NTFS) are inefficient at the petabyte scale. A DFS employs
distinct logical strategies to manage massive datasets efficiently.

3.1 File Chunking and Block Sizes

Files in a large-scale DFS are not stored as single continuous streams. Instead, files are split into massive,
fixed-size blocks (or chunks)—commonly 64 MB, 128 MB, or even 256 MB.
• Minimized Metadata: Larger blocks drastically reduce the amount of metadata the master node
must track.
• Optimized Throughput: Large block sizes minimize disk seek times, optimizing the system for
massive sequential reads, which is the dominant workload in big data analytics.

3.2 Namespace and Metadata Management

A centralized master server manages the entire namespace (directories, files, and permissions) and the
block-to-node mapping.
• In-Memory Architecture: For high-performance lookups, the entire directory structure and
block mapping are held in the master node’s RAM.
• Fault Tolerance: To prevent catastrophic data loss, namespace mutations are sequentially recorded
to a Write-Ahead Log (WAL) stored on highly durable, replicated storage.

3.3 Replication and Rack-Awareness

Because commodity hardware has a high failure rate, data replication is mandatory. A standard repli-
cation factor is three (each block has three copies across the cluster).
• Rack-Aware Placement: To survive both single-node and total-rack power/network failures, a
smart DFS uses a rack-aware placement policy. Typically, the first replica is written to the local
node, the second to a different node in the same rack, and the third to a node in a completely
different rack.
• Heartbeats and Self-Healing: Storage nodes continuously send heartbeat signals to the master.
If a node fails to report, the master marks it as dead and autonomously initiates the re-replication
of the lost blocks to other healthy nodes, maintaining the desired replication factor.

4 How these operations work in practice in HDFS

Let’s dive deep into the specific mechanics of how data flows during read and write operations. In
a Distributed File System (DFS) like Hadoop (HDFS) or Google File System (GFS), the core design
philosophy is to decouple control flow from data flow.
The Master node handles the control flow (metadata and permissions), while the Client and Worker
nodes handle the data flow directly. This prevents the Master from becoming a catastrophic network
bottleneck.

3
4.1 The Write Pipeline: Data Ingestion and Replication
Writing a massive file to a DFS is not a single transaction; it is a coordinated, streaming pipeline designed
to maximize throughput and guarantee fault tolerance.
Step-by-Step Write Flow:
• The Request: The Client reaches out to the Master node to request the creation of a new file. The
Master checks if the file already exists and if the Client has the correct permissions. If valid, the
Master creates a new empty record in its namespace.
• Block Allocation: As the Client begins writing data, it asks the Master for a block allocation. The
Master responds with a list of Worker nodes where the replicas for the first block should be stored
(e.g., Node A, Node B, and Node C, chosen based on rack-awareness).
• The Data Pipeline: The Client does not send the data to all three nodes simultaneously, as this
would exhaust its outbound bandwidth. Instead, it forms a pipeline:
The Client streams the data chunk to Node A.
As Node A receives the data, it immediately begins streaming a copy to Node B.
As Node B receives the data, it streams a copy to Node C.
• Acknowledgements: Once Node C successfully writes the data to its disk, it sends an acknowledg-
ment (ACK) to Node B. Node B sends an ACK to Node A, and Node A sends the final ACK back
to the Client.
• Completion: The Client repeats this process for every subsequent block of the file. Once the
entire file is written, the Client signals the Master node that the file is closed and the operation is
complete.

5 Introduction to mapreduce

Figure 2: Mapreduce

MapReduce is a programming model designed for processing massive volumes of data in parallel across
a distributed cluster. In above diagram, elegantly breaks down the complete lifecycle of a MapReduce
job from input to output.
Here is the step-by-step breakdown of that flow:

• File & Input Format: The process begins with raw data files stored in HDFS. The Input Format
determines how these files should be read and divided into logical chunks.
• Split (Input Splits): The input data is broken down into smaller, logical ”Splits.” Usually, one
split corresponds to one HDFS block. One Map task is created for each split, allowing for parallel
processing.

• RR (Record Reader): The Map task cannot process raw text. The Record Reader reads the split
data line-by-line and converts it into Key-Value (KV) pairs (e.g., Key = byte offset, Value = the
actual line of text).

4
 • Map Phase: This is where the core logic happens. The Map function processes the Key-Value pairs
generated by the RR. It filters, sorts, or transforms the data, generating a new set of intermediate
Key-Value pairs.
• Partitioner (Shuffle & Sort phase): Before data goes to the Reducer, the Partitioner determines
which Reducer gets which Key-Value pairs. It groups all identical keys together. Following this,
the Sort phase orders these keys sequentially. This shuffle and sort phase involves heavy network
traffic as data moves across nodes.
• Reducer: The Reducer takes the grouped Key-Value pairs (e.g., Word: [1, 1, 1, 1]) and applies an
aggregation or summary function (e.g., summing them to Word: 4).

• Output Format: Finally, the Output Format dictates how the final Key-Value pairs generated by
the Reducer are written back into HDFS as physical files.

5.1 How Hadoop 1.0, 2.0, and 3.0 Affected MapReduce

The MapReduce programming paradigm (the code you write) has stayed largely the same, but the
execution engine underneath it has undergone massive overhauls across versions.

5.1.1 Hadoop 1.0: The Bottleneck

• In Hadoop 1.0, MapReduce was the only way to process data.
• It relied on a single master daemon called the JobTracker to handle both cluster resource manage-
ment and job scheduling, while TaskTrackers on slave nodes executed the tasks.
• The Problem: The JobTracker became a massive bottleneck in large clusters, and because MapRe-
duce was hardcoded into the architecture, you couldn’t run other processing frameworks (like graph
processing or streaming) on the same cluster.

5.1.2 Hadoop 2.0: Decoupling via YARN

• Hadoop 2.0 introduced YARN (Yet Another Resource Negotiator). This decoupled resource man-
agement from the MapReduce processing engine.
• MapReduce was demoted from being the ”ruler” of Hadoop to just being one of many processing
applications running on top of YARN.
• The Effect: MapReduce jobs became much more scalable. The central Resource Manager now only
handled allocating memory/CPU, while a dedicated ApplicationMaster was spun up to manage
each specific MapReduce job.

5.1.3 Hadoop 3.0: Optimization and Efficiency

• Hadoop 3.0 didn’t change the MapReduce execution model but improved the environment it runs
in.
• The Effect: MapReduce jobs benefit from platform-level upgrades like Java 8 support, which
improved performance. Furthermore, Hadoop 3.0 introduced support for GPUs and FPGAs via
YARN, allowing MapReduce tasks involving heavy machine learning or mathematical computations
to be hardware-accelerated. The introduction of Erasure Coding also drastically reduced the storage
footprint of the MapReduce output files.

5.2 The Map Tasks

The Map phase is the first stage of data processing in the MapReduce paradigm. Before the Map
task begins, the underlying framework divides the input data into fixed-size pieces called Input Splits
(typically aligning with HDFS block sizes, such as 128 MB).
A Record Reader parses these splits into initial key-value pairs, which are then passed to the Map
function. The Map task is fundamentally a transformation and filtering operation. It processes each
input pair independently and in parallel across the cluster to produce intermediate key-value pairs.

5
 Formally, the Map function can be defined as:

M ap(k1 , v1 ) → list(k2 , v2 ) (1)

Where (k1 , v1 ) represents the input data (e.g., byte offset and line of text), and the output is a list of
intermediate keys and values.

5.3 Grouping by Key (Shuffle and Sort)

This phase bridges the Map and Reduce tasks. Once the Map tasks generate intermediate outputs, the
data must be organized so that all values associated with the same key are sent to the same Reducer.

• Partitioning: A partitioner determines which Reducer will process a specific key. The default parti-
tioner uses a hash function:
P artition = hash(k2 ) (mod n) (2)
(where n is the number of Reduce tasks).
• Sorting and Grouping: The framework sorts the intermediate data by key. It then groups all
values associated with the same key together. This phase is highly network-intensive, as data must be
transferred physically across the cluster’s nodes.

• Output of this phase: The data is transformed into a grouped format ready for reduction: (k2 , list(v2 )).

5.4 The Reduce Tasks

The Reduce phase aggregates, summarizes, or processes the grouped data generated by the shuffle and
sort phase. Each Reduce task processes the intermediate keys assigned to it (one key at a time, along
with its list of values).
The output of the Reduce task is typically written directly back to the distributed file system (HDFS),
and it is not further partitioned or sorted.
Formally, the Reduce function is defined as:

Reduce(k2 , list(v2 )) → list(v3 ) (3)

Where the final output (v3 ) is usually a single aggregated value or a smaller set of values.

5.5 Combiners (The “Mini-Reducers”)

A Combiner is an optional optimization component that acts as a local Reducer on the output of a Map
task before the data is sent over the network for the Shuffle phase.

• Purpose: To minimize network bandwidth consumption. If a Map task outputs a massive amount
of repetitive keys (e.g., (the, 1), (the, 1), (the, 1)), sending all of them across the network is
inefficient.
• Execution: The Combiner aggregates these local key-value pairs on the Mapper node to (the, 3).

• Constraint: Combiners can only be used when the Reduce function is both commutative and
associative (e.g., addition or finding a maximum). They cannot be used for operations like calculating
an average, as combining averages locally will mathematically skew the final global average.

5.6 Details of MapReduce Execution

The end-to-end execution of a MapReduce job is orchestrated by the cluster’s resource management
framework (e.g., YARN in Hadoop 2.x/3.x).

1. Job Submission: The client submits the MapReduce job, including the Map and Reduce classes
and configuration parameters.
2. Resource Allocation: The Resource Manager allocates an Application Master for the specific job.

6
3. Data Locality Optimization: The framework attempts to schedule Map tasks on the exact physical
nodes where the data blocks reside (Rack Awareness). Moving computation to the data is significantly
faster than moving large datasets across the network.
4. Task Execution: The Application Master negotiates processing containers on worker nodes and
launches the Map tasks.
5. Synchronization: Reduce tasks cannot begin processing until all Map tasks have successfully fin-
ished, ensuring all data for a specific key has been accounted for during the Shuffle phase.

5.7 Coping With Node Failures

MapReduce was explicitly designed to operate on commodity hardware where failures are treated as an
expectation, not an exception. The framework handles this autonomously:

• Heartbeats: Worker nodes periodically send “heartbeat” signals to the Master node. If a node fails
to send a heartbeat within a specified timeout threshold, the Master assumes the node is dead.
• Handling Map Task Failures: If a node running a Map task dies, the Master simply reschedules
that specific Map task on another node that contains a replica of that data block. Even if a Map
task had completed successfully on that node, it must be re-executed because its intermediate output
(stored on the dead node’s local disk) is now lost and cannot be shuffled to the Reducers.
• Handling Reduce Task Failures: If a node running a Reduce task dies, the framework reschedules
the task on another available node. The new Reduce task will simply pull the required intermediate
data from the completed Map nodes and restart its processing.

Problem Statement
Trace the complete execution of a MapReduce job designed to calculate total sales per city. Demonstrate
how the data transforms at every phase shown in the MapReduce architecture diagram.
Input Dataset ([Link]):

Mumbai, 100
Delhi, 200
Mumbai, 150
Chennai, 300
Delhi, 100

Phase-by-Phase Execution Trace

1. File & Input Format
The raw file resides in HDFS. The TextInputFormat is selected, which defines how the data should
be logically read (line by line).

2. Split
The framework divides the input data into logical Input Splits for parallel processing. Assuming the file
is divided into two splits based on block size:
• Split 1: Mumbai, 100 | Delhi, 200 | Mumbai, 150
• Split 2: Chennai, 300 | Delhi, 100

7
3. RR (Record Reader)
The Record Reader converts the raw text splits into initial Key-Value pairs. The key is the byte offset,
and the value is the line of text.

• RR for Split 1:

(0, “Mumbai, 100”), (12, “Delhi, 200”), (23, “Mumbai, 150”)

• RR for Split 2:
(0, “Chennai, 300”), (14, “Delhi, 100”)

4. Map
Two Map tasks are spawned. The Mapper discards the byte offset, splits the text by the comma, and
outputs the City as the Key and the Sales Amount as the Value.

• Mapper 1 Output:
(Mumbai, 100), (Delhi, 200), (Mumbai, 150)

• Mapper 2 Output:
(Chennai, 300), (Delhi, 100)

5. Partitioner
The Partitioner determines which Reducer receives which keys. Let us assume a hash partitioner dividing
data across two Reducers (e.g., Reducer 1 for cities A-M, Reducer 2 for cities N-Z).
• Routed to Reducer 1: (Delhi, 200), (Chennai, 300), (Delhi, 100)
• Routed to Reducer 2: (Mumbai, 100), (Mumbai, 150)

6. Sort (and Group)

Before the Reducer processes the data, it is sorted by key and grouped together.

• Reducer 1 Sort/Group Output:

(Chennai, [300])
(Delhi, [200, 100])

• Reducer 2 Sort/Group Output:

(Mumbai, [100, 150])

7. Reducer
The Reducer iterates through the grouped values for each key and applies the aggregation logic (Sum).
• Reducer 1 Execution:

Chennai → 300
Delhi → 200 + 100 = 300

• Reducer 2 Execution:

Mumbai → 100 + 150 = 250

8
8. Output Format
The TextOutputFormat writes the final Key-Value pairs back to HDFS into separate part files.
• part-r-00000 (from Reducer 1):


Chennai300

Delhi300

• part-r-00001 (from Reducer 2):


Mumbai250

Problem Statement
Assume we have three small text files stored in HDFS. We need to execute a MapReduce job to determine
the total frequency of each word across all files.

Input Dataset:
• File 1: Deer Bear River
• File 2: Car Car River
• File 3: Deer Car Bear

Step-by-Step Data Flow

Step 1: Input Split & Record Reader
Hadoop splits the input files and assigns a unique Map task to each split. The RecordReader converts
the raw text into the initial ⟨Key, V alue⟩ pairs. The key is the byte offset of the line, and the value is
the actual text.

Initial Input ⟨Key, V alue⟩ Pairs

• Mapper 1 (File 1): ⟨0, ”Deer Bear River”⟩

• Mapper 2 (File 2): ⟨0, ”Car Car River”⟩
• Mapper 3 (File 3): ⟨0, ”Deer Car Bear”⟩

Step 2: Map Phase

The custom Mapper code executes on each node. The logic splits the sentence into individual words and
emits a value of 1 for each word.

Map Phase

Mapper Output ⟨Key, V alue⟩ Pairs

Mapper 1 Output:
⟨”Deer”, 1⟩, ⟨”Bear”, 1⟩, ⟨”River”, 1⟩
Mapper 2 Output:
⟨”Car”, 1⟩, ⟨”Car”, 1⟩, ⟨”River”, 1⟩
Mapper 3 Output:
⟨”Deer”, 1⟩, ⟨”Car”, 1⟩, ⟨”Bear”, 1⟩

9
Step 3: Shuffle and Sort Phase
This phase is handled automatically by the MapReduce framework. It transfers data across the network,
merging and sorting the output from all Mappers so that all identical keys are grouped together and
sent to the same Reducer.

Shuffle & Sort Output (Input to Reducers)

• ⟨”Bear”, [1, 1]⟩

• ⟨”Car”, [1, 1, 1]⟩

• ⟨”Deer”, [1, 1]⟩
• ⟨”River”, [1, 1]⟩

Step 4: Reduce Phase

The Reducer receives the grouped keys and the list of values. The custom Reducer logic iterates through
the list, summing the integers to find the total count.

Reduce Phase
Reducer Output (Final Output to HDFS)

• ⟨”Bear”, 2⟩
• ⟨”Car”, 3⟩
• ⟨”Deer”, 2⟩

• ⟨”River”, 2⟩

Summary Trace Table

Phase Data Transformation Format

Input Deer Bear River Raw Text

RecordReader ⟨0, ”Deer Bear River”⟩ ⟨K1, V 1⟩
Mapper ⟨”Deer”, 1⟩, ⟨”Bear”, 1⟩, ⟨”River”, 1⟩ ⟨K2, V 2⟩
Shuffle & Sort ⟨”Bear”, [1, 1]⟩, ⟨”Deer”, [1, 1]⟩ . . . ⟨K2, List(V 2)⟩
Reducer ⟨”Bear”, 2⟩, ⟨”Deer”, 2⟩ . . . ⟨K3, V 3⟩

Table 1: Data state at each phase of the Word Count job.

6 Matrix-Vector Multiplication by MapReduce

Suppose we have an n × n matrix M and
Pna vector v of length n. We want to compute the matrix-vector
product x = M v, where element xi = j=1 mij vj .
Assumption: The vector v is small enough to fit into the main memory of every Map worker. The
matrix M is massive and stored in HDFS as tuples of (i, j, mij ).

10
 Map Phase

For each matrix element mij , the Mapper accesses vj from main memory and computes the partial
product mij vj .
• Input: A tuple representing a matrix element (i, j, mij ).

• Output: Emit ⟨i, mij vj ⟩.

Reduce Phase
The Shuffle and Sort phase groups all values associated with the same row index i. The Reducer
simply sums these values.
• Input: ⟨i, [mi1 v1 , mi2 v2 , . . . , min vn ]⟩.
Pn
• Logic: Compute xi = j=1 mij vj .
• Output: Emit ⟨i, xi ⟩.

7 Relational-Algebra Operations
Relational algebra operations are the foundation of SQL queries. Because data sets in Big Data are
enormous, relational operations on tables (relations) like Selection, Projection, and Set Operations must
be distributed using MapReduce. Let R and S be large relations (tables) stored in HDFS.

7.1 Computing Selections (σC (R))

Selection extracts tuples from relation R that satisfy a specific condition C.

Map Phase

The Mapper applies the condition C to every incoming tuple.

• Input: A tuple t ∈ R.
• Logic: If C(t) is true, emit the tuple. Otherwise, discard it.
• Output: Emit ⟨t, t⟩.

Reduce Phase
Since Selection does not require aggregation, the Reducer essentially acts as an identity function.
• Input: ⟨t, [t]⟩.

• Output: Emit t.

7.2 Computing Projections (πA (R))

Projection creates a new relation by extracting only a specified subset of attributes A from R. Because
removing attributes might create duplicate tuples, the Reduce phase is critical for duplicate elimination.

11
 Map Phase

The Mapper extracts the required attributes from the tuple.

• Input: A tuple t ∈ R.
• Logic: Extract the attributes A to form a new tuple t′ .

• Output: Emit ⟨t′ , t′ ⟩.

Reduce Phase
The MapReduce framework automatically groups identical tuples together. The Reducer outputs
only one instance of the tuple, thereby eliminating duplicates.
• Input: ⟨t′ , [t′ , t′ , . . . , t′ ]⟩.
• Output: Emit t′ .

7.3 Union (R ∪ S)
Union combines the tuples of R and S. Like Projection, we must eliminate duplicates (if the same tuple
appears in both R and S).

Map Phase

The Mapper simply passes every tuple it reads from either dataset.
• Input: A tuple t ∈ R or t ∈ S.

• Output: Emit ⟨t, t⟩.

Reduce Phase
Identical tuples from R and S will be grouped into the same key. The Reducer ignores the duplicates
and outputs the key once.
• Input: ⟨t, [t, t, . . . ]⟩.
• Output: Emit t.

7.4 Intersection (R ∩ S)
Intersection identifies tuples that exist in both relation R and relation S.

Map Phase

Similar to Union, the Mapper passes every tuple from both datasets.
• Input: A tuple t ∈ R or t ∈ S.
• Output: Emit ⟨t, t⟩.

12
 Reduce Phase
If a tuple exists in both R and S, its value list will contain exactly two elements (assuming R and
S themselves are true sets with no internal duplicates).

• Input: ⟨t, [t1 , t2 , . . . ]⟩.

• Logic: If the length of the value list is 2, emit the tuple.
• Output: Emit t.

7.5 Difference (R − S)
Difference identifies tuples that exist in relation R but do not exist in relation S.

Map Phase

The Mapper must tag each tuple with its source relation so the Reducer knows where it came from.
• Input: A tuple t.
• Logic:
– If t ∈ R, emit ⟨t, ’R’⟩.
– If t ∈ S, emit ⟨t, ’S’⟩.

Reduce Phase
The Reducer examines the list of tags associated with each tuple. It only emits the tuple if it is
tagged with ’R’ but missing the ’S’ tag.
• Input: ⟨t, [List of tags (’R’ or ’S’)]⟩.
• Logic: If the list contains ’R’ but does not contain ’S’.

• Output: Emit t.

8 Introduction to YARN
Introduced in Hadoop 2.0, YARN (Yet Another Resource Negotiator) is the resource management
and job scheduling layer of the Hadoop distributed processing ecosystem. By decoupling resource man-
agement from data processing logic (MapReduce), YARN transformed Hadoop from a single-application
system into a multi-purpose distributed operating system capable of running batch processing, interactive
queries, and real-time streaming simultaneously.

8.1 The Need for YARN (Overcoming Hadoop 1.x Limitations)

In Hadoop 1.x, the JobTracker was a single point of failure and a massive bottleneck. It was responsible
for both Cluster Resource Management and Task Scheduling/Monitoring. As clusters grew beyond 4,000
nodes, the JobTracker could not handle the load of tracking every individual map and reduce task.
YARN solves this by splitting these two responsibilities into separate daemons.

8.2 Core Architecture and Components

The YARN architecture operates on a Master-Slave model, consisting of the following core components:
1. ResourceManager (RM) – The Master The ResourceManager is the ultimate authority that arbi-
trates resources among all competing applications in the cluster. It has two main sub-components:
• Scheduler: Strictly responsible for allocating resources to the various running applications subject
to familiar constraints of capacities, queues, etc. It performs no monitoring or tracking of status
for the application.

13
 • ApplicationsManager (AsM): Responsible for accepting job submissions, negotiating the first
container for executing the ApplicationMaster, and providing the service for restarting the Appli-
cationMaster container on failure.
2. NodeManager (NM) – The Slave The NodeManager is the per-machine framework agent. It is
responsible for:
• Launching application containers as directed by the ResourceManager.
• Monitoring the resource usage (CPU, memory, disk, network) of those containers.
• Reporting the node’s health and resource availability back to the ResourceManager via heartbeats.

3. ApplicationMaster (AM) – Per-Job Manager Unlike the centralized JobTracker in Hadoop 1.x,
YARN spawns a dedicated ApplicationMaster for each submitted application. Its responsibilities include:
• Negotiating appropriate resource containers from the ResourceManager.
• Tracking the status and progress of the application’s tasks.
• Handling task failures by requesting new containers and rescheduling the tasks.

4. Container – The Resource Unit A Container is the fundamental unit of resource allocation in
YARN. It represents a strictly isolated package of physical resources (e.g., 2 GB of RAM, 1 CPU core)
on a specific worker node. All application tasks (like a Map task or a Reduce task) execute inside a
YARN Container.

8.3 YARN Job Execution Workflow

When a client submits an application (e.g., a MapReduce job) to a YARN cluster, the execution follows
a strict sequence of events:

1. Job Submission: The client submits the application to the central ResourceManager.
2. AM Allocation: The ResourceManager’s ApplicationsManager negotiates a single Container
on an available NodeManager and launches the ApplicationMaster for that specific job.

3. Resource Request: The newly launched ApplicationMaster analyzes the job requirements (e.g.,
calculating how many map and reduce tasks are needed based on data splits) and registers with
the ResourceManager. It then requests the necessary number of Containers.
4. Task Launch: Once the ResourceManager grants the leases for the Containers, the Application-
Master contacts the respective NodeManagers to start those Containers.

5. Execution: The NodeManagers launch the Containers, and the actual application code executes
inside them.
6. Monitoring: While tasks run, they report their progress and status back to the Application-
Master (not the ResourceManager).

7. Completion: Once all tasks are successfully completed, the ApplicationMaster unregisters with
the ResourceManager and shuts itself down, freeing its own Container back to the cluster pool.

14