Semi-static distribution technique

• US 7,185,144 B2
• Filed: 11/24/2003
• Issued: 02/27/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): Bragdon; Reginald G.
• Assistant Examiner(s): Namazi; Mehdi
• Application Number:
  US10/720,364
• Publication Number:
  US 20050114594A1
• Time in Patent Office: 1,191 Days
• Field of Search: 711/114, 711/170, 714/7, 395/182.05
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system

Abstract

A semi-static distribution technique distributes parity across disks of an array. According to the technique, parity is distributed (assigned) across the disks of the array in a manner that maintains a fixed pattern of parity blocks among the stripes of the disks. When one or more disks are added to the array, the semi-static technique redistributes parity in a way that does not require recalculation of parity or moving of any data blocks. Notably, the parity information is not actually moved; the technique merely involves a change in the assignment (or reservation) for some of the parity blocks of each pre-existing disk to the newly added disk.

Claims

1. A method for distributing parity blocks across a disk array, the method comprising the steps of:

adding a new disk to a number of pre-existing disks of the array;

dividing each disk into blocks, the blocks being organized into stripes such that each stripe contains one block from each disk; and

distributing parity among blocks of the new and pre-existing disks by moving every Nth parity block to the new disk to arrange each disk of the array with approximately 1/N parity blocks, where N is equal to the number of pre-existing disks plus the new disk.

2. The method of claim 1 wherein the step of distributing comprises the step of distributing parity among blocks of the new and pre-existing disks in a manner that maintains a fixed pattern of parity blocks among stripes of the disks.

3. The method of claim 1 wherein the step of distributing comprises the step of changing an assignment for one or more blocks containing parity of each pre-existing disk to the newly added disk.

4. The method of claim 2 wherein the step of adding comprises the step of initializing the added disk so as to not affect parity of the stripes.

5. The method of claim 4 wherein the step of initializing comprises the step of reassigning blocks containing parity in certain stripes to the new disk without calculation or writing of parity.

6. The method of claim 5 wherein the step of reassigning comprises the step of changing a block containing parity (parity block) to a block containing data (data block) and not changing a data block to a parity block.

7. The method of claim 1, wherein the step of distributing parity among blocks of the new and pre-existing disks is accomplished without recalculation of parity blocks or moving of any blocks containing data.

8. A system adapted to distribute parity across disks of a storage system, the system comprising:

a disk array comprising a number of pre-existing disks and at least one new disk; and

a storage module configured to compute parity in blocks of stripes across the disks and reconstruct blocks of disks lost as a result of failure, the storage module further configured to assign the parity among the blocks of the new and pre-existing disks by moving every Nth parity block to the at least one new disk to arrange each disk of the array with approximately 1/N parity blocks, where N is equal to the number of pre-existing disks plus with at least one new disk.

9. The system of claim 8 further comprising a table configured to store parity assignments calculated for one of a known group size of the disk array and a maximum group size of the array, the stored parity assignments defining a repeat interval of a parity distribution pattern used to determine locations of parity storage on any disk in the array.

10. The system of claim 8 wherein the storage module is embodied as a RAID system of the storage system.

11. The system of claim 8 wherein the storage module is embodied as an internal disk array controller of the storage system.

12. The system of claim 8 wherein the storage module is embodied as a disk array control system externally coupled to the storage system.

13. The system of claim 8 wherein the disk array is a block-based RAID array.

14. The system of claim 8, wherein the storage module is further configured to assign the parity among the blocks of the new and pre-existing disks without recalculation of parity blocks or moving of any blocks containing data.

15. Apparatus for distributing parity across a disk array, the apparatus comprising:

means for adding a new disk to a number of pre-existing disks of the array;

means for dividing each disk into blocks, the blocks being organized into stripes such that each stripe contains one block from each disk; and

means for distributing parity among blocks of the new and pre-existing disks by moving every Nth parity block to the new disk to arrange each disk of the array with approximately 1/N parity blocks, where N is equal to the number of pre-existing disks plus the new disk.

16. The apparatus of claim 15, wherein the means for distributing parity among blocks of the new and pre-existing disks is accomplished without recalculation of parity blocks or moving of any blocks containing data.

17. A computer readable medium containing executable program instructions for distributing parity across a disk array, the executable instructions comprising one or more program instructions for:

adding a new disk to a number of pre-existing disks of the array;

dividing each disk into blocks, the blocks being organized into stripes such that each stripe contains one block from each disk; and

