Parity assignment technique for parity declustering in a parity array of a storage system

• US 7,346,831 B1
• Filed: 11/13/2001
• Issued: 03/18/2008
• Est. Priority Date: 11/13/2001
• Status: Expired due to Term

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Corbett, Peter F.
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): THAI, HANH B
• Application Number:
  US10/008,565
• Time in Patent Office: 2,317 Days
• Field of Search: 707/100, 707/202, 707/10, 711112-114, 714 5- 7, 714 8- 9, 714/48, 714/755, 714/761, 714/766, 714/770, 714/800, 714/805
• 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 parity assignment technique enables parity declustering in a large, balanced parity (“super-stripe”) array of a storage system. The balanced array may be constructed by combining a plurality of unbalanced parity stripe arrays, each having parity blocks on a set of storage devices, such as disks, that are disjoint from the set of disks storing the data blocks. The technique distributes the assignment of disks to parity groups among the combined super-stripe array such that all disks contain the same amount of data or parity information. Moreover, the technique ensures that all surviving data disks of the array are loaded uniformly during a reconstruction phase after a single or double disk failure.

Claims

1. A method for enabling parity declustering in a balanced parity array of a storage system, comprising:

combining a plurality of unbalanced parity stripe arrays to form the balanced parity array, the balanced parity array storing substantially the same number of parity blocks on all disks, each unbalanced parity stripe array and the balanced parity array having parity blocks on a set of storage devices that are disjoint from a set of storage devices storing data blocks, wherein each unbalanced parity stripe array is an arrangement having fewer parity blocks per disk than data blocks per disk in a stripe; and

distributing assignment of storage devices to parity groups throughout the balanced parity array.

2. The method of claim 1 further comprising, after a single or double storage device failure, ensuring that all surviving data storage devices are loaded uniformly during reconstruction of the failed storage device or devices.

3. The method of claim 1 wherein the storage system is a filer.

4. The method of claim 1 further comprising:

dividing each storage device into blocks; and

organizing the blocks into stripes across the devices, wherein each stripe contains data and parity blocks from each of the devices of a balanced array, where the balanced array includes the set of storage devices to store data blocks and the set of storage devices to store parity blocks.

5. The method of claim 4 wherein the step of organizing comprises selecting patterns of characters representing data storage devices of each stripe to thereby change the association of the data storage devices with parity groups from stripe to stripe of the balanced array.

6. The method of claim 5 wherein the characters are binary numbers.

7. The method of claim 5 wherein the characters are ternary numbers.

8. The method of claim 1 further comprising:

configuring the balanced array as a RAID-4 style array;

initially under-populating the array with storage devices; and

adding storage devices until a fully populated array of predetermined size is achieved.

9. The method of claim 8 wherein the storage devices are disks.

10. The method of claim 1 further comprising:

after a single or double storage device failure, ensuring that all surviving data storage devices are loaded uniformly during reconstruction of the failed storage device or devices.

11. A system that enables parity declustering in a balanced parity array of a storage system, the system comprising:

a plurality of storage devices, each storage device divided into blocks that are further organized into stripes, wherein each stripe contains data and parity blocks from each of the devices of a balanced array;

a storage operating system including a storage layer configured to implement a parity assignment technique that distributes assignment of devices to parity groups throughout the balanced array such that all storage devices contain the same amount of information; and

a processing element configured to execute the operating system to thereby invoke storage access operations to and from the balanced parity array in accordance with a concentrated parity technique, where the concentrated parity technique combines unbalanced parity stripe arrays from two or more of the parity groups to form a balanced parity array with an equal number of parity blocks per disk storing parity, wherein each unbalanced parity stripe array is an arrangement having fewer parity blocks per disk than data blocks per disk in the stripe.

12. The system of claim 11 wherein each unbalanced stripe array having parity blocks on a set of storage devices that are disjoint from a set of storage devices storing data blocks.

13. The system of claim 12 wherein the storage devices are disks and wherein the storage layer is a RAID layer.

14. The system of claim 13 wherein the RAID layer is implemented in logic circuitry.

