Uniform and symmetric double failure correcting technique for protecting against two disk failures in a disk array

• US 7,263,629 B2
• Filed: 11/24/2003
• Issued: 08/28/2007
• Est. Priority Date: 11/24/2003
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: English, Robert M., Kleiman, Steven R., Corbett, Peter F.
• Primary Examiner(s): BONZO, BRYCE P
• Application Number:
  US10/720,361
• Publication Number:
  US 20050114727A1
• Time in Patent Office: 1,373 Days
• Field of Search: 714/770, 714/6
• US Class Current: 714/6.21
• 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

A uniform and symmetric, double failure-correcting technique protects against two or fewer disk failures in a disk array of a storage system. A RAID system of the storage system generates two disks worth of “redundant” information for storage in the array, wherein the redundant information (e.g., parity) is illustratively derived from computations along both diagonal parity sets (“diagonals”) and row parity sets (“rows”). Specifically, the RAID system computes row parity along rows of the array and diagonal parity along diagonals of the array. However, the contents of the redundant (parity) information disks interact such that neither disk contains purely (solely) diagonal or row redundancy information; the redundant information is generated using diagonal parity results in row parity computations (and vice versa).

Claims

1. A system configured to provide double failure-correction of two or fewer storage device failures in a storage system, the system comprising:

an array having a number of storage devices, wherein the number of storage devices is p and wherein p is a prime number greater than two, wherein the storage devices have a storage space divided into stripes and wherein any two storage devices are selected to store redundant information, the selected storage devices varying arbitrarily from stripe to stripe, and the remaining storage devices of each stripe configured to store data; and

a storage module of the storage system, the storage module adapted to construct the redundant information using a redundant storage algorithm involving summation or combination computation along row parity sets (rows) and diagonal parity sets (diagonals) of the array for storage on the selected storage devices,

wherein the redundant storage algorithm used to construct the two or fewer storage device failures is the same regardless of which storage devices fail or roles of the storage devices when constructing or reconstructing the redundant information or data.

2. The system of claim 1 wherein the redundant information is constructed along both diagonals and rows for storage on the selected storage devices, such that neither selected storage device contains solely diagonal or row redundancy information.

3. The system of claim 2 wherein the redundant information stored on the selected storage devices interacts such that the redundant information is uniquely determined by row parity and diagonal parity computation contributions.

4. The system of claim 1 wherein the storage module is a disk array controller.

5. The system of claim 1 wherein the storage module is a RAID system.

6. The system of claim 5 wherein the rows and diagonals are combined using a linear combining algorithm over bit fields that are one or more bits wide.

7. The system of claim 6 wherein the redundant information ensures that each diagonal and each row have known parity values.

8. The system of claim 6 wherein the roles of the storage devices in the array are irrelevant with respect to computation of contents of any two failed storage devices.

9. The system of claim 8 wherein the storage devices are one of video tape, magnetic tape, optical, DVD, bubble memory, magnetic disk, electronic random access memory and micro-electro mechanical storage devices.

10. The system of claim 8 wherein the storage devices are media adapted to store information contained within data and parity blocks.

11. The system of claim 10 wherein the array has two or more RAID groups, one or more RAID groups employing the redundant storage algorithm to protect against two or fewer failures within any one of the RAID groups, wherein each RAID group comprises p storage devices with p equal to a prime greater than two and wherein a value of p may vary among the groups.

12. The system of claim 11 wherein not all p storage devices are present in the array and wherein contents of the storage devices not present have predetermined and fixed values.

13. The system of claim 1 wherein not all p storage devices are present in the array and wherein contents of the storage devices not present have predetermined and fixed values.

14. A system configured to provide double failure-correction of two or fewer storage device failures in a storage system, the system comprising:

an array having a number of storage devices, wherein the number of storage devices is p and wherein p is a prime number greater than two, the storage devices including two storage devices selected to store redundant information, the remaining storage devices configured to store data; and

a storage module of the storage system, the storage module adapted to construct the redundant information using a redundant storage algorithm involving summation or combination computation along row parity sets (rows) and diagonal parity sets (diagonals) of the array for storage on the selected storage devices, the storage module further adapted to use the redundant storage algorithm to reconstruct the two or fewer storage device failures,

wherein the storage devices have a storage space divided into stripes with any two storage devices selected to store the redundant information, the selected storage devices varying from stripe to stripe, arbitrarily, and wherein the two or fewer storage device failures are recovered without any knowledge of roles of those devices or any other storage device in the array.

15. The system of claim 14 wherein the redundant information is constructed along both diagonals and rows for storage on the selected storage devices, such that neither selected storage device contains solely diagonal or row redundancy information.

16. The system of claim 15 wherein the redundant information stored on the selected storage devices interacts such that the redundant information is uniquely determined by row parity and diagonal parity computation contributions.

