Abstract
In modern distributed storage systems, the efficiency of data recovery and the cost of updating stored information are critical performance bottlenecks. This paper introduces a formal mathematical framework that bridges Locally Repairable Codes (LRCs) with combinatorial packings. By characterizing the support sets of parity check symbols as blocks in a packing, the authors derive new constructions for systematic LRCs that are optimal in terms of both repair locality and update-efficiency. These constructions offer greater parameter flexibility than previous geometric methods, specifically by removing the requirement that repair group sizes must perfectly divide the message length.
Introduction
Massive distributed storage infrastructures, such as Amazon EBS or GoogleFS, rely on erasure coding to ensure data durability against frequent disk failures. While traditional Maximum Distance Separable (MDS) codes provide optimal storage efficiency, they suffer from high repair costs: recovering a single lost symbol typically requires reading $k$ other symbols from across the network.
Locally Repairable Codes (LRCs) were developed to mitigate this by ensuring that any single symbol can be recovered using a small subset of $r$ other symbols ($r \ll k$). However, designing LRCs that simultaneously achieve optimal minimum distance (reliability), optimal update-efficiency (minimum parity changes per data update), and support multiple disjoint repair groups remains a significant challenge. This paper addresses these challenges by mapping the coding problem onto the well-studied field of combinatorial design.
The Packing-LRC Correspondence
The central contribution of this work is the proof that the structure of an optimal systematic LRC is fundamentally linked to a mathematical object known as a packing.
A $(k, R, 1)$ packing is a collection of subsets (blocks) of a set of $k$ elements such that any two distinct elements appear together in at most one block. The authors demonstrate that the support sets—the indices of non-zero entries—of the parity check symbols in an optimal LRC must satisfy this packing property. This "bridge" is intuitive yet powerful: the requirement for disjoint repair groups in a storage system mirrors the "at most one common element" constraint in combinatorial packings.
To formalize this, the authors provide an algorithm (Algorithm 1) that can transform the support sets of any optimal LRC into a valid packing, proving that these two mathematical structures are inextricably linked.
Construction Methodologies
Leveraging this connection, the paper proposes two primary construction methods:
Construction A: Binary LRCs from Packings
This method builds binary LRCs directly from known combinatorial packings. This approach is particularly effective for creating codes with optimal update-efficiency. In these codes, the number of parity symbols that must be modified when a single data symbol changes is minimized, hitting the theoretical limit defined by the code's distance $d$. Because it utilizes the packing blocks to define the parity-check matrix, the resulting codes naturally support parallel repair operations.
Construction B: Resolvable Packings and MDS Integration
Construction B is more sophisticated, combining an existing MDS code with a "resolvable packing." This method generalizes the well-known "Pyramid Codes." While Pyramid Codes typically allow for a single repair group, Construction B enables multiple repair groups, providing higher tolerance for simultaneous failures and more flexible locality requirements. While this method often requires larger finite fields (alphabet sizes), it provides a robust framework for high-reliability systems.
Key Insights and Results
Breaking the Divisibility Constraint
A major limitation of previous optimal LRC constructions was the "divisibility constraint," which required the repair group size $r$ to be a divisor of the message size $k$. The packing-based approach presented here functions even when $r$ does not divide $k$. This provides system architects with significantly more flexibility when configuring storage clusters with non-standard node counts.
Theoretical Optimality
The authors demonstrate that their codes meet the Singleton-type upper bounds for minimum Hamming distance. This proves that for a given amount of redundancy and locality, these codes are as reliable as mathematically possible. The paper includes a catalog of new optimal LRC families derived from classical regular packings, such as those based on finite fields and Steiner systems.
Conclusion and Future Work
By establishing a rigorous link between coding theory and combinatorial packings, this research provides a new toolkit for designing efficient distributed storage systems. The resulting codes are not only theoretically optimal but also practically flexible, addressing real-world constraints like update-efficiency and arbitrary repair group sizes.
Future research may expand beyond systematic codes to explore non-systematic packing-based structures. Additionally, as Construction B relies on the availability of resolvable packings, the discovery of new combinatorial designs will directly translate into the discovery of new, high-performance storage codes. Reducing the required alphabet size for these complex constructions remains a priority for making these codes even more efficient for hardware implementation.
Summary updated