Chapter 2. Map/Reduce and Hadoop
12
Emit(key, val)
g
So given a list of numbers as 5;4;2;1;3;6;8;7;9, the final output file will look like
this -
Even 2,4,6,8
Odd 1,3,5,7,9
This is a very simple example where both the map and reduce function do not
do anything much interesting. But a programmer has the freedom to write something
alot more complex in these functions, as will be seen in the coming chapters.
2.4 Hadoop and HDFS
1
2.4.1 Hadoop Overview
Hadoop [2] is the Apache Software Foundation open source and Java-based imple-
mentation of the Map/Reduce framework. Hadoop was created by Doug Cutting, the
creator of Apache Lucene
2
,the widely used text library. Hadoop has its origins in
Apache Nutch
3
,an open source web search engine, itself a part of the Lucene project.
Nutch was an ambitious project started in 2002, and it soon ran into problems
with the creators realizing that the architecture they had developed would not scale to
the billions of web-pages on the Internet. But in 2003, a paper [10] was published
that described Google’s distributed filesystem - the Google File System (GFS). The
idea was adopted by the Nutch project and developed into what they called the Nutch
Distributed File System or NDFS.
In 2004, [9] was published, introducing the concept of Map/Reduce to the world
and the developers at Nutch implemented it for their purposes. Hadoop was born in
February 2006, when they decided to move NDFS and Nutch under a separate sub-
project under Lucene. In January 2008, Hadoop was made its own top level project
under Apache and NDFS was renamed to HDFS or Hadoop Distributed File System.
1
Thissection borrows heavily from [18]
2
http://lucene.apache.org/java/docs/index.html
3
http://nutch.apache.org/
Pdf to tiff file - Library application class:C# PDF Convert to Tiff SDK: Convert PDF to tiff images in C#.net, ASP.NET MVC, Ajax, WinForms, WPF
Online C# Tutorial for How to Convert PDF File to Tiff Image File
www.rasteredge.com
Pdf to tiff file - Library application class:VB.NET PDF Convert to Tiff SDK: Convert PDF to tiff images in vb.net, ASP.NET MVC, Ajax, WinForms, WPF
Free VB.NET Guide to Render and Convert PDF Document to TIFF
www.rasteredge.com
Chapter 2. Map/Reduce and Hadoop
13
Hadoop provides the tools for processing vast amounts of data using the Map/Re-
duce framework and, additionally, implements the Hadoop Distributed File System
(HDFS). It can be used to process vast amounts of data in-parallel on large clusters
in a reliable and fault-tolerant fashion. Consequently, it renders the advantages of the
Map/Reduce available to the users.
2.4.2 Hadoop Distributed File System or HDFS
“HDFS is a filesystem designed for storing very large files with streaming data access
patterns, running on clusters on commodity hardware.” [18].
HDFS was designed keeping in mind the ideas behind Map/Reduce and Hadoop.
What this implies is that it is capable of handling datasets of much bigger size than
conventional file systems (even petabytes). These datasets are divided into blocks and
stored across a cluster of machines which run the Map/Reduce or Hadoop jobs. This
helps the Hadoop framework to partition the work in such a way that data access is
local as much as possible.
Avery important feature of the HDFS is its “streaming access”. HDFS works on
theidea that the most efficient data processing pattern is awrite-once, read-many-times
pattern. Once the data is generated and loaded on to the HDFS, it assumes that each
analysis will involvea large proportion, if not all, of the dataset. So thetime to read the
whole dataset ismore important than the latency in reading the first record. Thishasits
advantages and disadvantages. One on hand, it can read bigger chunks of contiguous
data locations very fast, but on the other hand, random seek turns out to be a so slow
that it is highly advisable to avoid it. Hence, applications for which low-latency access
to data is critical, will not perform well with HDFS.
The feature affected the design of a few of the algorithms discussed in chapter 3.
For instance in section 3.2.1, the reduce function had to buffer data in memory in
order to allow random access. This will be explained in detail later.
2.4.3 Hadoop Cluster
AHadoop cluster consists of the following main components, all of which are imple-
mented as JVM daemons -
 JobTracker