15. The system of claim 11 wherein the storage system is a network-attached storage appliance.

16. The system of claim 11 wherein the storage devices are one of video tape, optical, DVD, magnetic tape and bubble memory devices.

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

18. Apparatus for enabling parity declustering in a balanced parity array of a storage system, the apparatus comprising:

means for combining a plurality of unbalanced parity stripe arrays to form the balanced parity array, the balanced parity array storing substantially the same number of parity blocks on all disks, each unbalanced parity stripe array and the balanced parity array having parity blocks on a set of storage devices that are disjoint from a set of storage devices storing data blocks, wherein the unbalanced parity stripe array is an arrangement having fewer parity blocks per disk than data blocks per disk in a stripe; and

means for distributing assignment of devices to parity groups throughout the balanced parity array.

19. The apparatus of claim 18 further comprising:

means for dividing each storage device into blocks; and

means for organizing the blocks into stripes across the devices, wherein each stripe contains data and parity blocks from each of the devices of a balanced array, where the balanced array includes the set of storage devices to store data blocks and the set of storage devices to store parity blocks.

20. The apparatus of claim 19 wherein the means for organizing comprises means for selecting patterns of characters representing data storage devices of each stripe to thereby change the association of the data storage devices with parity groups from stripe to stripe of the balanced array.

21. The apparatus of claim 18 wherein each unbalanced stripe array has fewer parity blocks per disk than data blocks per disk.

22. A computer readable medium containing executable program instructions for enabling parity declustering in a balanced parity array of a storage system, the executable program instructions comprising program instructions for:

combining a plurality of unbalanced parity stripe arrays to form the balanced parity array, the balanced parity array storing substantially the same number of parity blocks on all disks, each unbalanced parity stripe array and the balanced parity array having parity blocks on a set of storage devices that are disjoint from a set of storage devices storing data blocks, wherein each unbalanced parity stripe array storing an unequal number of parity blocks per storage device then data blocks per storage device in a stripe; and

distributing assignment of devices to parity groups throughout the balanced parity array.

23. The computer readable medium of claim 22 further comprising program instructions for:

dividing each storage device into blocks; and

organizing the blocks into stripes across the devices, wherein each stripe contains data and parity blocks from each of the devices of a balanced array, where the balanced array includes the set of storage devices to store data blocks and the set of storage devices to store parity blocks.

24. The computer readable medium of claim 23 wherein the program instructions for organizing comprises program instructions for selecting patterns of characters representing data storage devices of each stripe to thereby change the association of the data storage devices with parity groups from stripe to stripe of the balanced array.

25. The computer readable medium of claim 22 wherein each unbalanced stripe array has fewer parity blocks per disk than data blocks per disk.

26. A method for declustering a parity array having a plurality of storage devices, comprising:

assigning a first plurality of data and parity blocks to a first group, where the data blocks are stored on a plurality of storage devices that are disjoint from a plurality of storage devices storing parity blocks to form a first parity group, wherein the parity blocks are striped across the plurality of storage devices in the first parity group with fewer parity blocks per storage device than data blocks per storage device in a stripe;

assigning a second plurality of data and parity blocks to a second group, where the data blocks are stored on a plurality of storage devices that are disjoint from a plurality of storage devices storing parity blocks to form a second parity group, wherein the parity blocks are striped across the plurality of storage devices in the second parity group with fewer parity blocks per storage device than data blocks per storage device in a stripe, wherein the first and second parity groups being independent from each other; and

combining the first parity group and the second parity group to form a balanced parity array, the balanced parity array storing substantially the same number of parity blocks on the storage devices configured to store parity.

27. A method for declustering a parity array having a plurality of storage devices, comprising:

assigning a plurality of parity blocks to a plurality of parity groups, the plurality of parity groups being independent from each other and distributed throughout the plurality of storage devices of the parity array where each parity group forms an unbalanced parity stripe array, wherein each unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe; and

combining the plurality of parity groups to form a balanced array, the balanced array storing substantially the same number of blocks on all disks.

28. A disk array having a declustered parity array, comprising:

a plurality of storage devices having a first and second parity group;

