On an Approximation Algorithm for HDFS Data Block Placement in Heterogeneous Hadoop Clusters

Hadoop stands out as one of the most widely employed systems for processing big data. Embedded within Hadoop as a foundational technological layer is the Hadoop Distributed File System (HDFS), providing fault tolerance and high throughput in data storage. This is achieved through mechanisms such as data partitioning, block replication, and cluster-wide distribution, which in turn facilitate parallel computing in the upper layers. Consequently, the strategy governing block placement emerges as a pivotal factor influencing the performance of Hadoop clusters. However, the default block distribution approach of HDFS overlooks the varying capacities of data nodes and their diverse data access patterns, rendering it unsuitable for heterogeneous Hadoop clusters. To address this challenge, we formulate a Block Distribution problem for heterogeneous clusters, prove it to be NP-complete, and design an approximation algorithm, Linear Programming-based Iterative Rounding (LPIR-BD), with a rigorous performance guarantee. Extensive experiments illustrate the notable performance superiority of LPIR-BD over several state-of-the-art algorithms, thus confirming the efficacy of our theoretical analysis.