Technique for efficiently organizing and distributing parity blocks among storage devices of a storage array

• US 7,398,460 B1
• Filed: 01/31/2005
• Issued: 07/08/2008
• Est. Priority Date: 01/31/2005
• Status: Active Grant

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Corbett, Peter F.
• Primary Examiner(s): CHASE, SHELLY A
• Application Number:
  US11/047,084
• Time in Patent Office: 1,254 Days
• Field of Search: 714/800
• US Class Current: 714/800
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

A method for organizing and distributing parity blocks among storage devices of an array coupled to a storage system is disclosed. First the array is configured with a predetermined number of devices. Each device is divided into blocks. The blocks are organized into stripes, wherein each stripe contains at least one first device that holds at least one row parity block, at least one second device that holds at least one diagonal parity block, and a plurality of devices that hold data blocks. An extra parity block is appended within each stripe. Each data block is assigned to one row parity set and one diagonal parity set, such that any one or any combination of two devices can fail concurrently and data on the failed devices can be reconstructed.

Claims

1. A method for organizing and distributing parity blocks among storage devices of an array coupled to a storage system, comprising:

configuring the array with a predetermined number of devices;

dividing each device into blocks;

organizing the blocks into stripes, wherein each stripe contains at least one first device that holds at least one row parity block, at least one second device that holds at least one diagonal parity block, and a plurality of devices that hold data blocks;

appending an extra parity block within each stripe; and

assigning each data block to one row parity set and one diagonal parity set, such that any one or any combination of two devices can fail concurrently and data on the failed devices can be reconstructed.

2. The method of claim 1, wherein the extra parity block is appended to the second device holding the diagonal parity blocks within that stripe, such that an uneven device length arises within the stripe.

3. The method of claim 1, wherein the first predetermined number of devices is n.

4. The method of claim 3, wherein n is any prime number plus 2.

5. The method of claim 3, further comprising:

distributing the parity blocks among the devices of each of n different adjacent stripes to create a super-stripe containing n stripes that balances the sizes of the devices.

6. The method of claim 5, further comprising:

repeating the super-stripe over an entire length of the devices.

7. The method of claim 3, wherein organizing further comprises:

organizing the blocks into stripes, each stripe comprising (n×

(n−

3))+1 blocks.

8. The method of claim 1, wherein appending further compromises:

obviating additional logical operations to thereby reduce the amount of computation needed to encode diagonal parity.

9. The method of claim 8, further comprising:

computing parity contained in the parity blocks using addition over fixed size multi-bit fields.

10. The method of claim 1, wherein organizing further comprises:

exchanging a first block at a first position on a device to a second position of a second block on the device without affecting contents of the blocks; and

altering assignment of the blocks to parity sets.

11. The method of claim 1, further comprising:

rotating assignment of the diagonal parity blocks by one device after each pattern recurrence.

12. The method of claim 1, wherein each device is a disk.

13. The method of claim 1, wherein dividing further comprises:

dividing each device into blocks of fixed size.

14. A system for efficiently organizing and distributing parity blocks among devices coupled to a storage system, the system comprising:

an array having a plurality of devices, each device divided into blocks, the blocks organized into stripes, wherein each stripe contains a first device that holds row parity blocks, a second device that holds diagonal parity blocks and remaining devices that hold data blocks and wherein the number of blocks on each device of each stripe is equal;

a storage operating system including a device storage layer configured to implement a distributed parity technique that appends an extra parity block within each stripe, the device storage layer assigning each data block to one row parity set and one diagonal parity set, such that any one or any combination of two devices can fail concurrently and data on the failed devices can be reconstructed; and

a processing element configured to execute the storage operating system to thereby invoke storage access operations to and from the array in accordance with the distributed parity technique.

15. The system of claim 14, wherein the extra parity is appended to the second device holding the diagonal parity blocks within that stripe, such that an uneven device length arises within that stripe.

16. The system of claim 14, wherein the device storage layer further distributes the parity blocks among the devices of each stripe to create a super-stripe that balances the sizes of the devices.

17. The system of claim 16, wherein the devices are disks and wherein the device storage layer is a RAID layer.

18. The system of claim 14, wherein the devices are a video tape, magnetic tape, optical, DVD, or bubble memory devices.

19. The system of claim 14, wherein the devices are media adapted to store information contained within the data and parity blocks.

20. The system of claim 14, wherein the blocks are of fixed size.

21. The system of claim 20, wherein the fixed size of the blocks is a power of two number of bytes.

22. The system of claim 14, wherein the device storage layer is further configured to rotate assignment of the diagonal parity blocks by one device after each pattern recurrence.

23. A computer readable medium containing executable program instructions for efficiently organizing and distributing parity blocks among disks of a disk array coupled to a storage system, the executable program instructions comprising program instructions for:

configuring the array with a predetermined number of devices;

dividing each device into blocks;

organizing the blocks into stripes, wherein each stripe contains at least one first device that holds at least one row parity block, at least one second device that holds at least one diagonal parity block, and a plurality of devices that hold data blocks;

appending an extra parity block within each stripe; and

assigning each data block to one row parity set and one diagonal parity set, such that any one or any combination of two devices can fail concurrently and data on the failed devices can be reconstructed.