PaperlayerView exact revision on arXiv

Source-linked AI summary

Partial-MDS Codes and their Application to RAID Type of Architectures

Mario Blaum, James Lee Hafner, Steven Hetzler

arXiv:1205.0997v2cs.IT

TL;DR

SSDs combine catastrophic device failures with silent hard errors, while conventional RAID 5 or RAID 6 can be insufficient or wasteful. The paper develops PMDS codes whose two-dimensional structure targets both failure types and gives constructions and conditions for obtaining PMDS codes. It presents application-relevant codes and necessary and sufficient conditions for an optimality criterion.

  • Problem

    SSD arrays combine catastrophic device failures with silent hard sector errors, creating protection needs that RAID 5 may not meet and RAID 6 may address inefficiently.

  • Method

    The paper develops two-dimensional PMDS code constructions with row-wise MDS protection and additional global parity, analyzed through parity-check matrices and PMDS conditions.

  • Results

    The paper presents application-relevant PMDS codes and necessary and sufficient conditions for codes satisfying an optimality criterion.

  • Takeaways & Limitations

    PMDS codes provide a code family for flash-array architectures in which hard errors coexist with catastrophic device failures.

  • Takeaways & Limitations

    The general construction is not PMDS for all parameters; its status depends on the parameters and the polynomial defining the ring or field.

Abstract

from arXiv · show

A family of codes with a natural two-dimensional structure is presented, inspired by an application of RAID type of architectures whose units are solid state drives (SSDs). Arrays of SSDs behave differently to arrays of hard disk drives (HDDs), since hard errors in sectors are common and traditional RAID approaches (like RAID 5 or RAID 6) may be either insufficient or excessive. An efficient solution to this problem is given by the new codes presented, called partial-MDS (PMDS) codes.

1 Introduction

SSDs combine catastrophic device failures with silent hard sector errors, making RAID 5 insufficient and RAID 6 potentially excessive. The paper proposes PMDS codes to handle both failure types with intermediate protection tailored to SSD writes.

  • Failure model: SSDs experience catastrophic failures and increasingly likely hard sector errors as devices age and accumulate writes.Hard errors may remain silent until affected sectors are accessed.
  • Failure model: RAID 5 cannot recover when a failed device’s stripe also contains a hard error, because two sectors in that stripe are lost.RAID 5 reconstructs a failed device by XORing corresponding surviving sectors.
  • Motivation: RAID 6 protects against two erased sectors in a stripe but requires an additional whole parity device and can still fail with two hard errors plus a device failure.The paper seeks protection between RAID 5 and RAID 6 without dedicating a whole second SSD to parity.
  • SSD-aware design: SSD writes erase and rewrite groups of m sectors, so the array is modeled as independent m × n blocks whose parity is recomputed per block.Each new write may contain one or more such blocks.
  • Contribution: PMDS codes are introduced to correct catastrophic failures and hard errors simultaneously in SSD arrays.The construction is designed around the mixed failure environment created by SSD storage behavior.

2 Partial-MDS codes

The paper defines PMDS codes through a two-dimensional array structure: each row is locally MDS-protected, while extra global parities address erasures distributed across rows. The motivating example targets one failed column and two additional hard errors.

  • Array structure: An m × n array uses r parity entries per stripe so that any r erasures in each row can be recovered.Each row therefore forms an [n, n−r, r + 1] MDS code.
  • Array structure: The construction adds s global parities affecting all mn array entries, illustrated by a 4 × 5 array with r = 1 and s = 2.The example places both global parities in the last stripe.
  • Correction goal: A PMDS code must correct one catastrophic column failure together with up to two hard errors located anywhere in the array.The two hard errors may occur in the same stripe or in different stripes.
  • Design rationale: Using one large MDS code could protect the entire array, but its complexity grows with typical array sizes such as m = 16 or m = 32.For the 4 × 5 example, this would require a [20, 14, 7] MDS code with six parity symbols.
  • Formal definition: An (r; s1, s2, …, st)-erasure correcting code recovers up to sj + r erasures in each selected row ij, with the sj values summing to s.A PMDS code satisfies this correction property for every allowed partition of the global-parity budget.
  • Formal definition: The paper constructs parity-check matrices of size (mr + s) × mn and emphasizes the practically important case r = 1, which extends RAID 5.The general construction is followed by analyses of when the resulting codes are PMDS.

3 Code Construction