a first plurality of parity blocks assigned to the first parity group where the first parity group forms a first unbalanced parity stripe array, wherein the first unbalanced parity array has fewer parity blocks per disk than data blocks per disk in a stripe;

a second plurality of parity blocks assigned to the second parity group where the second parity group forms a second unbalanced parity stripe array, wherein the second unbalanced parity array has fewer parity blocks per disk than data blocks per disk in a stripe, the first and second parity groups being independent from each other and distributed throughout the plurality of storage devices of the parity array; and

a balanced parity array created by combining the first parity group and the second parity group, the balanced parity array storing substantially the same number of blocks on all disks.

29. A disk array having a declustered parity array, comprising:

a plurality of storage devices having a plurality of parity groups;

a plurality of parity blocks assigned to the plurality of parity groups where each parity group forms an unbalanced parity stripe array, wherein each unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe, the plurality of parity groups being independent from each other and distributed throughout the plurality of storage devices of the parity array; and

a balanced parity array created by combining the plurality parity groups, the balanced parity array storing substantially the same number of parity blocks on all disks.

30. A disk array having a declustered parity array, comprising:

a plurality of storage devices;

means for assigning a first plurality of parity blocks to a first parity group where the first parity group forms a first unbalanced parity stripe array, wherein the first unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe;

means for assigning a second plurality of parity blocks to a second parity group, where the second parity group forms a second unbalanced parity stripe array, wherein the second unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe, the first and second parity groups being independent from each other and distributed throughout the plurality of storage devices of the parity array; and

means for combining the first parity group and the second parity group to form a balanced parity array, the balanced parity array storing substantially the same number of parity blocks on all disks.

31. A disk array having a declustered parity array, comprising:

a plurality of storage devices;

means for assigning a plurality of parity blocks to a plurality of parity groups, the plurality of parity groups being independent from each other and distributed throughout the plurality of storage devices of the parity array where each parity group forms an unbalanced parity stripe array, wherein each unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe; and

means for combining the plurality of parity groups to form a balanced parity array, the balanced parity array storing substantially the same number of parity blocks on all disks.

32. A computer implemented method for enabling parity declustering of a storage system, comprising:

providing a first array of storage devices for storing data blocks and parity blocks, the data blocks organized into at least one parity group associated with the parity blocks, the first array forming a first unbalanced parity stripe array, wherein the first unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe;

providing a second array of storage devices for storing data blocks and parity blocks, the data blocks organized into at least one parity group associated with the parity blocks, the second array forming a second unbalanced parity stripe array, wherein the second unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe;

combining the first and second arrays to form a combined array having substantially the same number of parity blocks stored on each storage device of the combined array; and

changing the association of data blocks with parity groups in the first array and the second array so that each parity group is associated with data blocks that are distributed substantially uniformly throughout the storage devices that store data blocks in the combined array.

33. The method of claim 32 further comprising:

organizing the data and parity blocks into stripes across the storage devices.

34. The method of claim 33 wherein the step of redistributing comprises changing the association of the data storage devices with parity groups from stripe to stripe in the combined array.

35. The method of claim 34 wherein the step of changing further comprises selecting differing patterns of characters representing data storage devices of each stripe.

36. The method of claim 35 wherein the characters are binary numbers.

37. The method of claim 35 wherein the characters are ternary numbers.

38. The method of claim 32 wherein the storage devices are disk drives.

39. A computer implemented method for enabling parity declustering of a storage array having a plurality of storage devices, comprising:

dividing each storage device into blocks;

organizing the blocks into a plurality of stripes across the storage devices, wherein each stripe contains data and parity blocks;

storing data in data blocks and parity information in parity blocks, the parity blocks storing parity information for a plurality of parity groups; and

varying the association of the storage devices to parity groups from stripe to stripe in the storage array such that each parity group is associated with data blocks that are distributed substantially uniformly throughout the storage devices that store data blocks in the storage array.

40. The method of claim 39 wherein the step of varying comprises selecting differing patterns of characters representing data storage devices of a stripe to thereby change the association of data blocks with parity groups from stripe to stripe of the storage array.

