PaperlayerView exact revision on arXiv

Source-linked AI summary

Zigzag Codes: MDS Array Codes with Optimal Rebuilding

Itzhak Tamo, Zhiying Wang, Jehoshua Bruck

arXiv:1112.0371v1cs.IT

TL;DR

The paper addresses the design of MDS array codes with optimal rebuilding ratios for erased information. It constructs explicit codes achieving the lower bound e/r for e systematic erasures, with efficient implementation and optimal updates.

  • Problem

    The paper seeks to design systematic (n, k) MDS array codes with optimal rebuilding ratio for arbitrary numbers of parity nodes.

  • Method

    The construction uses parity sets based on row and zigzag sets, with permutations derived from binary vectors to maximize their intersections.

  • Results

    The codes achieve rebuilding ratio e/r for e systematic erasures, including 1/2 for one erasure with two parities and 2/3 for two erasures with three parities.

  • Takeaways & Limitations

    The codes combine optimal rebuilding with systematic access, efficient encoding and decoding, finite field size 3 when r=2, and optimal updates.

Abstract

from arXiv · show

MDS array codes are widely used in storage systems to protect data against erasures. We address the \emph{rebuilding ratio} problem, namely, in the case of erasures, what is the fraction of the remaining information that needs to be accessed in order to rebuild \emph{exactly} the lost information? It is clear that when the number of erasures equals the maximum number of erasures that an MDS code can correct then the rebuilding ratio is 1 (access all the remaining information). However, the interesting and more practical case is when the number of erasures is smaller than the erasure correcting capability of the code. For example, consider an MDS code that can correct two erasures: What is the smallest amount of information that one needs to access in order to correct a single erasure? Previous work showed that the rebuilding ratio is bounded between 1/2 and 3/4, however, the exact value was left as an open problem. In this paper, we solve this open problem and prove that for the case of a single erasure with a 2-erasure correcting code, the rebuilding ratio is 1/2. In general, we construct a new family of $r$-erasure correcting MDS array codes that has optimal rebuilding ratio of $\frac{e}{r}$ in the case of $e$ erasures, $1 \le e \le r$. Our array codes have efficient encoding and decoding algorithms (for the case $r=2$ they use a finite field of size 3) and an optimal update property.

I. INTRODUCTION

The paper constructs systematic MDS array codes that minimize the fraction of surviving information accessed to rebuild erased systematic nodes, while retaining optimal update and practical encoding properties. Its zigzag-based designs achieve rebuilding ratio e/r for e erasures and support MDS correction.

  • Problem: The rebuilding ratio is the fraction of information accessed in surviving nodes to rebuild erased nodes exactly.When r nodes are erased, the ratio is 1; the paper focuses on fewer than r erasures.
  • Construction: The codes use row and zigzag parity sets, with zigzag sets formed through permutations of systematic-column elements.Unlike straight-line parity sets in EVENODD and X-code, zigzag sets can follow zigzag lines.
  • Two parities: 1/2 is the rebuilding ratio for any single erased systematic node in the two-parity construction.Rebuilding combines row and zigzag parities, accessing only half of the remaining elements.
  • General construction: 1/r is the rebuilding ratio for a single erased systematic node in the construction with r parities.The construction is designed by choosing permutations derived from binary vectors so row and zigzag sets intersect substantially.
  • Code properties: For two parity nodes, the codes are MDS over a finite field of size 3, and the field size is optimal.The codes also provide efficient encoding and decoding, systematic access, and optimal update properties.
  • Multiple erasures: e/r is the optimal rebuilding ratio when e systematic nodes are erased, for 1 ≤ e ≤ r.The construction achieves the lower bound on repair bandwidth for any number of erasures in this range.

II. (k + 2, k) MDS ARRAY CODE CONSTRUCTIONS