17. The system of claim 14 wherein the storage module is a disk array controller.

18. The system of claim 14 wherein the storage module is a RAID system.

19. The system of claim 18 wherein the rows and diagonals are combined using a linear combining algorithm over bit fields that are one or more bits wide and wherein the redundant information ensures that each diagonal and each row have known parity values.

20. The system of claim 19 wherein the array is a symmetric row-diagonal (SRD) parity array.

21. The system of claim 19 wherein the roles of the storage devices in the array are irrelevant with respect to computation of contents of any two failed storage devices.

22. The system of claim 21 wherein the storage devices are one of video tape, magnetic tape, optical, DVD, bubble memory, magnetic disk, electronic random access memory and micro-electro mechanical storage devices.

23. The system of claim 21 wherein the storage devices are media adapted to store information contained within data and parity blocks.

24. The system of claim 23 wherein the array has two or more RAID) groups, one or more RAID groups employing the redundant storage algorithm to protect against two or fewer failures within any one of the RAID groups, wherein each RAID group comprises p storage devices with p equal to a prime greater than two and wherein a value of p may vary among the groups.

25. The system of claim 24 wherein not all p storage devices are present in the array and wherein contents of the storage devices not present are zero.

26. The system of claim 14 wherein not all p storage devices are present in the array and wherein contents of the storage devices not present have predetermined and fixed values.

27. A method for protecting against two or fewer disk failures in a storage system, the method comprising the steps of:

providing an array with a number of disks, wherein the number of disks is p and wherein p is a prime number greater than two;

dividing each disk into blocks;

organizing the blocks into stripes that contain a same number of blocks in each disk, wherein each stripe comprises p−

1 rows of blocks;

computing the redundant information through summation or combination computation along row parity sets (rows) and diagonal parity sets (diagonals) of the array;

arbitrarily assigning the roles of the blocks to thereby allow balancing of data loads across the array, where any two disks of each stripe are selected to store redundant information; and

storing the computed redundant information on the selected disks.

28. The method of claim 27 wherein the step of computing comprises the step of computing the redundant information along both diagonals and rows for storage on the selected storage devices, such that neither selected storage device contains solely diagonal or row redundancy information.

29. The method of claim 28 wherein the step of computing further comprises the step of computing row parity along rows of the array and diagonal parity along diagonals of the array, such that the redundant information ensures that each diagonal and each row have known parity values.

30. The method of claim 29 wherein the step of computing further comprises the step of computing the redundant information using exclusive-OR logical operation computations.

31. The method of claim 30 wherein roles of the disks in the array are irrelevant with respect to computation of contents of any two failed storage devices.

32. The method of claim 27 wherein the step of computing further comprises the step of computing by addition over bit fields that are one or more bits wide.

33. The method of claim 27 further comprising the step of reassigning the role of a block without moving data to balance the data loads or add a disk to the array.

34. The method of claim 27 further comprising the step of constructing the rows from one or more blocks from each disk, arbitrarily.

35. The method of claim 27 further comprising the step of combining the rows of blocks to form a single stripe of larger blocks when p−

1 is a power of two.

36. The method of claim 27 further comprising the steps of:

adding an initialized disk to the array; and

designating blocks on the initialized disk to contain data or redundant information, while ensuring that two blocks store redundant information in each stripe.

37. The method of claim 36 wherein contents of the initialized disk match imputed contents of a missing disk, such that the redundant information in the array does not need recalculation.

38. The method of claim 37 wherein the contents of the initialized disk are zero.

39. The method of claim 27 further comprising the step of, wherein the disks have a disk space divided into stripes, selecting any two disks to store the redundant information, the selected disks varying from stripe to stripe, arbitrarily.

40. The method of claim 28 further comprising the step of, wherein the disks are numbered from 0 to m−

1, for m>

=p, renumbering the disks by rotating the disks by amount k, such that disk j becomes disk (f+k) modulo m, does not change the computations to compute the redundant information or the results of the computations.

41. A system configured to provide double failure-correction of two or fewer storage device failures in a storage system, the system comprising:

an array having a number of storage devices, wherein the number of storage devices is p and wherein p is a prime number greater than two; and

a storage module of the storage system, the storage module adapted to construct redundant information using a redundant storage algorithm involving summation or combination computation along row parity sets (rows) and diagonal parity sets (diagonals) of the array for storage on the selected storage devices, the storage module further adapted to use the redundant storage algorithm to reconstruct the two or fewer storage device failures, regardless of which storage devices fail or whether the storage devices store redundant information or data,

wherein the storage devices have a storage space divided into stripes with any two storage devices selected to store the redundant information, the selected storage devices varying from stripe to stripe, arbitrarily, and wherein the two or fewer storage device failures are recovered without any knowledge of roles of those devices or any other storage device in the array.

