Concentrated parity technique for handling double failures and enabling storage of more than one parity block per stripe on a storage device of a storage array

• US 7,970,996 B1
• Filed: 11/30/2009
• Issued: 06/28/2011
• Est. Priority Date: 11/13/2001
• Status: Expired due to Fees

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Corbett, Peter F.
• Primary Examiner(s): TSAI, SHENG JEN
• Application Number:
  US12/627,901
• Time in Patent Office: 575 Days
• Field of Search: 711/114
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks

Abstract

A method for constructing an array of storage devices is disclosed. A number of storage devices is selected. Each storage device stores data in data blocks. A redundancy is established, the redundancy being a number of data blocks for a parity block. A plurality of parity sets is established, a parity set having the number of data blocks for a parity block and having a set parity block. The set parity block for each parity set is computed. Each set parity block is stored on one of the data storage devices that does not store one of the data-block members of the parity set, to store more than one parity block on each storage device, with an exception that two parity blocks for the same data storage location are precluded from being stored on the same data storage device.

Claims

1. A method for constructing an array of storage devices, comprising:

establishing a selected number of storage devices in the array of storage devices, each selected storage device storing data in blocks;

establishing a selected number of data storage blocks for a parity block;

establishing a plurality of parity sets, a parity set having the number of data blocks and having a set parity block, the parity sets chosen so that each data storage block is in more than one parity set;

computing the set parity block for each parity set; and

storing each set parity block on a storage device of the array selected to store parity blocks (hereinafter a parity storage device for each of the plurality of parity sets), to store more than one parity block on each parity storage device, with an exception that two parity blocks for a same data storage location are precluded from being stored on the same is parity storage device.

2. The method of claim 1, further comprising:

establishing each data block in two or more parity sets.

3. The method of claim 1, further comprising:

assigning a data block at a data storage location indicated by “

i”

to a first parity set indicated by “

j” and

to a second parity set indicated by “

k”

, so that there are “

p”

parity sets, as determined by the number of data storage blocks for a parity block;

assigning a selected block to both parity set i+k mod(N) and to parity set (j+k) mod(N), where mod(N) represents modulo N, and where N is the number of data storage devices;

computing a parity delta, where the parity delta is j-k for a row of data; and

having a selected parity delta, where two parity blocks having the same delta are not stored on the same storage device.

4. The method of claim 1, further comprising:

protecting against all single device failures by implementing one parity block for each data block, where a single failure is the loss of one storage device.

5. The method of claim 1, further comprising:

protecting against all double device failures by implementing two parity blocks for each data block, where a double device failure is the loss of two storage devices.

6. The method of claim 1, further comprising:

adding additional data storage devices without moving any data blocks.

7. The method of claim 1, further comprising:

adding additional storage devices without reconfiguring any parity.

8. The method of claim 1, further comprising:

adding additional storage devices without re-computing any parity.

9. The method of claim 1, further comprising:

using a disk as the data storage device.

10. The method of claim 1, further comprising:

using a plurality of disks as the data storage device.

11. The method of claim 1, further comprising:

using a plurality of disks arranged in a RAID configuration as the data storage device.

12. The method of claim 1, further comprising:

using a memory as the data storage device.

13. The method of claim 1, further comprising:

using a magnetic tape as the data storage device.

14. The method of claim 1, further comprising:

using a computer writeable media as the data storage device.

15. The method of claim 1, further comprising:

using a media adapted to store information contained within the data and parity blocks as the storage device.

16. A computer operated data storage system apparatus, comprising:

a selected number of storage devices established as an array of storage devices, each selected storage device storing data in blocks;

a selected number of data storage blocks established for a parity block;

a plurality of parity sets, a parity set having the number of data blocks and having a set parity block, the set the parity sets chosen so that each data storage block is in more than one parity set;

the data storage system configured to compute the set parity block for each parity set; and

the data storage system configured to store each set parity block on a storage device of the array selected to store parity blocks (hereinafter parity storage device for each of the plurality of parity sets), to store more than one parity block on each parity storage device, with an exception that two parity blocks for a same data storage location are precluded is from being stored on the same parity storage device.

17. The apparatus of claim 16, further comprising:

each data block is established in two or more parity sets.

18. The apparatus of claim 16, further comprising:

a data block is assigned a data storage location indicated by “

i”

is assigned to a first parity set indicated by “

j” and

is assigned to a second parity set indicated by “

k”

, so that there are “

p”

parity sets, as determined by the number of data storage blocks for a parity block;

the data storage system configured to assign a selected block to both parity set i+k mod(N) and to parity set (j+k)mod(N), where mod(N) represents modulo N, and where N is the number of data storage devices;

