Technique for correcting multiple storage device failures in a storage array

• US 7,080,278 B1
• Filed: 03/08/2002
• Issued: 07/18/2006
• Est. Priority Date: 03/08/2002
• Status: Active Grant

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: English, Robert M., Kleiman, Steven R., Corbett, Peter F.
• Primary Examiner(s): Beausoliel, Robert
• Assistant Examiner(s): GUYTON, PHILIP A
• Application Number:
  US10/094,086
• Time in Patent Office: 1,593 Days
• Field of Search: 714/6, 714/804
• US Class Current: 714/6.24
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

A technique efficiently corrects multiple storage device failures in a storage array. The storage array comprises a plurality of concatenated sub-arrays, wherein each sub-array includes a set of data storage devices and a local parity storage device that stores values used to correct a failure of a single device within a row of blocks, e.g., a row parity set, in the sub-array. Each sub-array is assigned diagonal parity sets identically, as if it were the only one present using a double failure protection encoding method. The array further includes a single, global parity storage device holding diagonal parity computed by logically adding together equivalent diagonal parity sets in each of the sub-arrays.

Claims

1. A system adapted to correct multiple storage device failures in a storage array, the system comprising:

a storage array having a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a local parity storage device, each sub-array assigned diagonal parity sets identically as if it were the only one present using a double failure protection encoding method, the array further including a global parity storage device holding diagonal parity computed by logically combining together a plurality of equivalent diagonal parity sets each from a differing one of the sub-arrays, wherein the global parity storage device is adapted to be used in connection with the local parity storage device of each sub-array to correct a double failure within the sub-array.

2. The system of claim 1 wherein the local parity storage device is configured to store values encoded with a single device error correction method used to correct a failure of a single device within a row parity set in the sub-array.

3. The system of claim 2 wherein the row parity set is a row of blocks.

4. The system of claim 2 wherein the encoding method that protects against a second device failure is independent of the single device error correction method.

5. The system of claim 4 wherein the double failure protection encoding method is row-diagonal encoding.

6. The system of claim 4 wherein the single device error correction method is row parity.

7. The system of claim 1 wherein each sub-array is organized as a concentrated parity device array.

8. The system of claim 1 wherein each sub-array is organized as a distributed parity device array.

9. The system of claim 1 wherein the storage devices are video tape, magnetic tape, optical, DVD, bubble memory, electronic random access memory or magnetic disk devices.

10. A method for encoding data for correction of double failures in a storage array, the method comprising 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 local parity storage device, the storage array further including a global parity storage device for holding diagonal parity;

assigning diagonal parity sets to each sub-array identically as if the sub-array were the only one present using a double failure protection encoding method; and

computing the diagonal parity by logically combining together a plurality of equivalent diagonal parity sets each from a differing one of the sub-arrays.

11. The method of claim 10 further comprising correcting storage device failure within the array using the local parity storage device associated with each sub-array and the global parity storage device associated with the storage array.

12. The method of claim 11 wherein the step of computing comprises the step of computing diagonal parity blocks along the diagonal parity sets of each sub-array.

20. The method of claim 10 wherein the step of organizing comprises the step of organizing each sub-array as a concentrated parity device array.

21. The method of claim 10 wherein the step of organizing comprises the step of organizing each sub-array as a distributed parity device array.

22. The method of claim 10 wherein the storage devices are video tape, magnetic tape, optical, DVD, bubble memory, electronic random access memory or magnetic disk devices.

13. A method for encoding data for correction of double failures in a storage array, the method comprising 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 local parity storage device, the storage array further including a global parity storage device for holding diagonal parity;

assigning diagonal parity sets to each sub-array identically as if the sub-array were the only one present using a double failure protection encoding method;

computing the diagonal parity by logically combining together equivalent diagonal parity sets in each of the sub-arrays and computing diagonal parity blocks along the diagonal parity sets of each sub-array, and logically combining the computed diagonal parity blocks of corresponding diagonal parity sets of the sub-arrays for storage as the diagonal parity on the global parity storage device; and

correcting storage device failure within the array using the local parity storage device associated with each sub-array and the global parity storage device associated with the storage array.

14. The method of claim 13 wherein the step of logically combining comprises the step of using exclusive OR operations to compute the diagonal parity.