distributing parity among blocks of the new and pre-existing disks by moving every Nth parity block to the new disk to arrange each disk of the array with approximately 1/N parity blocks, where N is equal to the number of pre-existing disks plus the new disk.

18. The computer readable medium of claim 17, wherein the program instruction for distributing parity among blocks of the new and pre-existing disks is accomplished without recalculation of parity blocks or moving of any blocks containing data.

19. A method for distributing parity blocks across a disk array, comprising:

providing a pre-existing disk array with a number of pre-existing disks, each pre-existing disk divided into a plurality of blocks;

assigning data blocks and parity blocks to the pre-existing disks in stripes, where each disk is arranged with approximately one over the number of pre-existing disks of parity blocks per disk;

adding a new disk to the pre-existing array to form an expanded array with a new number of disks, where N is equal to the number of pre-existing disks plus the new disk, the new disk divided into a plurality of blocks; and

reassigning the parity blocks across the expanded array to arrange the parity blocks with approximately 1/N blocks of parity on each disk by moving every Nth parity block stored on each of the pre-existing disks to the new disk.

20. The method of claim 19, wherein the reassigning of parity blocks is accomplished without recalculation of parity blocks or moving of any blocks containing data.

21. The method of claim 19, further comprising:

moving the parity blocks reassigned to the new disk.

22. The method of claim 21, further comprising:

zeroing the parity blocks moved to the new disk.

23. The method of claim 22, further comprising:

storing data blocks in the parity blocks zeroed.

24. The method of claim 19, wherein the step of reassigning further includes:

creating a fixed pattern of 1/N of parity blocks per a repeat interval.

25. The method of claim 24, wherein the fixed pattern is not a rotating pattern through the disks of the expanded array.

27. The method of claim 25, where the step of reassigning is accomplished without recalculation of parity blocks or moving of any blocks containing data.

28. The method of claim 25, where the plurality of disks can be any number of disks and there is no limit to the number of disks in the expanded array.

26. A method for distributing parity blocks across a disk array, comprising:

providing a pre-existing disk array with a number of pre-existing disks, each pre-existing disk divided into a plurality of blocks;

assigning data blocks and parity blocks to the pre-existing disks in stripes, where each disk is arranged with approximately one over the number of pre-existing disks of parity blocks per disk;

adding a plurality of new disks to the pre-existing array to form an expanded array with a new number of disks, where N is equal to the number of pre-existing disks plus the plurality of new disks, the plurality of new disks each divided into a plurality of blocks; and

reassigning the parity blocks across the expanded array to arrange the parity blocks with approximately 1/N blocks of parity on each disk by moving every Nth parity block stored on each of the pre-existing disks to the plurality of new disks.

29. An apparatus to distribute parity blocks across a disk array, comprising:

means for providing a pre-existing disk array with a number of pre-existing disks, each pre-existing disk divided into a plurality of blocks;

means for assigning data blocks and parity blocks to the pre-existing disks in stripes, where each disk is arranged with approximately one over the number of pre-existing disks of parity blocks per disk;

means for adding a new disk to the pre-existing array to form an expanded array with a new number of disks, where N is equal to the number of pre-existing disks plus the new disk, the new disk divided into a plurality of blocks; and

means for reassigning the parity blocks across the expanded array to arrange the parity blocks with approximately 1/N blocks of parity on each disk by moving every Nth parity block stored on each of the pre-existing disks to the new disk.

30. The apparatus of claim 29, wherein the means for reassigning of parity blocks is accomplished without recalculation of parity blocks or moving of any blocks containing data.

31. The apparatus of claim 29, further comprising:

means for moving the parity blocks reassigned to the new disk.

32. The apparatus of claim 30, further comprising:

means for zeroing the parity blocks moved to the new disk.

33. The apparatus of claim 31, further comprising:

means for storing data blocks in the parity blocks zeroed.

34. The apparatus of claim 29, wherein the means for reassigning further includes:

means for creating a fixed pattern of 1/N of parity blocks per a repeat interval.

35. The apparatus of claim 34, wherein the fixed pattern is not a rotating pattern through the disks of the expanded array.

36. A apparatus for distributing parity blocks across a disk array, comprising:

means for providing a pre-existing disk array with a number of pre-existing disks, each pre-existing disk divided into a plurality of blocks;