Master node controlling the distribution of a Hadoop (Map/Reduce) Job across
Library application class:Online Convert PDF file to Tiff. Best free online PDF Tif
Using this .NET PDF to TIFF conversion control, C# developers can render and convert PDF document to TIFF image file with no loss in original file quality.
www.rasteredge.com
Library application class:Online Convert PDF file to Word. Best free online PDF Conversion
Download Free Trial. Convert a Tiff/Tif File to PDF. Then just wait until the conversion from Tiff/Tif to PDF is complete and download the file.
www.rasteredge.com
Chapter 2. Map/Reduce and Hadoop
14
free nodes on the cluster. It is responsible for scheduling the jobs on the vari-
ous TaskTracker nodes. In case of a node-failure, the JobTracker starts the work
scheduled on the failed node on another free node. The simplicity of Map/Re-
duce tasks ensures that such restarts can be achieved easily.
 NameNode
Node controlling the HDFS. It is responsible for serving any component that
needs access to files on the HDFS. It is also responsible for ensuring fault-
tolerance on HDFS. Usually, fault-tolerance is achieved by replicating the files
over 3 different nodes with one of the nodes being an off-rack node.
 TaskTracker
Node actually running the Hadoop Job. It requests work from the JobTracker
and reports back on updates to the work allocated to it. The TaskTracker dae-
mon does not run the job on its own, but forks a separate daemon for each task
instance. This ensure that if the user code is malicious it does not bring down
the TaskTracker
 DataNode
This node is part of the HDFS and holds the files that are put on the HDFS.
Usually these nodes also work as TaskTrackers. The JobTracker tries to allocate
work to nodes such files accesses are local, as much as possible.
2.4.4 Hadoop Job
Figure 2.2 shows Map/Reduce workflow in a user job submitted to Hadoop.
To run a Map/Reduce or Hadoop job on a Hadoop cluster, the client program must
create a JobConf configuration file. This configuration file -
 Identifies classes implementing Mapper and Reducer interfaces.
– JobConf.setMapperClass(), setReducerClass()
 Specifies inputs, outputs
– FileInputFormat.addInputPath(conf)
– FileOutputFormat.setOutputPath(conf)
Library application class:C# Create PDF from Tiff Library to convert tif images to PDF in C#
TIFFDocument doc = new TIFFDocument(inputFilePath); // Convert loaded TIFF file to PDF document. doc.ConvertToDocument(DocumentType.PDF, outputFilePath);
www.rasteredge.com
Library application class:Online Convert Excel to PDF file. Best free online export xlsx
Download Free Trial. Convert a Excel File to PDF. Your file will then be instantly converted to PDF and ready to download. The perfect conversion tool.
www.rasteredge.com
Chapter 2. Map/Reduce and Hadoop
15
Figure 2.2: Hadoop Cluster [18]
 Optionally, other options too:
– JobConf.setNumReduceTasks()
– JobConf.setOutputFormat()
TheJobTracker inserts the program (supplied in theform ofa .jar file)and the JobConf
file in a shared location. TaskTrackers running on slave nodes periodically query the
JobTracker for work and retrievejob-specificjar and configuration files. As mentioned
earlier, they then launch tasks in separate instances of Java Virtual Machine.
2.4.5 Map and Reduce Functions
The Map and Reduce classes in Hadoop extend MapReduceBase class and the map
and reduce functions have the signature as shown in figure 2.3.
Hadoop has its own serialization format. Central to this serialization format is the
Writable interface, which is a part of the signatures shown in figure 2.3. Writable-
Comparable is a sub-interface of Writable that requires the implementation of a Com-
parator function. OutputCollector is agenericclass used purely foremitting key/value
pairs. Reporter is for updating counters and statuses.
Library application class:VB.NET PDF File Compress Library: Compress reduce PDF size in vb.
Also able to uncompress PDF file in VB.NET programs. Offer flexible and royalty-free developing library license for VB.NET programmers to compress PDF file.
www.rasteredge.com
Library application class:C# PDF File Split Library: Split, seperate PDF into multiple files
Application. Best and professional adobe PDF file splitting SDK for Visual Studio .NET. outputOps); Divide PDF File into Two Using C#.
www.rasteredge.com
Chapter 2. Map/Reduce and Hadoop
16
map(WritableComparable key,
Writable value,
OutputCollector
output, Reporter reporter)
(a) map function
reduce(WritableComparable
key,
Iterator values,
OutputCollector
output, Reporter reporter)
(b) reduce function
Figure 2.3: Signatures of
map
and
reduce
functions in Hadoop
2.4.6 Partitioning and Grouping
The Hadoop framework takes the output from the Mapper and does the following -
1. Partitions the output
2. Sorts the individual partitions
3. Sends relevant partitions to Reducers
4. Merges the partitions received from different Mappers
5. Groups the tuples in the partition based on key and calls the reduce function
Figure 2.4 shows the steps just described in the context of the entire Hadoop
(Map/Reduce) job -
Hadoop lets the programmer control the partitioning and grouping of tuples, al-
though it does providewith adefault implementation in the absence ofone provided by
the programmer. This would be required for some of the Reduce-Side Join algorithm
specified in section 3.2.1 and Reduce-Side One-Shot Join and Reduce-Side Cascade
Join discussed in section 3.3 A ’Partitioner’ class can be defined by implementing the
Partitioner interface of the org.apache.hadoop.mapred package. And this class needs
to be specified as part of theJob Configuration by using JobConf.setPartitionerClass()
function. See Appendix B for how this is done.
Library application class:VB.NET PDF File Merge Library: Merge, append PDF files in vb.net
Combine multiple specified PDF pages in into single one file. VB.NET Components to combine various scanned images to PDF, such as tiff, jpg, png, gif, bmp
www.rasteredge.com
Library application class:VB.NET PDF File Split Library: Split, seperate PDF into multiple
Professional VB.NET PDF file splitting SDK for Visual Studio and .NET framework 2.0. Split PDF file into two or multiple files in ASP.NET webpage online.
www.rasteredge.com
Chapter 2. Map/Reduce and Hadoop
17
Figure 2.4: Shuffle and Sort in Map/Reduce [18]
To overridethe grouping donein the Reduceroneneedsto writea class that extends
org.apache.hadoop.io.WritableComparator class. This class must have functions to
compare key values, but the behaviour of the comparison is completely dependent on
the programmer. To make sure the Reducer uses this class for comparison, it needs to
be
specified
as
part
of
the
Job
Configuration
by
using
JobConf.setOutputValueGroupingComparator() function. The class FirstComparator
defined inside the TextPair class in Appendix A is an example of such a class.
Partitioning and Grouping functions are used as part of the ’Reduce-Side Join’,
which is described in chapter 3.
2.4.7 Hadoop Counters
When a client program initiates a Hadoop job, the Hadoop framework keeps track of
alot of metrics and counters as part of its logs. These are usually system metrics like
time taken, amount of data read, etc. Apart from these, Hadoop also allows users to
specify their own user-defined counters which are then incremented as desired in the
mapper and thereducer. Formore details on thedefault countersprovided by Hadoop,
see [18]. Only user-defined counters are described here, which are used in one of the
join algorithms described later in chapter 3. There are two ways of defining a counter-
 Java enum
Users can define any number of Java enums with any number of fields in them.
For ex. -
Chapter 2. Map/Reduce and Hadoop
18
enum NumTypef
EVEN,
ODD
g
These can be incremented in the mapper or the reducer as -
Reporter.incrementCounter(NumType.EVEN, 1)
 Dynamic Counters