The construction uses binary-vector-derived permutations to define zigzag sets and combines them with row-sum parity, yielding (k + 2, k) MDS array codes with optimal rebuilding for two parities. The resulting codes achieve rebuilding ratio 1/2, use finite field size 3, and retain optimal rebuilding after shortening.

  • Binary-vector construction: The construction starts with a 2^m × k array and nonzero binary vectors that induce permutations by binary-vector addition.For v ∈ T, the permutation is f_v(x) = x + v over binary representations.
  • Parity construction: The first parity is formed by row sums, while the second parity groups elements into zigzag sets defined by the induced permutations.For an erased systematic column, elements in X_j are rebuilt by rows and the remaining elements by zigzags.
  • Theorem 1: Theorem 1 constructs orthogonal permutations from standard binary basis vectors, with X_0 defined using the all-ones vector, producing an (m + 3, m + 1) code.The resulting permutations have rebuilding ratio 1/2, and the code can be shortened while retaining optimal rebuilding.
  • Example 1: In the 4 × 3 example, rebuilding a systematic node accesses half of each surviving node’s elements, whereas rebuilding a parity node accesses all information elements.The example instantiates the row and zigzag access procedure for a (5, 3) MDS array code.
  • Optimal rebuilding: Orthogonal permutations ensure that rebuilding any systematic node accesses only 2^(m−1) elements from each surviving node, giving optimal rebuilding ratio 1/2.The construction makes the relevant row and zigzag sets disjoint across the required permutation pairs.
  • MDS property: The parity coefficients are assigned so the construction is MDS; the resulting (m + 3, m + 1) code uses the optimal finite field size 3.The construction also has optimal array size, meaning the maximum number of columns for the given number of rows.

III. FORMAL PROBLEM SETTINGS AND CONSTRUCTIONS

The section formalizes two-parity MDS array codes with optimal update and reduces optimal rebuilding to designing intersecting row and zigzag sets. It establishes lower bounds and constructs codes attaining ratio 1/2, with exponential rows and bounded column growth.

  • Code model: An MDS array code with 2 parities is represented by an information array plus row and zigzag parity columns.The row and zigzag parity sets partition the information array into equally sized sets, each containing one element from every systematic column.
  • Code model: Optimal update requires exactly three updated elements when one information element changes.The systematic element and one element in each parity node are updated.
  • Rebuilding objective: Rebuilding a systematic node accesses parity elements and surviving elements from row or zigzag sets, so minimizing access means maximizing their intersections.Each erased element can be rebuilt through its row set or zigzag set.
  • Rebuilding objective: 1/2 is a lower bound on the rebuilding ratio for 2-parity codes, and the Figure 3 construction attains it for k = 3.The minimum average accessed fraction is denoted R(k), with R(3) = 1/2.
  • Construction: The optimal orthogonal-permutation construction has at most m + 1 columns, while its number of rows is exponential in the number of columns.The construction reaches the lower bound asymptotically and has O(m^3) columns in the stated regime.

IV. CODE DUPLICATION

Code duplication increases the number of systematic columns independently of the base code’s row count while preserving near-optimal rebuilding. The section characterizes asymptotic performance through a directed graph on binary vectors.

  • Duplication construction: An s-duplication repeats each base zigzag permutation s times, producing an (sk + 2, sk) MDS code.The duplicated copies may use different parity coefficients to preserve the MDS property.
  • Duplication performance: The duplicated code has rebuilding ratio R(C)(1 + s−1/(sk+1)).The rebuilding algorithm applies the base code’s row-versus-zigzag choices across duplicated columns.
  • Duplication performance: A 2-duplication example has 6 information nodes, 2 parity nodes, and rebuilding ratio 4/7.The erased copy is rebuilt using selected rows and columns together with all elements in its duplicate copy.
  • Duplication performance: Duplication permits arbitrarily many columns independent of row count while retaining an almost optimal ratio.For the optimal base code, the ratio approaches 1/2 as the number of copies grows.
  • Graph characterization: For duplicated Construction 1 codes, asymptotic rebuilding ratio is determined by the density of an induced directed graph on binary-vector labels.An edge indicates that rebuilding one corresponding column can access only half of the information from another.
  • Graph characterization: The standard-basis construction achieves the optimal asymptotic ratio among codes formed from Construction 1 and duplication.The proof bounds the maximum density of the associated binary-vector graph.

2. However

The density proof separates induced subgraphs by vector parity and bounds their directed-edge density by (m−1)/m. This rules out denser constructions under the stated graph model.

  • Density bound: An induced subgraph containing both even and odd vectors has density at most 1.There is exactly one directed edge between each even and odd vertex.
  • Density bound: A maximal-density induced subgraph cannot contain both even and odd vectors, so it consists entirely of one parity class.The mixed-parity case contradicts the target upper bound for m > 2.
  • Density bound: For independent same-parity vectors, the number of vertices is at most m and the edge count yields density no greater than (m−1)/m.The dependent-vector case is reduced to the independent case through a spanning basis and parity embedding.
  • Density bound: The even-vector case is transformed into an odd-vector case in one higher dimension, preserving the relevant graph structure.The embedding maps each v to (1, v).

