Maximally Recoverable Codes for Grid-like Topologies

Parikshit Gopalan, Guangda Hu, Shubhangi Saraf, Carol Wang, Sergey Yekhanin

Abstract: The explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Yet, the codes being deployed in practice are fairly short. In this work, we address what we view as the main coding theoretic barrier to deploying longer codes in storage: at large lengths, failures are not independent and correlated failures are inevitable. This motivates designing codes that allow quick data recovery even after large correlated failures, and which have efficient encoding and decoding. We propose that code design for distributed storage be viewed as a two-step process. The first step is choose a topology of the code, which incorporates knowledge about the correlated failures that need to be handled, and ensures local recovery from such failures. In the second step one specifies a code with the chosen topology by choosing coefficients from a finite field. In this step, one tries to balance reliability (which is better over larger fields) with encoding and decoding efficiency (which is better over smaller fields). This work initiates an in-depth study of this reliability/efficiency tradeoff. We consider the field-size needed for achieving maximal recoverability: the strongest reliability possible with a given topology. We propose a family of topologies called grid-like topologies which unify a number of topologies considered both in theory and practice, and prove a collection of results about maximally recoverable codes in such topologies including the first super-polynomial lower bound on the field size.

Introduction

In massive distributed storage systems, such as those operated by Microsoft or Meta, data protection is moving away from simple replication toward sophisticated erasure coding. While traditional codes like Reed-Solomon are highly effective for independent node failures, real-world large-scale systems frequently encounter correlated failures. An entire server rack or even a whole data center may go offline simultaneously, creating erasure patterns that standard codes struggle to handle efficiently.

To address this, researchers have turned to Maximally Recoverable (MR) codes. These codes are considered the "gold standard" for reliability because they are guaranteed to correct every erasure pattern that is information-theoretically fixable given a specific layout of local and global parity checks. However, a significant barrier to deploying these codes at scale is the field size ($F_q$) required for the underlying arithmetic. Large fields lead to slower encoding and decoding speeds. This research investigates the fundamental tradeoff between reliability and computational efficiency by asking: how small can the field size be while maintaining maximal recoverability?

The Framework: Grid-like Topologies

The authors propose that code design should be viewed as a two-step process. First, designers select a topology—a layout of parity checks—that reflects the physical failure correlations of the hardware. Second, they choose the mathematical coefficients to maximize reliability.

This work introduces Grid-like Topologies, which arrange data in an $m \times n$ grid with the following constraints:

  1. Local Column Checks: Each column has $a$ local parity checks.
  2. Local Row Checks: Each row has $b$ local parity checks.
  3. Global Checks: The entire grid is protected by $h$ global parity checks.

This framework unifies several topologies used in both theoretical research and practical industry applications, such as the codes used in Facebook’s f4 storage system.

Methodology

To analyze these topologies, the authors utilize several novel theoretical techniques:

  • Combinatorial Graph Theory: The problem of determining field size is reduced to a labeling problem on bipartite graphs ($K_{n,n}$). The goal is to assign weights to edges such that no simple cycle sums to zero, a property that directly relates to the independence of parity constraints.
  • Boosting: This technique allows the authors to transform complex, high-weight erasure patterns into simpler ones, making it easier to prove whether a pattern is correctable.
  • Duality and Linear Algebra: By examining the dual constraints of the code, the researchers characterize which sets of failed nodes are information-theoretically correctable.

Key Insights

The Field Size Barrier

The most significant finding is that even for relatively simple grid topologies, the field size must grow super-polynomially relative to the code length. This reveals a hidden cost: as we build larger and more reliable storage systems, the computational overhead of maintaining MR status grows much faster than previously anticipated.

Iterative vs. Global Decoding

In practice, many systems rely on "iterative" decoding—alternating between fixing rows and columns. The authors demonstrate that MR codes can correct patterns that iterative decoding cannot. This proves that global Gaussian elimination is strictly more powerful for these topologies, though it comes at a higher computational price.

Major Results

  1. First Super-Polynomial Lower Bound: The authors prove that for a basic grid topology ($T_{n \times n}(1, 1, 1)$), the field size $q$ must be at least $\exp(\Omega((\log n)^2))$. This is a landmark result, as no super-linear lower bound was previously known for any topology.
  2. Characterization of Tensor Products: The work provides a full characterization of correctable erasure patterns for a specific class of tensor product codes (where $a=1$), providing clarity for systems similar to those used in industry.
  3. Optimal Construction: The researchers provide a new, explicit construction for the $T_{m \times n}(1, 0, 2)$ topology that achieves an optimal field size of $O(mn)$.

Discussion and Future Work

While this work establishes the first super-polynomial lower bound, a significant gap remains between this bound ($\exp(\log^2 n)$) and the best-known upper bounds ($\exp(n \log n)$). Closing this gap is a primary objective for future research.

Furthermore, while this paper focuses on "maximal" recoverability, the results suggest a potential pivot for practitioners: exploring "near-maximal" recoverability. By sacrificing a negligible amount of reliability, it may be possible to achieve massive gains in field-size efficiency, leading to significantly faster storage systems.

Summary updated

Abstract

The explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Yet, the codes being deployed in practice are fairly short. In this work, we address what we view as the main coding theoretic barrier to deploying longer codes in storage: at large lengths, failures are not independent and correlated failures are inevitable. This motivates designing codes that allow quick data recovery even after large correlated failures, and which have efficient encoding and decoding. We propose that code design for distributed storage be viewed as a two-step process. The first step is choose a topology of the code, which incorporates knowledge about the correlated failures that need to be handled, and ensures local recovery from such failures. In the second step one specifies a code with the chosen topology by choosing coefficients from a finite field. In this step, one tries to balance reliability (which is better over larger fields) with encoding and decoding efficiency (which is better over smaller fields). This work initiates an in-depth study of this reliability/efficiency tradeoff. We consider the field-size needed for achieving maximal recoverability: the strongest reliability possible with a given topology. We propose a family of topologies called grid-like topologies which unify a number of topologies considered both in theory and practice, and prove a collection of results about maximally recoverable codes in such topologies including the first super-polynomial lower bound on the field size.
BibTeX
@inproceedings{gopalan2017maximally,
  author = {Parikshit Gopalan and Guangda Hu and Shubhangi Saraf and Carol Wang and Sergey Yekhanin},
  title = {{Maximally Recoverable Codes for Grid-like Topologies}},
  booktitle = {SODA},
  year = {2017},
  url = {https://openreview.net/forum?id=zkqTYotemi},
}
Figure