The paper constructs codes from binary polynomials modulo an irreducible polynomial or a prime-length polynomial, using parity-check matrices and syndrome-based recovery. Whether the construction is PMDS depends on its parameters and defining polynomial.

  • Algebraic setting: Array entries are modeled in a polynomial-defined ring; when the defining polynomial is irreducible, the ring is GF(2^b).Multiplication is polynomial multiplication reduced modulo a degree-b polynomial.
  • Algebraic setting: The exponent e(f(x)) is the smallest positive ℓ such that a root α of f(x) satisfies α^ℓ = 1.For primitive f(x), the exponent is 2^b − 1.
  • Algebraic setting: For f(x) = M_p(x), the resulting structure is generally a ring rather than a field, unless M_p(x) is irreducible.This family includes the polynomial setting used for Blaum–Roth codes.
  • General construction: The construction defines C(m, n, r, s; f(x)) through an (mr + s) × mn parity-check matrix over binary polynomials modulo f(x), subject to mn ≤ e(f(x)).The matrices are built from structured component matrices H(n, r, i, j).
  • PMDS conditions: The construction is not PMDS for all parameters: the property depends on the selected parameters and the polynomial defining the ring or field.The paper therefore studies conditions that determine PMDS status, especially for r = 1.
  • Decoding: Recovery first computes mr + s syndromes and then solves a linear system based on the parity-check matrix when a solution exists.This procedure is used to retrieve erased entries.

4 The case r = 1

For r = 1, the paper characterizes when the construction C(m, n, 1, s; f(x)) is PMDS through invertibility conditions for specified erasure patterns. It then reduces these conditions to odd erasure counts and gives a PMDS family when f(x) = Mp(x) is irreducible.

  • General characterization: The construction C(m, n, 1, s; f(x)) is PMDS exactly when the stated conditions hold for all admissible distributed erasure patterns.These conditions arise from requiring the associated syndrome system, and hence its relevant matrix, to be invertible.
  • General characterization: The PMDS test can be reduced to patterns in which every s_j is odd.For even s_j, the corresponding erasure parameter is reduced by one while preserving the relevant erasure-correction property.
  • General characterization: Theorem 4.1 states that PMDS status is determined by condition (15) for every odd tuple (s_1, s_2, ..., s_t) summing to s and every admissible row and column choice.The theorem converts the preceding lemmas into a direct set of conditions to check.
  • PMDS family: The general theorem supplies verification conditions, whereas the irreducible Mp(x) result supplies an explicit family of PMDS codes.The paper notes that the general conditions alone do not provide a family.
  • PMDS family: If Mp(x) is irreducible, then C(m, n, 1, s; Mp(x)) is PMDS.The result assumes mn < e(Mp(x)) = p; irreducibility is equivalent to 2 being primitive in GF(p).

5 Special cases

This section characterizes PMDS conditions for several special code families and examines their decoding and parameter choices. It shows how PMDS behavior changes as additional erasure patterns and parity structures are considered.

  • 5.1 The case C(m, n, 1, 1; f(x)): C(m, n, 1, 1; f(x)) is always PMDS.This result underpins subsequent constructions for larger values of s.
  • 5.2 The case C(m, n, 1, 2; f(x)): Theorem 5.1 gives necessary and sufficient conditions for C(m, n, 1, 2; f(x)) to be PMDS.Decoding requires solving linear systems whose determinants can involve Vandermonde factors and polynomial expressions modulo f(x).
  • 5.3 The case C(m, n, 1, 3; f(x)): Codes C(m, n, 1, 3; f(x)) are PMDS only when C(m, n, 1, 2; f(x)) is PMDS and additional conditions hold.The additional condition is restrictive for many finite-field examples, although several codes over Mp(x) satisfy it.
  • 5.4 The case C(m, n, 1, 4; f(x)): Code C(m, n, 1, 4; f(x)) is PMDS exactly when C(m, n, 1, 3; f(x)) is PMDS and a further polynomial condition is satisfied.Separately, the paper shows that selected C(m, n, 1, 4; Mp(x)) codes are both (1;4)- and (1;2,2)-erasure correcting.
  • 5.5 The case C(m, n, r, 1; f(x)): Theorem 5.4 relates PMDS status for C(m, n, r, 1; f(x)) to the preceding value of r, with an extra condition when r is odd.In particular, C(m, n, 2, 1; f(x)) is PMDS because C(m, n, 1, 1; f(x)) is PMDS.
  • 5.6 The case C(m, n, 2, 2; f(x)): Theorem 5.5 characterizes when C(m, n, 2, 2; f(x)) is PMDS through PMDS status of C(m, n, 3, 1; f(x)) and an invertibility condition.The condition is stated for pairs of triples of column indices.

6 An alternative construction

This section introduces an alternative construction of PMDS codes using a different parity-check matrix structure. The resulting family is unrestricted for the single-local-parity case, while higher-parity cases retain explicit algebraic conditions and open questions.

  • 6.1 The construction: Construction 6.1 defines an alternative code family C(1)(m, n, r, s; f(x)) over binary polynomials modulo f(x).The construction uses a parity-check matrix built from component matrices H(1)(n, r, i, j).
  • 6.1 The case C(1)(m, n, r, 1; f(x)): C(1)(m, n, r, 1; f(x)) is PMDS for all stated parameters.The proof uses invertibility of a Vandermonde determinant.
  • 6.1 The case C(1)(m, n, r, 1; f(x)): For r ≥2, C(1)(m, n, r, 1; f(x)) is preferable to C(m, n, r, 1; f(x)) because it is PMDS without restrictions.The comparison is based on Theorems 5.4 and 6.1.
  • 6.2 The case C(1)(m, n, 1, 3; f(x)): C(1)(m, n, 1, 3; f(x)) is PMDS under stated matrix-invertibility conditions.The conditions involve one matrix for two distinct row indices and another for three row indices.
  • 6.2 The case C(1)(m, n, 1, 3; f(x)): For 19 ≤p ≤227, C(1)(m, n, 1, 3; Mp(x)) is PMDS when Mp(x) is irreducible.The result follows from testing the relevant matrices for primes where 2 is primitive in GF(p).
  • 6.2 The case C(1)(m, n, 1, 3; f(x)): Whether C(1)(m, n, 1, 3; Mp(x)) is PMDS for every irreducible Mp(x) remains an open problem.The paper also reports parameter instances where the original and alternative constructions differ in PMDS status.