15. The method of claim 13 further comprising reconstructing the computed diagonal parity blocks of any sub-array with an error by subtracting the combined diagonal parity blocks of the other sub-arrays from the diagonal parity stored on the global parity storage device.

16. The method of claim 13 further comprising the step of storing parity values encoded with a single device error correction method on the local parity storage device of each sub-array.

17. The method of claim 16 further comprising correcting a failure of a single device within a row of blocks in each sub-array using the single device error correction method, where the single device correction method is accomplished using a plurality of local row parity.

18. The method of claim 17 wherein the encoding method that protects against a second device failure is independent of the single device error correction method.

19. The method of claim 18 wherein the single device error correction method is row-oriented and the rows of blocks in each sub-array are independent.

72. The method of claim 13 wherein the step of correcting comprises the step of reconstructing a failed diagonal parity block by logically combining equivalent diagonal parity sets in all sub-arrays.

73. The method of claim 13 wherein the step of correcting comprises the step of reconstructing failed row parity blocks from data disks of the sub-array and failed diagonal parity blocks from equivalent diagonal parity sets in all sub-arrays.

23. Apparatus for correcting double failures in a storage array, the apparatus 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 local parity storage device, the storage array further including a global parity storage device for holding diagonal parity;

means for assigning diagonal parity sets to each sub-array identically as if the sub-array were the only one present using a double failure protection encoding method;

means for computing the diagonal parity using parity encoding operations that logically combine together a plurality of equivalent diagonal parity sets each from a differing one of the sub-arrays; and

means for correcting storage device failure within the array using parity decoding operations on the local parity storage device associated with each sub-array and the global parity storage device associated with the storage array.

24. The apparatus of claim 23 wherein the means for organizing comprises means for organizing each sub-array as a concentrated parity device array.

25. The apparatus of claim 23 wherein the means for organizing comprises means for organizing each sub-array as a distributed parity device array.

26. The apparatus of claim 23 wherein the storage devices are video tape, magnetic tape, optical, DVD, bubble memory, electronic random access memory or magnetic disk devices.

27. The apparatus of claim 23 wherein the parity encoding and decoding operations are performed by special purpose hardware, such as a field programmable gate array or an application specific integrated circuit.

28. A computer readable medium containing executable program instructions for correcting double failures in a storage array, the executable program instructions comprising program instructions for:

organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a local parity storage device, the storage array further including a global parity storage device for holding diagonal parity;

assigning diagonal parity sets to each sub-array identically as if the sub-array were the only one present using a double failure protection encoding method;

computing the diagonal parity by logically combining together a plurality of equivalent diagonal parity sets each from a differing one of the sub-arrays; and

correcting storage device failure within the array using the local parity storage device associated with each sub-array and the global parity storage device associated with the storage array.

29. The computer readable medium of claim 28 wherein the program instructions for computing comprise the program instructions for computing diagonal parity blocks along the diagonal parity sets of each sub-array.

32. The computer readable medium of claim 28 wherein the executable instructions are performed by a general or special purpose computer, including an embedded microprocessor.

30. A computer readable medium containing executable program instructions for correcting double failures in a storage array, the executable program instructions comprising program instructions for:

organizing the storage array as a plurality of concatenated sub-arrays, each sub-array including a set of data storage devices and a local parity storage device, the storage array further including a global parity storage device for holding diagonal parity;

assigning diagonal parity sets to each sub-array identically as if the sub-array were the only one present using a double failure protection encoding method;

computing the diagonal parity by logically combining together equivalent diagonal parity sets in each of the sub-arrays, computing diagonal parity blocks along the diagonal parity sets of each sub-array, and logically combining the computed diagonal parity blocks of corresponding diagonal parity sets of the sub-arrays for storage as the diagonal parity on the global parity storage device; and

correcting storage device failure within the array using the local parity storage device associated with each sub-array and the global parity storage device associated with the storage array.

31. The computer readable medium of claim 30 wherein the program instruction for correcting comprises the program instruction for reconstructing the computed diagonal parity blocks of any sub-array by subtracting the combined diagonal parity blocks of the other sub-arrays from the diagonal parity stored on the global parity storage device.

33. A system adapted to correct multiple storage element failures in a storage array, the system comprising:

a storage array having a plurality of concatenated sub-arrays, each sub-array including a set of data storage elements and a local parity storage element configured to store values encoded with a single element error correction method used to correct a failure of a single element within a row parity set in the sub-array, each sub-array assigned diagonal parity sets identically as if it were the only one present using a double failure protection encoding method, the array further including a global parity storage element holding diagonal parity computed by logically combining together a plurality of equivalent diagonal parity sets such that each diagonal parity set is logically combined with at least one other equivalent diagonal parity set from a differing one of the sub-arrays, wherein the global parity storage element is used in connection with the local parity storage element of each sub-array to correct a double failure within the sub-array.

34. The system of claim 33 wherein the storage elements are packets and wherein logically combining together comprises use of exclusive OR (XOR) operations.

35. The system of claim 34 wherein p is a prime number and wherein every pth packet contains a row parity XOR of previous p−

1 packets.

36. The system of claim 35 wherein a packet containing diagonal parity is sent after every n sets of p packets.

37. The system of claim 36 wherein, if one packet is dropped in a set of p, the packet is recoverable using row parity and if two packets are dropped in one set of p, the packets are recovered using row and diagonal parity.

38. A method for correcting double failures within data adapted for transmission over a communication medium, the method comprising the steps of:

dividing the data into packets for transmission over the communications medium;

organizing the packets into n sub-groups of p packets, wherein p is a smallest prime number that is at least as large as a number of packets in any sub-group of packets and wherein each sub-group of packets includes data packets and a local parity packet configured to store values encoded with a single error correction method used to correct a failure of a single packet in the sub-group;

assigning diagonal parity sets to each sub-group identically as if it were the only one present using a double failure protection encoding method; and

providing a global parity packet with the group of packets, the global parity packet holding diagonal parity computed by logically combining equivalent diagonal parity sets in each of the sub-groups, wherein the global parity packet is used in connection with the local parity packet of each sub-group to correct a double failure within the sub-array.

39. The method of claim 38 wherein logically combining together comprises use of exclusive OR (XOR) operations and wherein every pth packet contains a row parity XOR of previous p−

1 packets.

40. The method of claim 39 wherein the step of providing comprises the step of sending the global parity packet containing diagonal parity after every n sub-group of p packets.

41. The method of claim 40 further comprising the steps of:

if one packet is dropped in a set of p, recovering the packet using row parity; and

if two packets are dropped in one set of p, recovering the packets using row and diagonal parity.

42. A method for encoding data for correction of double failures in a storage array, comprising:

organizing the storage array as a plurality of sub-arrays, each sub-array including a set of data storage devices and a plurality of local parity storage blocks, each of the plurality of local storage blocks storing parity information for a corresponding sub-array;

assigning diagonal parity sets to each sub-array as if the sub-array were the only one present using a double failure protection encoding method;

including a plurality of global diagonal parity storage blocks, the global diagonal parity storage blocks holding global diagonal parity; and

computing the global diagonal parity by logically combining together a plurality of equivalent diagonal parity sets such that each diagonal parity set is logically combined with at least one other equivalent diagonal parity set from a differing one the sub-arrays.

43. The method of claim 42, further comprising:

storing the plurality of global diagonal parity storage blocks in a global parity storage device.

44. The method of claim 42, further comprising:

logically combining the computed diagonal parity blocks of corresponding diagonal parity sets of the sub-arrays for storage as the diagonal parity on the plurality of global parity storage blocks.

45. The method of claim 44 wherein the step of logically combining comprises the step of using exclusive OR operations to compute the diagonal parity.

46. The method of claim 45 further comprising reconstructing the computed diagonal parity blocks of any sub-array with an error by subtracting the combined diagonal parity blocks of the other sub-arrays from the diagonal parity stored on the global parity storage device.

47. The method of claim 42, further comprising:

distributing the plurality of global diagonal parity storage blocks across the storage array.

48. The method of claim 42, further comprising:

storing the plurality of local parity storage blocks in a local parity storage device.

49. The method of claim 42, further comprising:

distributing the plurality of local parity storage blocks across the storage array.

50. An apparatus for encoding data for correction of double failures in a storage array, comprising:

means for organizing the storage array as a plurality of sub-arrays, each sub-array including a set of data storage devices and a plurality of local parity storage blocks, each of the plurality of local storage blocks storing parity information for a corresponding sub-array;

means for assigning diagonal parity sets to each sub-array as if the sub-array were the only one present using a double failure protection encoding method;

means for including a plurality of global diagonal parity storage blocks, the global diagonal parity storage blocks holding global diagonal parity; and

means for computing the global diagonal parity by logically combining together a plurality of equivalent diagonal parity sets such that each diagonal parity set is logically combined with at least one other equivalent diagonal parity set from a differing one of the sub-arrays.

51. The apparatus of claim 50, further comprising:

means for storing the plurality of global diagonal parity storage blocks in a global parity storage device.

52. The apparatus of claim 50, further comprising:

means for logically combining the computed diagonal parity blocks of corresponding diagonal parity sets of the sub-arrays for storage as the diagonal parity on the plurality of global diagonal parity storage blocks.

53. The apparatus of claim 52 wherein the step of logically combining comprises the means for using exclusive OR operations to compute the diagonal parity.

54. The apparatus of claim 53 further comprising:

means for reconstructing the computed diagonal parity blocks of any sub-array with an error by subtracting the combined diagonal parity blocks of the other sub-arrays from the diagonal parity stored on the global parity storage device.

55. The apparatus of claim 50, further comprising:

means for distributing the plurality of global diagonal parity storage blocks across the storage array.

56. The apparatus of claim 50, further comprising:

means for storing the plurality of local parity storage blocks in a local parity storage device.

57. The apparatus of claim 50, further comprising:

means for distributing the plurality of local parity storage blocks across the storage array.

58. A system for encoding data for correction of double failures, comprising:

a storage array organized as a plurality of sub-arrays, each sub-array including a set of data storage devices and a plurality of local parity storage blocks, each of the local parity storage blocks storing parity information for a corresponding sub-array;

a storage operating system within a storage system to assign diagonal parity sets to each sub-array as if the sub-array were the only one present using a double failure protection encoding method;

a plurality of global diagonal parity storage blocks within the storage array, the global diagonal parity storage blocks holding global diagonal parity; and

the storage operating system computing the global diagonal parity by logically combining together equivalent diagonal parity sets in each of the sub-arrays such that each diagonal parity set is logically combined with at least one other equivalent diagonal parity set from a differing one of the sub-arrays.

59. The system of claim 58, further comprising:

a global parity storage device for storing the plurality of global diagonal parity storage blocks.

60. The system of claim 58, further comprising:

the operating system logically combines the computed diagonal parity blocks of corresponding diagonal parity sets of the sub-arrays for storage as the diagonal parity on the plurality of global diagonal parity storage blocks.

61. The system of claim 60 wherein the operating system logically combines using exclusive OR operations to compute the diagonal parity.

62. The system of claim 61 wherein the operating system corrects error by reconstructing the computed diagonal parity blocks of any sub-array with an error by subtracting the combined diagonal parity blocks of the other sub-arrays from the diagonal parity stored on the global parity storage device.

63. The system of claim 58, further comprising:

the storage operating system for distributing the plurality of global diagonal parity storage blocks across the storage array.

64. The system of claim 58, further comprising:

a local parity storage device for storing the plurality of local parity storage blocks.

65. The system of claim 58, further comprising:

the storage operating system for distributing the plurality of local parity storage blocks across the storage array.

66. A computer readable media, comprising:

said computer readable media having instructions written thereon for execution on a processor for the practice of the method of encoding data for correction of double failures in a storage array, comprising;

organizing the storage array as a plurality of sub-arrays, each sub-array including a set of data storage devices and a plurality of local parity storage blocks, each of the plurality of local storage blocks storing parity information for a corresponding sub-array;

assigning diagonal parity sets to each sub-array as if the sub-array were the only one present using a double failure protection encoding method;

including a plurality of global diagonal parity storage blocks, the global diagonal parity storage blocks holding global diagonal parity; and

computing the global diagonal parity by logically combining together equivalent diagonal parity sets in each of the sub-arrays such that each diagonal parity set is logically combined with at least one other equivalent diagonal parity set from a differing one of the sub-arrays.

