Method and system for a disk fault tolerance in a disk array using rotating parity
First Claim
1. A method of providing disk fault tolerance in an array of independent data storage disks, wherein the disks are indexed and organized into a plurality of indexed stripes, each stripe further comprising a plurality of strips indexed by both disk and stripe, each of the strips being located on only a corresponding single disk, the method comprising:
- forming a plurality of blocks, each block comprising a plurality of stripes extending across multiple disks;
reserving at least one parity stripe in each block for storing only parity in parity strips of the parity stripe;
dividing each block into a plurality of chunks, wherein each chunk is defined by the intersection of a respective block and the respective disk on which the strips comprising the chunk are located, and each strip of each chunk is defined by the intersection of a respective stripe and the respective disk on which the strip is located;
reserving at least one of the chunks for storing horizontal parity;
reserving at least one of the chunks for storing diagonal parity;
arranging, in respective blocks, strips containing data into horizontal and diagonal parity sets, wherein each parity set comprises at least one data strip as a member and no single data strip is repeated in any one parity set;
calculating, for respective blocks, a horizontal parity for each horizontal parity set;
calculating, for respective blocks, a diagonal parity for each diagonal parity set;
storing, in respective blocks, each respective calculated horizontal parity of each horizontal parity set in a corresponding strip of a horizontal parity chunk;
storing, in respective blocks, at least some of the calculated diagonal parities of each diagonal parity set in a respective one of a plurality of strips of a first diagonal parity chunk and storing, in respective blocks, a remainder of the calculated diagonal parities in a respective one of a plurality of strips in a first diagonal parity stripe so that no members of a contributing diagonal parity set have the same disk index as the disk index of the respective one of a plurality of strips of the first diagonal parity stripe; and
shifting the position of each parity chunk in each block to a different disk with respect to a corresponding parity chunk storing parity values of a corresponding parity set in adjacent blocks.
18 Assignments
0 Petitions
Accused Products
Abstract
A two-dimensional parity method and system for rotating parity information in a disk array, such as a RAID, to provide multiple disk fault tolerance with reduced write bottlenecks, is presented. The method includes forming a plurality of blocks, each block comprising a plurality of stripes extending across multiple disks, reserving at least one stripe in each block for parity, dividing each block into a plurality of chunks, wherein at least one of the chunks in the block comprises parity information, and shifting the position of each parity chunk in each block to a different disk with respect to the parity chunk in adjacent blocks. The method further includes shifting the position of each parity strip in the at least one stripe in each block to a different disk with respect to the parity chunk in adjacent blocks. A system for translating information in a disk array includes an array controller configured to shift parity chunks and parity strips.
126 Citations
17 Claims
-
1. A method of providing disk fault tolerance in an array of independent data storage disks, wherein the disks are indexed and organized into a plurality of indexed stripes, each stripe further comprising a plurality of strips indexed by both disk and stripe, each of the strips being located on only a corresponding single disk, the method comprising:
-
forming a plurality of blocks, each block comprising a plurality of stripes extending across multiple disks; reserving at least one parity stripe in each block for storing only parity in parity strips of the parity stripe; dividing each block into a plurality of chunks, wherein each chunk is defined by the intersection of a respective block and the respective disk on which the strips comprising the chunk are located, and each strip of each chunk is defined by the intersection of a respective stripe and the respective disk on which the strip is located; reserving at least one of the chunks for storing horizontal parity; reserving at least one of the chunks for storing diagonal parity; arranging, in respective blocks, strips containing data into horizontal and diagonal parity sets, wherein each parity set comprises at least one data strip as a member and no single data strip is repeated in any one parity set; calculating, for respective blocks, a horizontal parity for each horizontal parity set; calculating, for respective blocks, a diagonal parity for each diagonal parity set; storing, in respective blocks, each respective calculated horizontal parity of each horizontal parity set in a corresponding strip of a horizontal parity chunk; storing, in respective blocks, at least some of the calculated diagonal parities of each diagonal parity set in a respective one of a plurality of strips of a first diagonal parity chunk and storing, in respective blocks, a remainder of the calculated diagonal parities in a respective one of a plurality of strips in a first diagonal parity stripe so that no members of a contributing diagonal parity set have the same disk index as the disk index of the respective one of a plurality of strips of the first diagonal parity stripe; and shifting the position of each parity chunk in each block to a different disk with respect to a corresponding parity chunk storing parity values of a corresponding parity set in adjacent blocks. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A system for providing disk fault tolerance in an array of independent disks, comprising:
-
an array of disks consecutively indexed and organized into a plurality of indexed stripes, each stripe further comprising a plurality of strips indexed by both disk and stripe; and an array controller coupled to the disk array and configured to; form a plurality of blocks, each block comprising a plurality of stripes extending across multiple disks; reserve at least one parity stripe in each block for storing only parity in parity strips of the parity stripe; divide each block into a plurality of chunks, wherein each chunk is defined by the intersection of a respective block and the respective disk on which the strips comprising the chunk are located, and each strip of each chunk being defined by the intersection of a respective stripe and the respective disk on which the strip is located; reserve at least one of the chunks for storing horizontal parity; reserve at least one of the chunks for storing diagonal parity; arrange, in respective blocks, strips containing data into horizontal and diagonal parity sets, wherein each parity set comprises at least one data strip as a member and no single data strip is repeated in any one parity set; calculate, for respective blocks, a horizontal parity for each horizontal parity set for each block; calculate, for respective blocks, a diagonal parity for each diagonal parity set for each block; store, in respective blocks, each respective calculated horizontal parity of each horizontal parity set in a corresponding strip of a horizontal parity chunk for each block; store, in respective blocks, at least some of the calculated diagonal parities of each diagonal parity set in a respective one of a plurality of strips of a first diagonal parity chunk and store, in respective blocks, a remainder of the calculated diagonal parities in a respective one of a plurality of strips in a first diagonal parity stripe so that no members of a contributing diagonal parity set have the same disk index as the disk index of the respective one of a plurality of strips of the first diagonal parity stripe for each block; and shift the position of each parity chunk in each block to a different disk with respect to the parity chunk in adjacent blocks. - View Dependent Claims (13, 14, 15, 16, 17)
-
Specification