7 A Simplified Construction

The simplified construction provides alternative codes with smaller field or ring requirements while preserving PMDS behavior in key cases. It corrects two pairs of erasures in different rows but trades away correction of three erasures in one row.

  • Construction: The construction C(2)(m, n, 1, 2; f(x)) is an alternative to earlier codes and uses a smaller finite field or ring.The construction is defined over binary polynomials modulo an irreducible f(x) or f(x) = Mp(x), subject to max{m, n} ≤ e(f(x)).
  • Erasure correction: C(2)(m, n, 1, 2; f(x)) corrects two pairs of erasures in different rows but not three erasures in the same row.This is the stated tradeoff for reducing the field or ring size.
  • Construction: C(2)(m, n, 1, 1; f(x)) is formed from the first m + 1 rows of the parity-check matrix for C(2)(m, n, 1, 2; f(x)).
  • PMDS conditions: C(2)(m, n, 1, 1; g(x)) is PMDS under less stringent polynomial conditions than C(m, n, 1, 1; f(x)).For the examples given, p = 5 suffices for the simplified codes where p = 17 is needed for the corresponding original codes.
  • Erasure correction: C(2)(m, n, 1, 2; f(x)) is (1;1,1)-erasure correcting but is not (1;2)-erasure correcting, and increasing s beyond 2 offers little gain in the mixed failure setting.The construction can be extended to other horizontal and vertical erasure combinations, but those extensions are omitted.
  • Applications: For max{m, n} ≤15, the simplified construction can use GF(2^4), while the comparable PMDS construction requires GF(2^16) when n = 15.Using GF(2^5) with a primitive polynomial permits m = 16 in the simplified construction.

8 Probability of Data Loss After One Disk Failure

The section compares data-loss probabilities after one catastrophic device failure for (1;1,1)-erasure correcting and (1;2) PMDS codes. With equal parity-entry redundancy, the PMDS code tolerates more hard-error patterns and can provide lower data-loss probability as SSD error rates rise.

  • Comparison: The analysis compares (1;2) PMDS and (1;1,1)-erasure correcting codes after one catastrophic device failure.Both codes are evaluated with the same redundancy in the stated comparison.
  • Failure patterns: A (1;2) PMDS code loses data after three hard errors in one stripe, whereas a (1;1,1)-erasure correcting code loses data after two.With one failed device, one hard error in each of at least three different stripes also causes data loss.
  • Probability analysis: For m = 16 and 32G devices, (1;1,1)-erasure-correcting loss probability is dominated by P_m,2,1, while (1;2) PMDS loss probability is dominated by P_m,1,3.
  • Comparison: Increasing s does not materially change the data-loss probability of a (1;1,1, ..., 1)-erasure correcting code when a whole device has failed.For s = m, the code corresponds to RAID 6, which tolerates a second device failure but loses data if hard errors occur with two device failures.
  • Results: At p = .0007, the cited miscorrection probability is 7.8E-5, while at p = .0008 the (1;2) PMDS data-loss probability is 6.3E-6.The latter is reported as more than an order of magnitude better than the (1;1,1)-erasure correcting code and permits further degradation of p.

9 Conclusions

The paper presents two code constructions for flash arrays with coexisting hard errors and catastrophic device failures. It also gives necessary and sufficient conditions for codes meeting an optimality criterion.

  • Conclusions: Two code constructions are presented for flash-array architectures with hard errors and catastrophic device failures.
  • Conclusions: Necessary and sufficient conditions are given for codes satisfying an optimality criterion.

A Appendix

The appendix proves a determinant result for a matrix built from distinct elements in a characteristic-2 field or ring. The proof proceeds by induction and bounds the zeros of an associated polynomial.

  • Appendix: The appendix considers an s × s matrix whose parameters γ0, γ1, ..., γs−1 are distinct elements of a characteristic-2 field or ring.
  • Proof: The determinant result is proved by induction on s, beginning with the case s = 1.
  • Proof: The associated polynomial h(x) has degree 2s−1 and therefore at most 2s−1 zeros.
  • Proof: Linearity of the square operation in characteristic 2 is used to express the relevant quantity through subset terms.
Loading 1205.0997v2…