4003-440 Operating Systems I
Lecture Notes -- Map-Reduce Systems

• All examples and figures taken from:
  • T. White. Hadoop: The Definitive Guide, 2nd Edition. O'Reilly, 2011.

The Map-Reduce Paradigm

• Example: Determine the maximum temperature for each year from National Climatic Data Center weather data

• A large quantity of raw data
  • YYYY = Year
  • TTTTT = Temperature in units of 0.1 C; 9999 means missing
  • Q = Quality code

               YYYY                                                                    TTTTTQ
0029029070999991901010106004+64333+023450FM-12+000599999V0202701N015919999999N0000001N9-00781+99999102001ADDGF108991999999999999999999
0029029070999991901010113004+64333+023450FM-12+000599999V0202901N008219999999N0000001N9-00721+99999102001ADDGF104991999999999999999999
0029029070999991901010120004+64333+023450FM-12+000599999V0209991C000019999999N0000001N9-00941+99999102001ADDGF108991999999999999999999
0029029070999991901010206004+64333+023450FM-12+000599999V0201801N008219999999N0000001N9-00611+99999101831ADDGF108991999999999999999999
0029029070999991901010213004+64333+023450FM-12+000599999V0201801N009819999999N0000001N9-00561+99999101761ADDGF108991999999999999999999
0029029070999991901010220004+64333+023450FM-12+000599999V0201801N009819999999N0000001N9-00281+99999101751ADDGF108991999999999999999999
0029029070999991901010306004+64333+023450FM-12+000599999V0202001N009819999999N0000001N9-00671+99999101701ADDGF106991999999999999999999
0029029070999991901010313004+64333+023450FM-12+000599999V0202301N011819999999N0000001N9-00331+99999101741ADDGF108991999999999999999999
0029029070999991901010320004+64333+023450FM-12+000599999V0202301N011819999999N0000001N9-00281+99999101741ADDGF108991999999999999999999
0029029070999991901010406004+64333+023450FM-12+000599999V0209991C000019999999N0000001N9-00331+99999102311ADDGF108991999999999999999999

Figure 2-1. MapReduce logical data flow
White, op. cit.

Figure 2-2. MapReduce data flow with a single reduce task
White, op. cit.

Figure 2-3. MapReduce data flow with multiple reduce tasks
White, op. cit.

Figure 2-4. MapReduce data flow with no reduce tasks
White, op. cit.

Hadoop

• Hadoop web site: http://hadoop.apache.org/

• A full-featured, enterprise-scale implementation of map-reduce in Java

• Who uses Hadoop? See http://wiki.apache.org/hadoop/PoweredBy

• Hadoop code for the maximum temperature example
  • Mapper: Class MaxTemperatureMapper
  • Reducer: Class MaxTemperatureReducer
  • Main program: Class MaxTemperature

• Demo

• Input files
  • 1901.txt
  • 1902.txt

• Command line

  $ hadoop MaxTemperature '*.txt' output
  

• Output directory

  $ ls -l output
  total 4
  -rwxrwxrwx 1 ark ark 18 2011-10-23 14:27 part-00000
  -rwxrwxrwx 1 ark ark  0 2011-10-23 14:27 _SUCCESS
  $ cat output/part-00000
  1901    317
  1902    244
  

• Combiner (optional)
  • Performs the reduction step on the output of each mapper before sending it to the reducer
  • Can reduce load on the reducer if there are many mappers

• Hadoop code for the maximum temperature example with a combiner
  • Mapper: Same as above
  • Reducer: Same as above
  • Main program: Class MaxTemperatureWithCombiner

• Demo

• Command line

  $ hadoop MaxTemperatureWithCombiner '*.txt' output2
  

• Output directory

  $ ls -l output2
  total 4
  -rwxrwxrwx 1 ark ark 18 2011-10-23 14:29 part-00000
  -rwxrwxrwx 1 ark ark  0 2011-10-23 14:29 _SUCCESS
  $ cat output2/part-00000
  1901    317
  1902    244
  

What Map-Reduce Is Good For

• If you have petabytes of data to analyze, just transferring the data off the disk is going to take forever

• Instead:
  • Split the data into N pieces, each on a different disk (node)
  • Run N mappers in parallel, each on a different node
  • Each mapper only has to read 1/N of the data from its own local disk

• Map-reduce versus traditional relational database

  		Map-reduce		RDBMS
  Data size		Petabytes		Gigabytes
  Disk access		Streaming (batch)		Random (interactive or batch)
  Structure		Unstructured or structured		Highly structured
  Updates		Write once, read many times		Write and read many times

• Map-reduce versus traditional parallel computing (OpenMP, MPI, etc.)

  		Map-reduce		Parallel computing
  Type of problems		Mainly data-intensive		Mainly CPU-intensive
  Thread/process coupling		Minimal		Minimal to maximal
  Programming patterns		Just one		Anything
  Programming effort		Small		Medium to large
  Fault tolerance		Automatic		Manual

Operating Systems I • 4003-440-02 • Winter Quarter 2012

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2013 Alan Kaminsky. All rights reserved. Last updated 13-Feb-2013. Please send comments to ark­@­cs.rit.edu.