A Data Replica Selection Algorithm Based on Cloud Platform

Shaomin Zhang, Qi Wang, Baoyi WangAdvances 2015 · DOI

Abstract

Aiming at the problem of choosing the least cost data resources from multiple datasets with identical content but different locations for smart grid tasks, a least cost selection algorithm based on locality (LCSL) is proposed. First, the problem of choosing data replicas is abstracted as a shortest-path issue from a source point to other vertices in a directed graph. Second, to optimize the join operation, related data is grouped within the same datanode during the Map stage, effectively avoiding the data-pulling overhead in the Reduce stage. Experimental results demonstrate that the LCSL algorithm significantly reduces data transmission time and overall task completion time, enhancing the real-time performance of smart grid processing tasks.

Introduction

Smart grids are massive data engines, generating approximately 430GB of information daily for a typical provincial power grid, totaling nearly 150TB annually. To ensure data reliability and availability, cloud platforms like Hadoop store multiple "replicas" (copies) of this data across various physical locations.

The primary challenge lies in selection efficiency. When a smart grid task requires data analysis—such as correlating weather patterns with power usage—it must determine which replica to access. Standard Hadoop strategies often rely on simple network "hops" (physical distance), which do not always correlate with the fastest transmission time. Furthermore, traditional MapReduce "Join" operations are notorious for "shuffling" massive amounts of data across the network during the Reduce stage, creating a significant bottleneck for real-time grid applications.

Methodology: The LCSL Algorithm

The researchers propose a two-pronged optimization strategy called LCSL (Least Cost of Selection based on Local data) to address these bottlenecks.

1. Dijkstra-Based Replica Selection

Instead of relying on physical distance, the LCSL algorithm treats the cloud network as a weighted directed graph. By applying Dijkstra’s Algorithm, the system identifies the "shortest path" from the task to the data, where the edge weights represent actual access costs, including latency and available bandwidth. This ensures the system consistently selects the most cost-effective data source.

The cloud network abstracted as a weighted directed graph for replica selection.

2. Map-Side Join Optimization

In a standard MapReduce workflow, data from different tables is joined during the "Reduce" phase, necessitating a massive data transfer (shuffle). The LCSL algorithm optimizes this by grouping related data on the same physical node and performing the join during the Map stage. This data locality ensures the system only processes relevant data and avoids pulling unnecessary information across the network, effectively eliminating the most time-consuming part of the MapReduce process for these specific tasks.

Experimental Evaluation

The algorithm was evaluated using CloudSim, a specialized cloud computing simulation environment. The simulation featured four data centers, each containing five frames. Data was distributed uniformly with three replicas per block (the Hadoop default). The researchers tested the system by increasing the number of datasets from one to eight to observe scaling performance.

Key Results and Insights

The experimental results from the CloudSim environment were significant, particularly when comparing LCSL to the Set Covering Problem (SCP) heuristic approach. While SCP is a common optimization method, it is computationally expensive and can be unstable for real-time tasks.

Comparison of task completion time (s) between LCSL and SCP algorithms across varying dataset sizes.
  • Speedup: The LCSL algorithm reduced total task completion time by approximately 27% compared to the SCP-based method.
  • Data Locality: The "data transmission ratio" (the proportion of time spent moving data versus processing it) was consistently lower for LCSL, proving the effectiveness of the Map-side join.
  • Scalability: As the number of datasets increased, the performance gap between LCSL and traditional methods widened, suggesting the algorithm is well-suited for the growing scale of smart grid data.

Conclusion

The LCSL algorithm provides a deterministic and efficient path to optimization in smart grid cloud environments. By prioritizing actual transmission costs over physical distance and leveraging data locality through Map-side joins, it significantly improves task real-time performance. Future work will involve validating LCSL on a physical production-grade power grid cluster and refining the algorithm to handle unstructured data types like monitoring audio and video.

Summary updated

Abstract

Aiming at the problem that how to choose the least cost data resources from multiple datasets which have the same contents but different locations for smart grid tasks, a least cost of selection algorithm based on locality is proposed. First, the problem of choosing data replicas is abstract as a shortest path issue that is from the source point to other vertices in directed graph. Second, in order to complete the join operation in Map stage, the related data is grouped in the same datanode, so as to avoid pulling data in Reduce stage. Experimental results show that the algorithm can effectively reduce the data transmission time, and then reduce the task completion time, improve the real-time performance of the smart grid processing tasks.
BibTeX
@inproceedings{zhang2015data,
  author = {Shaomin Zhang and Qi Wang and Baoyi Wang},
  title = {{A Data Replica Selection Algorithm Based on Cloud Platform}},
  booktitle = {Advances},
  year = {2015},
  doi = {10.2991/icmmita-15.2015.100},
}
Figure