Apart from enums, users can also create dynamic counters. The user will have
to make sure he/she uses the same name every where. An example is -
Reporter.incrementCouner("NumType", "Even", 1)
2.4.8 Hadoop Data Types
Hadoop uses its own serialization format called Writables. It is fast and compact. For
ease of use, Hadoop comes with built-in wrappers for most of Java primitives. The
only one that is used in this project Text, which is a wrapper around the Jave String
object. See [18] for more details.
2.4.9 Compression in Hadoop
Compression can be easily implemented in Hadoop. It has built-in libraries or codecs
that implement most of the well-known compression algorithms. Compression will
be used in section 3.3.3 for optimizing one of the multi-way join algorithms. Shown
below aretwo of themost famous ones used - Theinteresting thing to noteis that some
Compression Format
Hadoop CompressionCodec
gzip
org.apache.hadoop.io.compress.GzipCodec
bzip2
org.apache.hadoop.io.compress.BZip2Codec
Table 2.1: Hadoop compression codecs
of the codecs allow you to split and some dont. For instance, its not possible to read
Chapter 2. Map/Reduce and Hadoop
19
agzip file in the middle but it is possible to do so for a bzip2 file. Hence depend-
ing on one’s needs, they must use the relevant codec. For our purpose, we used the
bzip2 codec so that Hadoop can efficiently split the compressed input files. To com-
press the output of a MapReduce job, the mapred.output.compress property is set
to true and the mapred.output.compression.codec property is set to the classname
of the required codec (in our case org.apache.hadoop.io.compress.GzipCodec)
in the Job Configuration. If the inputs are compressed, Hadoop automatically infers
the compression codec using the file’s name. Hence it is quite straightforward to im-
plement compression in Hadoop.
Chapter 3
Join Algorithms
Most of the existing work has concentrated on two-way joins leaving the reader to ex-
tend theideafor multi-way joins. Onesuch paper is[6]. TheBroadcast Join algorithm
mentioned in section 3.2.3 is a variation of an idea mentioned in it. This project deals
with both two-way and multi-way joins. Before moving any further, let us define what
these are specifically in context of this project-
 Two-way Joins - Given two dataset P and Q, a two-way join is defined as a
combination of tuples p 2 P and q 2 Q, such that p:a = q:b. a and b are values
from columns in P and Q respectively on which the join is to be done. Please
note that this is specifically an ‘equi-join’ in database terminology. This can be
represented as-
P./
a=b
Q
 Multi-way Joins - Given n datasets P
1
;P
2
;:::;P
n
,a multi-way join is defined as
acombination of tuples p
1
2P
1
;p
2
2P
2
;:::;p
n
2P
n
,such that p
1
:a
1
=p
2
:a
2
=
::: = p
n
:a
n
. a
1
;a
2
;:::;a
n
are values from columns in P
1
;P
2
;:::;P
n
respectively
on which the join is to be done. Notice once again that this is specifically an
‘equi-join’. This can be represented as-
P
1
./
a
1
=a
2
P
2
./
a
2
=a
3
::: ./
a
n 1
=a
n
P
n
Thealgorithms thusdescribed in thischapter havebeen divided into two categories-
1. Two-Way Joins - Joins involving only two tables
2. Multi-Way Joins - Joins involving more than two tables
20
Chapter 3. Join Algorithms
21
3.1 Join Algorithms in standard database context
Before jumping on to join algorithms using Map/Reduce (or Hadoop) it might be a
good idea to review the currently exiting join algorithms in the standard database con-
text. There are three of them that are very popular. These are -
1. Nested Loops Join
2. Sort-Merge Join
3. Hash Join
Nested Loops Join
We described the Nested Loops Join earlier in chapter 1. It is one of the oldest join
algorithms and is one of the simplest. It is capable of joining two datasets based on
any join condition. It does not suffer from the drawback of the next two algorithms
that can only perform equi-joins. Unfortunately, all the algorithms using Map/Reduce
that are discussed in this chapter suffer from this very drawback. They all can perform
only equi-joins.
Sort-Merge Join
Given two datasets P and Q, the Sort-Merge Join algorithm sorts both datasets on
the join attribute and then looks for qualifying tuples p 2 P and q 2 Q by essentially
merging the two datasets. [17]. The sorting step groups all tuples with the same value
in the join column together and thus makes it easy to identify partitions or groups
of tuples with the same value in the join column. This partitioning is exploited by
comparing the P tuples in a partition with only the Q tuples in the same partition
(rather than with all tuples in Q), thereby avoiding enumeration orthe cross-product of
Pand Q. This partition-based approach works only for equality join conditions.
Documents you may be interested
Documents you may be interested