HaLoop: Efficient Iterative Data Processing on Large Clusters
📜 Abstract
The growing demand for large-scale data mining and data analysis applications has led both industry and academia to design new types of highly scalable data-intensive computing platforms. MapReduce and Dryad are two popular platforms in which the dataflow takes the form of a directed acyclic graph of operators. These platforms lack built-in support for iterative programs, which arise naturally in many applications including data mining, web ranking, graph analysis, model fitting, and so on. This paper presents HaLoop, a modified version of the Hadoop MapReduce framework that is designed to serve these applications. HaLoop not only extends MapReduce with programming support for iterative applications, it also dramatically improves their efficiency by making the task scheduler loop-aware and by adding various caching mechanisms. We evaluated HaLoop on real queries and real datasets. Compared with Hadoop, on average, HaLoop reduces query runtimes by 1.85, and shuffles only 4% of the data between mappers and reducers.
✨ Summary
HaLoop extends Hadoop MapReduce with framework-level support for iterative computations. Its principal mechanisms are loop-aware scheduling, reuse and indexing of loop-invariant data, mapper and reducer caches, and distributed fixpoint or convergence checking. Experiments with PageRank, descendant queries, and k-means reported an average runtime reduction of 1.85× and reduced shuffle volume to 4% of Hadoop’s volume for the tested workloads.
The paper influenced subsequent work on iterative data-processing systems and query optimization. A later VLDB Journal article by the same authors explicitly identifies itself as an extended version of this paper and preserves its central focus on inter-iteration caching and loop-aware scheduling. (vldb.org) Differential Dataflow later cited HaLoop as an iterative dataflow system that executes chains of MapReduce jobs until a data-dependent stopping condition is met, while pursuing a more general model supporting incremental and nested iteration. (microsoft.com) The OptIQ project cited HaLoop as prior work on iterative MapReduce caching and scheduling, and extended the research direction toward automatic optimization of iterative queries through view materialization and incremental evaluation rather than programmer-specified caching. (vldb.org)