Capacity of Clustered Distributed Storage

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

Abstract

A new system model reflecting the clustered structure of distributed storage is suggested to investigate the 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 networks) 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 is 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 the 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.

Introduction

In modern data centers, storage nodes are typically organized into physical clusters such as racks or disks. Standard theoretical models for Distributed Storage Systems (DSS) often assume "homogeneous" repair bandwidth, implying that the cost of retrieving data from a neighbor in the same rack is identical to retrieving it from a node across the data center. In reality, cross-rack communication is a major bottleneck, often 5 to 20 times slower than intra-rack communication. This research addresses the gap between theory and practice by modeling a Clustered DSS to determine the maximum amount of data a system can reliably store (Capacity) when distinguishing between intra-cluster repair bandwidth ($\beta_I$) and cross-cluster repair bandwidth ($\beta_c$).

System Model and Methods

The authors employ Information Flow Graphs and Min-cut Analysis to derive a closed-form capacity expression $C(\alpha, \beta_I, \beta_c)$, where $\alpha$ is the storage capacity per node. The system model consists of $n$ nodes divided into $L$ clusters. To repair a failed node, the system contacts $d_I$ nodes within the same cluster and $d_c$ nodes in other clusters.

Clustered repair model distinguishing intra-cluster ($\beta_I$) and cross-cluster ($\beta_c$) bandwidth.

The study assumes "functional repair," where a newcomer node maintains the overall system's Maximum Distance Separable (MDS) property without needing to be an exact replica of the failed node. The authors prove that "symmetric repair"—requesting equal information from helper nodes within the same category—is optimal for maximizing capacity.

Key Insights and Results

The Cost of Locality and Efficiency Thresholds

To reduce expensive cross-cluster traffic to zero (creating "intra-cluster repairable codes"), the system must increase either storage overhead ($\alpha$) or intra-cluster bandwidth ($\beta_I$). A critical finding is that the minimum possible storage overhead ($\alpha = M/k$) can only be achieved if the cross-cluster bandwidth ratio $\epsilon = \beta_c / \beta_I$ is at least $1/(n-k)$. If cross-cluster bandwidth is scarcer than this threshold, the system must store more redundant data to remain reliable.

Impact of Clustering on Capacity

The research introduces a dispersion factor $\sigma$ related to the number of clusters. It demonstrates that as nodes become more dispersed (more clusters with fewer nodes per cluster), the total capacity of the system asymptotically decreases. Capacity is shown to be a monotonic decreasing function of the number of clusters $L$. While gathering nodes into fewer, larger clusters increases theoretical storage capacity, it may simultaneously decrease rack-fault tolerance.

Capacity $C$ as a function of the number of clusters $L$ under different resource availability scenarios.

Connection to Locally Repairable Codes (LRCs)

The authors establish that their "intra-cluster repairable codes" (where $\beta_c = 0$) are a specific class of LRCs. This provides a formal bridge between network coding for repair bandwidth and codes designed specifically for repair locality.

Conclusion and Future Work

This paper provides the first exact formula for the capacity of a clustered DSS and characterizes the optimal trade-off curves between storage and repair bandwidth. However, the current model primarily focuses on single node failures. Future research should explore concurrent failures or entire rack failures, as well as the trade-off between repair latency and storage capacity. While the existence of capacity-achieving codes is proven, explicit low-complexity code constructions for all parameters remain an area for further development.

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