V. FINITE FIELD SIZE OF A CODE

The section studies field sizes needed to make the constructions MDS, including duplicated optimal codes and a constant-field construction. It gives explicit trade-offs among field size, columns, array size, and rebuilding ratio.

  • Field-size requirements: An s-duplication of the optimal code requires a field of size q ≥ s + 1.Distinct nonzero coefficients are necessary for duplicated information elements sharing row and zigzag sets.
  • Duplicated codes: Construction 3 is an (s(m + 1) + 2, s(m + 1)) MDS code with coefficients arranged by duplication index.The construction is verified to satisfy the required linear-independence conditions.
  • Duplicated codes: For m = 10, duplication factors s = 2 and s = 6 give ratios 0.522 and 0.537, with field sizes 4 and 8, respectively.The corresponding code lengths are 24 and 68.
  • Constant-field construction: The construction generalizes to c-part supports, yielding O(m^c) columns and field size at least 2^c + 1.For odd c, the rebuilding ratio is 1/2 + 1/m for large m.

VI. DECODING OF THE CODES

The section presents erasure-decoding procedures for parity and information-column failures, including recovery of one or two erasures and correction of one column error. The algorithms use row and zigzag parities, syndromes, and permutation-based checks.

  • Erasure Decoding: One erased parity node is rebuilt using row or zigzag parity equations, while an erased information node is recovered by splitting rows between those two mechanisms.The selected rows are determined by the construction's rebuilding sets.
  • Erasure Decoding: Two erasures are handled by direct parity reconstruction, choosing rows or zigzags for mixed failures, and solving coupled equations for two erased information nodes.The two-information-node case distinguishes whether the associated permutations are equal.
  • Column Errors: A syndrome-based algorithm identifies and corrects a single column error by testing transformed syndrome vectors against candidate systematic columns.If neither syndrome is zero, the algorithm computes candidate vectors and subtracts the error syndrome from the identified column.
  • Column Errors: Theorem 17 guarantees that Algorithm 2 corrects one column error because the code is MDS.The proof establishes that the tested vector equals the syndrome exactly for the erroneous column and cannot do so for another column.
  • Complexity: Parallel computation over all row indices gives Algorithm 2 running time O(k), and the optimal-code permutations permit straightforward implementation.The stated implementation benefit relies on permutations that change only one bit.

VII. GENERALIZATION OF THE CODE CONSTRUCTION

The paper generalizes zigzag-code construction to r parity nodes using vector-indexed permutations and rebuilding sets. Orthogonal permutations yield the optimal rebuilding ratio 1/r, while coefficient assignments ensure the resulting arrays are MDS.

  • Generalized Construction: The generalized construction produces an (n,k) MDS array code with r=n−k parity nodes and optimal rebuilding ratio 1/r for a systematic-node erasure.Each systematic node stores an array of size r^m.
  • Generalized Construction: Construction 5 indexes information and zigzag sets with vectors in Z_r^m, assigning rebuilding rows according to vector inner products.The construction defines parity-specific zigzag sets and row subsets for rebuilding each systematic column.
  • Optimal Ratio: Orthogonal permutation families make the rebuilding ratio 1/r, which is optimal under the lower bound.The ratio follows from minimizing overlaps among parity-specific rebuilding sets.
  • Optimal Ratio: Theorem 20 constructs orthogonal permutations and an (m+1+r,m+1) code with optimal ratio 1/r.The construction modifies the zero-vector rebuilding sets and defines the remaining permutations by coordinate shifts.
  • Examples and Limits: Increasing the number of parities from 2 to 3 adds one node while reducing the systematic-column rebuilding ratio from 1/2 to 1/3.For m=2, Figure 5 gives a six-column code with three systematic and three parity nodes, achieving ratio 1/3.
  • Examples and Limits: Any systematic MDS code with optimal ratio, optimal update, and r parities requires exponentially many rows in the number of columns.This constraint follows from the orthogonal-permutation structure.
  • MDS Coefficients: For three parities, a field of size at most 2(m+1) suffices to make the constructed code MDS.For m=2, the example uses the field F7 with primitive element 3.

