Capacity of Clustered Distributed Storage

Jy-yong Sohn, Beongjun Choi, Sung Whan Yoon, Jaekyun Moon

TL;DR

This paper introduces a new model for clustered distributed storage systems that accounts for the imbalance between intra-cluster and cross-cluster repair bandwidth. It derives a closed-form expression for system capacity and analyzes the feasible resource trade-offs, showing how to minimize cross-cluster traffic by strategically allocating storage and repair bandwidth.

What Problem Does This Paper Address?

Modern data centers and large-scale storage systems are increasingly distributed, often organized into clusters (e.g., racks of servers). When a storage node fails, it needs to be repaired by retrieving data from other nodes. In clustered systems, this repair process involves two types of communication: intra-cluster (within the same cluster) and cross-cluster (between different clusters). Realistic network architectures often have significantly more bandwidth for intra-cluster communication than for cross-cluster communication. Existing models for distributed storage typically assume homogeneous systems where repair bandwidth is uniform, failing to capture this crucial imbalance. This paper addresses this gap by proposing a model that explicitly differentiates between intra-cluster and cross-cluster repair bandwidth, and investigates how this impacts the overall storage capacity and resource requirements for reliable data storage.

Methods

The authors propose a new system model for clustered distributed storage systems (DSSs). They leverage information flow graphs and the max-flow min-cut theorem to derive a closed-form expression for the storage capacity of the clustered DSS. This capacity is expressed as a function of key system parameters: node storage capacity ($\alpha$), intra-cluster repair bandwidth ($\beta_I$), and cross-cluster repair bandwidth ($\beta_C$). A crucial aspect of their analysis is the introduction of a parameter $\epsilon = \beta_C / \beta_I$ to quantify the imbalance between cross-cluster and intra-cluster repair bandwidth. They then analyze the feasible sets of $(\alpha, \beta_I, \beta_C)$ that allow for reliable data storage, focusing on the trade-offs between these resources. They also introduce the concept of "intra-cluster repairable codes" for scenarios where cross-cluster repair traffic is eliminated.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Realistic Clustered Model: The paper's core contribution is a more realistic model for distributed storage that acknowledges the bandwidth disparity between intra-cluster and cross-cluster communication, which is prevalent in modern data centers.
  • Capacity Trade-offs: The capacity of the system is shown to be a function of node storage capacity, intra-cluster repair bandwidth, and cross-cluster repair bandwidth. Importantly, the capacity is asymptotically equivalent to a decreasing function of the number of clusters, suggesting that fewer, larger clusters might be more capacity-efficient, but this comes with trade-offs in fault tolerance.
  • Minimizing Cross-Cluster Traffic: The research provides a clear path to minimize or even eliminate cross-cluster repair traffic ($\epsilon = 0$). This is achievable by allocating additional storage capacity ($\alpha$) and/or intra-cluster repair bandwidth ($\beta_I$), as dictated by a specific law derived in the paper.
  • Intra-Cluster Repairable Codes: The paper defines and analyzes "intra-cluster repairable codes," which are network coding schemes that enable node repair using only intra-cluster communication. These codes are shown to be a subset of previously studied locally repairable codes.
  • Feasible Resource Sets: The work provides closed-form solutions for the feasible combinations of storage and repair bandwidth resources required to reliably store data, offering practical guidance for system design.

Key Results

  • A closed-form expression for the capacity of clustered distributed storage systems is derived, dependent on node storage capacity, intra-cluster repair bandwidth, and cross-cluster repair bandwidth.
  • The capacity is shown to be asymptotically equivalent to a monotonically decreasing function of the number of clusters ($L$).
  • Feasible sets of $(\alpha, \beta_I, \beta_C)$ for reliable storage are characterized.
  • It's demonstrated that achieving the minimum storage overhead ($\alpha = M/k$) requires a sufficient level of cross-cluster repair bandwidth ($\epsilon > 1/(n-k)$).
  • The paper shows that cross-cluster repair traffic can be reduced to zero ($\epsilon = 0$) by allowing extra storage capacity and intra-cluster repair bandwidth, with specific trade-off laws provided.

Limitations and Future Work

  • Single Node Failure: The model primarily considers the failure of a single node at a time, as in prior work. Analyzing simultaneous multiple node failures, especially within the same cluster, is a potential area for future research.
  • Optimal Number of Clusters: While the paper shows capacity decreases with more clusters, it acknowledges that a larger number of clusters is desirable for tolerating cluster failures. Finding the optimal number of clusters ($L^*$) that balances capacity and fault tolerance is identified as an important future research topic.
  • General $d_I, d_C$ Settings: The paper assumes maximum helper node settings ($d_I = n_I - 1, d_C = n - n_I$) for capacity maximization. Extending the analysis to general $d_I, d_C$ settings, which might offer lower latency, and exploring the trade-off between capacity and latency, is suggested.
  • Explicit Coding Schemes: While the existence of capacity-achieving coding schemes is proven, explicit constructions for all parameters are still an area for further work.
  • Repair Link Aggregation: The paper mentions that techniques like repair link aggregation could change the trade-off picture and warrant further investigation.

Summary updated

Abstract

A new system model reflecting the clustered structure of distributed storage is suggested to investigate interplay between storage overhead and repair bandwidth as storage node failures occur. Large data centers with multiple racks/disks or local networks of storage devices (e.g., sensor network) are good applications of the suggested clustered model. In realistic scenarios involving clustered storage structures, repairing storage nodes using intact nodes residing in other clusters are more bandwidth consuming than restoring nodes based on information from intra-cluster nodes. Therefore, it is important to differentiate between intra-cluster repair bandwidth and cross-cluster repair bandwidth in modeling distributed storage. Capacity of the suggested model is obtained as a function of fundamental resources of distributed storage systems, namely, node storage capacity, intra-cluster repair bandwidth, and cross-cluster repair bandwidth. The capacity is shown to be asymptotically equivalent to a monotonic decreasing function of number of clusters, as the number of storage nodes increases without bound. Based on the capacity expression, feasible sets of required resources which enable reliable storage are obtained in a closed-form solution. Specifically, it is shown that the cross-cluster traffic can be minimized to zero (i.e., intra-cluster local repair becomes possible) by allowing extra resources on storage capacity and intra-cluster repair bandwidth, according to the law specified in the closed form. The network coding schemes with zero cross-cluster traffic are defined as intra-cluster repairable codes, which are shown to be a class of the previously developed locally repairable codes.
BibTeX
@article{sohn2019capacity,
  author = {Jy-yong Sohn and Beongjun Choi and Sung Whan Yoon and Jaekyun Moon},
  title = {{Capacity of Clustered Distributed Storage}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  url = {https://openreview.net/forum?id=34vcyM23-aL},
}
Figure