Explicit Construction of MBR Codes for Clustered Distributed Storage

Jy-yong Sohn, Jaekyun MoonarXiv 2018 · arXiv · OpenReview

Abstract

This paper considers capacity-achieving coding for the clustered form of distributed storage that reflects practical storage networks. To reflect the clustered structure with limited cross-cluster communication bandwidths, nodes in the same cluster are set to communicate $\beta_I$ symbols, while nodes in other clusters can communicate $\beta_c \leq \beta_I$ symbols with one another. We provide two types of exact regenerating codes which achieve the capacity of clustered distributed storage: the minimum-bandwidth-regenerating (MBR) codes and the minimum-storage-regenerating (MSR) codes. First, we construct MBR codes for general parameter settings of clustered distributed storage. The suggested MBR code is a generalization of an existing code proposed by Rashmi et al., for scenarios where storage nodes are dispersed into $L > 1$ clusters. The proposed MBR code for the $\beta_c = 0$ case requires a much smaller field size compared to existing local MBR codes. Secondly, we devise MSR codes for clustered distributed storage. Focus is given on two important cases: $\epsilon=0$ and $\epsilon \in [1/(n-k), 1]$, where $\epsilon=\beta_c/\beta_I$ is the ratio of the available cross- to intra-cluster repair bandwidths, $n$ is the total number of distributed nodes and $k$ is the number of contact nodes in data retrieval. For $\epsilon=0$, two existing locally repairable codes are proven to be MSR codes for the clustered model. For $\epsilon \in [1/(n-k), 1]$, existing MSR codes for the non-clustered model are applicable to clustered scenarios with a simple modification.

The Clustered Storage Model

In modern distributed storage systems (DSS), data is spread across many nodes to ensure reliability. Traditional coding theory often assumes a "flat" network where the cost of communicating between any two nodes is identical. However, real-world data centers are hierarchical: nodes are grouped into racks or clusters.

Encoding and repair processes in a clustered distributed storage system.

As shown in Figure 1, communicating within a rack (intra-cluster) is typically fast and cheap, while communicating between racks (cross-cluster) is slow and expensive. This paper addresses the challenge of designing codes that are "capacity-achieving" for this specific clustered topology by accounting for the difference between intra-cluster bandwidth ($\beta_I$) and cross-cluster bandwidth ($\beta_c$).

Optimal Storage-Bandwidth Tradeoff

The system aims to optimize two primary metrics: node storage capacity ($\alpha$) and repair bandwidth ($\gamma$). There exists a fundamental tradeoff between these two values, leading to two optimal operating points:

  1. Minimum-Bandwidth-Regenerating (MBR): This point minimizes the total data moved during the repair of a failed node.
  2. Minimum-Storage-Regenerating (MSR): This point minimizes the amount of physical storage used per node.
The tradeoff curve between node capacity and repair bandwidth, identifying MSR and MBR points.

Figure 2 illustrates this tradeoff curve. The authors provide explicit construction algorithms for both MBR and MSR codes across different ratios of cross-cluster to intra-cluster bandwidth, defined as $\epsilon = \beta_c/\beta_I$.

Methods and Constructions

MBR Constructions

The authors generalize the "Repair-by-Transfer" (RBT) scheme. For the case where cross-cluster communication is forbidden ($\epsilon=0$), they utilize incidence matrices of fully connected graphs to distribute symbols among nodes. For cases where cross-cluster communication is allowed ($0 < \epsilon \leq 1$), they introduce a novel partitioning of symbols into local symbols (shared only within a cluster) and global symbols (shared across clusters).

MSR Constructions

The research demonstrates that for certain scenarios, existing Locally Repairable Codes (LRCs) satisfy the MSR conditions for clustered storage. Specifically, for the case where $n=kL$ (total nodes = contact nodes $\times$ clusters), a new construction based on simple Maximum Distance Separable (MDS) codes is proposed. The validity of these codes is proven using majorization theory and combinatorial analysis of storage capacity expressions.

Key Results and Insights

  • Field Size Efficiency: A major contribution of this work is the reduction of the required "field size." High field sizes lead to prohibitive computational costs for encoding and decoding. By tailoring codes to the cluster structure, the authors achieve reliability with a field size that scales linearly rather than exponentially with the number of nodes.
  • The $\epsilon$ Threshold: The optimal code structure changes based on the bandwidth ratio. When $\epsilon \geq 1/(n-k)$, existing MSR codes for non-clustered systems can be adapted with a simple modification to the repair rule.
  • LRC Equivalence: The authors prove that existing locally repairable codes are mathematically equivalent to MSR codes in a clustered setting where cross-cluster repair is impossible ($\epsilon=0$).

Conclusion

This paper provides explicit, capacity-achieving constructions for MBR and MSR codes in clustered distributed storage. By significantly reducing the required field size—for example, the proposed MSR construction for $n=kL$ requires a field size of at most $n$ compared to $2(n-k)$ in previous state-of-the-art methods—these codes offer a more practical path toward implementing advanced error correction in hierarchical data center environments.

Summary updated

Abstract

This paper considers capacity-achieving coding for the clustered form of distributed storage that reflects practical storage networks. To reflect the clustered structure with limited cross-cluster communication bandwidths, nodes in the same cluster are set to communicate $\beta_I$ symbols, while nodes in other clusters can communicate $\beta_c \leq \beta_I$ symbols with one another. We provide two types of exact regenerating codes which achieve the capacity of clustered distributed storage: the minimum-bandwidth-regenerating (MBR) codes and the minimum-storage-regenerating (MSR) codes. First, we construct MBR codes for general parameter settings of clustered distributed storage. The suggested MBR code is a generalization of an existing code proposed by Rashmi et al., for scenarios where storage nodes are dispersed into L > 1 clusters. The proposed MBR code for the $\beta_c = 0$ case requires a much smaller field size compared to existing local MBR codes. Secondly, we devise MSR codes for clustered distributed storage. Focus is given on two important cases:$\epsilon=0$ and $\epsilon \in [1/(n-k), 1]$, where $\epsilon=\beta_c/\beta_I$ is the ratio of the available cross- to intra-cluster repair bandwidths, n is the total number of distributed nodes and k is the number of contact nodes in data retrieval. The former represents the scenario where cross-cluster communication is not allowed, while the latter corresponds to the case of minimum node storage overhead. For $\epsilon=0$, two existing locally repairable codes are proven to be MSR codes for the clustered model. For $\epsilon \in [1/(n-k), 1]$, existing MSR codes for the non-clustered model are applicable to clustered scenarios with a simple modification.
BibTeX
@misc{sohn2018explicit,
  author = {Jy-yong Sohn and Jaekyun Moon},
  title = {{Explicit Construction of MBR Codes for Clustered Distributed Storage}},
  year = {2018},
  eprint = {1801.02287},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1801.02287},
}
Figure