VIII. REBUILDING MULTIPLE ERASURES

The section studies rebuilding of e erasures for 1 ≤ e ≤ r, first establishing lower bounds and then describing constructions and algorithms intended to attain them.

  • Scope: The analysis covers simultaneous rebuilding of e erased nodes for every 1 ≤ e ≤ r.It separates lower-bound proofs, constructions achieving the bound for systematic nodes, and a subgroup-and-coset generalization.
  • Scope: The exposition initially assumes prime r and computations over F_r, while stating that the results extend with minor changes to arbitrary integer r and Z_r.The assumption is used to simplify the results rather than restrict the claimed generalization.

A. Lower Bounds

This section proves lower bounds on rebuilding ratio and repair bandwidth for simultaneous recovery of e erasures. The bounds apply broadly, and the Construction 5 ratio meets the rebuilding lower bound.

  • Rebuilding Ratio: Theorem 23 states that Construction 5 has rebuilding ratio at least e/r when 1 ≤ e ≤ r systematic nodes are erased.The proof counts zigzag sets and the information accessed in surviving systematic and parity nodes.
  • Model: A general exact-repair model measures node storage, the number of connected surviving nodes, and transmitted information for simultaneous rebuilding of e erased nodes.The model does not require the code to be MDS, systematic, or optimally updated.
  • Repair Bandwidth: Theorem 25 gives a lower bound on repair bandwidth for any reconstructing code with file size M and any 1 ≤ e ≤ r.The bound is expressed using the remainder s = k mod e.
  • Repair Bandwidth: For an MDS code, the per-node transmitted amount satisfies β_e ≥ eM/k.This is the MDS-specific consequence stated with the general lower bound.
  • Connection: The resulting repair-bandwidth lower bound is eM/[k(d−k+e)], matching the rebuilding-ratio lower bound in Theorem 23.The section explicitly identifies the two lower bounds as the same.

B. Rebuilding Algorithms

The rebuilding algorithm selects zigzag equations and accessed elements so erased columns can be reconstructed at the lower-bound ratio e/r. Its conditions use stabilized cosets and linear independence to ensure solvability.

  • Lower bound and target: e/r is the lower bound for rebuilding e erasures, and the algorithm asks whether this ratio is achievable.Theorem 25 supplies the lower bound; subsequent constructions target equality.
  • Access pattern: For e erased columns, each parity node contributes ep/r equations, while the selected zigzag sets determine which surviving elements are accessed.The accessed elements in surviving column j and parity l are those in rows X_l − lv_j.
  • Solvability conditions: Optimal rebuilding requires a set X whose parity-generated permutation groups stabilize it and whose ep zigzag equations are linearly independent.These conditions ensure every erased element is covered and the resulting equations can be solved.
  • Coset construction: When p = r^m, stabilization is characterized by choosing X as a union of cosets of a suitable subspace Z.The coset construction provides a concrete way to satisfy the permutation-invariance condition.
  • Existence and decoding: A sufficiently large field makes the equation matrix invertible, and an explicit subspace X0 enables selecting e cosets that satisfy all three conditions.The determinant argument extends to all erased-node sets when the relevant condition holds universally.
  • Achieving optimality: The resulting construction achieves rebuilding ratio at most the lower bound under the theorem’s vector-separation condition.Corollary 30 states the achieved ratio, while the condition requires vi − ve not to belong to Z for erased columns.

C. Minimum Number of Erasures with Optimal Rebuilding

This section characterizes how many systematic columns can support optimal rebuilding and shows that optimality for one erasure extends monotonically to larger erasure counts.

  • Monotonicity: Optimal rebuilding of e erasures implies property e for the generating vectors, and this property is monotonic for larger subset sizes.Thus a code optimal for e erasures also satisfies the corresponding property for every a with e ≤ a ≤ |S|.
  • Threshold behavior: Some codes exhibit a threshold e* such that optimal rebuilding occurs only when the number of erasures is at least e*.The paper describes this behavior as counterintuitive and surprising.
  • Systematic-column bound: k ≤ m + e bounds the number of systematic columns in a code optimal for e erasures.The bound applies to codes constructed from vectors in F_m^r.
  • Proof idea: The proof derives the bound by showing that a dependent set of generating vectors cannot support optimal rebuilding when too many surviving columns remain.If k − e were at least s, condition (33) would be violated for a suitable erased column.
  • Tightness: The bound is tight for e = 1 and e = 2, including a two-erasure code with k = 4 systematic columns.For e = 1, the construction reaches k = m + 1; for e = 2, vectors 0, e1, e2, e1 + e2 reach the upper bound.

