Boosting the Performance of Degraded Reads in RS-coded Distributed Storage Systems

Tian Xie, Juntao Fang, Shenggang Wan, Changsheng Xie, Xubin HearXiv 2023 · DOI · arXiv

TL;DR

This paper introduces APLS, a novel approach to speed up "degraded reads" in Reed-Solomon (RS) coded distributed storage systems. By intelligently utilizing all available source nodes for data reconstruction and selecting lightly loaded nodes as data receivers, APLS significantly reduces read latency, especially under heavy workloads, bridging the gap between degraded and normal reads.

What Problem Does This Paper Address?

Distributed storage systems often use Reed-Solomon (RS) codes for data redundancy, offering better storage efficiency than simple replication. However, when data chunks become unavailable (due to failures or high demand, known as "hot spots"), the system must reconstruct them from surviving data. This process, called a "degraded read," is significantly slower than a "normal read" because it involves transmitting multiple data chunks (k chunks for an RS(k,m) code) to a single "starter node" for reconstruction. Existing solutions like PPR and ECPipe improve this by introducing parallelism, but a performance gap between degraded and normal reads persists. This paper aims to close that gap by addressing the bottlenecks in both data transmission from source nodes and data reception at the starter node.

Methods

APLS (All Parallelism with a Light-loaded Starter) is the core contribution. It tackles the degraded read latency problem by focusing on two key observations:

  • Maximizing Upstream Bandwidth: Instead of using only the minimum required k source nodes, APLS leverages all available surviving source nodes (up to k+m-1) to participate in reconstruction. This is achieved by breaking down the reconstruction of a chunk into smaller units (words or packets) that can be computed in parallel across multiple source nodes, effectively increasing the total upstream network bandwidth available for sending data.
  • Optimizing Downstream Bandwidth: APLS identifies that the starter node's downstream network bandwidth is often a bottleneck. It proposes selecting a "light-loaded" storage node as the starter node. By analyzing request history, the system can identify nodes with lower current workloads and assign them as starter nodes, thereby gaining access to more available downstream bandwidth for receiving the reconstructed data.

APLS integrates these ideas by partitioning the reconstruction task among multiple "agent nodes" (which are the participating source nodes) and directing the final reconstructed data to a carefully chosen, lightly loaded starter node.

Datasets

Not discussed in the paper. The evaluation is based on a prototype implemented on a cluster of sixteen servers.

Key Insights and Ideas

  • Beyond k Source Nodes: The traditional approach of using only k source nodes for reconstruction is a significant limitation. By involving more nodes, even if they contribute smaller pieces of data, the aggregate upstream bandwidth can be substantially increased.
  • The Starter Node is Key: The downstream bandwidth of the starter node is a critical bottleneck. Simply adding more parallelism in reconstruction doesn't help if the starter node can't ingest the data fast enough. Choosing a lightly loaded node dramatically improves this.
  • Parallelism is Multi-faceted: APLS exploits parallelism not just in the computation of individual words or packets (as in ECPipe), but also in the number of nodes contributing data and the selection of the receiving node.
  • Closing the Gap: The paper argues that by optimizing both data sending and receiving, the latency gap between degraded and normal reads can be significantly reduced, and in some cases, even surpassed by degraded reads under specific conditions.

Key Results

  • Significant Latency Reduction: APLS reduces degraded read latency by up to 28% compared to ECPipe, particularly under medium to heavy workloads.
  • Performance under Heavy Workloads: APLS shows substantial improvements when network bandwidth is limited (e.g., 100 Mbps), demonstrating its effectiveness in challenging network conditions.
  • Scalability with Source Nodes: The performance improvement of APLS increases as the number of participating source nodes (q) increases, especially when helpers have heavier background workloads.
  • Robustness to Chunk Size: APLS remains effective even with smaller chunk sizes, though network hop latencies and synchronization can become more influential.
  • Competitive with Normal Reads: In some scenarios, especially under heavy workloads, the latency of degraded reads using APLS can be lower than that of normal reads.

Limitations and Future Work

  • Light-loaded Node Selection: The paper uses a statistical approach based on request history to select light-loaded nodes. Real-time dynamic workload monitoring could offer further improvements.
  • Packet Size Impact: While APLS generally outperforms ECPipe, there are specific scenarios (e.g., very light workloads or when the requestor is the bottleneck) where ECPipe might perform slightly better, particularly with certain packet sizes. The paper notes that very small packet sizes can negatively impact network transmission performance.
  • Future Work: The paper suggests that further research could explore more sophisticated methods for selecting light-loaded starter nodes and optimizing packetization strategies. The authors also mention that their approach is applicable to other RS-coded storage systems.

Summary updated

BibTeX
@misc{xie2023boosting,
  author = {Tian Xie and Juntao Fang and Shenggang Wan and Changsheng Xie and Xubin He},
  title = {{Boosting the Performance of Degraded Reads in RS-coded Distributed Storage Systems}},
  year = {2023},
  eprint = {2306.10528},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.10528},
}
Figure