Reducing Insertion Time in LRC-based Cloud Storage Systems

Zhenyuan Liu, Zhen Huang, Dongsheng LiAdvances 2015 · DOI

Abstract

In traditional erasure codes, all the redundant data are created and uploaded to the different storage nodes by a unique source node. However, such a source node may have limited communication and computation capabilities, which constrain the storage process throughput. In-network redundancy generation can improve data insertion throughput through distributing the data insertion load among the source and storage nodes. But it's hard to schedule the generation process. Many works have proposed some heuristic scheduling algorithms to improve data insertion throughput. We propose a new method combined global and local optimization to schedule the process. Experimental results show that our method reduce insertion time up to 18% compared with the best heuristic scheduling algorithm.

1. Introduction

Modern cloud storage systems increasingly rely on Erasure Coding (EC) rather than simple replication to ensure data reliability with minimal storage overhead. In a standard EC setup, a single source node calculates all parity fragments and uploads them to various storage nodes. This centralized approach often results in a significant performance bottleneck, as the source node's CPU and upload bandwidth become saturated.

To mitigate this, "in-network redundancy generation" has been proposed. This technique allows storage nodes to participate in the encoding process by performing XOR operations on received fragments to generate new ones. However, the efficiency of this distributed process depends heavily on the scheduling of data transfers. While local heuristic algorithms like Random Flow (RndFlw) exist, they often lack a global perspective, leading to suboptimal performance.

2. Methodology: A Two-Layer Scheduling Strategy

We propose a hybrid scheduling framework that combines global planning with local execution to optimize the data insertion pipeline.

2.1 The Logical Layer (Global Optimization)

The first layer focuses on constructing an optimal "Transport Graph." This is modeled as a Directed Acyclic Graph (DAG) where nodes represent data fragments and edges represent transfers. We employ a greedy algorithm to minimize the "max distance" from the source node to the final fragment, effectively treating time-steps as graph distance. By shortening the longest path in this logical blueprint, we reduce the theoretical minimum time required for the entire encoding process.

The two-layer scheduling architecture combining a logical greedy algorithm with local RndFlw execution.

2.2 The Physical Layer (Local Optimization)

The second layer maps the logical tasks onto physical servers. We utilize an enhanced version of the RndFlw policy. A critical innovation here is out-degree priority scheduling. When a node has multiple outgoing transfers in the transport graph, it prioritizes the peer with the highest out-degree. This ensures that nodes responsible for the most downstream work are unblocked as early as possible, maintaining high system-wide throughput.

3. Experimental Results

The proposed system was evaluated on a 10-node cluster (Intel Xeon 2.4GHz, 8GB RAM, 1 Gbps network) using synthetic data blocks ranging from 512KB to 32MB.

Comparison of insertion times between the original RndFlw (Ori) and the optimized (Opt) scheduling method across different data sizes.

As shown in the results, the optimized method significantly outperforms the baseline RndFlw policy for larger data blocks. For 16MB and 32MB blocks, insertion time was reduced by approximately 18% and 17%, respectively. For smaller blocks (e.g., 512KB), the performance gains are negligible because the computational overhead of generating the logical transport graph offsets the scheduling benefits. The system demonstrated consistent performance across consecutive workloads, proving its robustness.

4. Conclusion

By combining global logical optimization with local physical heuristics, our two-layer approach effectively addresses the bottlenecks inherent in traditional cloud storage encoding. Future work will focus on adapting the transport graph to handle node churn and scaling the greedy algorithm for massive data center environments where node availability is more dynamic.

Summary updated

Abstract

In traditional erasure codes, all the redundant data are created and uploaded to the different storage nodes by a unique source node. However, such a source node may have limited communication and computation capabilities, which constrain the storage process throughput. In-network redundancy generation can improve data insertion throughput through distributing the data insertion load among the source and storage nodes. But it's hard to schedule the generation process. Many works have proposed some heuristic scheduling algorithms to improve data insertion throughput. We propose a new method combined global and local optimization to schedule the process. Experimental results show that our method reduce insertion time up to 18% compared with the best heuristic scheduling algorithm.
BibTeX
@inproceedings{liu2015reducing,
  author = {Zhenyuan Liu and Zhen Huang and Dongsheng Li},
  title = {{Reducing Insertion Time in LRC-based Cloud Storage Systems}},
  booktitle = {Advances},
  year = {2015},
  doi = {10.2991/esac-15.2015.24},
}
Figure