Semi-static distribution technique

• US 20050114594A1
• Filed: 11/24/2003
• Published: 05/26/2005
• 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.
• Granted Patent: US 7,185,144 B2
• Time in Patent Office: Days
• 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 across a disk array, the method comprising the steps of:

adding a new disk to 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 without recalculation or moving of any blocks containing data.

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 certain stripes comprise 1/N of the stripes, where N is equal to the number of disks in the array.

7. 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.

8. The method of claim 1 wherein the step of distributing comprises the step of reassigning one of N blocks containing parity (parity blocks) from each pre-existing disk to the added disk, wherein N is equal to the number of disks in the array.

9. The method of claim 8 wherein the step of reassigning comprises the step of reassigning one of N parity blocks to the new disk, with each pre-existing disk continuing to hold 1/N of the parity blocks in the array.

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

a disk array comprising 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 without recalculation or moving of any data blocks.

11. The system of claim 10 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.

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

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

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

15. The system of claim 10 wherein the disk array is a block-based RAID array.

16. A method for distributing commodities over containers of a system, the method comprising the steps of:

adding a new container to pre-existing containers of the system to thereby provide N containers; and

moving only 1/N of the commodities to the new container.

17. The method of claim 16 wherein the system is a storage system, the commodities are data structures adapted for storage on storage devices of an array, and the containers are storage entities coupled to the array.

18. The method of claim 17 wherein the storage entities are storage heads.

19. The method of claim 17 wherein the data structures are inode file blocks.

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

means for adding a new disk to 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 without recalculation or moving of any blocks containing data.

21. 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 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 without recalculation or moving of any blocks containing data.