42. The system of claim 41 wherein the redundant information is constructed along both diagonals and rows for storage on the selected storage devices, such that neither selected storage device contains solely diagonal or row redundancy information.

43. The system of claim 42 wherein the redundant information stored on the selected storage devices interacts such that the redundant information is uniquely determined by row parity and diagonal parity computation contributions.

44. The system of claim 42 wherein each storage device is divided into blocks, the blocks are organized into stripes that contain a same number of blocks in each disk.

45. The system of claim 44 wherein each diagonal d=(i+j) modulo p, wherein i is a disk number of a block and j is a row number of the block within a set of p−

1 rows.

46. The system of claim 44 wherein each diagonal d=(i−

j) modulo p, wherein i is a disk number of a block and j is a row number of the block within a set of p−

1 rows.

47. The system of claim 44 wherein each diagonal d=(i+k) modulo p, wherein i is a disk number of a block, j is a row number of the block within a set of p−

1 rows and k is a fixed integer, and wherein k≠

0 and −

p<

k<

p.

48. The system of claim 44 wherein a series of blocks is organized as a chain, such that all blocks in the chain belong to two storage devices, and two blocks at either end of the chain are on different storage devices and are in the same row as nearest neighboring blocks on the chain, and wherein all other blocks in the chain are in the same row as one other block in the chain and in the same diagonal as one other block in the chain.

49. The system of claim 41 wherein the storage module is a disk array controller.

50. The system of claim 41 wherein the storage module is a RAID system.

51. The system of claim 50 wherein the rows and diagonals are combined using a linear combining algorithm over bit fields that are one or more bits wide and wherein the redundant information ensures that each diagonal and each row have known parity values.

52. The system of claim 51 wherein the array is a uniform and symmetric row-diagonal (SRD) parity array.

53. The system of claim 51 wherein the roles of the storage devices in the array are irrelevant with respect to computation of contents of any two failed storage devices.

54. The system of claim 53 wherein the storage devices are one of video tape, magnetic tape, optical, DVD, bubble memory, magnetic disk, electronic random access memory and micro-electro mechanical storage devices.

55. The system of claim 53 wherein the storage devices are media adapted to store information contained within data and parity blocks.

56. The system of claim 55 wherein the array has two or more RAID groups, one or more RAID groups employing the redundant storage algorithm to protect against two or fewer failures within any one of the RAID groups, wherein each RAID group comprises p storage devices with p equal to a prime greater than two and wherein a value of p may vary among the groups.

57. The system of claim 56 wherein not all p storage devices are present in the array and wherein contents of the storage devices not present are zero.

58. The system of claim 41 wherein not all p storage devices are present in the array and wherein contents of the storage devices not present have predetermined and fixed values.

59. Apparatus for protecting against two or fewer disk failures in a storage system, the apparatus comprising:

means for providing an array with a number of disks, wherein the number of disks is p and wherein p is a prime number greater then two;

means for dividing each disk into blocks;

means for organizing the blocks into stripes that contain a same number of blocks in each disk, wherein each stripe comprises p-1 rows of blocks;

means for computing the redundant information from both diagonal and row parity computation contributions;

means for arbitrarily assigning the roles of the blocks to thereby allow balancing of data loads across the array, where any two disks of each stripe are selected to store redundant information and the two disks selected vary from stripe to stripe; and

means for storing the computed redundant information on the selected disks, such that neither selected disk contains solely diagonal or row parity information.

60. 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 one or more groups adapted to employ a uniform and symmetric double failure-correcting algorithm to protect against two or fewer failures of packets within any one of the groups, wherein each group comprises p packets with p equal to a prime greater than two and wherein a value of p may vary among the groups, and wherein two packets of each group are selected to store redundant information, the remaining packets of the group configured to store data;

computing the redundant information through summation or combination computation along row parity sets (rows) and diagonal parity sets (diagonals) of the group; and

storing the computed redundant information in the selected packets.

61. A method for protecting against two or fewer disk failures in a storage system, comprising:

providing an array with a number of disks, wherein the number of disks is p and wherein p is a prime number greater than two;

dividing each disk into blocks;

organizing the blocks into stripes that contain a same number of blocks in each disk, wherein each stripe comprises p−

1 rows of blocks

choosing any two disks of the array, a first parity disk and a second parity disk, in a stripe to contain parity, arbitrarily;

choosing a first block in either of the first parity disk or the second parity disk, where the first block does not belong to a diagonal that contains a second block in remaining parity disk;

computing diagonal parity for the first block; and

computing row parity for a row block on remaining parity disk, where the row block and the first block are in a same row.

62. The method of claim 61, further comprising:

computing remaining parity blocks in the stripe by alternating diagonal computation followed by row computation.

63. The method of claim 61, wherein the two disks selected to store parity change after each stripe.

64. The method of claim 61, wherein neither of the two disks selected to store parity contain solely diagonal or row parity.