SCALLA: A Platform for Scalable One-Pass Analytics Using MapReduce

Boduo Li, Edward Mazur, Yanlei Diao, Andrew McGregor, Prashant J. ShenoyACM Trans. Database Syst 2012 · DOI

TL;DR

This paper introduces SCALLA, a novel platform designed to bring the power of MapReduce to incremental, one-pass analytics. By replacing the traditional sort-merge bottleneck with efficient hash-based techniques, SCALLA significantly speeds up data processing, reduces data spills, and enables continuous results, making it ideal for real-time data analysis.

What Problem Does This Paper Address?

Modern applications increasingly demand real-time analytics on continuously flowing data. While MapReduce is a popular framework for processing large datasets in batches, its traditional implementation, particularly the sort-merge mechanism, is ill-suited for incremental, one-pass analytics. This is because it requires the entire dataset to be loaded before processing, leading to high latency and preventing the delivery of early, continuous results. The authors identify the sort-merge implementation as a fundamental barrier, causing CPU and I/O bottlenecks and blocking progress, especially when dealing with large intermediate datasets.

Methods

The core of SCALLA lies in its innovative approach to replacing the sort-merge paradigm with hash-based techniques. The platform introduces three key hash-based mechanisms:

  • MR-hash: This technique replaces the sort-merge step with a purely hash-based framework. It partitions map output using hash functions and employs a two-phase hash processing in reducers, allowing for early answers from buffered data and avoiding the CPU cost of sorting.
  • INC-hash (Incremental Hash): Designed for reduce functions that support incremental processing (like sum or count), this method uses initialize, combine, and finalize functions. It builds an in-memory hash table to map keys to computation states, allowing for incremental updates and early results as data arrives. This significantly reduces intermediate data and I/O costs.
  • DINC-hash (Dynamic Incremental Hash): This advanced technique addresses workloads with large key-state spaces that exceed available memory. It dynamically identifies "hot" (frequent) keys and keeps their states in memory for incremental processing, while less frequent keys are handled through disk spilling. This approach prioritizes important keys, leading to substantial I/O reduction and enabling early, approximate answers.

The platform also includes optimizations for memory management (using byte arrays) and a flexible bucket file manager for both HDDs and SSDs.

Datasets

The paper evaluates SCALLA using two real-world datasets:

  • WorldCup click stream: A 236GB dataset used for workloads like sessionization, user click counting, and frequent user identification.
  • GOV2 dataset: A 156GB dataset used for trigram counting.

The authors also reference their previous benchmarking study using the World Cup 1998 website click log, which was replicated to larger sizes. No new benchmarks were introduced, but the evaluation focuses on scenarios relevant to incremental one-pass analytics.

Key Insights and Ideas

  • Sort-merge is the Achilles' heel: The paper strongly argues that the sort-merge implementation, while standard in MapReduce, is the primary bottleneck for incremental, one-pass analytics, causing significant I/O and CPU overheads.
  • Hash is the key to speed: Replacing sort-merge with hash-based techniques is crucial for achieving fast, in-memory processing and enabling incremental computation.
  • Incremental processing pays off: Even for workloads that don't strictly require real-time output, incremental processing (as enabled by INC-hash) can lead to reduced intermediate data, smaller spills, and faster overall job completion.
  • Prioritizing hot keys is essential for large state spaces: For workloads where memory is a constraint, dynamically identifying and prioritizing frequent keys (DINC-hash) is critical for minimizing I/O and delivering timely results.
  • Early answers are valuable: The ability to provide partial or approximate results as data streams in is a significant advantage for many real-time analytics applications.

Key Results

SCALLA demonstrated significant improvements over optimized Hadoop (1-pass SM) and other approaches:

  • Sessionization (0.5KB state): INC-hash reduced running time from 4424s (1-pass SM) to 2258s and reduced reduce spills from 250GB to 51GB.
  • Sessionization (large state, DINC-hash): DINC-hash achieved a dramatic reduction in reduce spills from 203GB (INC-hash with 2KB state) to just 0.1GB, with a running time of 2067s compared to 3271s for INC-hash. This represents up to a 3-orders-of-magnitude reduction in internal data spills compared to original Hadoop (370GB).
  • User Click Counting: INC-hash achieved a running time of 1113s compared to 1430s for 1-pass SM, with reduce spills reduced from 1.1GB to 0GB.
  • Frequent User Identification: Similar improvements were seen, with INC-hash reducing reduce spills to 0GB.
  • Progress: INC-hash and DINC-hash significantly improved reduce progress, often keeping pace with map progress, enabling continuous results.

Limitations and Future Work

  • Limitations:
    • The paper notes that for INC-hash, if the memory is less than the total distinct key-state pairs (A), I/O is still incurred.
  • For DINC-hash, if the data is not skewed, the benefits of prioritizing hot keys might be less pronounced.
  • The performance of DINC-hash can be affected if a key's state is evicted and then re-enters memory, resetting its counter.
  • Future Work:
    • Extend the platform to support a wider range of incremental computation tasks with minimized I/O.
  • Incorporate online aggregation with early approximate answers.
  • Support stream query processing with window operations.
  • Further explore optimizing Hadoop parameters using their analytical model.

Summary updated

BibTeX
@article{li2012scalla,
  author = {Boduo Li and Edward Mazur and Yanlei Diao and Andrew McGregor and Prashant J. Shenoy},
  title = {{SCALLA: A Platform for Scalable One-Pass Analytics Using MapReduce}},
  journal = {ACM Trans. Database Syst.},
  year = {2012},
  doi = {10.1145/2389241.2389246},
}
Figure