Large-scale incremental processing for mapreduce

Abstract

An important property of today`s big data processing is that the same computation is often repeated on datasets evolving over time, such as web and social network data. This style of repeated computation is also used for many iterative algorithms. While repeating full computation of the entire datasets is feasible with distributed computing frameworks such as Hadoop, it is obviously inefficient and wastes resources.In this dissertation, we present HadUP (Hadoop with Update Processing), a modified Hadoop architecture tailored to large-scale incremental processing for conventional MapReduce algorithms. Several approaches have been proposed to achieve a similar goal using task-level memoization. They keep the previous results of tasks permanently, and reuse them when the same computation on the same task input is needed again. However, task-level memoization detects the change of datasets at a coarse-grained level, which often makes such approaches ineffective. Our analysis reveals that task-level memoization can be effective only if each task processes a few KB of input data. In contrast, HadUP detects and computes the change of datasets at a fine-grained level using deduplication-based snapshot differential algorithm (D-SD) and update propagation.Update propagation is a key primitive for efficient incremental processing of HadUP. Many applications for today`s big data processing consist of data parallel operations, where an operation transforms one or more input datasets into one output dataset. For each operation, the same computation is concurrently applied to a single input record or a group of input records. The independence between these executions allows us to compute the records to be inserted into or deleted from the output dataset, if those records inserted into or deleted from the input datasets are explicitly given. In this way, update propagation computes the updated result without full recomputation. Our evaluation shows that HadUP provides high pe...