Welcome!

Virtualization and Cloud

Jonathan Gershater

Subscribe to Jonathan Gershater: eMailAlertsEmail Alerts
Get Jonathan Gershater via: homepageHomepage mobileMobile rssRSS facebookFacebook twitterTwitter linkedinLinkedIn


Blog Post

Hadoop Deep Dive: HDFS and MapReduce

How does Hadoop process data? What is MapReduce?

Following my initial introduction to Hadoop and overview of Hadoop components, I studied the Yahoo Hadoop tutorial,  and have a deeper understanding of Hadoop. I  would like to share my learning and help others understand Hadoop.

Why does Hadoop require HDFS, what's wrong with NFS?

Nothing! NFS been around for years and is incredibly stable. A distributed file system, such as NFS, provides the functionality required for servers to share files. It does this by exposing a volume to the network, which users connect to over the TCP/IP protocol.

For Hadoop applications that require highly available distributed file systems with unlimited capacity HDFS is preferred. The following table outlines where NFS is deficient for Hadoop and where HDFS solves the limitation.

NFS limitation Hadoop optimization
What happens when the volume is full? No more files can be stored. HDFS stores information (terabytes or petabytes) across many servers. HDFS supports larger file sizes than NFS
What happens if a volume or server fails? There is no built-in redundancy. HDFS stores data reliably. If a server in the cluster fails, the data is still available on other servers.
NTFS & EXT3 file systems typically used by NFS have 4-8KB block sizes that result in large metadata about each file and multiple reads from the file system. The default block size in HDFS is 64MB, which results in fewer files to store and decreased metadata information stored for each file. HDFS is optimized to provide streaming read performance, rather than random seek to arbitrary positions in files
Most NFS administration is command line or included with overall system management tools. HDFS provides a web server to perform status monitoring and file browsing operations (by default port 50070).

Hadoop can exploit HDFS and thus:

  • Hadoop is aware of physical racks that span more than one network switch. Replicas of the data exist across racks, thus if a physical switch fails, the data is available from another server rack.
  • There is no local caching since files are large and sequentially read
  • HDFS reads a block start-to-finish for the Hadoop MapReduce application. MapReduce? Read on....

What is MapReduce?

MapReduce is a programming model to process large volumes of data, usually tuple (pair) lists, for example:

  • city, temperature
  • student, grade
  • car, maximum speed

MapReduce accomplishes this in parallel by dividing the work into independent tasks, spread across many nodes (servers). This model would not scale to large clusters (hundreds or thousands of nodes) if the components shared data arbitrarily. The communication overhead required to keep the data on the nodes synchronized would be inefficient. Rather, the data elements in MapReduce are immutable, meaning that they cannot be updated. Example, if during a MapReduce job, input data is changed eg. (modifying a student grade or car's speed) the change does not get reflected in the input files; instead new output (key, value) pairs are generated which are then forwarded by Hadoop into the next phase of execution.

Driver

The driver initializes the job and instructs Hadoop to execute the job on a set of input files, and controls where the output files are placed. Pretty simple.

Map

The map portion of MapReduce provides a list of data elements, one at a time, to a function called the Mapper. The mapper transforms each input element to an output data element.

Reduce

Reducing aggregates the values together.  A reducer function receives the input values from an input list, then combines these values together, returning a single output value; example: average car speed, student grade or city temperature.

Sounds simple? At a high level yes, details details...

The mapper produces one output element for each input element, and a reducer produces one output element for each input list. A map job may input into zero or more outputs; a reducer may compute over an input list and create one or more  outputs.

What if the amount of data to reduce is enormous? Keys divide the reduce space: A reducing function turns a large list of values into one (or a few) output values but may not be reduced together. All of the values with the same key are presented to a single reducing function together. This is performed independently of any reduce operations occurring on other lists of values, with different keys attached. So in our example, perhaps all the Toyota vehicles are reduced together, Ford vehicles in another group and Chevrolet in a third set; similarly grade 10 kids' scores are reduced in one set, grade 11 in another etc.

So why is HDFS needed for MapReduce?

The map jobs: MapReduce inputs come from input files loaded which are evenly distributed across all servers. Executing a MapReduce program involves running mapping tasks on many or all of the nodes. Each of these mapping tasks is identical, therefore, any mapper can process any input file. Each mapping job loads the files on that server and processes them. Thus data is processed at the node where it exists and not copied to a central server (see my introductory article for more details). Individual map tasks do not communicate with one another, nor are they aware of one another's existence.

The reduce jobs:
When the mapping phase has completed, the intermediate (key, value) pairs must be exchanged between servers to send all values with the same key to a single reduce job. To illustrate the example above, all the values from the Toyota vehicles must be sent to the reduce job responsible for Toyota; similarly for other vehicles, city temperatures and class grades must be sent to their unique reduce function. The reduce tasks are spread across the same nodes in the Hadoop cluster as the map jobs. Similarly, different reduce tasks do not communicate with one another.

If servers in the Hadoop cluster fail, the map or reduce tasks must be able to be restarted. Thus a highly scalable and fault tolerant file system like HDFS is required for successful MapReduce jobs.

Fault tolerance HDFS is key

Hadoop achieves fault tolerance by restarting tasks when a server (node) fails. Individual task nodes (TaskTrackers) communicate with the head node of the system (JobTracker). If a TaskTracker fails to communicate with the JobTracker  (by default, 1 minute), the JobTracker will assume that the specific TaskTracker has failed. The JobTracker knows which map and reduce tasks were assigned to each TaskTracker; other TaskTrackers will re-execute a failed map or reduce job.

Completed reduce tasks, are written back to HDFS. Thus, if a TaskTracker has already completed two out of three reduce tasks assigned to it, only the third task must be executed on another node/server.
Hadoop code should have no 'side effects'
If Map and Reduce jobs had individual identities and communicated with one another (rather than the TaskTracker) , then restarting a task would require the other nodes to communicate with the new instances of the map and reduce tasks, and the re-executed tasks would need to reestablish their prior state.  An individual task sees only its own direct inputs and knows only its own outputs, to make this failure and restart process clean and dependable.

Sounds complicated? Try a tutorial download from HortonWorks, Cloudera or Yahoo.

Image below show two nodes, multiple mappers and reducers; courtesy of Yahoo Hadoop tutorial, module 4

More Stories By Jonathan Gershater

Jonathan Gershater has lived and worked in Silicon Valley since 1996, primarily doing system and sales engineering specializing in: Web Applications, Identity and Security. At Red Hat, he provides Technical Marketing for Virtualization and Cloud. Prior to joining Red Hat, Jonathan worked at 3Com, Entrust (by acquisition) two startups, Sun Microsystems and Trend Micro.

(The views expressed in this blog are entirely mine and do not represent my employer - Jonathan).

Comments (0)

Share your thoughts on this story.

Add your comment
You must be signed in to add a comment. Sign-in | Register

In accordance with our Comment Policy, we encourage comments that are on topic, relevant and to-the-point. We will remove comments that include profanity, personal attacks, racial slurs, threats of violence, or other inappropriate material that violates our Terms and Conditions, and will block users who make repeated violations. We ask all readers to expect diversity of opinion and to treat one another with dignity and respect.