67. A method for correcting double failures within data adapted for transmission over a communication medium, the method comprising the steps of:

dividing the data into packets for transmission over the communications medium;

organizing the packets into subgroups, wherein each subgroup of packets includes data packets and a local parity packet configured to store values encoded with a single error correction method used to correct a failure of a single packet within the subgroup;

assigning diagonal parity sets to each subgroup as if it were the only subgroup present using a double failure protection encoding method; and

providing a global parity packet within the group of packets, the global parity packet holding diagonal parity computed by logically combining together a plurality of equivalent diagonal parity sets in each of the subgroups such that each diagonal parity set is logically combined with at least one other equivalent diagonal parity set from a differing one of the subgroups, wherein the global parity packet is used in connection with the local parity packet of each subgroup to correct a double failure within the subgroup.

68. The method of claim 67 wherein logically combining together comprises use of exclusive Or (XOR) operations.

69. The method as defined in claim 67 wherein the step of organizing the packets into subgroups, comprises:

organizing the packets into n sub-groups of p packets wherein p is a smallest prime number that is at least as large as a number of packets in any subgroup of packets.

70. The method as defined in claim 69 further comprising the step of:

sending the global parity packet containing diagonal parity after every n sub-group of p packets.

71. The method of claim 69 further comprising the steps of:

if one packet is dropped in the set of p, recovering the packet using row parity; and

if two packets are dropped in one set of p, recovering the packets using row and diagonal parity.

74. The method of 13 wherein the step of correcting comprises the step of reconstructing a failed data disk block using local row parity and a failed global diagonal parity disk block from equivalent diagonal parity sets in all sub-arrays.

75. An apparatus for correcting double failures within data adapted from transmission over a communications medium, comprising:

means for dividing the data into packets for transmission over the communications medium;

means for organizing the packets into subgroups, wherein each subgroup of packets includes data packets and a local parity packet configured to store values encoded with a single error correction method used to correct a failure of a single packet within the subgroup;

means for assigning diagonal parity sets to each subgroup as if it were the only subgroup present using a double failure protection encoding method; and

means for providing a global parity packet within the group of packets, the global parity packet holding diagonal parity computed by logically combining together a plurality of equivalent diagonal parity sets in each of the subgroups such that each diagonal parity set is logically combined with at least one other equivalent diagonal parity set from a differing one of the subgroups, wherein the global parity packet is used in connection with the local parity packet of each subgroup to correct a double failure within the subgroup.

76. The apparatus of claim 75 wherein logically combining together comprises use of exclusive Or (XOR) operations.

77. The apparatus of claim 75 wherein means for organizing the packets into subgroups, further comprises:

means for organizing the packets into n sub-groups of p packets wherein p is a smallest prime number that is at least as large as a number of packets in any subgroup of packets.

78. A method for correcting multiple storage element failures in a storage array, the method comprising the steps of:

dividing the storage array into a first sub-array and a second sub-array, the first sub-array and the second sub-array each including a plurality of storage devices;

calculating row parity for the first sub-array and storing the row parity for the first-sub array on one or more storage devices of the first sub-array;

calculating row parity for the second sub-array and storing the row parity for the second sub-array on one or more storage devices of the second sub-array;

selecting a plurality of diagonal parity sets on the first sub-array;

selecting a plurality of diagonal parity sets on the second sub-array;

pairing each diagonal parity set on the first sub-array with a corresponding diagonal parity set on the second sub-array, and calculating a global diagonal parity value for each pair of diagonal parity sets; and

storing the global diagonal parity values on one or more storage devices of the storage array.

79. A system for correcting multiple storage element failures comprising:

a storage array organized into a first sub-array and a second sub-array, the first sub-array and the second sub-array each including a plurality of storage devices, the first sub-array storing row parity information on one or more storage devices of the first sub-array, the second sub-array storing row parity information on one or more storage devices of the second sub-array;

a storage operating system configured to select a plurality of diagonal parity sets on the first sub-array and to select a plurality of diagonal parity sets on the second sub-array and configured to pair each diagonal parity set on the first sub-array with a corresponding diagonal parity set on the second sub-array, and calculate a global diagonal parity value for each pair of diagonal parity sets, the storage operating system further configured to store the global diagonal parity values on one or more storage devices of the storage array.