Hadoop is the most popular open source Java implementation of the MapReduce programming model proposed by Google. There are many other implementations of MapReduce (such as Sphere, Starfish, Riak , and so on), which implement all the features described in the Google documentation or only a subset of these features. Hadoop consists of distributed data storage engine and MapReduce execution engine. It has been successfully used for processing highly distributable problems across a large amount of datasets using a large number of nodes. These nodes collectively form a Hadoop cluster, which in turn consists of a single master node called JobTracker, and multiple worker (or slave) nodes; each worker node is called a TaskTracker. In this framework, a user program is called a job and is divided into two steps: map and reduce.
Like in the MapReduce programing model, the user has to only define the map and reduce functions when using the Hadoop MapReduce implementation. The Hadoop MapReduce system automatically parallelizes the execution of these functions and
ensures fault tolerance.
Basically, the Hadoop MapReduce framework utilizes a distributed filesystem to read and write its data. This distributed filesystem is called Hadoop Distributed File System (HDFS), which is the open source counterpart of the Google File System (GFS). Therefore, the I/O performance of a Hadoop MapReduce job strongly depends on HDFS.
HDFS consists of a master node called NameNode, and slave nodes called DataNodes. Within the HDFS, data is divided into fixed-size blocks (chunks) and spread across all DataNodes in the cluster. Each data block is typically replicated with two replicas: one placed within the same rack and the other placed outside it. NameNode keeps track of which DataNodes hold replicas of which block.
Hadoop MapReduce internals
The MapReduce programing model can be used to process many large-scale data problems using one or more steps. Also, it can be efficiently implemented to support problems that deal with large amount of data using a large number of machines. In a Big Data context, the size of data processed may be so large that the data cannot be stored on a single machine In a typical Hadoop MapReduce framework, data is divided into blocks and distributed across many nodes in a cluster and the MapReduce framework takes advantage of data locality by shipping computation to data rather than moving data to where it is processed. Most input data blocks for MapReduce applications are located on the local node, so they can be loaded very fast, and reading multiple
blocks can be done on multiple nodes in parallel. Therefore, MapReduce can achieve very high aggregate I/O bandwidth and data processing rate.
To launch a MapReduce job, Hadoop creates an instance of the MapReduce application and submits the job to the JobTracker. Then, the job is divided into map tasks (also called mappers) and reduce tasks (also called reducers). When Hadoop launches a MapReduce job, it splits the input dataset into even-sized data blocks and uses a heartbeat protocol to assign a task. Each data block is then scheduled to one TaskTracker node and is processed by a map task. Each task is executed on an available slot in a worker node, which is configured with a fixed number of map slots, and another fixed number of reduce slots. If all available slots are occupied, pending tasks must wait until some slots are freed up.
The TaskTracker node periodically sends its state to the JobTracker. When the TaskTracker node is idle, the JobTracker node assigns new tasks to it. The JobTracker node takes data locality into account when it disseminates data blocks. It always tries
to assign a local data block to a TaskTracker node. If the attempt fails, the JobTracker node will assign a rack-local or random data block to the TaskTracker node instead.
When all map functions complete execution, the runtime system groups all intermediate pairs and launches a set of reduce tasks to produce the final results. It moves execution from the shuffle phase into the reduce phase. In this final reduce phase, the reduce function is called to process the intermediate data and write the final output. Users often use terms with different granularities to specify Hadoop map and reduce tasks, subtasks, phases, and subphases. While the map task consists of two subtasks: map and merge, the reduce task consists of just one task. However, the shuffle and sort happen first and are done by the system. Each subtask in turn gets divided into many subphases such as read-map, spill, merge, copy-map, and reduce-write.
Factors affecting the performance of MapReduce
The processing time of input data with MapReduce may be affected by many factors. One of these factors is the algorithm you use while implementing your map and reduce functions. Other external factors may also affect the MapReduce performance. Based on our experience and observation, the following are the major factors that may affect MapReduce performance:
• Hardware (or resources) such as CPU clock, disk I/O, network bandwidth, and memory size.
• The underlying storage system.
• Data size for input data, shuffle data, and output data, which are closely correlated with the runtime of a job.
• Job algorithms (or program) such as map, reduce, partition, combine, and compress. Some algorithms may be hard to conceptualize in MapReduce, or may be inefficient to express in terms of MapReduce.
While running a map task, intermediate output of the shuffle subtasks is stored in a memory buffer to reduce disk I/O. However, since the size of this output may exceed that of the memory buffer and such an overflow may occur, the spill subphase is needed to flush the data into a local filesystem. This subphase may affect the MapReduce performance and is often implemented using multithreading to maximize the utility of disk I/O and to reduce the runtime of jobs.
The MapReduce programming model enables users to specify data transformation logic using their own map and reduce functions. The model does not specify how intermediate pairs produced by map functions are grouped for reduce functions to process. Therefore, the merge-sort algorithm is employed as the default grouping algorithm. However, the merge-sort algorithm is not always the most efficient algorithm, especially for analytical tasks, such as aggregation and equal-join, which do not care about the order of intermediate keys.
The MapReduce performance is based on the runtime of both map and reduce. This is because parameters such as the number of nodes in a cluster or the number of slots in a node are unmodifiable in a typical environment.
Other factors that may potentially affect the performance of MapReduce are:
• The I/O mode: This is the way to retrieve data from the storage system.
There are two modes to read data from the underlying storage system:
°° Direct I/O: This is used to read directly from the local disk cache to memory through hardware controllers; therefore, no inter-process communication costs are required.
°° Streaming I/O: This allows you to read data from another running process (typically the storage system process) through certain interprocess communication schemes such as TCP/IP and JDBC.
• Input data parsing: This is the conversion process from raw data into the key/value pairs when data is retrieved from the storage system. The data parsing process aims to decode raw data from its native format and transform it into data objects that can be processed by a programming language such as Java. Input data can be decoded to (Java or other) objects so that the content can be altered after an instance is created, typically when you use a reference to an instance of the object (these objects are called mutable objects) or to objects where the content cannot be altered after it is created (called immutable objects). In the case of a million records, the immutable decoding process is significantly slower than the mutable decoding process as it may produce
a huge number of immutable objects. Therefore, this can lead to poor performance of the system.
• Input data storage: The underlining storage system must ensure a high speed access and data availability (such as HDFS, and HBase) when data is retrieved by MapReduce to be processed. If you choose to use a storage filesystem other than those recommended to be used with MapReduce, the access to the input data may potentially affect MapReduce performance.
When using the Hadoop framework, many factors may affect the overall system performance and the runtime of a job. These factors may be part of the Hadoop MapReduce engine or may be external to it. The Hadoop configuration parameters usually indicate how many tasks can run concurrently and determine the runtime of a job since other factors are not modifiable after the Hadoop cluster is set up and the job starts the execution. A misconfigured Hadoop framework may underutilize the cluster resources and therefore impact the MapReduce job performance. This is due to the large number of configuration parameters that control the Hadoop framework’s behavior.
A Hadoop job is often composed of many submodules that implement different algorithms, and some of these sub-modules are connected in serial, while others are connected in parallel. A misconfiguration of the Hadoop framework may impact how all internal tasks coordinate together to achieve tasks.
MapReduce job performance can also be affected by the number of nodes in the Hadoop cluster and the available resources of all the nodes to run map and reduce tasks. Each node capacity determines the number of mapper and reducer tasks that a node can execute. Therefore, if the resources of nodes are underutilized or overutilized, it will directly impact the MapReduce tasks’ performance.