Correcting multiple block data loss in a storage array using a combination of a single diagonal parity group and multiple row parity groups

• US 20060242542A1
• Filed: 04/12/2006
• Published: 10/26/2006
• Est. Priority Date: 12/28/2001
• Status: Active Grant

• Current Assignee: Peter F. Corbett, Robert M. English, Steven R. Kleiman
• Original Assignee: Peter F. Corbett, Robert M. English, Steven R. Kleiman
• Inventors: English, Robert M., Kleiman, Steven R., Corbett, Peter F.
• Granted Patent: US 7,437,652 B2
• Time in Patent Office: Days
• 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

Abstract

A method for correcting double failures in a storage array has the following steps. A storage array is organized as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a row parity storage device. Row parity is computed for each row of each sub-array. The row parity of a particular sub-array is stored on a row parity storage device of the particular sub-array. A diagonal parity is computed across the concatenated sub-arrays. A double storage device failure is corrected using both the sub-array row parity and the diagonal parity.

Claims

1. A method for correcting double failures in a storage array, comprising:

organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a row parity storage device;

computing row parity for each row of each sub-array;

storing the row parity of a particular sub-array on a row parity storage device of the particular sub-array;

computing the diagonal parity across the concatenated sub-arrays; and

correcting a double storage device failure two of data disks within a single sub-array using the row parity storage device of that sub-array and the diagonal parity.

2. The method of claim 1, further comprising:

correcting a single storage device failure within a sub-array using the row parity storage device of that sub-array.

3. The method of claim 1, further comprising:

storing the diagonal parity on a single diagonal parity storage device.

4. The method of claim 1, further comprising:

reconstructing the diagonal parity from all row storage devices of all sub-arrays of the array.

5. The method of claim 1, further comprising:

correcting a two storage device failure, where a first failure is in a sub-array and a second failure is in the diagonal parity storage device, by first correcting the sub-array using row parity, and secondly reconstructing the diagonal parity from all row storage devices of all sub-arrays of the array.

6. A method for correcting double failures in a storage array, comprising:

organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a row parity storage device;

computing row parity for each row of each sub-array;

storing the row parity of a particular sub-array on a row parity storage device of the particular sub-array;

computing the diagonal parity across the concatenated sub-arrays; and

correcting a double storage device failure, where a first failure of the double failure is in a data disk of a first sub-array and the second failure of the double failure is in a row parity disk of the same sub-array by using the diagonal parity disk and the row parity of the first sub-array to reconstruct the failed disks.

7. The method of claim 6, further comprising:

correcting a single storage device failure within a sub-array using the row parity storage device of that sub-array.

8. The method of claim 6, further comprising:

storing the diagonal parity on a single diagonal parity storage device.

9. The method of claim 6, further comprising:

reconstructing the diagonal parity from all row storage devices of all sub-arrays of the array.

10. The method of claim 6, further comprising:

correcting a two storage device failure, where a first failure is in a sub-array and a second failure is in the diagonal parity storage device, by first correcting the sub-array using row parity, and secondly reconstructing the diagonal parity from all row storage devices of all sub-arrays of the array.

11. A method for correcting double failures in a storage array, comprising:

organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a row parity storage device;

computing row parity for each row of each sub-array;

storing the row parity of a particular sub-array on a row parity storage device of the particular sub-array;

computing the diagonal parity across the concatenated sub-arrays; and

correcting a double storage device failure, where a first failure of the double failure is in a data disk of a first sub-array and the second failure of the double failure is in the diagonal parity by using the row parity of the first sub-array to restore the data disk and then reconstructing the diagonal parity using all disks of the array.

12. The method of claim 11, further comprising:

correcting a single storage device failure within a sub-array using the row parity storage device of that sub-array.

13. The method of claim 11, further comprising:

storing the diagonal parity on a single diagonal parity storage device.

14. The method of claim 11, further comprising:

reconstructing the diagonal parity from all row storage devices of all sub-arrays of the array.

15. The method of claim 11, further comprising:

