US6581185B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for reconstructing data using cross-parity stripes on storage media
Assignee: Oracle America Inc
•
Filing: 2000-01-24
•
Granted: 2003-06-17
•
Expires: 2020-01-24
Abstract
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.
Inventors
- 👤 James Prescott Hughes
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 03:38
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; G11; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1833; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/11; G06F2211/00; G06F2211/10; G06F2211/1002; G06F2211/108
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
131 words
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.
Claim 2
Independent Claim
131 words
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.
Claim 3
Dependent Claim
24 words
The method of claim 1 , wherein the parity symbol values and the data symbols have a data size of at least two bits.
Claim 4
Dependent Claim
20 words
The method of claim 1 , wherein each line within the plurality of lines is associated with a parity shape.
Claim 5
Dependent Claim
29 words
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.
Claim 6
Dependent Claim
46 words
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.
Claim 7
Dependent Claim
18 words
The method of claim 1 , wherein the plurality of parity stripes includes at least four cross-parity stripes.
Claim 8
Dependent Claim
81 words
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.
Claim 9
Dependent Claim
81 words
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.
Claim 10
Dependent Claim
23 words
The storage medium claim 7 , wherein the data symbols and the parity symbols have a data size of at least two bits.
Claim 11
Dependent Claim
39 words
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.
Claim 12
Dependent Claim
40 words
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.
Claim 13
Dependent Claim
58 words
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.
Claim 14
Dependent Claim
124 words
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.
Claim 15
Dependent Claim
124 words
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.
Claim 16
Dependent Claim
24 words
The RAIT system of claim 12 , wherein the data symbols and the parity symbols have a data size of two or more bits.
Claim 17
Dependent Claim
39 words
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.
Claim 18
Dependent Claim
42 words
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.
Claim 19
Dependent Claim
64 words
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.
Claim 20
Independent Claim
114 words
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.
Claim 21
Independent Claim
114 words
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.
Claim 22
Dependent Claim
28 words
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.
Claim 23
Dependent Claim
21 words
The method of claim 17 , wherein each line is associated with a parity stripe of the plurality of parity stripes.
Claim 24
Dependent Claim
35 words
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.
Claim 25
Dependent Claim
52 words
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.
Claim 26
Dependent Claim
18 words
The method of claim 17 , wherein the plurality of parity stripes includes at least four cross-parity stripes.
Claim 27
Dependent Claim
141 words
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.
Claim 28
Dependent Claim
141 words
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.
Claim 29
Dependent Claim
41 words
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.
Claim 30
Dependent Claim
23 words
The data reconstruction apparatus of claim 24 , wherein each line is associated with a parity stripe of the plurality of parity stripes.
Claim 31
Dependent Claim
18 words
The method of claim 24 , wherein the plurality of parity stripes includes at least four cross-parity stripes.
Claim 32
Dependent Claim
37 words
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.
Claim 33
Dependent Claim
54 words
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.
References Cited (Backward Citations)
US4201976A
Cited
US5579475A
Cited
US5351246A
Cited
US5537567A
Cited
US5623595A
Cited
US5812753A
Cited
US5862158A
Cited
US5884098A
Cited
US5805788A
Cited
US6092215A
Cited
WO1999017217A1
Cited
US6223300B1
Cited
US6138201A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-06-16 | 2006-12-16 | 2007-06-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-06-16 | 2010-12-16 | 2011-06-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-06-16 | 2014-12-16 | 2015-06-17 | $7700.00 | Window Closed / Lapsed |