Abstract
The communication overhead from the big data sets' transmission affects the performance of Hadoop greatly. In consideration of data locality, Hadoop schedules tasks to the nodes near the data locations preferentially to decrease data transmission overhead, which works well in homogeneous and dedicated MapReduce environments. However, due to practical considerations about cost and resource utilization, it is common to maintain heterogeneous clusters or share resources by multiple users. Unfortunately, it's difficult to take advantage of data locality in these heterogeneous or shared environments. To improve the performance of MapReduce in heterogeneous or shared environments, a data prefetching mechanism is proposed in this paper, which can fetch the data to corresponding compute nodes in advance. It is proved that the proposal of this paper reduces data transmission overhead effectively with theoretical analysis. The mechanism is implemented and evaluated on Hadoop-1.0.4. Experiment results on real applications show that the data prefetching mechanism can reduce data transmission time by up to 94%.
What Problem Does This Paper Address?
The "holy grail" of big data frameworks like MapReduce (and its open-source implementation, Hadoop) is data locality: the idea that you should move the computation to the data, rather than moving the data to the computation. In a perfect, "homogeneous" world where every server is identical and dedicated to one task, Hadoop is great at scheduling tasks on the exact nodes where their data lives.
However, real-world data centers are rarely perfect. They are often heterogeneous (a mix of old and new hardware with different speeds) or shared (multiple users running different jobs at once). In these environments, the node holding the data might be too busy to run the task, forcing Hadoop to run the task elsewhere. When this happens, the task has to fetch data over the network. Standard Hadoop does this serially: it fetches a slice of data, processes it, and only then asks for the next slice. This creates a "stop-and-go" bottleneck where the CPU sits idle while the network works, and vice versa.
Methods
The authors propose a Data Prefetching Mechanism designed to turn that serial "stop-and-go" process into a parallel pipeline. The core of their approach is a classic Producer-Consumer model:
- The Prefetcher (Producer): A dedicated background thread is created on the compute node. Its only job is to look ahead and fetch the next required data slices from the remote node into a local buffer.
- The Map Task (Consumer): The actual computation task pulls data from this local buffer instead of waiting for the network.
- The Prefetching Buffer: Interestingly, the authors prove that you don't need a massive amount of RAM for this. Just two buffer units are enough to keep the pipeline full, meaning the memory overhead is negligible.
By overlapping the data transmission with the data processing in the time dimension, the network latency is effectively "hidden" behind the computation time.
Datasets and Experimental Setup
The researchers evaluated their implementation (built on Hadoop-1.0.4) using two primary applications:
- WordCount: The standard "Hello World" of MapReduce, used to count word frequencies in large text files.
- CCV (Class-Center Vectors) Evaluator: A more complex, real-world application used in machine learning classification algorithms.
They tested these on a virtualized cluster with varying node configurations (1-2 processors, 256MB-2GB RAM) and data sizes ranging from 1GB to 8GB to simulate different levels of cluster "busyness" and network congestion.
Key Insights and Ideas
- The Bottleneck Shift: The effectiveness of prefetching depends on the ratio between processing speed ($V_{map}$) and transmission speed ($V_{tran}$). If the network is much slower than the CPU, prefetching provides the most dramatic gains because it ensures the CPU never has to wait for the "slow" network.
- Split Size Matters: The paper finds that larger "input splits" (the chunks of data a task processes) lead to better performance gains. With a 64MB split size, they saw a 25% improvement in map task performance compared to smaller splits.
- Shared Environments Benefit Evenly: One of the most promising findings is that the performance boost remains consistent regardless of how many nodes are available in a shared cluster. Whether you are limited to 2 nodes or 8, the prefetching mechanism scales its benefits proportionally.
Key Results
The implementation of the prefetching mechanism yielded significant performance improvements:
- Transmission Time Reduction: In scenarios with poor network connections, the prefetching mechanism reduced the time spent waiting for data by up to 94%.
- Overall Job Speedup: For complete MapReduce jobs, the authors recorded an average execution time reduction of 15% in heterogeneous environments.
- Efficiency: Because the system uses a small, two-unit buffer, it achieves these speedups with almost zero additional memory cost to the server.
Limitations and Future Work
While the results are impressive, the paper focuses almost exclusively on the Map phase of the MapReduce pipeline. The authors acknowledge that the Reduce phase and the "Shuffle" (where data is moved between Map and Reduce tasks) also suffer from network overhead and are prime candidates for similar prefetching logic.
Additionally, the current system is reactive—it starts prefetching once a task is assigned. The authors suggest that predictive scheduling (guessing which node will run a task before it is even assigned) could allow for even earlier data movement, potentially eliminating transmission overhead entirely.
Summary updated