41. An apparatus for enabling parity declustering of a storage system, the apparatus comprising:

a first array of storage devices for storing data blocks and parity blocks, the data blocks organized into at least one parity group associated with the parity blocks, the first array forming a first unbalanced parity stripe array, wherein the first unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe;

a second array of storage devices for storing data blocks and parity blocks, the data blocks organized into at least one parity group associated with the parity blocks, the second array forming a second unbalanced parity stripe array, wherein the second unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe; and

a storage operating system configured to combine the first and second arrays to form a combined array having substantially the same number of blocks stored on each storage device of the combined array, and configured to change the association of data blocks with parity groups in the first array and the second array so that each parity group is associated with data blocks that are distributed substantially uniformly throughout the storage devices that store data blocks in the combined array.

42. The apparatus of claim 41 wherein each the blocks are organized into stripes across the storage devices.

43. The apparatus of claim 42 wherein the storage devices are disk drives.

44. The apparatus of claim 41 wherein the storage devices are one of video tape, optical, DVD, magnetic tape and bubble memory devices.

45. The apparatus of claim 41 wherein the system is a network-attached storage appliance.

46. The system of claim 45 wherein the storage operating system is configured to select differing patterns of characters representing data storage devices of a stripe to thereby change the association of data blocks with parity groups from stripe to stripe of the storage array.

47. An apparatus for enabling parity declustering of a storage array having a plurality of storage devices, the apparatus comprising:

a storage operating system configured to divide each storage device into blocks and organize the blocks into a plurality of stripes across the storage devices, wherein each stripe contains data and parity blocks and store data in data blocks and parity information in parity blocks, the parity blocks storing parity information for a plurality of parity groups; and

the storage operating system further configured to vary the association of the storage devices to parity groups from stripe to stripe in the storage array such that, each parity group is associated with data blocks that are distributed substantially uniformly throughout the storage devices that store data blocks in the storage array.

48. A system that enables parity declustering of a storage system, the system comprising:

means for providing a first array of storage devices for storing data blocks and parity blocks, the data blocks organized into at least one parity group associated with the parity blocks, the first array forming a first unbalanced parity stripe array, wherein the first unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe;

means for providing a second array of storage devices for storing data blocks and parity blocks, the data blocks organized into at least one parity group associated with the parity blocks, the second array forming a second unbalanced parity stripe array, wherein the second unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe;

means for combining the first and second arrays to form a combined array having substantially the same number of blocks stored on each storage device of the combined array; and

means for changing the association of data blocks with parity groups in the first array and the second array so that each parity group is associated with data blocks that are distributed substantially uniformly throughout the storage devices that store data blocks in the combined array.

49. An apparatus for enabling parity declustering of a storage array having a plurality of storage devices, the apparatus comprising:

means for dividing each storage device into blocks;

means for organizing the blocks into a plurality of stripes across the storage devices, wherein each stripe contains data and parity blocks;

means for storing data in data blocks and parity information in parity blocks, the parity blocks storing parity information for a plurality of parity groups; and

means for varying the association of the storage devices to parity groups from stripe to stripe in the storage array such that, each parity group is associated with data blocks that are distributed substantially uniformly throughout the storage devices that store data blocks in the storage array.

50. A computer readable medium containing program instructions for execution on a processor, the executable program instructions comprising program instructions for:

dividing each storage device into blocks;

organizing the blocks into a plurality of stripes across the storage devices, wherein each stripe contains data and parity blocks;

storing data in data blocks and parity information in parity blocks, the parity blocks storing parity information for a plurality of parity groups; and

varying the association of the storage devices to parity groups from stripe to stripe in the storage array such that, each parity group is associated with data blocks that are distributed substantially uniformly throughout the storage devices that store data blocks in the storage array.

51. An apparatus for parity declustering in a storage system, the apparatus comprising:

a storage operating system configured to combine a plurality of first arrays of storage devices, each first array has fewer parity blocks per storage device than data blocks per storage device in a stripe, to form a second array, the second array storing substantially the same number of parity blocks on storage devices that store parity blocks; and