correcting a two storage device failure, where a first failure is in a sub-array and a second failure is in the diagonal parity storage device, by first correcting the sub-array using row parity, and secondly reconstructing the diagonal parity from all row storage devices of all sub-arrays of the array.

16. A computer readable media, comprising:

said computer readable media containing instructions for execution on a processor for the practice of a method for correcting double failures in a storage array, the method having the steps of,

organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a row parity storage device;

computing row parity for each row of each sub-array;

storing the row parity of a particular sub-array on a row parity storage device of the particular sub-array;

computing the diagonal parity across the concatenated sub-arrays; and

correcting a double storage device failure within a single sub-array using the row parity storage device of that sub-array and the diagonal parity.

17. A computer readable media, comprising:

said computer readable media containing instructions for execution on a processor for the practice of a method for correcting double failures in a storage array, the method having the steps of,

organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a row parity storage device;

computing row parity for each row of each sub-array;

storing the row parity of a particular sub-array on a row parity storage device of the particular sub-array;

computing the diagonal parity across the concatenated sub-arrays; and

correcting a double storage device failure of two data disks within a single sub-array using the row parity storage device of that sub-array and the diagonal parity.

18. A computer readable media, comprising:

said computer readable media containing instructions for execution on a processor for the practice of a method for correcting double failures in a storage array, the method having the steps of,

organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a row parity storage device;

computing row parity for each row of each sub-array;

storing the row parity of a particular sub-array on a row parity storage device of the particular sub-array;

computing the diagonal parity across the concatenated sub-arrays; and

correcting a double storage device failure, where a first failure of the double failure is in a data disk of a first sub-array and the second failure of the double failure is in a row parity disk of the same sub-array by using the diagonal parity disk and the row parity of the first sub-array to reconstruct the failed disks.

19. A computer readable media, comprising:

said computer readable media containing instructions for execution on a processor for the practice of a method for correcting double failures in a storage array, the method having the steps of,

organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a row parity storage device;

computing row parity for each row of each sub-array;

storing the row parity of a particular sub-array on a row parity storage device of the particular sub-array;

computing the diagonal parity across the concatenated sub-arrays; and

correcting a double storage device failure, where a first failure of the double failure is in a data disk of a first sub-array and the second failure of the double failure is in the diagonal parity by using the row parity of the first sub-array to restore the data disk and then reconstructing the diagonal parity using all disks of the array.

20. A method for correcting multiple failures in a storage array, comprising:

organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a row parity storage device;

computing row parity for each row of each sub-array;

storing the row parity of a particular sub-array on a row parity storage device of the particular sub-array;

computing the diagonal parity across the concatenated sub-arrays and storing the diagonal parity on a diagonal parity device; and

correcting a multiple storage device failure using the row parity devices and the diagonal parity device.

21. The method as in claim 20, further comprising:

correcting a double storage device failure of two of data disks within a single sub-array using the row parity storage device of that sub-array and the diagonal parity.

22. The method as in claim 20, further comprising:

correcting a double storage device failure, where a first failure of the double failure is in a data disk of a first sub-array and the second failure of the double failure is in a row parity disk of the same sub-array by using the diagonal parity disk and the row parity of the first sub-array to reconstruct the failed disks.

23. The method as in claim 20, further comprising:

correcting a double storage device failure, where a first failure of the double failure is in a data disk of a first sub-array and the second failure of the double failure is in the diagonal parity device by using the row parity of the first sub-array to restore the data disk and then reconstructing the diagonal parity using all disks of the array.

24. An apparatus for correcting double failures in a storage array, comprising:

means for organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a row parity storage device;

means for computing row parity for each row of each sub-array;

means for storing the row parity of a particular sub-array on a row parity storage device of the particular sub-array;

means for computing the diagonal parity across the concatenated sub-arrays; and

means for correcting a double storage device failure two of data disks within a single sub-array using the row parity storage device of that sub-array and the diagonal parity.

25. The apparatus of claim 24, further comprising:

means for correcting a single storage device failure within a sub-array using the row parity storage device of that sub-array.

26. The apparatus of claim 24, further comprising:

