System and method for enabling efficient recovery of data in a storage array

• US 20060074954A1
• Filed: 09/30/2004
• Published: 04/06/2006
• Est. Priority Date: 09/30/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Hafner, James Lee, Kanungo, Tapas, Hartline, Jeffrey R.
• Granted Patent: US 7,321,905 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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/1059 Parity-single bit-RAID5, i.e. RAID 5 implementations
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A recovery enabling system for storage arrays is a high distance generalization of RAID-5 with optimal update complexity and near optimal storage efficiency. The recovery enabling system utilizes presets, data cells with known values that initialize the reconstruction process. The presets allow resolution of parity equations to reconstruct data when failures occur. In one embodiment, additional copies of the layout of the recovery enabling system are packed onto the same disks to minimize the effect of presets on storage efficiency without destroying the clean geometric construction of the recovery enabling system. The recovery enabling system has efficient XOR-based encoding, recovery, and updating algorithms for arbitrarily large distances, making the recovery enabling system an ideal candidate when storage-efficient reliable codes are required.

Claims

1. A method of reliably storing data on a plurality of storage devices, comprising:

forming a stripe by;

logically partitioning a portion of each of the storage devices into one strip;

organizing strips on the storage devices into a stripe;

designating a plurality of strips as data strips and the remainder of the strips in the stripe as parity strips;

partitioning each data strip into a plurality of data elements;

partitioning each parity strip into a plurality of parity elements;

ordering the data strips containing data from a first data strip to a last data strip;

defining a set of parity slopes as a plurality of parity slope values, wherein each parity slope labels one parity strip;

designating at least some of the data elements as a plurality of preset data elements by assigning a predetermined value to each of the preset data elements;

identifying at least two data strips that contain a different number of presets;

associating with each parity element, a set of data elements defined by selecting a data element from the first data strip, following a sloped line having a parity slope corresponding to a parity strip of the parity element through the data elements from one data strip to a next data strip, with wrap-around from a top of one data strip to a bottom of the next data strip, until all the data strips have been touched by the sloped line; and

for each parity element, computing a parity value from data values stored in the data elements associated to the parity element and storing that parity value in the parity element.

2. The method of claim 1, wherein for a jth parity element on a parity strip, selecting a data element from the first data strip comprises starting at a jth data element of the first data strip.

3. The method of claim 1, wherein computing the parity value comprises computing an XOR of the data values stored in the data elements associated with the parity element.

4. The method of claim 1, wherein each strip contains a fixed number of blocks;

and

wherein the fixed number of blocks is the same for each strip.

5. The method of claim 1, wherein partitioning each strip comprises partitioning each strip into a plurality r of elements;

wherein the strips comprise n data strips and p parity strips; and

wherein r is at least equal to [(p−

1)*n].

6. The method of claim 1, wherein the parity slope values of the parity slopes comprise integers.

7. The method of claim 1, wherein some of the preset data elements comprise logical elements that do not require a physical location on a storage device.

8. The method of claim 1, wherein the presets generally form a triangle.

9. The method of claim 1, wherein the presets generally form two triangles.

10. The method of claim 7, further comprising a plurality of stripes;

and

wherein at least some logical presets of each stripe are physically assigned to any one or more of presets, data elements, and parity elements from a stripe.

11. The method of claim 10, wherein each stripe is rotated by at least one storage device with respect to a preceding stripe;

and

wherein all the presets are logical and are assigned to any of data elements or parity elements by shifting up each strip of each stripe so that any of a data element or a parity element overlays a logical preset of a stripe.

12. The method of claim 10, comprising forming a first stripe and a second stripe;

wherein the second stripe forms a reflection of the first stripe; and

wherein all the logical presets of the first stripe are assigned to any of data elements or parity elements of the second stripe by overlaying any of the data elements or parity elements of the first stripe onto the logical presets of the second stripe.

13. The method of claim 10, comprising forming a first stripe and a second stripe;

wherein the first stripe is formed so that the presets form a concave wedge;

wherein the second stripe is formed so that the presets form a convex wedge; and

wherein some of the logical presets of each of the first and second stripes are assigned to any of presets, data elements, or parity elements of the other stripe by overlaying a convex wedge of the second stripe into the concave wedge of the first stripe.

14. A computer program product having a plurality of executable instruction codes for reliably storing data on a plurality of storage devices, comprising:

instruction codes for forming a stripe including;

a first set of instruction codes for logically partitioning a portion of each of the storage devices into one strip;

a second set of instruction codes for organizing strips on the storage devices into a stripe;

a third set of instruction codes for designating a plurality of strips as data strips and the remainder of the strips in the stripe as parity strips;

a fourth set of instruction codes for partitioning each data strip into a plurality of data elements;

a fifth set of instruction codes for partitioning each parity strip into a plurality of parity elements;

a sixth set of instruction codes for ordering the data strips containing data from a first data strip to a last data strip;

a seventh set of instruction codes for defining a set of parity slopes as a plurality of parity slope values, wherein each parity slope labels one parity strip;

an eight set of instruction codes for designating at least some of the data elements as a plurality of preset data elements by assigning a predetermined value to each of the preset data elements;

a ninth set of instruction codes for identifying at least two data strips that contain a different number of presets;

a tenth set of instruction codes for associating with each parity element, a set of data elements defined by selecting a data element from the first data strip, following a sloped line having a parity slope corresponding to a parity strip of the parity element through the data elements from one data strip to a next data strip, with wrap-around from a top of one data strip to a bottom of the next data strip, until all the data strips have been touched by the sloped line; and

for each parity element, an eleventh set of instruction codes for computing a parity value from data values stored in the data elements associated to the parity element and storing that parity value in the parity element.

15. The computer program product of claim 14, wherein for a jth parity element on a parity strip, the tenth set of instruction codes selects a data element from the first data strip by starting at a jth data element of the first data strip.

16. The computer program product of claim 14, wherein the eleventh set of instruction codes computes the parity value by computing an XOR of the data values stored in the data elements associated with the parity element.

17. The computer program product of claim 14, wherein each strip contains a fixed number of blocks;

and

wherein the fixed number of blocks is the same for each strip.

18. The computer program product of claim 14, wherein some of the preset data elements comprise logical elements that do not require a physical location on a storage device.

19. The computer program product of claim 18, further comprising a plurality of stripes;

and

wherein at least some logical presets of each stripe are physically assigned to any one or more of presets, data elements, and parity elements from a stripe.

20. A storage system capable of reliably storing data on a plurality of storage devices, comprising:

means for forming a stripe comprising;

means for logically partitioning a portion of each of the storage devices into one strip;

means for organizing strips on the storage devices into a stripe;

means for designating a plurality of strips as data strips and the remainder of the strips in the stripe as parity strips;

means for partitioning each data strip into a plurality of data elements;

means for partitioning each parity strip into a plurality of parity elements;

means for ordering the data strips containing data from a first data strip to a last data strip;

means for defining a set of parity slopes as a plurality of parity slope values, wherein each parity slope labels one parity strip;

means for designating at least some of the data elements as a plurality of preset data elements by assigning a predetermined value to each of the preset data elements;

means for identifying at least two data strips that contain a different number of presets;

means for associating with each parity element, a set of data elements defined by selecting a data element from the first data strip, following a sloped line having a parity slope corresponding to a parity strip of the parity element through the data elements from one data strip to a next data strip, with wrap-around from a top of one data strip to a bottom of the next data strip, until all the data strips have been touched by the sloped line; and

for each parity element, means for computing a parity value from data values stored in the data elements associated to the parity element and storing that parity value in the parity element.