Apparatus and method for reconstructing data using cross-parity stripes on storage media

• US 6,581,185 B1
• Filed: 01/24/2000
• Issued: 06/17/2003
• Est. Priority Date: 01/24/2000
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Storage Technologies Corporation (Oracle Corporation)
• Inventors: Hughes, James Prescott
• Primary Examiner(s): Chung, Phung M.
• Assistant Examiner(s): BRITT, CYNTHIA H
• Application Number:
  US09/490,258
• Time in Patent Office: 1,240 Days
• Field of Search: 714/701, 714/702, 714/804, 714/723, 714/766, 714/711, 714/770, 711/114
• US Class Current: 714/804
• 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/108 RAIT, i.e. RAID on tape drive
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• CPC Class Codes: H03M 13/11 using multiple parity bits

Abstract

An apparatus and method for reconstructing missing data using cross-parity stripes on a storage medium is provided. The apparatus and method may operate on data symbols having sizes greater than a data bit. The apparatus and method makes use of a plurality of parity stripes for reconstructing missing data stripes. The parity symbol values in the parity stripes are used as a basis for determining the value of the missing data symbol in a data stripe. A correction matrix is shifted along the data stripes, correcting missing data symbols as it is shifted. The correction is performed from the outside data stripes towards the inner data stripes to thereby use previously reconstructed data symbols to reconstruct other missing data symbols.

Claims

1. A method of reconstructing missing data when reading data from a storage medium, comprising:

reading parity symbol values from a plurality of parity stripes on the storage medium;

determining, for each parity symbol, a total data value for known data symbols along a line associated with a parity stripe within the plurality of parity stripes;

calculating a value for any missing data from the parity symbol value and the total data value; and

using a correction matrix to reconstruct the missing data, wherein the correction matrix has a plurality of lines of different slope that are used to reconstruct missing data in data stripes, and wherein the missing data of the data stripes is reconstructed in an order based on an ordering of slopes of the lines of the correction matrix.

2. The method of claim 1, wherein the parity symbol values and the data symbols have a data size of at least two bits.

3. The method of claim 1, wherein each line within the plurality of lines is associated with a parity shape.

4. The method of claim 1, wherein a line of the correction matrix having a smallest slope is used to reconstruct missing data in an outer most data stripe.

5. The method of claim 4, wherein, once missing data in the outer most data stripe is reconstructed, a line of the correction matrix having a next larger slope than the smallest slope line is used to reconstruct missing data in a next inner data stripe.

6. The method of claim 1, wherein the plurality of parity stripes includes at least four cross-parity stripes.

7. A storage medium, comprising:

a plurality of data stripes, the data stripes being comprised of a plurality of data symbols;

at least three cross-parity stripes, the cross parity stripes being comprised of a plurality of parity symbols, wherein the parity symbols of the cross-parity stripes are used to reconstruct missing data symbols when the data stripes are read; and

a preface section and suffix section, wherein the data symbols in the preface section and suffix section are assumed to be zero.

8. The storage medium claim 7, wherein the data symbols and the parity symbols have a data size of at least two bits.

9. The storage medium of claim 7, wherein sizes of the preface section and the suffix section are each equal to a number of the plurality of data stripes multiplied by a number of the plurality of parity stripes.

10. The storage medium of claim 7, wherein a length of the parity stripes is equal to a sum of a length of the plurality of data stripes and a multiple of the number of the plurality of data stripes.

11. The storage medium of claim 7, wherein each parity symbol of the plurality of parity symbols is a resulting value obtained from an exclusive OR operation applied to each of the data symbols in a line traversing the plurality of data stripes, the line being associated with a parity stripe in which the parity symbol is located.

12. A redundant array of independent tapes (RAIT) system having a set of tape drives, comprising:

a plurality of data stripes, the data stripes being comprised of a plurality of data symbols;

a set of parity stripes, the set of parity stripes being comprised of a plurality of parity symbols, wherein the plurality of data stripes and the set of parity stripes are distributed over the set of tape drives of the RAIT system, and wherein the parity symbols of the set of parity stripes are used to reconstruct data symbols that are not read when the data stripes are read; and

a preface section and a suffix section, wherein data symbols in the preface section and the suffix section are assumed to be zero.

13. The RAIT system of claim 12, wherein the data symbols and the parity symbols have a data size of two or more bits.

14. The RAIT system of claim 12, wherein sizes of the preface section and the suffix section are each equal to a number of the plurality of data stripes multiplied by a number of the set of parity stripes.

15. The RAIT system of claim 12, wherein a length of the set of parity stripes is equal to a sum of a length of the plurality of data stripes and a multiple of the number of the plurality of data stripes.

16. The RAIT system of claim 12, wherein each parity symbol of the plurality of parity symbols is a resulting value obtained from an exclusive OR operation applied to each of the data symbols in a line traversing the plurality of data stripes, the line being associated with a parity stripe in the set of parity stripes in which the parity symbol is located.

17. A method of reconstructing data lost due to a stripe read error when reading a storage medium, comprising:

reading data symbols from a plurality of data stripes of the storage medium, the data symbols having missing data symbols;

reading parity symbols from a plurality parity stripes; and

using the parity symbols and data symbols along with a correction matrix to reconstruct the missing data symbols, wherein the correction matrix has a plurality of lines of different slope that are used to reconstruct missing data in data stripes, and wherein the missing data of the data stripes is reconstructed in an order based on an ordering of slopes of the lines of the correction matrix.

18. The method of claim 17, wherein the data symbols and the parity symbols have a size of one of a byte of data or a data word.

19. The method of claim 17, wherein each line is associated with a parity stripe of the plurality of parity stripes.

20. The method of claim 17, wherein a line of the correction matrix having a smallest slope is used to reconstruct missing data in an outer most data stripe of the plurality of data stripes.

21. The method of claim 20, wherein, once missing data in the outer most data stripe is reconstructed, a line of the correction matrix having a next larger slope than the smallest slope line is used to reconstruct missing data in a next inner data stripe of the plurality of data stripes.

22. The method of claim 17, wherein the plurality of parity stripes includes at least four cross-parity stripes.

23. A data reconstruction apparatus, comprising:

a controller;

a data input interface; and

a data reconstruction unit, wherein data is read from a plurality of data stripes on a medium and input to the controller via the data input interface, the controller determines if the data input to the controller indicates that there is missing data, if missing data is present, the controller instructs the data reconstruction unit to reconstruct the missing data, and wherein the data reconstruction unit uses a correction matrix to reconstruct the missing data, wherein the correction matrix has a plurality of lines of different slope that are used to reconstruct missing data in the plurality of data stripes, and wherein the missing data of the plurality of data stripe is reconstructed in an order based on an ordering of slopes of the lines of the correction matrix.

24. The reconstruction apparatus of claim 23, wherein the data reconstruction unit reads parity data from a plurality of parity stripes and uses other parity data, the data input into the controller, and a correction matrix to reconstruct the missing data.

25. The data reconstruction apparatus of claim 24, wherein each line is associated with a parity stripe of the plurality of parity stripes.

26. The method of claim 24, wherein the plurality of parity stripes includes at least four cross-parity stripes.

27. The data reconstruction apparatus of claim 23, wherein a line of the correction matrix having a smallest slope is used to reconstruct missing data in an outer most data stripe of the plurality of data stripes.

28. The data reconstruction apparatus of claim 27, wherein, once missing data in the outer most data stripe is reconstructed, a line of the correction matrix having a next larger slope than the smallest slope line is used to reconstruct missing data in a next inner data stripe of the plurality of data stripes.