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.
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.
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