Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction

K. V. Rashmi, Nihar B. Shah, P. Vijay Kumar

Abstract

Regenerating codes are a class of distributed storage codes that optimally trade the bandwidth needed for repair of a failed node with the amount of data stored per node. Minimum Storage Regenerating (MSR) codes prioritize storage efficiency, while Minimum Bandwidth Regenerating (MBR) codes prioritize repair efficiency. This paper introduces the Product-Matrix (PM) framework, providing the first explicit constructions of exact-repair codes where the number of nodes $n$ can be chosen independently of other system parameters. We present optimal MBR codes for all feasible parameters and MSR codes for the range $d \ge 2k - 2$.

Introduction

In large-scale distributed storage systems, such as cloud infrastructures, node failures are a routine occurrence. Maintaining data reliability requires erasure coding; however, traditional codes like Reed-Solomon are often inefficient during node repair, requiring the download of the entire file to reconstruct a single failed node.

Regenerating codes solve this by optimizing the "repair bandwidth." There are two primary optimal points on the storage-bandwidth trade-off curve:

  1. Minimum Storage Regenerating (MSR): Minimizes storage per node first (reaching the MDS bound), then minimizes repair bandwidth.
  2. Minimum Bandwidth Regenerating (MBR): Minimizes repair bandwidth first, then minimizes storage.

This paper addresses the challenge of Exact Repair. Unlike "functional repair," where a replacement node only needs to maintain the code's mathematical properties, exact repair requires the replacement to be a bit-for-bit identical copy. This is highly preferred in practical systems to avoid massive metadata overhead.

The Product-Matrix Framework

The authors propose a unified framework where the data stored at each node is represented as a row in a code matrix $C$. This matrix is defined as the product of two matrices:

$$C = \Psi M$$

  • $\Psi$ (Encoding Matrix): A fixed $n \times d$ matrix (typically Vandermonde or Cauchy) that determines how data is distributed across the $n$ nodes.
  • $M$ (Message Matrix): A $d \times \alpha$ matrix containing the message symbols arranged in a specific structure.

MBR Construction

In the MBR case, the message matrix $M$ is constructed as a symmetric matrix containing all message symbols. The symmetry ($M = M^T$) is the key innovation. When a replacement node contacts a helper node, the helper performs a simple inner product. The symmetric property allows the replacement node to use linear algebra to "cancel out" unwanted terms and recover the exact missing symbols. This construction is proven optimal for all feasible values of $[n, k, d]$.

MSR Construction

The MSR construction utilizes two symmetric matrices and a diagonal matrix to achieve Interference Alignment. This technique, borrowed from wireless communications, ensures that the "interference" (unwanted data from helper nodes) aligns in a way that allows the replacement node to discard it easily. This construction provides optimal exact-repair MSR codes for the range $d \ge 2k - 2$.

Key Insights and Advantages

  • Decoupling $n$ from $d$: Previous constructions often required $n = d + 1$. The PM framework allows $n$ to be chosen independently, meaning new nodes can be added to the system simply by adding rows to the $\Psi$ matrix without altering the existing code structure.
  • Low Complexity: The repair process involves only simple linear combinations (additions and multiplications) over a finite field, making it computationally efficient for hardware implementation.
  • Field Size Efficiency: The required finite field size is relatively small ($q \ge n$ or $q \ge 2n$), which is crucial for maintaining high throughput in real-world storage systems.
  • Striping: The authors employ "striping," dividing large files into smaller units where the repair parameter $\beta$ is set to 1. This simplifies the implementation and reduces the memory buffer requirements during the repair process.

Conclusion and Future Work

The Product-Matrix framework provides a robust and practical approach to designing exact-repair regenerating codes. While it provides a complete solution for MBR codes, the MSR construction currently covers the regime $d \ge 2k - 2$. The region $k \le d < 2k - 2$ remains an area of interest, although exact repair with $\beta=1$ is known to be impossible for some parameters in that range. Future research may also focus on optimizing these codes for binary fields to further enhance computational speed through XOR operations.

Summary updated

Abstract

Regenerating codes are a class of distributed storage codes that optimally trade the bandwidth needed for repair of a failed node with the amount of data stored per node of the network. Minimum Storage Regenerating (MSR) codes minimize first, the amount of data stored per node, and then the repair bandwidth, while Minimum Bandwidth Regenerating (MBR) codes carry out the minimization in the reverse order. An [n, k, d] regenerating code permits the data to be recovered by connecting to any k of the n nodes in the network, while requiring that repair of a failed node be made possible by connecting (using links of lesser capacity) to any d nodes. Previous, explicit and general constructions of exact-regenerating codes have been confined to the case n=d+1. In this paper, we present optimal, explicit constructions of MBR codes for all feasible values of [n, k, d] and MSR codes for all [n, k, d >= 2k-2], using a product-matrix framework. The particular product-matrix nature of the constructions is shown to significantly simplify system operation. To the best of our knowledge, these are the first constructions of exact-regenerating codes that allow the number n of nodes in the distributed storage network, to be chosen independent of the other parameters. The paper also contains a simpler description, in the product-matrix framework, of a previously constructed MSR code in which the parameter d satisfies [n=d+1, k, d >= 2k-1].
BibTeX
@article{rashmi2011optimal,
  author = {K. V. Rashmi and Nihar B. Shah and P. Vijay Kumar},
  title = {{Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction}},
  journal = {IEEE Trans. Information Theory},
  year = {2011},
  url = {https://openreview.net/forum?id=PkKUZwGdmgl},
}
Figure