MapReduce: Simplified Data Processing on Large Clusters
by Jeffrey Dean and Sanjay Ghemawat

Key theme: "Key it simple"
Major contributions of this work: a simple and powerful interface that enables automatic parallelization and distribution of large scale computations +
implementation of this interface that achieves high performance on large clusters of PCs.

Programming model: Map --> Intermediate <kay, value> pairs --> Reduce
See example pseudo code
Input keys are in from a diff domain than intermediate keys and output keys.
Intermediate keys and output keys are from the same domain.

Implementation:
Machines typically dual-processor x86 processor running Linux, 4-GB of memory per machine, hyper-threading, 160GB IDE disks,
1gigabit per second interconnect bandwidth (max). Thousands of such machines, failure is norm, replication used for fault -tolerance.

Users submit jobs to a scheduling system, each job has tasks, mapped by scheduler to set of available machines.
 Execution overview: Many copies of the MR program are started. M mappers, R reducers, Master; master picks and idle worker and assigns a map task or reduce task.
Map executes and intermediate values are buffered in memory. Partitioned into regions by partitioners.

Master now passes this partition info to Reducers/ reduce workers. and reducer uses RPC to read in intermediate data and does its work.
It iterates over the values and appended to a file in the reduce partition.

when all the mappers and reducers are done master wakes up the client. See Fig 1

Master maintains many data structures:
Tasks  State  Identity
map    idle, in-progress, completed  #3456
reduce  ...

Handling failures
User supplied Map and Reduce are deterministic
Locality
Backups and stragglers
Refinements:  user-specified partitioners , combiners, custom input (splits), custom outputs,
prototype on a single machine for debugging.

Experience:
MR first version in Feb 2003
Where is it used within Google:
-- large scale machine learning problems
-- clustering problems
-- Extracting data for popular queries
-- processing of satellite imagery data
-- language model processing for statistical machine translation
--large scale graph computation
Look at fig 4 and table 1 for interesting facts:
by 2007 about 10000 MR jobs
Sept 07: 403152 tera bytes map input data

Significant improvements:
Traditional indexer in C++ of 3800 lines of code dropped to 700 MR code.
Took few months to implement
can improve perf by adding machines

=============================================================================
Data-Intensive Text Processing
with MapReduce by Jimmy Lin and Chris Dyer

Ch. 1
scale-out and not scale-up
assume failures are common
move processing to data
hide system-level details from application developer
seamless scalability

===============================================================================

Ch.5 Map-Reduce Basics

Read the series of questions (issues ) about MR.
(this reads like midterm questions? ;)

map: (k1,v1) --> [(k2,v2)]
reduce: (k2,[v2])-->[(k3,v3)]
Implicit between map and reduce is the implicit "group by" operation of intermediate keys
Fig. 2.2 and 2.3
Hadoop does not have the GFS restriction that reducer's input key and output key type should be same.
A Map method is called for every key value.
On the other hand you can specify the number of reducers. The intermediate key space will be divided among the
# of reducers you specify.
Mapper querying a SQL database is bottleneck. Dont do this.
Identify Reducer function means the MR is a simple sort and groups the data and outputs them.

Combiners are an optimization in MR that allow for local aggregation before the shuffle and sort phase.
mini-reducers
fig.2-4

HDFS Architecture fig.2.5
HDFS Namenode:
Namespace management: metadata, dir structue, file - block mapping, location, access permissions
Coordinating file operations: data transfers between client and datanodes
Maintaining overall health of the file system: heartbeat, error block, rescheduling operations
Datanodes's computational requirements are much stringent than Namenode (Namenode is simply a manager)
Architecture of HDFS: fig 2.6
mapper and reducer can produce limited side-effect; see counters
preserve state across keys values and across iterations(!)