TL;DR
As big data grows and evolves, existing mining results quickly become stale. This paper introduces i²MapReduce, a novel extension to Hadoop MapReduce that enables incremental processing for both one-step and iterative computations. By processing only changed data at a fine-grained level and intelligently managing intermediate states, i²MapReduce significantly speeds up the refreshing of big data mining results compared to re-computation.
What Problem Does This Paper Address?
The core problem this paper tackles is the staleness of big data mining results due to the continuous arrival of new data and updates. Traditional MapReduce frameworks require re-computing everything from scratch, which is computationally expensive and time-consuming for large, evolving datasets. While incremental processing offers a solution by reusing previous computation states, existing approaches either require entirely new programming models (like Percolator, CBP, Naiad) or have limitations in their granularity and support for iterative algorithms (like Incoop). This paper aims to bridge this gap by providing an incremental processing extension that works within the familiar MapReduce paradigm, supporting both simple and complex iterative computations efficiently.
Methods
i²MapReduce introduces several key innovations:
- Fine-grain Incremental Processing (MRBG-Store): Instead of re-computing entire Map or Reduce tasks, i²MapReduce operates at the key-value pair level. It models data flow and dependencies using a bipartite graph (MRBGraph) and preserves fine-grained intermediate states in a specialized store (MRBG-Store). This allows for precise re-computation only on affected data.
- General-Purpose Iterative Computation: The framework enhances the MapReduce API to support general iterative algorithms. This includes allowing users to explicitly separate loop-invariant structure data from loop-variant state data and providing a
ProjectAPI to define dependencies between them. This is a modest modification compared to adopting entirely new programming models. - Incremental Processing for Iterative Computation: This is a significant challenge addressed by i²MapReduce. It reuses converged states from previous iterations and employs a change propagation control mechanism to manage how updates spread through iterative computations. The MRBG-Store is also optimized for the access patterns of iterative processing.
- MRBG-Store Optimizations: The MRBG-Store uses techniques like indexed access, dynamic read windows, and multi-windowing to efficiently retrieve preserved states, minimizing I/O overhead. It also supports incremental storage by appending changes and reconstructing files offline.
- Change Propagation Control (CPC): To mitigate the issue of changes propagating widely in iterative algorithms, CPC filters out kv-pairs with changes below a certain threshold, significantly reducing redundant computations.
Datasets
The paper evaluates i²MapReduce using the following datasets:
- Twitter: Used for the APriori algorithm (one-step mining).
- ClueWeb: A large web graph dataset used for PageRank.
- ClueWeb2: A weighted version of ClueWeb for Single Source Shortest Path (SSSP).
- BigCross: A semi-synthetic dataset for K-means clustering.
- WikiTalk: A dataset used for GIM-V (matrix-vector multiplication).
The paper also mentions the use of a "semi-synthetic data set generated from a base real-world data set" for ClueWeb, and a "high-volume and high-dimensional real data set" for BigCross.
Key Insights and Ideas
- Fine-grained is Crucial: The paper strongly advocates for key-value pair level incremental processing over task-level. This is because even small data changes can affect only a tiny fraction of key-value pairs within a task, making task-level re-computation wasteful.
- Iterative Incremental is Hard, But Solvable: Handling incremental updates in iterative algorithms is significantly more complex due to cascading effects. i²MapReduce's approach of reusing converged states and controlling change propagation is key to making this practical.
- Structure vs. State Separation is Key for Iterative: Explicitly separating immutable structure data from evolving state data, and defining their dependencies, is fundamental to building efficient iterative processing frameworks.
- Change Propagation Control is a Performance Lever: The CPC mechanism is shown to be critical for performance in iterative algorithms, allowing for significant speedups by filtering out minor changes, albeit with a potential trade-off in accuracy that can be managed.
- MRBG-Store Design Matters: The efficiency of preserving and retrieving fine-grained states is paramount. The MRBG-Store's design, with its focus on efficient I/O and handling of multiple iterations, is a core component of i²MapReduce's success.
Key Results
- One-Step Processing: For the APriori algorithm, i²MapReduce achieved a 12x speedup over plain MapReduce re-computation.
- Iterative Processing (10% data change):
- PageRank: i²MapReduce achieved an 8-fold speedup compared to plain MapReduce re-computation, and significant improvements over iterative MapReduce.
- SSSP: Similar performance gains to PageRank were observed.
- GIM-V: i²MapReduce achieved a 10.3x speedup over plain MapReduce and a 1.4x speedup over HaLoop.
- MRBG-Store Performance: Optimizations like multi-dynamic-windowing in the MRBG-Store led to a 1.6x speedup over a basic index-only approach.
- Fault Tolerance: The system demonstrated efficient fault recovery, with failed tasks recovering within 12 seconds without significantly impacting overall performance.
Limitations and Future Work
- Load Balancing: The paper acknowledges that integrating online skew migration for load balancing, especially for the MRBGraph file, is a challenge and is left for future work.
- Accuracy Trade-off with CPC: While CPC significantly improves performance, it can lead to minor inaccuracies if the filter threshold is too high. The authors note that users can disable CPC for applications requiring strict accuracy.
- Comparison with Incoop: The paper mentions that Incoop, a task-level incremental system, was not publicly available for direct comparison. However, they provide anecdotal evidence suggesting that without careful data partitioning, task-level incremental processing might not be effective.
- Future Work: The authors suggest exploring similar ideas for incremental processing in Pregel-like systems and further optimizing load balancing. They also mention that the project homepage provides code examples for various algorithms.
Summary updated