Map Reduce and Merge Sort Concepts

Big Data Systems - Map Reduce I

• This presentation covers Big Data Systems and MapReduce.
• MapReduce is a programming model and framework for large-scale, distributed data processing, inspired by functional programming's "map" and "reduce" functions.
• It's a simple parallelization model using "shared nothing" architectures (commodity hardware).
• MapReduce was developed by Google (Jeff Dean and Sanjay Ghemawat) and presented in 2004.
• It's frequently used for web indexing and various other data processing jobs.
• It has an open-source implementation known as Apache Hadoop.

Announcements

• One week remained for the first exercise.
• Students should check out discussions in Moodle.

Timeline I

• A detailed schedule for the topics covered in the course.

This Lecture

• MapReduce Paradigm
• Sorting large amounts of data
• MR Architecture

Sources

• Dean and Ghemawat's paper on MapReduce for simplifying data processing on large clusters.
• Links to additional online resources on MapReduce.

Where are we?

• Introduction to Big data processing.
• MapReduce is one of the ancestor of frameworks for big data processing.
• It can be used independently of the complete stack

Basic Web Search Interaction

• Big data involves billions of web pages.
• Non-interactive workloads operate within minutes or hours.
• Search relies on distributed processing using many servers.

Large Scale Data Analysis

• Google's 2004 challenges with storing and processing 20+ billion web pages.
• One computer's limited processing speeds and the duration it takes processing the web.
• The difficulties of distributed and parallel programming.

MapReduce

• MapReduce's architecture is described
• It is a programming paradigm for large-scale data processing using functional programming paradigms: Map and Reduce
• It's a simple parallelization model using commodity hardware.
• Details on how it was developed by Google.
• MapReduce is a part of Google's Big Data Stack.
• Components of Google's Big Data Stack.

Open Source Implementation

• Apache Hadoop is an open-source clone of Google's framework.
• Developed at Yahoo.
• Key elements and components of the Hadoop architecture.

Map – Shuffle/Sort – Reduce

• Map functions take input data and transform it into intermediate values.
• Shuffle and Sort steps organize the intermediate data.
• Reduce works on grouped data to calculate the final outcome.

Simple Example

• A simple example in counting the frequencies of words in a petabyte of text using MapReduce.
• Steps required for the solution

MapReduce - Conceptual Data Flow

• Diagram showing the MapReduce process flow.
• Intermediate outputs and their distribution.

Map Example

• Illustrative example of the map function in MapReduce, along with code example.

Reduce Example

• Explanation of the reduce function in MapReduce.
• Code example

Full Code Example (Hadoop)

• Examples of Hadoop code (Map and Reduce)

Map Phase – Example Word Count

• Diagrams illustrate the input processing and how data is passed from the map to reduce phase

Sort Phase – Example Word Count

• Diagrams that show how the data is sorted by the Map-Reduce framework

Reduce Phase – Example Word Count

• Illustrations of the Map-Reduce process results

Shuffling / Sorting Stage

• Details about the Map side shuffling and sorting
• Details about the Reduce side shuffling and sorting

Sorting in Detail

• Algorithm used for sorting: Merge Sort
• How it works.

Merge Sort

• Description of the Merge Sort algorithm to order inputs
• Cost analysis
• Recursive nature of the algorithm

Two-Phase, Multiway Merge-Sort (TPMMS)

• Handling cases when data does not fit in main memory.
• Two-phase process (Phase 1 and Phase 2).

2-Way Sort

• Diagram illustrating the two-phase sort process using two buffer blocks.

TPMMS – Phase 1

• Recursion for multi-way merge sort.
• Steps involved in filling memory and writing sorted chunks to disk.

TPMMS – Phase 2

• Algorithm to merge partitions in main memory for efficient sorting.
• Handling large partitions

Two-Phase Multiway Merge Sort

• Diagram showing the steps involved in the multi-way merge sort process using the main memory

Limitations of TPMMS

• Specifics on how limited memory can be leveraged.
• Analysis on the limits of the process.

Multi-Phase MMS

• Handling cases where the dataset is even larger.
• The three-phase process (Phase 1, Phase 2, and Phase 3).

Short Break

• Briefly pause for a break.

MapReduce Architecture

• Overview of the MapReduce architecture.

Simplified Architecture

• Diagram illustrating the phases and flow of the MapReduce architecture.

MapReduce Execution Stages

• Stages in MapReduce execution, emphasizing planning, processing, handling data, and managing failures.

Parallelism

• Processes handled in parallel/concurrently by MapReduce.
• Bottlenecks in the system, such as the reduce phase starting only after the map phase is finalized

Parallelism II

• Diagrams showing details of how tasks are divided and processed and results from the map tasks are passed for sorting.

Additional Optimizations

• Techniques like combiners and locality for performance tuning.

Combiners

• Use of combiners for intermediate data reduction, to decrease network overhead.

Partitioning Function

• Function used to assign output tasks to reduce tasks.

Locality

• Optimizations used to improve data locality for I/O efficiency.

Other Optimizations

• Techniques such as replicating tasks, skipping "bad" records, and data compression.

Fault Tolerance

• Handling failures using heartbeats and re-executing tasks.

Summary

• Recap of MapReduce.
• MapReduce programming paradigm
• MapReduce framework

Next Part

• Introduction of Map Reduce II.

Questions

• Information for questions, such as email and Moodle support.