means for assigning data blocks and parity blocks to the pre-existing disks in stripes, where each disk is arranged with approximately one over the number of pre-existing disks of parity blocks per disk;

means for adding a plurality of new disks to the pre-existing array to form an expanded array with a new number of disks, where N is equal to the number of pre-existing disks plus the plurality of new disks, the plurality of new disks each divided into a plurality of blocks; and

means for reassigning the parity blocks across the expanded array to arrange the parity blocks with approximately 1/N blocks of parity on each disk by moving every Nth parity block stored on each of the pre-existing disks to the plurality of new disks.

37. The apparatus of claim 36, where the means for reassigning is accomplished without recalculation of parity blocks or moving of any blocks containing data.

38. The apparatus of claim 36, where the plurality of disks can be any number of disks and there is no limit to the number of disks in the expanded array.

39. A system to distribute parity blocks across a disk array, comprising:

a pre-existing disk array with a number of pre-existing disks, each pre-existing disk divided into a plurality of blocks;

a storage module to assign data blocks and parity blocks to the pre-existing disks in stripes, where each disk is arranged with approximately one over the number of pre-existing disks of parity blocks per disk;

an expanded array comprising a new disk and the number of pre-existing disks, where the expanded array includes a new number of disks, the new disk divided into a plurality of blocks, where N is equal to the number of pre-existing disks plus the new disk; and

the storage module further configured to reassign the parity blocks across the expanded array to arrange the parity blocks with approximately 1/N blocks of parity on each disk by moving every Nth parity block stored on each of the pre-existing disks to the new disk.

40. The system of claim 39, wherein the storage module is further configured to reassign the parity blocks without recalculation of parity blocks or moving of any blocks containing data.

41. The system of claim 39, wherein the storage module is further configured to generate to reassigning the parity blocks in a fixed pattern of 1/N of parity blocks per a repeat interval.

42. The system of claim 41, wherein the fixed pattern is not a rotating pattern through the disks of the expanded array.

43. A system for distributing parity blocks across a disk array, comprising:

a pre-existing disk array with a number of pre-existing disks, each pre-existing disk divided into a plurality of blocks;

a storage module configured to assign data blocks and parity blocks to the pre-existing disks in stripes, where each disk is arranged with approximately one over the number of pre-existing disks of parity blocks per disk;

an expanded array comprising a plurality of new disks and the number of pre-existing disks, where the expanded array includes a new number of disks, the plurality of new disks each divided into a plurality of blocks, where N is equal to the number of pre-existing disks plus the plurality of new disks; and

the storage module further configured to reassign the parity blocks across the expanded array to arrange the parity blocks with approximately 1/N blocks of parity on each disk by moving every Nth parity block stored on each of the pre-existing disks to the plurality of new disks.

44. The system of claim 43, wherein the storage module is further configured to reassign without recalculation of parity blocks or moving of any blocks containing data.

45. The system of claim 43, wherein the plurality of disks can be any number of disks and there is no limit to the number of disks in the expanded array.

46. A computer readable medium containing executable program instructions for distributing parity blocks across a disk array, comprising:

providing a pre-existing disk array with a number of pre-existing disks, each pre-existing disk divided into a plurality of blocks;

assigning data blocks and parity blocks to the pre-existing disks in stripes, where each disk is arranged with approximately one over the number of pre-existing disks of parity blocks per disk;

adding a new disk to the pre-existing array to form an expanded array with a new number of disks, where N is equal to the number of pre-existing disks plus the new disk, the new disk divided into a plurality of blocks; and

reassigning the parity blocks across the expanded array to arrange the parity blocks with approximately 1/N blocks of parity on each disk by moving every Nth parity block stored on each of the pre-existing disks to the new disk.

47. A computer readable medium containing executable program instructions for distributing parity blocks across a disk array, comprising:

providing a pre-existing disk array with a number of pre-existing disks, each pre-existing disk divided into a plurality of blocks;

assigning data blocks and parity blocks to the pre-existing disks in stripes, where each disk is arranged with approximately one over the number of pre-existing disks of parity blocks per disk;

adding a plurality of new disks to the pre-existing array to form an expanded array with a new number of disks, where N is equal to the number of pre-existing disks plus the plurality of new disks, the plurality of new disks each divided into a plurality of blocks; and

reassigning the parity blocks across the expanded array to arrange the parity blocks with approximately 1/N blocks of parity on each disk by moving every Nth parity block stored on each of the pre-existing disks to the plurality of new disks.