Efficient method for providing fault tolerance against double device failures in multiple device systems

• US 5,862,158 A
• Filed: 02/14/1996
• Issued: 01/19/1999
• Est. Priority Date: 11/08/1995
• Status: Expired due to Term

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Park, Chan-ik, Baylor, Sandra Johnson, Corbett, Peter Frank
• Primary Examiner(s): CHUNG, PHUNG M
• Application Number:
  US08/601,394
• Time in Patent Office: 1,070 Days
• Field of Search: 371/49.1, 371/49.2, 371/21.1, 395/182, 395/182.04
• US Class Current: 714/800
• 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/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations

Abstract

A method for storing redundant information in an array of data storage devices such that data is protected against two simultaneous storage device failures. The method assigns each data block to two different parity sets, each protected by a different parity block. The protected data blocks and the parity block each reside on a different data storage device.

Claims

1. A method for protecting against single and double storage device failures in a group of N storage devices, comprising:

logically partitioning each of the storage devices into a plurality of data storage locations;

a) selecting a data storage location on 1 to N-2 of the data storage devices to be data-block-members of a parity set to be protected by parity, the selected data storage locations storing data to be protected;

b) computing a parity block for the data-block-members and assigning the parity block to the parity set;

c) storing the parity block in one of the storage devices that does not store one of the data-block-members of the parity set;

generating one or more additional parity sets by repeating steps a)-c) such that each data-block-member is a member of two or more parity sets, and such that no two members of a parity set are members of the same additional parity set.

2. The method of claim 1, wherein each data storage location is the same size.

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

4. The method of claim 1, wherein each device includes M data locations, and wherein N is greater than or equal to 2M.

5. The method of claim 1, wherein each data-block-member is a member of three or more parity sets.

6. A method for protecting against single and double storage device failures in a group of N storage devices, comprising:

logically partitioning each of the storage devices into a plurality of data storage locations;

defining a plurality of data stripes on each storage device, each data stripe on each data storage device comprising a plurality of data storage locations on that data storage device;

assigning each data stripe to a data band, such that no two data stripes from the same storage device are assigned to the same data band;

a) selecting one data storage location from each of 1 to N-2 stripes of a band to be data-block-members of a parity set to be protected by parity;

b) computing a parity block for the data-block-members and assigning the parity block to the parity set;

c) storing the parity block in the same band in one of the storage devices that does not store one of the data-block-members of the parity set;

generating one or more additional parity sets by repeating steps a)-c) such that each data-block-member is a member of two parity sets, and such that no two members of a parity set are members of the same additional parity set.

7. The method of claim 6, wherein each data stripe in a data band contains the same number of data storage locations.

8. The method of claim 6, wherein each data storage device contains the same number of data stripes.

9. The method of claim 6, wherein the data storage devices are disks in an array of disks.

10. The method of claim 6, wherein each data storage device has the same number of data storage locations.

11. The method of claim 6, wherein the parity block of a parity set is computed by XORing each of the data-block-members of the parity set.

12. The method of claim 6, wherein each parity set has the same number of members.

13. The method of claim 6, wherein the members of each parity set are assigned in a cyclic pattern.

14. The method of claim 13, wherein the cyclic pattern is determined as follows:

defining a parity set vector containing N symbols that include one which corresponds to a parity block stored on the data storage device and the remaining symbols including two each that correspond to each unique data block stored on the data storage device, and the remaining symbol or symbols in the vector being null symbols;

defining a parity assignment matrix having N rows, each row comprising the elements of the parity set vector shifted by one or more places from the previous row, wherein each column of the matrix represents a different parity set and each row of the matrix represents a different storage device;

for each data block and parity block;

assigning a data block on a given storage device to the two parity sets represented by the columns in which the symbol corresponding to that data block appears in the matrix;

assigning a parity block on a given storage device to the parity set represented by the column in which the symbol corresponding to that parity block appears in the matrix.

15. The method of claim 14, further comprising permuting the device assignments after the steps of assigning a data block and assigning a parity block.

16. The method of claim 14, further comprising permuting the symbols that correspond to the parity blocks and the data blocks.

17. The method of claim 14, further comprising permuting the data blocks on a device.

18. A method for assigning parity and data blocks to a parity set to insure recovery from single and double storage device failures in a system having a plurality of data storage devices, comprising the steps of:

assigning one of N unique symbols to each storage device;

partitioning each storage device into M different data blocks, and assigning each data block a unique symbol;

defining a parity set vector containing N symbols that include one which corresponds to a parity block stored on the data storage device and the remaining symbols including two each that correspond to each unique data block symbol stored on the data storage device, and the remaining symbol or symbols in the vector being null symbols;

defining a parity assignment matrix having N rows, each row comprising the elements of the parity set vector shifted by one or more places from the previous row, wherein each column of the matrix represents a different parity set and each row of the matrix represents a different storage device;

for each data block and parity block;

assigning a data block on a given storage device to the two parity sets represented by the columns in which the symbol corresponding to that data block appears in the matrix;

assigning a parity block on a given storage device to the parity set represented by the column in which the symbol corresponding to that parity block appears in the matrix.

19. The method of claim 18 further comprising:

computing a parity for the data blocks in a parity data set; and

storing the parity in the parity block of the parity set.

20. The method of claim 18, wherein the parity is computed by XORing the data blocks of the parity set.

21. The method of claim 18, wherein N is greater than or equal to 2M.

22. The method of claim 18, wherein each data storage device is a disk in a redundant array of disks.

23. A system for protecting against single and double storage device failures in a group of N storage devices, comprising:

means for logically partitioning each of the storage devices into a plurality of data storage locations;

a) means for selecting a data storage location on 1 to N-2 of the data storage devices to be data-block-members of a parity set to be protected by parity, the selected data storage locations storing data to be protected;

b) means for computing a parity block for the data-block-members and assigning the parity block to the parity set;

c) means for storing the parity block in one of the storage devices that does not store one of the data-block-members of the parity set; and

means for generating one or more additional parity sets by repeating steps a)-c) such that each data-block-member is a member of two parity sets, and such that no two members of a parity set are members of the same additional parity set.