means for storing the diagonal parity on a single diagonal parity storage device.

27. The apparatus of claim 24, further comprising:

means for reconstructing the diagonal parity from all row storage devices of all sub-arrays of the array.

28. The apparatus of claim 24, further comprising:

means for correcting a two storage device failure, where a first failure is in a sub-array and a second failure is in the diagonal parity storage device, by first correcting the sub-array using row parity, and secondly reconstructing the diagonal parity from all row storage devices of all sub-arrays of the array.

29. A apparatus for correcting double failures in a storage array, comprising:

means for organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a row parity storage device;

means for computing row parity for each row of each sub-array;

means for storing the row parity of a particular sub-array on a row parity storage device of the particular sub-array;

means for computing the diagonal parity across the concatenated sub-arrays; and

means for correcting a double storage device failure, where a first failure of the double failure is in a data disk of a first sub-array and the second failure of the double failure is in a row parity disk of the same sub-array by using the diagonal parity disk and the row parity of the first sub-array to reconstruct the failed disks.

30. The apparatus of claim 29, further comprising:

means for correcting a single storage device failure within a sub-array using the row parity storage device of that sub-array.

31. The apparatus of claim 29, further comprising:

means for storing the diagonal parity on a single diagonal parity storage device.

32. The apparatus of claim 29, further comprising:

means for reconstructing-the diagonal parity from all row storage devices of all sub-arrays of the array.

33. The apparatus of claim 29, further comprising:

means for correcting a two storage device failure, where a first failure is in a sub-array and a second failure is in the diagonal parity storage device, by first correcting the sub-array using row parity, and secondly reconstructing the diagonal parity from all row storage devices of all sub-arrays of the array.

34. A apparatus for correcting double failures in a storage array, comprising:

means for organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a row parity storage device;

means for computing row parity for each row of each sub-array;

means for storing the row parity of a particular sub-array on a row parity storage device of the particular sub-array;

means for computing the diagonal parity across the concatenated sub-arrays; and

means for correcting a double storage device failure, where a first failure of the double failure is in a data disk of a first sub-array and the second failure of the double failure is in the diagonal parity by using the row parity of the first sub-array to restore the data disk and then reconstructing the diagonal parity using all disks of the array.

35. The apparatus of claim 34, further comprising:

means for correcting a single storage device failure within a sub-array using the row parity storage device of that sub-array.

36. The apparatus of claim 34, further comprising:

means for storing the diagonal parity on a single diagonal parity storage device.

37. The apparatus of claim 34, further comprising:

means for reconstructing the diagonal parity from all row storage devices of all sub-arrays of the array.

38. The apparatus of claim 34, further comprising:

means for correcting a two storage device failure, where a first failure is in a sub-array and a second failure is in the diagonal parity storage device, by first correcting the sub-array using row parity, and secondly reconstructing the diagonal parity from all row storage devices of all sub-arrays of the array.

39. A apparatus for correcting multiple failures in a storage array, comprising:

means for organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a row parity storage device;

means for computing row parity for each row of each sub-array;

means for storing the row parity of a particular sub-array on a row parity storage device of the particular sub-array;

means for computing the diagonal parity across the concatenated sub-arrays and storing the diagonal parity on a diagonal parity device, and

means for correcting a multiple storage device failure using the row parity devices and the diagonal parity device.

40. The apparatus as in claim 39, further comprising:

means for correcting a double storage device failure of two of data disks within a single sub-array using the row parity storage device of that sub-array and the diagonal parity.

41. The apparatus as in claim 39, further comprising:

means for correcting a double storage device failure, where a first failure of the double failure is in a data disk of a first sub-array and the second failure of the double failure is in a row parity disk of the same sub-array by using the diagonal parity disk and the row parity of the first sub-array to reconstruct the failed disks.

42. The apparatus as in claim 39, further comprising:

means for correcting a double storage device failure, where a first failure of the double failure is in a data disk of a first sub-array and the second failure of the double failure is in the diagonal parity device by using the row parity of the first sub-array to restore the data disk and then reconstructing the diagonal parity using all disks of the array.