iMapReduce - Large Scale and Big Data: Processing and Management - page 117

the map task needs only the state data from its corresponding reduce task, a map
task can start its execution as soon as its input state data arrives, without waiting
for the other reduce tasks' completion. iMapReduce schedules the execution of map
tasks asynchronously. By enabling the asynchronous execution, the synchronization
barriers between MapReduce jobs are eliminated, which can further speed up the
iterative process.
To implement the asynchronous execution, iMapReduce builds a persistent socket
connection from a reduce task to its paired map task. In a naive implementation, as
soon as the reduce task produces a state KV, it is immediately sent back to its paired
map task. Upon receipt of the data from the reduce task, the map task performs the
map operation on the data immediately. However, the eager triggering in the native
implementation will result in frequent context switches that impact performance.
Thus, a buffer is designed in each reduce task. As the buffer size grows larger than a
threshold, the buffered state KVs are sent to the paired map task.
3.3.3 i teration t ermination
Iterative algorithm typically stops when a termination condition is met. Users termi-
nate an iterative process in two ways: (1) fixed number of iterations: iterative algo-
rithm stops after a fixed number of iterations; (2) bounding the distance between two
consecutive iterations: iterative algorithm stops when the difference between two
consecutive iterations is less than a threshold.
iMapReduce performs termination check after each iteration. To terminate the
iterative computation by a fixed number of iterations, it is straightforward to record
the iteration number in each task and terminate it when the number exceeds a thresh-
old. To bound the distance between two consecutive iterations, the reduce tasks
save the output from two consecutive iterations and calculate the distance. Users
should specify the distance measurement method, for example, Euclidean distance,
Manhattan distance, etc. To obtain a global distance value from all reduce tasks, the
local distance values from the reduce tasks are merged by the master. The master
then checks the termination condition to decide whether to terminate or not. If the
termination condition is satisfied, the master will notify all the persistent map/reduce
tasks to terminate their executions.
3.3.4 F fault t oleranCe
Fault tolerance is important in a server cluster environment. MapReduce splits a
job into multiple fine-grained tasks. Whenever a task failure is detected, the failed
task is rescheduled. Moreover, MapReduce provides speculative execution [19] that
is designed on clusters of heterogeneous hardware. Speculative execution starts
another concurrent task to process the same data block if extra resources are avail-
able, where the first completed task's output is preferred.
iMapReduce relies on checkpointing mechanism for fault tolerance. For each map
task, the structure data block has several replicas on DFS. For each reduce task, the
output state data as the checkpoint are dumped to DFS every few iterations. In case
there is a failure, iMapReduce recovers from the most recent checkpoint, instead of