D. Generalized Rebuilding Algorithms

The generalized algorithm chooses a subspace and coset unions to formulate rebuilding as a constrained minimization problem over accessed elements.

  • Generalized method: The generalized rebuilding method selects a subspace Z, then optimizes coset-based sets subject to coverage and solvability constraints.The paper summarizes the procedure as choosing Z first and solving the minimization problem under conditions (39) and (40).
  • Access construction: Accesses are determined by zigzag sets X_l: surviving column j contributes rows X_l − lv_j for parity l.Each X_l is a union of cosets of Z.
  • Constraints: The constraints require enough equations, solvability for each erased column, and uniform element multiplicity across the selected zigzag sets.The union, treated as a multiset, must contain every row exactly e times.
  • Special case: For r = 2 and e = 1, the generalized formulation specializes to the two-parity, single-erasure case.The corresponding constraints are identified as equations (39) and (40).
  • Combinatorial objective: The coset optimization minimizes cycles that are entirely contained in or entirely excluded from the chosen set X.Each v0 + vj induces a permutation on cosets of Z, and the objective counts its relevant cycles.
  • Scope and limitation: For a nonoptimal two-parity code with one erasure, finding the best rebuilding algorithm becomes an interesting combinatorial minimization problem.Choosing a different subspace Z may improve on earlier constructions.

IX. CONCLUDING REMARKS

The paper presents explicit systematic MDS array codes whose rebuilding access matches the information-theoretic lower bound. For two parities, the construction combines optimal updates, a small field, and reduced rebuilding time.

  • Main conclusion: 1/(n − k) is the rebuilding amount for an erased column in the first known explicit systematic constructions with constant redundancy, matching the information-theoretic lower bound.The result applies to codes with n − k equal to some constant.
  • Practical significance: For n − k = 2, zigzag codes are presented as an alternative to RAID-6 with optimal update, a small finite field, and optimal rebuilding access.The paper identifies these properties as relevant to write and computational efficiency.
  • Rebuilding performance: With two parity nodes, the construction cuts current rebuilding time by a factor of two.This claim is stated in the context of RAID-6 storage systems.
  • Open extension: Adding a third parity node can reduce single-node rebuilding access from 1/2 to 1/3, but extending the two-parity construction this way remains open.The third parity is described as additional redundancy rather than protection against three concurrent failures.
  • Future work: A further research direction is the ratio of read accesses during write updates.For two parity nodes, updating one information element requires reading and writing at least three elements.
  • Update optimization: Updating a structured half-array region can avoid reads for computing new parities when the needed information is already known.The observation concerns updating the first information column and rows in the first half of the array.

APPENDIX B PROOF OF THEOREM 6

Appendix B proves Theorem 6 by formalizing rebuilding-set intersections and bounding the rebuilding ratio for (k + 2, k) MDS codes. The argument derives a lower bound of 1/2 and establishes monotonicity of the ratio function.

  • Intersection framework: A rebuilding example has set size 8 and four intersections for column 1.The example uses the rebuilding set S = {R0, R1, Z0, Z1}.
  • Intersection framework: The proof defines rebuilding-set restrictions, intersections, total intersections, and the maximal intersection function h(k) for (k + 2, k) MDS array codes.These definitions support recursive bounds on intersections across subsets of columns.
  • Lower-bound argument: For a systematic-node erasure, the proof accesses p row and zigzag sets and distributes them between the two parity nodes.If x elements are accessed from the first parity and p − x from the second, the proof assumes x ≥ p/2 without loss of generality.
  • Lower-bound argument: Each accessed parity element combines k terms, requiring at least x(k − 1) accesses among the k − 1 surviving systematic nodes.Using x ≥ p/2 yields the intersection bound used to constrain the rebuilding ratio.
  • Conclusion: The resulting rebuilding ratio is no less than 1/2.The appendix also notes that this lower bound can be derived from the repair bandwidth.
  • Conclusion: The ratio function is shown to be nondecreasing using Theorem 34 and the preceding inequality.The proof states that inequality (47) follows from inequality (45).
Loading 1112.0371v1…