the storage operating system further configured to redistribute the assignment storage devices to parity groups in the second array so that each storage device will have a substantially equal number of blocks associated with each parity group.

52. An method for parity declustering in a storage system, comprising:

combining a plurality of first arrays of storage devices, each first array has fewer parity blocks per storage device than data blocks per storage device in a stripe, the second array storing substantially the same number of parity blocks on storage devices that store parity blocks; and

configuring the storage operating system to redistribute the assignment storage devices to parity groups in the second array so that each storage device will have a substantially equal number of blocks associated with each parity group.

53. A computer implemented method for enabling parity declustering of a storage system, comprising:

providing a first array of storage devices for storing data blocks and parity blocks, the data blocks organized into at least one parity group associated with the parity blocks, the first array forming a first unbalanced parity stripe array, wherein the first unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe;

providing a second array of storage devices for storing data blocks and parity blocks, the data blocks organized into at least one parity group associated with the parity blocks, the second array forming a second unbalanced parity stripe array, wherein the second unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe; and

combining the first and second arrays to form a combined array having substantially the same number of parity blocks stored on each storage device of the combined array.

54. An apparatus for enabling parity declustering of a storage system, the apparatus comprising:

a first array of storage devices for storing data blocks and parity blocks, the data blocks organized into at least one parity group associated with the parity blocks, the first array forming a first unbalanced parity stripe array, wherein the first unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe;

a second array of storage devices for storing data blocks and parity blocks, the data blocks organized into at least one parity group associated with the parity blocks, the second array forming a second unbalanced parity stripe array, wherein the second unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe; and

a storage operating system configured to combine the first and second arrays to form a combined array having substantially the same number of parity blocks stored on each storage device of the combined array.

55. A method for enabling a balanced arrangement of a storage system, comprising:

creating a plurality of unbalanced stripe arrangements with each unbalanced stripe arrangement is an arrangement having fewer parity blocks per disk than data blocks per disk in a stripe;

combining the plurality of unbalanced stripe arrangements to form the balanced arrangement, with the balanced arrangement storing substantially the same number of parity blocks per disk in the array of disks configured to store parity;

storing parity blocks across one or more disks in the array of disks to create one or more parity groups;

storing data blocks across the remaining disks of the disks in the array with the parity blocks and the data blocks stored on different disks of the array; and

assigning storage devices to different parity groups throughout the balanced arrangement.

56. A method for enabling a balanced arrangement of a storage system, comprising:

creating a plurality of unbalanced stripe arrangements with each unbalanced stripe arrangement has fewer parity blocks per disk than data blocks per disk in a stripe; and

combining the plurality of unbalanced stripe arrangements to form the balanced arrangement, with the balanced arrangement storing substantially the same number of parity blocks per disk in the array of disks configured to store parity.

57. A method for enabling parity declustering in a balanced parity array of a storage system, comprising:

combining a plurality of unbalanced parity stripe arrays from a plurality of RAID groups to form the balanced parity array, the balanced parity array storing substantially the same number of parity blocks on all disks, each unbalanced parity stripe array and the balanced parity array having parity blocks on a set of storage devices that are disjoint from a set of storage devices storing data blocks, wherein each unbalanced parity stripe array is an arrangement having fewer parity blocks per storage device than data blocks per storage device in a stripe; and

distributing assignment of storage devices to parity groups throughout the balanced parity array.

58. A method, comprising:

providing a first array of storage devices for storing data blocks and parity blocks, the data blocks organized into at least one parity group associated with the parity blocks, the first array forming a first unbalanced parity stripe array, wherein the first unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in a stripe;

providing a second array of storage devices for storing data blocks and parity blocks, the data blocks organized into at least one parity group associated with the parity blocks, the second array forming a second unbalanced parity stripe array, wherein the second unbalanced parity array has fewer parity blocks per storage device than data blocks per storage device in the stripe;

determining to combine the first array and the second array when a number of parity blocks per a storage device divides evenly into a number of data blocks per storage device in the stripe; and

in response to determining to combine the first array and the second array, combining the first and second arrays to form a combined array having substantially the same number of parity blocks stored on each storage device of the combined array.