Dual parity RAID wherein no more than N+1 data symbols contribute to any parity symbol

• US 8,335,966 B1
• Filed: 08/03/2009
• Issued: 12/18/2012
• Est. Priority Date: 08/01/2008
• Status: Active Grant

• Current Assignee: Dell Products LP (Dell Technologies Inc.)
• Original Assignee: Dell Products LP (Dell Technologies Inc.)
• Inventors: Lary, Richard F., Hsu-Hung, Damon
• Primary Examiner(s): CHU, GABRIEL L
• Application Number:
  US12/534,533
• Time in Patent Office: 1,233 Days
• Field of Search: None
• US Class Current: 714/770
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations

Abstract

An efficient RAID-6 double parity erasure code scheme. Efficiency is provided by the addition of a single term to a diagonal parity equation. For example, in a five-wide layout (having five physical storage devices) the RAID-6 “parity diagonals” end up with six terms, which are the actual diagonal plus one more data block. As a result, no one data symbol contributes to the erasure code determined from the data symbols, such that no more than n+1 data symbols contribute to any one parity symbol.

Claims

1. An information handling system comprising:

a storage array comprising a plurality, n, of physical storage devices and at least two additional storage devices such that the total number of storage devices in the array is n+2, the storage array for storing data symbols, and for storing parity symbols used in reconstructing the data symbols wherein the storage array is divided into a plurality, k, of sub-arrays S₁, S₂, . . . S_k, each sub-array having the same number of physical storage devices n as the whole array, and each sub-array S_i (1≦

i<

k) having a number m_i of phantom storage devices such that n+m_i is a prime number, and where N is the total size of all k sub-arrays, given as

2. The information handling system of claim 1 wherein the logical combinations of the corresponding data symbols comprise only exclusive-or (XOR) operations.

3. The information handling system of claim 1 wherein at least some of the parity symbols are determined from data symbols located on a diagonal path through the symbol array, with at most one extra term belonging to a set of extra terms forming a “

Knight'"'"'s Tour”

as given by;

d_{(i+1)mod n,(2i+2)mod n} for 0≦

i<

n.

4. The information handling system of claim 3 wherein a first vector of parity symbols for the erasure code is determined from symbols in the data array as

5. The information handling system of claim 1 wherein n is a prime number.

6. The information handling system of claim 1 wherein n is not a prime number, and further wherein m is another number such that n+m is a prime number, and m additional phantom storage devices are assumed to exist during the determination of the erasure code, such that the m phantom storage devices also assumed to never fail and to always contain a predetermined data symbol.

7. The information handling system of claim 1 wherein the total size N of all k sub-arrays is not a prime number.

8. The information handling system of claim 1 wherein the total size N of all k sub-arrays is a power of 2.

9. The information handling system of claim 1 wherein a first vector, the P vector, of parity symbols is determined, if device j survived, as

10. The information handling system of claim 1 wherein if two data storage devices, j and k, have failed, a matrix of constant bitmaps, B_n,D,i (bits indexed by i) is used to derive a parity symbol based on the number of devices n and a difference D in column numbers (modulo n) corresponding to the two failed devices, j and k.

11. The information handling system of claim 10 wherein the difference D is a minimum of (k−

j)mod n and (j−

k)mod n.

12. A method for operating an information handling system comprising:

storing an array of data symbols in a storage array;

storing at least two vectors of parity symbols in the storage array the vectors of parity symbols used in reconstructing the array of data symbols,

the storage array comprising at least n+2 physical storage devices wherein the storage array is divided into a plurality, k, of sub-arrays S₁, S₂, . . . S_k, each sub-array having the same number of physical storage devices n as the whole array, and each sub-array S_i (1≦

i<

k) having a number m_i of phantom storage devices such that n+m_i is a prime number, and where N is the total size of all k sub-arrays, given as

13. The method of claim 12 wherein the logical combinations of the corresponding data symbols comprise only exclusive-or (XOR) operations.

14. The method of claim 12 wherein at least some of the parity symbols are determined from data symbols located on a diagonal path through the symbol array, with at most one extra term belonging to a set of extra terms forming a “

Knight'"'"'s Tour”

as given by;

d_{(i+1)mod n,(2i+2)mod n} for 0≦

i<

n.

15. The method of claim 14 wherein a first vector of parity symbols for the erasure code is determined from symbols in the data array as

16. The method of claim 12 wherein n is a prime number.

17. The method of claim 12 wherein a first array, the P array, of parity symbols is determined, if device j survived, as

18. The method of claim 17 wherein if two data storage devices, j and k, have failed, a matrix of constant bitmaps, B_n,D,i (bits indexed by i) is used to derive a correction based on the number of devices n and a difference D in column numbers (modulo n) corresponding to the two failed devices, j and k.

19. The method of claim 18 wherein the difference D is a minimum of (k−

j)mod n and (j−

k)mod n.