US5488701A
Expired / Lapsed
US
⏱️ 0.0 years remaining
In log sparing for log structured arrays
Assignee: International Business Machines Corp
•
Filing: 1994-11-17
•
Granted: 1996-01-30
•
Expires: 2014-11-17
Abstract
Abstract In a log structured array (LSA) storage subsystem, a method for recovering from a storage device failure which incorporates the LSA write and garbage collection procedures, thereby simplifying the recovery process and eliminating the need for dedicated or distributed sparing schemes. Data is distributed across the array in N+P parity groups. Upon a device failure, each lost data block is reconstructed from the remaining blocks of its parity group. The reconstructed block is then placed in the subsystem write buffer to be processed with incoming write data, and new parity is generated for the remaining N-1 data blocks of the group. A lost parity block is replaced by first moving one of the data blocks of its parity group to the write buffer, and then generating new parity for the remaining N-1 data blocks. Also disclosed is a storage subsystem implementing the preceding recovery method.
Inventors
- 👤 James T. Brady
- 👤 Jaishankar M. Menon
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 07:17
CPC Classifications
G; G11; G11C; G11C29/00; G11C29/70; G11C29/74; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; G06F11/1088; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; G06F3/00; G06F3/06; G06F3/0601; G06F3/0602; G06F3/0608; G06F3/0628; G06F3/0638; G06F3/064; G06F3/0646; G06F3/0652; G06F3/0668; G06F3/0671; G06F3/0683; G06F3/0689
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
186 words
In a log structured array (LSA) comprising a plurality of storage devices configured in a plurality of segments, wherein a plurality of parity groups are distributed to some of said segments, each parity group comprising a plurality of data block and a parity block, and wherein others of said segments are free, a method for restoring lost ones of said blocks, comprising the steps of: detecting a failure in one of said plurality of storage devices; copying a free segment table to a temporary storage to preserve the state of said free segment table at the time of said failure; testing each segment in said array against said copy of said free segment table, to determine if said segment stores a parity group; determining whether a lost segment column in said parity group is a data block or a parity block; generating a reconstructed data block, if said lost column is determined to be a data block; generating a new parity block from data blocks in said parity group; and storing said reconstructed data block and said new parity block in free segments in said array.
Claim 2
Dependent Claim
186 words
In a log structured array (LSA) comprising a plurality of storage devices configured in a plurality of segments, wherein a plurality of parity groups are distributed to some of said segments, each parity group comprising a plurality of data block and a parity block, and wherein others of said segments are free, a method for restoring lost ones of said blocks, comprising the steps of: detecting a failure in one of said plurality of storage devices; copying a free segment table to a temporary storage to preserve the state of said free segment table at the time of said failure; testing each segment in said array against said copy of said free segment table, to determine if said segment stores a parity group; determining whether a lost segment column in said parity group is a data block or a parity block; generating a reconstructed data block, if said lost column is determined to be a data block; generating a new parity block from data blocks in said parity group; and storing said reconstructed data block and said new parity block in free segments in said array.
Claim 3
Dependent Claim
28 words
The method of claim 1, wherein each lost data block is reconstructed by exclusive OR-ing said remaining of said data and parity blocks of the same parity group.
Claim 4
Dependent Claim
56 words
The method of claim 1, wherein said storage devices are organized by a plurality of physical addresses, said LSA further comprising an updatable LSA directory containing a current list of said data blocks and those of said physical addresses corresponding to said data blocks, wherein said corresponding physical addresses for said reconstructed data blocks are updated.
Claim 5
Dependent Claim
42 words
The method of claim 1, wherein said LSA further comprises a write buffer for temporarily storing a predetermined number of data blocks to be stored in said LSA, including means for generating a parity block therefrom to form a new parity group.
Claim 6
Dependent Claim
45 words
The method of claim 4, wherein said placing step further comprises temporarily storing said reconstructed data blocks in said write buffer, forming a plurality of new parity groups comprising said reconstructed data blocks, and writing each new parity group to one of said free segments.
Claim 7
Dependent Claim
28 words
The method of claim 5, wherein some of said new parity groups further comprise a portion of new write data from a host processor linked to said LSA.
Claim 8
Dependent Claim
28 words
The method of claim 5, wherein some of said new parity groups further comprise a portion of modified write data from a host processor linked to said LSA.
Claim 9
Dependent Claim
56 words
The method of claim 4, wherein a lost parity block is restored by copying one of said remaining data blocks of the same parity group into said write buffer, generating a new parity block from the other of said remaining data blocks, and replacing said copied data block in said array with said new parity block.
Claim 10
Dependent Claim
20 words
The method of claim 8, wherein said new parity block is generated by exclusive OR-ing said other remaining data blocks.
Claim 11
Dependent Claim
20 words
The method of claim 1, wherein said free segments are freed by a garbage collection procedure implemented in said LSA.
Claim 12
Dependent Claim
36 words
The method of claim 1, further comprising the step of generating a new parity block for said remaining data blocks of the same parity group, and replacing said remaining parity block with said new parity block.
Claim 13
Dependent Claim
24 words
The method of claim 11, wherein said new parity block is generated by exclusive OR-ing said remaining data blocks of the same parity group.
Claim 14
Dependent Claim
16 words
The method of claim 1, wherein said array further comprises a plurality of magnetic disk drives.
Claim 15
Dependent Claim
16 words
The method of claim 1, wherein said array further comprises a plurality of optical disk drives.
Claim 16
Dependent Claim
18 words
The method of claim 1, wherein said array further comprises a plurality of optical and magnetic disk drives.
Claim 17
Dependent Claim
34 words
A method according to claim 1, further comprising the step of: generating a new parity block from data blocks in said parity group if said lost column is determined to be a parity block.
Claim 18
Dependent Claim
157 words
A log structured storage array comprising: a plurality of storage devices configured in a plurality of segments, wherein a plurality of parity groups are distributed to some of said segments, each parity group comprising a plurality of data blocks and a parity block, and wherein others of said segments are free; means for detecting a failure in one of said plurality of storage devices; means for copying a free segment table to a temporary storage to preserve the state of said free segment table at the time of said failure; means for testing each segment in said array against said copy of said free segment table to determine if said segment stores a parity group; means for determining whether a lost segment column in said parity group is a data block or a parity block; means for generating a reconstructed data block; and means for generating a new parity block from data blocks in said parity group.
Claim 19
Dependent Claim
157 words
A log structured storage array comprising: a plurality of storage devices configured in a plurality of segments, wherein a plurality of parity groups are distributed to some of said segments, each parity group comprising a plurality of data blocks and a parity block, and wherein others of said segments are free; means for detecting a failure in one of said plurality of storage devices; means for copying a free segment table to a temporary storage to preserve the state of said free segment table at the time of said failure; means for testing each segment in said array against said copy of said free segment table to determine if said segment stores a parity group; means for determining whether a lost segment column in said parity group is a data block or a parity block; means for generating a reconstructed data block; and means for generating a new parity block from data blocks in said parity group.
Claim 20
Dependent Claim
33 words
The LSA of claim 17, wherein said means for reconstructing each lost data block further comprises means for exclusive OR-ing said remaining of said data and parity blocks of the same parity group.
Claim 21
Dependent Claim
57 words
The LSA of claim 17, wherein said storage devices are organized by a plurality of contiguous physical addresses, said LSA further comprising an updatable LSA directory containing a current list of said data blocks, and those of said physical addresses corresponding to said data blocks, wherein said corresponding physical addresses for said reconstructed data blocks are updated.
Claim 22
Dependent Claim
39 words
The LSA of claim 17, further comprising a write buffer for temporarily storing a predetermined number of data blocks to be stored in said LSA, including means for generating a parity block therefrom to form a new parity group.
Claim 23
Dependent Claim
55 words
The LSA of claim 20, wherein said means for placing said reconstructed blocks further comprises means for temporarily storing said reconstructed data blocks in said write buffer, means for forming a plurality of new parity groups comprising said reconstructed data blocks, and means for writing each new parity group to one of said free segments.
Claim 24
Dependent Claim
27 words
The LSA of claim 21, wherein some of said new parity groups include a portion of new write data from a host processor linked to said LSA.
Claim 25
Dependent Claim
27 words
The LSA of claim 21, wherein some of said new parity groups include a portion of modified write data from a host processor linked to said LSA.
Claim 26
Dependent Claim
64 words
The LSA of claim 20, further comprising means for restoring a lost parity block, including means for copying one of said remaining data blocks of the same parity group into said write buffer, means for generating a new parity block from the other of said remaining data blocks, and means for replacing said copied data block in said array with said new parity block.
Claim 27
Dependent Claim
24 words
The LSA of claim 24, wherein said means for generating a new parity further comprises means for exclusive OR-ing said other remaining data blocks.
Claim 28
Dependent Claim
20 words
The LSA of claim 17, wherein said free segments are freed by a garbage collection procedure implemented in said LSA.
Claim 29
Dependent Claim
37 words
The LSA of claim 17, further comprising means for generating a new parity block for said remaining data blocks of the same parity group, and means for replacing said remaining parity block with said new parity block.
Claim 30
Dependent Claim
29 words
The LSA of claim 27, wherein said means for generating a new parity block further comprise means for exclusive OR-ing said remaining data blocks of the same parity group.
Claim 31
Dependent Claim
16 words
The LSA of claim 17, wherein said array further comprises a plurality of magnetic disk drives.
Claim 32
Dependent Claim
16 words
The LSA of claim 17, wherein said array further comprises a plurality of optical disk drives.
Claim 33
Dependent Claim
18 words
The LSA of claim 17, wherein said array further comprises a plurality of optical and magnetic disk drives.
References Cited (Backward Citations)
US4761785B1
Cited
US4761785A
Cited
USRE34003E
Cited
US4914656A
Cited
US4989206A
Cited
US4989205A
Cited
US5163023A
Cited
US5166939A
Cited
US5233618A
Cited
US5124987A
Cited
US5265098A
Cited
US5235601A
Cited
US5258984A
Cited
US5301297A
Cited
US5418921A
Cited
US5349558A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-01-29 | 1999-07-31 | 2000-01-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-01-29 | 2003-07-31 | 2004-01-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-01-29 | 2007-07-31 | 2008-01-30 | $7700.00 | Window Closed / Lapsed |