Dynamic redistribution of parity groups

• US 7,356,730 B2
• Filed: 12/21/2004
• Issued: 04/08/2008
• Est. Priority Date: 01/29/2001
• Status: Expired due to Fees

• Current Assignee: Adaptec Incorporated (Steel Partners Holdings LP)
• Original Assignee: Adaptec Incorporated (Steel Partners Holdings LP)
• Inventors: Priester, George W., Schweitzer, James R., Bolstad, Gregory D., Staub, John R., Randall, Jay G., Ulrich, Thomas R.
• Primary Examiner(s): PEIKARI, BEHZAD
• Application Number:
  US11/018,114
• Publication Number:
  US 20050144514A1
• Time in Patent Office: 1,204 Days
• Field of Search: None
• US Class Current: 714/6.12
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1004 Adaptive RAID, i.e. RAID system adapts to changing circumstances, e.g. RAID1 becomes RAID5 as disks fill up
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A system and method for dynamic redistribution of parity groups is described. The system and method for dynamic redistribution of parity groups operates on a computer storage system that includes a plurality of disk drives for storing parity groups. Each parity group includes storage blocks. The storage blocks include one or more data blocks and a parity block that is associated with the data blocks. Each of the storage blocks is stored on a separate disk drive such that no two storage blocks from a given parity set reside on the same disk drive. The computer system further includes a redistribution module to dynamically redistribute parity groups by combining some parity groups to improve storage efficiency.

Claims

1. A method for storing data in a computer network, comprising:

determining a size of a parity group in response to a write request, said size describing a number of data blocks in said parity group;

arranging at least a portion of data from said write request according to said data blocks;

computing a parity block for said parity group;

storing each of said data blocks on a separate disk drive such that no two data blocks from said parity group reside on the same disk drive;

storing said parity block on a separate disk drive that does not contain any of said data blocks; and

redistributing said parity group to improve storage efficiency.

2. The method of claim 1, further comprising storing metadata to describe a disk and logical block location of each of said data blocks and said parity block.

3. The method of claim 1, wherein said redistributing comprises combining a first parity group having a first size and a second parity group having a second size to produce a combined parity group having a third size, wherein said third size specifies a number of blocks that is, at most, one less than the number of disk drives available to store data from said parity group.

4. The method of claim 1, wherein said redistributing comprises splitting a first parity group into a second parity group and a third parity group.

5. The method of claim 1, further comprising allocating a new parity group from a pool of available parity groups.

6. The method of claim 5, further comprising generating parity groups for said pool of available parity groups from unused disk space.

7. The method of claim 5, further comprising generating a plurality of differently-sized parity groups for said pool of available parity groups from unused disk space.

8. The method of claim 7, further comprising splitting a parity group in said pool of parity groups to produce two smaller parity groups in said pool of available parity groups.

9. The method of claim 7, further comprising combining one or more parity groups in said pool of parity groups to produce a combined parity group in said pool of available parity groups, said combined group larger than said one or more parity groups.

10. A method for storing data in a computer network, comprising:

storing a first parity group comprising first data blocks and a first parity block, wherein said act of storing the first parity group comprises storing each of said first data blocks on a separate disk drive such that no two of the first data blocks reside on the same disk drive;

storing a second parity group comprising second data blocks and a second parity block, wherein said act of storing the second parity group comprises storing each of said second data blocks on a separate disk drive such that no two of the second data blocks reside on the same disk drive; and

redistributing said first parity group and said second parity group to improve storage efficiency.

11. The method of claim 10, further comprising storing metadata to describe a disk and logical block location of each of said first data blocks and said first parity block.

12. The method of claim 10, wherein said act of redistributing comprises combining the first parity group having a first size and the second parity group having a second size to produce a combined parity group having a third size, wherein said third size specifies a number of blocks that is, at most, one less than the number of disk drives available to store data from said combined parity group.

13. The method of claim 12, wherein the first size of the first parity group is larger than the second size of the second parity group.

14. The method of claim 10, wherein said act of redistributing comprises splitting a first parity group into a third parity group and a fourth parity group.

15. The method of claim 10, further comprising allocating a new parity group from a pool of available parity groups.

16. The method of claim 10, further comprising storing metadata that specifies at least one Gnid-string.

17. The method of claim 16, wherein said Gnid-string comprises a collection of gnids.

18. The method of claim 17, wherein each of said gnids comprises information for locating a specified gnode.

19. A system for storing data in a computer network, comprising:

means for determining a size of a parity group in response to a write request, said size describing a number of data blocks in said parity group;

means for arranging at least a portion of data from said write request according to said data blocks;

means for computing a parity block for said parity group;

means for storing each of said data blocks on a separate disk drive such that no two data blocks from said parity group reside on the same disk drive;

means for storing said parity block on a separate disk drive that does not contain any of said data blocks; and

means for redistributing said parity group to improve storage efficiency.

20. The system of claim 19, wherein said redistributing comprises combining a first parity group having a first size and a second parity group having a second size to produce a combined parity group having a third size, wherein said third size specifies a number of blocks that is, at most, one less than the number of disk drives available to store data from said parity group.