the data storage system configured to compute a parity delta, where the parity delta is j-k for a row of data; and

the data storage system configured to have a selected parity delta, where two parity blocks having the same delta are not stored on the same storage device.

19. The apparatus of claim 16, further comprising:

the data storage system configured to protect against all single device failures by implementing one parity block for each data block, where a single failure is the loss of one storage device.

20. The apparatus of claim 16, further comprising:

the data storage system configured to protect against all double device failures by implementing two parity blocks for each data block, where a double device failure is the loss of two storage devices.

21. The apparatus of claim 16, further comprising:

the data storage system configured to add additional data storage devices without moving any data blocks.

22. The apparatus of claim 16, further comprising:

the data storage system configured to add additional storage devices without reconfiguring any parity.

23. The apparatus of claim 16, further comprising:

the data storage system configured to add additional storage devices without recomputing any parity.

24. The apparatus of claim 16, further comprising:

a disk used as the data storage device.

25. The apparatus of claim 16, further comprising:

a plurality of disks used as the data storage device.

26. The apparatus of claim 16, further comprising:

a plurality of disks arranged in a RAID configuration used as the data storage device.

27. The apparatus of claim 16, further comprising:

a memory used as the data storage device.

28. The apparatus of claim 16, further comprising:

a magnetic tape used as the data storage device.

29. The apparatus of claim 16, further comprising:

a computer writeable media used as the data storage device.

30. The apparatus of claim 16, further comprising:

a media adapted to store information contained within the data and parity blocks used as the storage device.

31. A computer readable storage media, comprising:

said computer readable storage media containing program instructions for execution on a processor for a method of constructing an array of storage devices, the program instructions for,

establishing a selected number of storage devices in the array of storage devices, each storage device storing data in blocks;

establishing a selected number of data storage blocks for a parity block;

establishing a plurality of parity sets, a parity set having the number of data blocks and having a set parity block, the parity sets chosen so that each data storage block is in more than one parity set;

computing the set parity block for each parity set; and

storing each set parity block on a storage device of the array selected to store parity blocks (hereinafter parity storage device for each of the plurality of parity sets), to store more than one parity block on each parity storage device, with an exception that two parity blocks for the same data storage location are precluded from being stored on the same parity storage device.

32. A method for constructing an array of storage devices, comprising:

dividing storage blocks of the storage devices into data blocks for storing data and parity blocks for storing parity;

assigning a plurality of data blocks to a parity set;

assigning each data block to a selected number of parity sets, where the selected number is greater than one; and

storing the parity blocks to a storage device such that, (1) a parity block for a parity set cannot be on a device holding a data block of the parity set, (2) more than one parity block for the parity set assigned to a data block cannot be on the same storage device, and (3) the array is recoverable from up to a selected number of device failures.

33. The method of claim 32, further comprising:

using a disk as the data storage device.

34. The method of claim 32, further comprising:

using a plurality of disks as the data storage device.

35. The method of claim 32, further comprising:

using a plurality of disks arranged in a RAID configuration as the data storage device.

36. The method of claim 32, further comprising:

using a memory as the data storage device.

37. A data storage system apparatus, comprising:

an array of storage devices, each storage device having storage blocks divided into data blocks for storing data and parity blocks for storing parity;

a plurality of data blocks assigned to a parity set;

the data storage system configured to assign each data block to a selected number of parity sets, where the selected number is greater than one; and

the parity blocks stored to a storage device such that, (1) a parity block for a parity set cannot be on a device holding a data block of the parity set, (2) more than one parity block for the parity set assigned to a data block cannot be on the same storage device, and (3) the array is recoverable from up to a selected number of device failures.

38. The apparatus of claim 37, further comprising:

a disk used as the data storage device.

39. The apparatus of claim 37, further comprising:

a plurality of disks used as the data storage device.

40. The apparatus of claim 37, further comprising:

a plurality of disks arranged in a RAID configuration used as the data storage device.

41. The apparatus of claim 37, further comprising:

a memory used as the data storage device.

42. A computer readable storage media, comprising:

said computer readable storage media containing program instructions for execution on a processor for a method of constructing an array of storage devices, each storage device having storage blocks, the program instructions for,

dividing the storage blocks into data blocks for storing data and parity blocks for storing parity;

assigning a plurality of data blocks to a parity set;

assigning each data block to a selected number of parity sets, where the selected number is greater than one; and

storing the parity blocks to a storage device such that, (1) a parity block for a parity set cannot be on a device holding a data block of the parity set, (2) more than one parity block for the parity set assigned to a data block cannot be on the same storage device, and (3) the array is recoverable from up to a selected number of device failures.