Method and system utilizing quintuple parity to provide fault tolerance
AssigneeArizona Board of Regents on Behalf of the University of Arizona
InventorsMohamad Moussa, Marek Rychlik
Life of this patent
Estimating the term…
Abstract
An error correction and fault tolerance method and system for an array of disks is presented. The array comprises k+5 disks, where k disks store user data and 5 disks store computed parity. The present invention further comprises a method and a system for reconstituting the original content of each of the k+5 disks, when up to 5 disks have been lost, wherein the number of disks at unknown locations is E and the number of disks wherein the location of the disks is known is Z. All combinations of faulty disks wherein Z+2×E≤4 are reconstituted. Some combinations of faulty disks wherein Z+2×E≥5 are either reconstituted, or errors are limited to a small list.
Claims20
A method of encoding data for providing higher fault tolerance to an associated array of disks in subsequent decoding, said array storing a plurality of identically sized logical or physical blocks of data, herein referred to as stripes, said method comprising:
- (a) logically or physically partitioning each stripe into k≥1 identically sized strips, herein referred to as data strips, wherein each data strip stores a portion of the data blocks of an associated stripe;
- (b) numbering the data strips in each stripe with whole numbers 1, 2, 3, . . . , k;
- (c) calculating parity data comprising x parity strips and numbered k+1, k+2, k+3, k+4, . . . k+x, wherein the calculating comprises:
- (i) selecting k non-zero distinct elements of a Galois field GF(2m), denoted by α1, α2, . . . , αk, and
- (ii) calculating parity of each parity strip according to the formula
- P
- j
- ,
- ℓ
- =
- ∑
- i
- =
- 1
- k
- M
- j
- ,
- i
- ·
- D
- i
- ,
- ℓ
- wherein j is a parity strip index, associated with parity strip numbered k+j in the associated strips, and is a stripe index of the associated stripe, and
- (d) extending each stripe of the plurality of stripes into an encoded strips by combining k data strips and the x parity strips and comprising a total of k+x strips to generate a plurality of encoded stripes, wherein the data strips are generated using a systematic coding of encoding data,
- wherein extending each stripe of the plurality of strips by combining k data strips and the x parity stripes provides an enhanced fault tolerance;
- and
- (e) storing the plurality of encoded strips in the array of disks such that each strip of the associated encoded stripe is stored in a unique disk in the array of disks, wherein each disk stores at least one strip from each encoded stripe, and wherein an order of the strips in each stripe can be optionally changed prior to storing to implement load balancing.
A method of encoding data logically or physically partitioned into a plurality of identically sized data blocks called stripes, said method comprising:
- (a) logically or physically partitioning each stripe into k≥1 identically sized strips, herein referred to as data strips, wherein each data strip stores a portion of the data blocks of an associated stripe;
- (b) numbering the data strips in each stripe with whole numbers 1, 2, 3, . . . , k;
- (c) calculating parity data comprising five parity strips, distinct from the data strips, and numbered k+1, k+2, k+3, k+4, . . . , k+x, wherein the calculating comprises:
- (i) selecting k non-zero distinct elements of a Galois field GF(2m), denoted by α1, α2, . . . , αk;
- and
- (ii) calculating parity of each parity strip according to the formula
- P
- j
- ,
- ℓ
- =
- ∑
- i
- =
- 1
- k
- M
- j
- ,
- i
- ·
- D
- i
- ,
- ℓ
- wherein j is a parity strip index, associated with parity strip numbered k+j in the associated strips, and is a stripe index of the associated stripe, and
- (d) extending each stripe of the plurality of stripes into an encoded stripe by combining k data strips and the five parity strips and comprising a total of k+x strips to generate a plurality of encoded stripes, wherein the data strips are unmodified and generated using a systematic coding of encoding data.
A system of encoding data for providing higher fault tolerance to an associated array of disks in subsequent decoding, said array storing a plurality of identically sized logical or physical blocks of data, herein referred to as stripes, the system comprising:
- (i) one or more processors, and (ii) a memory coupled to the one or more processors, the memory to store computer-executable instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising:
- (a) logically or physically partitioning each stripe into k≥1 identically sized strips, herein referred to as data strips, wherein each data strip stores a portion of the data blocks of an associated stripe;
- (b) numbering the data strips in each stripe with whole numbers 1, 2, 3, . . . , k;
- (c) calculating parity data comprising five parity strips, distinct from the data strips, and numbered k+1, k+2, k+3, k+4 and k+x, wherein the calculating comprises:
- (i) selecting k non-zero distinct elements of a Galois field GF(2m), denoted by α1, α2, . . . , αk;
- and
- (ii) calculating parity of each parity strip according to the formula
- P
- j
- ,
- ℓ
- =
- ∑
- i
- =
- 1
- k
- M
- j
- ,
- i
- ·
- D
- i
- ,
- ℓ
- wherein j is a parity strip index, associated with parity strip numbered k+j in the associated strips, and is a stripe index of the associated stripe, and
- (d) extending each stripe of the plurality of stripes into an encoded stripe by combining k data strips and the five parity strips and comprising a total of k+x strips to generate a plurality of encoded stripes, wherein the data strips are unmodified and generated using a systematic coding of encoding data;
- and
- (e) storing the plurality of encoded stripes in the array of disks such that each strip of the associated encoded stripe is stored in a unique disk in the array of disks, wherein each disk stores one strip from each encoded stripe, and wherein an order of the strips in each stripe can be optionally changed prior to storing to implement load balancing,
- wherein the step of extending each stripe of the plurality of stripes by combining k data strips and the five parity stripes provides an enhanced fault tolerance.
Dependencies are inferred from the claim text.