CoHadoop: Flexible Data Placement and Its Exploitation in Hadoop

Mohamed Y. Eltabakh, Yuanyuan Tian, Fatma Özcan, Rainer Gemulla, Aljoscha Krettek, John McPherson

TL;DR

This paper introduces CoHadoop, a system that allows users to provide "hints" to Hadoop about which files are related, enabling Hadoop to store these related files on the same nodes. This "colocation" significantly speeds up data processing tasks like joins and sessionization by reducing data shuffling and network overhead, outperforming existing Hadoop solutions.

What Problem Does This Paper Address?

Large-scale data analytics platforms like Hadoop are crucial for businesses, but a key performance bottleneck has been Hadoop's inability to colocate related data. Hadoop's default data placement strategy in HDFS (Hadoop Distributed File System) focuses on load balancing by distributing data blocks randomly across nodes, without considering data relationships. This means that when applications need to process related files (e.g., joining log data with reference data, or performing sessionization on user activity logs), Hadoop often has to shuffle large amounts of data across the network, leading to significant performance degradation. Existing solutions either require users to fundamentally change their data format (like converting to a relational database) or involve complex, static pre-processing that doesn't handle incremental data well.

Methods

CoHadoop addresses this by extending HDFS with a lightweight mechanism for data colocation. The core idea is to introduce a new file-level property called a "locator." Users can assign the same locator to files that are related. CoHadoop then modifies HDFS's data placement policy to ensure that all replicas of files sharing the same locator are stored on the same set of data nodes. This is achieved by maintaining a "locator table" in the namenode, which maps locators to the files they represent. When a new file is created, CoHadoop checks its locator and attempts to place its replicas on nodes that already store other files with the same locator, prioritizing nodes with available space. This approach is "best-effort," meaning it prioritizes availability and fault tolerance over strict colocation if resources are scarce.

The paper also proposes efficient map-only algorithms for common log processing tasks like join and sessionization that specifically exploit this colocation. These algorithms avoid the expensive shuffling and reduce phases of traditional MapReduce jobs.

Datasets

The authors generated synthetic transactional data to simulate log-processing scenarios. They created two types of data: "Accounts" (reference data, 50 bytes each) and "Transactions" (log data, 500 bytes each). The transaction data was generated with a log-normal distribution for the number of transactions per account, with parameters (µ = lg 10 and σ = 1) representing typical distributions. They varied the size of the transaction datasets from 70GB to 1120GB, keeping the Accounts dataset constant at 10GB. They also tested with a "mildly-skewed" distribution by increasing σ to 2.

Key Insights and Ideas

  • Colocation is Key, Not Just Partitioning: The experiments clearly show that simply partitioning data (like in ParHadoop) offers significant speedups over raw Hadoop, but true performance gains come from colocating those partitions. This highlights that the physical co-location of related data on the same nodes is crucial for eliminating network overhead.
  • Flexibility is Paramount: CoHadoop's strength lies in its flexibility. It doesn't force users into specific data formats and allows for incremental ingestion of new data without re-organizing the entire dataset, a significant advantage for real-world log processing scenarios.
  • Best-Effort Colocation Balances Performance and Resilience: The "best-effort" approach to colocation is a smart trade-off. It maximizes colocation benefits when possible but gracefully falls back to HDFS's default behavior when resources are limited, ensuring that availability and fault tolerance are not compromised.
  • Map-Only Algorithms Unlock Colocation's Potential: The paper demonstrates that the benefits of colocation are fully realized when paired with specialized map-only algorithms that can process colocated data directly, bypassing the expensive shuffle and reduce phases.

Key Results

  • Significant Query Speedups: CoHadoop achieved substantial performance improvements for sessionization and join queries. For sessionization, it offered up to 93% of the speedup compared to raw Hadoop, and up to 60% faster than ParHadoop (partitioned but not colocated). For joins, it provided up to 60% speedup over ParHadoop.
  • Faster Data Loading: CoHadoop and ParHadoop had similar data loading times, both significantly faster than Hadoop++, which required more time for its static co-partitioning and indexing. CoHadoop also excelled at incremental data loading.
  • Minimal Impact on Fault Tolerance: CoHadoop maintained Hadoop's fault tolerance characteristics. While colocation slightly increased data variation, it did not negatively impact recovery time from node failures.
  • Slightly Increased Data Distribution Variation: CoHadoop showed a higher variation in data distribution across nodes compared to RawHadoop and ParHadoop, especially with more colocated files. However, this variation was generally manageable and did not significantly degrade query performance.
  • Outperforms Hadoop++: CoHadoop consistently outperformed Hadoop++ on join queries, offering 20-55% better performance and greater flexibility for incremental data ingestion.

Limitations and Future Work

  • Data Distribution Variation: The paper acknowledges that colocation can lead to increased data distribution variation, especially with a large number of colocated files. While they argue this variation is often manageable, it's a trade-off to consider.
  • Handling Highly Skewed Data: The current approach can handle mild skew, but highly skewed data distribution in partitions might require more sophisticated algorithms, which are orthogonal to colocation itself.
  • Future Work: The authors suggest that higher-level languages like Pig, Hive, and Jaql could automatically leverage CoHadoop's capabilities to optimize query processing based on observed workloads. They also mention that the HDFS API could be used to incorporate their data placement policy, reducing maintenance costs. Further research into more advanced data distribution strategies and handling of extreme skew is also implied.

Summary updated

BibTeX
@article{eltabakh2011cohadoop,
  author = {Mohamed Y. Eltabakh and Yuanyuan Tian and Fatma Özcan and Rainer Gemulla and Aljoscha Krettek and John McPherson},
  title = {{CoHadoop: Flexible Data Placement and Its Exploitation in Hadoop}},
  journal = {Proc. VLDB Endow.},
  year = {2011},
  url = {https://openreview.net/forum?id=E0XJeSKEx4},
}
Figure