System and method for tolerating multiple storage device failures in a storage system with constrained parity in-degree

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

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Hafner, James Lee, Kanungo, Tapas, Hartline, Jeffrey R.
• Granted Patent: US 7,519,629 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: Y10S 707/99953 Recoverability

Abstract

A fault-tolerant system for storage arrays has constraints on the number of data from which each redundancy value is computed. The fault-tolerant system has embodiments that are supported on small array sizes to arbitrarily large array sizes, and can tolerate a large number T of failures. Certain embodiments can tolerate many instances of more than T failures. The fault-tolerant system has efficient XOR-based encoding, recovery, and updating algorithms and has simple redundancy formulas. The fault-tolerant system has improved IO seek costs for certain multiple-element sequential host updates.

Claims

1. A method of protecting against at least T storage device failures in a group of N storage devices, comprising:

setting a number K between 2 and T inclusive;

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

organizing strips on the storage devices into a stripe;

partitioning each of the strips into at least one data element and at least one parity element;

for each parity element, selecting a set of K data elements from the stripe so that;

(a) the selected set of data elements has not already been selected for another parity element;

(b) the selected data elements are located on K different storage devices; and

(c) the storage devices of the selected data elements are different from the storage device of the parity element;

ensuring that each data element is selected for T different parity elements; and

generating a parity value from data values stored in the K data elements in the selected set of data elements and storing the parity value in the parity element.

2. The method of claim 1, wherein each data element and each parity element have the same size.

3. The method of claim 1, wherein the data storage devices comprise disks in an array of disks.

4. The method of claim 1, wherein the data storage devices are storage nodes in a network of storage devices.

5. The method of claim 1, wherein all the strips have the same number of data elements.

6. The method of claim 1, wherein all the strips have the same number of parity elements.

7. The method of claim 1, wherein a ratio of a number of data elements to a number of parity elements is at most K/(T+K).

8. The method of claim 1, further comprising assigning the data elements to sets of data elements for each parity element in a cyclic pattern.

9. The method of claim 1, further comprising computing parity values by XORing data blocks in the data elements of the selected set of data elements.

10. The method of claim 1, wherein the stripe is characterized by parameters N, T, R, Q wherein:

RT=QK,

and where;

Q represents the number of rows of parity, and R represents the number of rows of data elements.

11. The method of claim 10, wherein R and Q have minimal values defined by the following equation:

R=K/M and Q=T/M where M=gcd(T, K),

where gcd represents a greatest common divisor.

12. The method of claim 1, wherein a pattern for one data element is derived by a rotation of the pattern for any other data element.

13. The method of claim 1, wherein a pattern for one parity element is derived by a rotation of the pattern for any other parity element.

14. The method of claim 1, wherein selecting the set of K data elements from the stripe comprises pairing a data element with one neighbor of the data element within the same row.

15. The method of claim 1, wherein selecting the set of K data elements from the stripe comprises pairing a data element with one neighbor of the data element in a row that is different from the row of the data element.

16. The method of claim 1, wherein selecting the set of K data elements from the stripe comprises selecting T data elements from a set of k data elements from the same row wherein k≧

T starting at some offset S from the parity element.

17. The method of claim 1, wherein selecting for a parity element in the Lth parity row, the set of K data elements from the stripe that comprise first K data elements from the sequence of every L+1 st data element from one row, moving to the right with wrap-around from right to left starting at an offset depending on some offset parameter Sand the numbers L and K.

18. A computer program product having a plurality of executable instruction codes for protecting against at least T storage device failures in a group of N storage devices, comprising:

a first set of instruction codes for setting a numberK between 2 and T inclusive;

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

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

a fourth set of instruction codes for partitioning each of the strips into at least one data element and at least one parity element;

a fifth set of instruction codes for selecting, for each parity element, a set of K data elements from the stripe so that;

(d) the selected set of data elements has not already been selected for another parity element;

(e) the selected data elements are located on K different storage devices; and

the storage devices of the selected data elements are different from the storage device of the parity element;

a sixth set of instruction codes for ensuring that each data element is selected for T different parity elements; and

a seventh set of instruction codes for generating a parity value from data values stored in the K data elements in the selected set of data elements and storing the parity value in the parity element.

19. The computer program product of claim 18, wherein each data element and each parity element have the same size.

20. The computer program product of claim 18, wherein the data storage devices comprise disks in an array of disks.

21. The computer program product of claim 18, wherein the data storage devices are storage nodes in a network of storage devices.

22. The computer program product of claim 18, wherein all the strips have the same number of data elements.

23. The computer program product of claim 18, wherein all the strips have the same number of parity elements.

24. The computer program product of claim 18, wherein a ratio of a number of data elements to a number of parity elements is at most K/(T+K).

25. The computer program product of claim 18, further comprising a ninth set of instruction codes for assigning the data elements to sets of data elements for each parity element in a cyclic pattern.

26. The computer program product of claim 18, further comprising a tenth set of instruction codes for computing parity values by XORing data blocks in the data elements of the selected set of data elements.

27. The computer program product of claim 18, wherein the stripe is characterized by parameters N, T, R, Q wherein:

RT=QK,

and where;

Q represents the number of rows of parity, and R represents the number of rows of data elements.

28. The computer program product of claim 27, wherein R and Q have minimal values defined by the following equation:

R=K/M and Q=T/M where M=gcd(T, K),

where gcd represents a greatest common divisor.

29. The computer program product of claim 18, wherein a pattern for one data element is derived by a rotation of the pattern for any other data element.

30. The computer program product of claim 18, wherein a pattern for one parity element is derived by a rotation of the pattern for any other parity element.

31. The computer program product of claim 18, wherein the fifth set of instruction codes selects the set of K data elements from the stripe by pairing a data element with one neighbor of the data element within the same row.

32. The computer program product of claim 18, wherein the fifth set of instruction codes selects the set of K data elements from the stripe by pairing a data element with one neighbor of the data element in a row that is different from the row of the data element.

33. The computer program product of claim 18, wherein the fifth set of instruction codes selects the set of K data elements from the stripe by selecting T data elements from a set of k data elements from the same row wherein k≧

T starting at some offset S from the parity element.

34. The computer program product of claim 18, wherein the fifth set of instruction codes selects for a parity element in the Lth parity row, the set of K data elements from the stripe that comprise first K data elements of the sequence of every L+1 st data element from one row, moving to the right with wrap-around from right to left, starting at an offset depending on some offset parameter S and the numbers L and K.

35. A storage system capable of protecting against at least T storage device failures in a group of N storage devices, comprising:

means for setting a number K between 2 and T inclusive;

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

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

means for partitioning each of the strips into at least one data element and at least one parity element;

means for selecting, for each parity element, a set of K data elements from the stripe so that;

(g) the selected set of data elements has not already been selected for another parity element;

(h) the selected data elements are located on K different storage devices; and

(i) the storage devices of the selected data elements are different from the storage device of the parity element;

means for ensuring that each data element is selected for T different parity elements; and

means for generating a parity value from data values stored in the K data elements in the selected set of data elements and storing the parity value in the parity element.