Maximally Recoverable Codes for Grid-like Topologies

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

TL;DR

This paper investigates the fundamental limits of Maximally Recoverable (MR) codes, the "gold standard" for reliability in distributed storage. The authors introduce a framework for "grid-like topologies" and prove the first super-polynomial lower bound on the field size required for these codes, revealing a significant hidden cost in balancing extreme reliability with computational efficiency.

What Problem Does This Paper Address?

In massive distributed storage systems (like those run by Microsoft or Facebook), data is protected using erasure codes. While traditional codes like Reed-Solomon are great for independent failures, real-world failures are often correlated—for example, an entire server rack or an entire data center might go offline at once.

To handle this, researchers use Maximally Recoverable (MR) codes. These codes are designed with a specific "topology" (a layout of local and global parity checks) and are guaranteed to correct every erasure pattern that is theoretically possible to fix given that layout.

However, there is a major catch: to achieve this "maximal" reliability, the codes often require arithmetic over very large finite fields ($F_q$). Large fields mean slower encoding and decoding. The central question this paper asks is: How small can we make the field size while still maintaining maximal recoverability?

Methods

The authors approach the problem by defining Grid-like Topologies. These topologies arrange data in an $m \times n$ grid where:

  1. Each column has $a$ local parity checks.
  2. Each row has $b$ local parity checks.
  3. The entire grid has $h$ global parity checks.

To prove their results, the authors employ several novel theoretical techniques:

  • Combinatorial Graph Theory: They reduce the problem of field size to a labeling problem on bipartite graphs ($K_{n,n}$), where edges are assigned weights such that no simple cycle sums to zero.
  • Boosting: A technique used to transform a complex erasure pattern into a simpler one to prove its correctability.
  • Duality and Linear Algebra: They use the dual constraints of the code to characterize which "erasure patterns" (sets of failed nodes) are information-theoretically correctable.

Datasets

As a theoretical paper in coding theory, this work does not use empirical datasets. Instead, it provides mathematical proofs and explicit constructions for code families.

Key Insights and Ideas

  • Topology as a Design Step: The authors argue that code design should be a two-step process: first, pick a topology that matches the physical failure correlations of the hardware, and second, choose the coefficients (the math) to maximize reliability.
  • The Field Size Barrier: The most surprising insight is that even for very simple grid topologies, the field size must grow super-polynomially relative to the code length. This means that as we try to build larger, more reliable storage systems, the computational overhead of MR codes might grow much faster than previously hoped.
  • Iterative vs. Global Decoding: In practice, many systems use "iterative" decoding (fixing rows, then columns, then rows again). The authors show that MR codes can correct patterns that iterative decoding cannot, proving that global Gaussian elimination is strictly more powerful for these topologies.
  • Regularity Condition: They propose a "regularity" condition for erasure patterns in tensor product codes, providing a potential path toward a complete combinatorial characterization of what these codes can actually survive.

Key Results

  • First Super-Polynomial Lower Bound: They prove that for a simple grid topology ($T_{n \times n}(1, 1, 1)$), the field size $q$ must be at least $\exp(\Omega((\log n)^2))$. Before this, no super-linear lower bound was known for any topology.
  • Characterization of Tensor Products: They fully characterize the correctable erasure patterns for a specific class of tensor product codes (where $a=1$), which are used in systems like Facebook’s f4 storage.
  • Optimal Construction: They provide a new, explicit construction for a specific basic topology ($T_{m \times n}(1, 0, 2)$) that achieves an optimal field size of $O(mn)$.

Limitations and Future Work

  • The Gap: While the authors proved a super-polynomial lower bound, there is still a large gap between their bound ($\exp(\log^2 n)$) and the best-known upper bounds ($\exp(n \log n)$). Closing this gap remains an open challenge.
  • Generalizing Topologies: The characterization of correctable patterns for more complex grids (where $a > 1$) remains a conjecture.
  • Practicality: The paper focuses on the "maximal" case. Future work could explore "near-maximal" recoverability—trading off a tiny bit of reliability for a massive gain in field-size efficiency (and thus speed).

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 correlate d 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 Fq. 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 recover ability: 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 the following results about codes for such topologies: The first super-polynomial lower bound on the field size needed for achieving maximal recoverability in a simple grid-like topology. To our knowledge, there was no super-linear lower bound known before, for any topology. A combinatorial characterization of erasure patterns correctable by Maximally Recoverable codes for a topology which corresponds to tensoring MDS codes with a parity check code. This topology is used in practice (for instance see [MLR+14]). We conjecture a similar characterization for Maximally Recoverable codes instantiating arbitrary tensor product topologies.
BibTeX
@inproceedings{gopalan2017maximally,
  author = {Parikshit Gopalan and Guangda Hu and Swastik Kopparty 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},
}

Loading related content...

Figure