Patent US5208813A successfully refreshed from Google Patents.
US5208813A
Expired / Lapsed
US
⏱️ 0.0 years remaining
On-line reconstruction of a failed redundant array system
Assignee: EMC Corp
•
Filing: 1990-10-23
•
Granted: 1993-05-04
•
Expires: 2010-10-23
Abstract
Abstract A method for on-line reconstruction of a failed storage unit in a redundant array system. After providing a replacement storage unit for the failed storage unit, reconstruction begins for each data stripe in the array. General reconstruction consists of applying an error-correction operation (such as an XOR operation on data blocks and a corresponding parity block) to the data blocks from the remaining storage units in the redundancy group, and storing the result in the corresponding block of the replacement storage unit. If a Read operation is requested by the CPU for a data block on the replacement storage unit, then a concurrent Read task is executed which reconstructs the stripe containing the requested data block. If a Read operation is requested by the CPU for a data block not on the replacement storage unit, a concurrent Read task is executed which performs a normal Read. If a Write operation is requested for any data block, then a concurrent Write task is executed which performs a Read-Modify-Write sequence in the general case (the Read operation being performed in accordance with the above rules).
Inventors
- 👤 David C. Stallmo
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 13:31
CPC Classifications
G; G11; G11C; G11C29/00; G11C29/70; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; G06F11/1092; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1833; G06F11/14
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
173 words
A method for on-line reconstruction of a failed data storage unit in a redundant array of storage units coupled to a controller, the storage units having a plurality of stripes each containing a plurality of data blocks and at least one associated error-correction block, comprising the steps of: a. providing a replacement storage unit for the failed storage unit; b. reconstructing the data block of the failed storage unit for each stripe in the array; c. storing the reconstructed data block on the replacement storage unit in the corresponding stripe; d. if the controller requests a read operation for a data block during reconstruction, then: (1) if the requested data block is located on the replacement storage unit, then: (a) accessing all of the other data blocks and at least one corresponding error-correction block in the stripe containing the requested data block; (b) reconstructing the requested data block from the accessed blocks; (2) if the requested data block is not located on the replacement storage unit, then: accessing the requested data block directly.
Claim 2
Independent Claim
173 words
A method for on-line reconstruction of a failed data storage unit in a redundant array of storage units coupled to a controller, the storage units having a plurality of stripes each containing a plurality of data blocks and at least one associated error-correction block, comprising the steps of: a. providing a replacement storage unit for the failed storage unit; b. reconstructing the data block of the failed storage unit for each stripe in the array; c. storing the reconstructed data block on the replacement storage unit in the corresponding stripe; d. if the controller requests a read operation for a data block during reconstruction, then: (1) if the requested data block is located on the replacement storage unit, then: (a) accessing all of the other data blocks and at least one corresponding error-correction block in the stripe containing the requested data block; (b) reconstructing the requested data block from the accessed blocks; (2) if the requested data block is not located on the replacement storage unit, then: accessing the requested data block directly.
Claim 3
Independent Claim
262 words
A method for on-line reconstruction of a failed data storage unit in a redundant array of storage units coupled to a controller, the storage units having a plurality of stripes each containing a plurality of data blocks and at least one associated error-correction block, comprising the steps of: a. providing a replacement storage unit for the failed storage unit; b. reconstructing the data block of the failed storage unit for each stripe in the array; c. storing the reconstructed data block on the replacement storage unit in the corresponding stripe; d. if the controller requests a write operation for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified is located on the replacement storage unit, then: (a) accessing all of the other blocks in the stripe containing the data block to be modified; (b) reconstructing the data block to be modified from the accessed blocks; (c) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (d) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified.
Claim 4
Independent Claim
262 words
A method for on-line reconstruction of a failed data storage unit in a redundant array of storage units coupled to a controller, the storage units having a plurality of stripes each containing a plurality of data blocks and at least one associated error-correction block, comprising the steps of: a. providing a replacement storage unit for the failed storage unit; b. reconstructing the data block of the failed storage unit for each stripe in the array; c. storing the reconstructed data block on the replacement storage unit in the corresponding stripe; d. if the controller requests a write operation for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified is located on the replacement storage unit, then: (a) accessing all of the other blocks in the stripe containing the data block to be modified; (b) reconstructing the data block to be modified from the accessed blocks; (c) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (d) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified.
Claim 5
Dependent Claim
97 words
The method of claim 2, wherein the write operation step includes the further steps of: a. if the at least one error-correction block associated with the data block to be modified is located on the replacement storage unit, then: (1) accessing all of the other data blocks in the stripe containing the data block to be modified; (2) computing at least one error-correction block from the accessed blocks and the new data block; (3) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.
Claim 6
Independent Claim
256 words
A method for on-line reconstruction of a failed data storage unit in a redundant array of storage units coupled to a controller, the storage units having a plurality of stripes each containing a plurality of data blocks and at least one associated error-correction block, comprising the steps of: a. providing a replacement storage unit for the failed storage unit; b. reconstructing the data block of the failed storage unit for each stripe in the array; c. storing the reconstructed data block on the replacement storage unit in the corresponding stripe; d. if the controller requests a write operation for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified or its at least one associated error-correction block are located on the replacement storage unit, then: (a) accessing all of the other data blocks in the stripe containing the data block to be modified; (b) computing at least one error-correction block from the accessed blocks and the new data block; (c) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.
Claim 7
Independent Claim
256 words
A method for on-line reconstruction of a failed data storage unit in a redundant array of storage units coupled to a controller, the storage units having a plurality of stripes each containing a plurality of data blocks and at least one associated error-correction block, comprising the steps of: a. providing a replacement storage unit for the failed storage unit; b. reconstructing the data block of the failed storage unit for each stripe in the array; c. storing the reconstructed data block on the replacement storage unit in the corresponding stripe; d. if the controller requests a write operation for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified or its at least one associated error-correction block are located on the replacement storage unit, then: (a) accessing all of the other data blocks in the stripe containing the data block to be modified; (b) computing at least one error-correction block from the accessed blocks and the new data block; (c) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.
Claim 8
Dependent Claim
182 words
The method of claim 1, further including the steps of: a. if the controller requests a write operation for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified is located on the replacement storage unit, then: (a) accessing all of the other blocks in the stripe containing the data block to be modified; (b) reconstructing the data block to be modified from the accessed blocks; (c) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (d) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified.
Claim 9
Dependent Claim
96 words
The method of claim 5, wherein the write operation step includes the further steps of: a. if the at least one error-correction block associated with the data block to be modified is located on the replacement storage unit, then: (1) accessing all of the data blocks in the stripe containing the data block to be modified; (2) computing at least one error-correction block from the accessed blocks and the new data block; (3) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.
Claim 10
Dependent Claim
176 words
The method of claim 1, further including the steps of: a. if the controller requests a write operation for a new data block during reconstruction, then: (1) if the data block to be modified and its at least one associated error-correction block are not located on the replacement storage unit, then: (a) updating the at least one associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated at least one error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified or its at least one associated error-correction block are located on the replacement storage unit, then: (a) accessing all of the other data blocks in the stripe containing the data block to be modified; (b) computing at least one error-correction block from the accessed blocks and the new data block; (c) writing the computed at least one error-correction block and the new data block in the stripe containing the data block to be modified.
Claim 11
Independent Claim
65 words
The method of claims 1, 2, or 4, wherein at least one error-correction block contains parity information, and the step of reconstructing each data block of the failed storage unit comprises the steps of: a. accessing all of the other data blocks and the corresponding parity error-correction block in the corresponding stripe; b. exclusively-OR'ing all of the accessed blocks to generate a new data block.
Claim 12
Independent Claim
77 words
The method of claims 2, 4, 5, or 7, wherein at least one error-correction block contains parity information, and the step of updating the at least one associated error-correction block during a write operation comprises the steps of: a. reading the data block to be modified and the associated parity error-correction block; b. exclusively-OR'ing the parity error-correction block with the data block to be modified and the new data block to generate an updated parity error-correction block.
Claim 13
Independent Claim
33 words
The method of claims 3, 4, 6, or 7, wherein the step of computing at least one error-correction block during a write operation comprises exclusively-OR'ing the accessed blocks and the new data block.
Claim 14
Dependent Claim
23 words
The method of claim 1, wherein the step of reconstructing the requested data block from the accessed blocks comprises exclusively-OR'ing the accessed blocks.
Claim 15
Independent Claim
27 words
The method of claims 2 or 5, wherein the step of reconstructing the data block to be modified from the accessed blocks comprises exclusively-OR'ing the accessed blocks.
Claim 16
Independent Claim
72 words
The method of claims 1, 5, or 7, wherein when the requested data block is located on the replacement storage unit: a. if the block has previously been reconstructed, then: (1) accessing the requested data block directly; b. otherwise: (1) accessing all of the other data blocks and at least one corresponding error-correction block in the stripe containing the requested data block; (2) reconstructing the requested data block from the accessed blocks.
Claim 17
Independent Claim
38 words
The method of claims 1, 2, or 4, wherein the step of reconstructing the data block of the failed storage unit for each stripe in the array is performed only for stripes that have not previously been reconstructed.
Claim 18
Dependent Claim
169 words
A controller for on-line reconstruction to a replacement storage unit of a failed data storage unit in a redundant array of storage units, the storage units having a plurality of stripes each containing a plurality of data blocks and an associated error-correction block, the controller including means for operatively coupling the controller to the array of storage units and means for: a. reconstructing the data block of the failed storage unit for each stripe in the array and storing the reconstructed data block on the replacement storage unit in the corresponding stripe; b. reading a requested data block during the reconstruction, by: (1) if the requested data block is located on the replacement storage unit, then: (a) accessing all of the other data blocks and the corresponding error-correction block in the stripe containing the requested data block; (b) reconstructing the requested data block from the accessed blocks; (2) if the requested data block is not located on the replacement storage unit, then: (a) accessing the requested data block directly.
Claim 19
Dependent Claim
169 words
A controller for on-line reconstruction to a replacement storage unit of a failed data storage unit in a redundant array of storage units, the storage units having a plurality of stripes each containing a plurality of data blocks and an associated error-correction block, the controller including means for operatively coupling the controller to the array of storage units and means for: a. reconstructing the data block of the failed storage unit for each stripe in the array and storing the reconstructed data block on the replacement storage unit in the corresponding stripe; b. reading a requested data block during the reconstruction, by: (1) if the requested data block is located on the replacement storage unit, then: (a) accessing all of the other data blocks and the corresponding error-correction block in the stripe containing the requested data block; (b) reconstructing the requested data block from the accessed blocks; (2) if the requested data block is not located on the replacement storage unit, then: (a) accessing the requested data block directly.
Claim 20
Dependent Claim
243 words
A controller for on-line reconstruction to a replacement storage unit of a failed data storage unit in a redundant array of storage units, the storage units having a plurality of stripes each containing a plurality of data blocks and an associated error-correction block, the controller including means for operatively coupling the controller to the array of storage units and means for: a. reconstructing the data block of the failed storage unit for each stripe in the array and storing the reconstructed data block on the replacement storage unit in the corresponding stripe; b. writing a new data block during the reconstruction, by: (1) if the data block to be modified and its associated error-correction block are not located on the replacement storage unit, then: (a) updating the associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified is located on the replacement storage unit, then: (a) accessing all of the other blocks in the stripe containing the data block to be modified; (b) reconstructing the data block to be modified from the accessed blocks; (c) updating the associated error-correction block in the stripe containing the data block to be modified; (d) writing the updated error-correction block and the new data block in the stripe containing the data block to be modified.
Claim 21
Dependent Claim
243 words
A controller for on-line reconstruction to a replacement storage unit of a failed data storage unit in a redundant array of storage units, the storage units having a plurality of stripes each containing a plurality of data blocks and an associated error-correction block, the controller including means for operatively coupling the controller to the array of storage units and means for: a. reconstructing the data block of the failed storage unit for each stripe in the array and storing the reconstructed data block on the replacement storage unit in the corresponding stripe; b. writing a new data block during the reconstruction, by: (1) if the data block to be modified and its associated error-correction block are not located on the replacement storage unit, then: (a) updating the associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified is located on the replacement storage unit, then: (a) accessing all of the other blocks in the stripe containing the data block to be modified; (b) reconstructing the data block to be modified from the accessed blocks; (c) updating the associated error-correction block in the stripe containing the data block to be modified; (d) writing the updated error-correction block and the new data block in the stripe containing the data block to be modified.
Claim 22
Dependent Claim
235 words
A controller for on-line reconstruction to a replacement storage unit of a failed data storage unit in a redundant array of storage units, the storage units having a plurality of stripes each containing a plurality of data blocks and an associated error-correction block, the controller including means for operatively coupling the controller to the array of storage units and means for: a. reconstructing the data block of the failed storage unit for each stripe in the array and storing the reconstructed data block on the replacement storage unit in the corresponding stripe; b. writing a new data block during the reconstruction, by: (1) if the data block to be modified and its associated error-correction block are not located on the replacement storage unit, then: (a) updating the associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified or its associated error-correction block are located on the replacement storage unit, then: (a) accessing all of the other data blocks in the stripe containing the data block to be modified; (b) computing a error-correction block from the accessed blocks and the new data block; (c) writing the computed error-correction block and the new data block in the stripe containing the data block to be modified.
Claim 23
Dependent Claim
235 words
A controller for on-line reconstruction to a replacement storage unit of a failed data storage unit in a redundant array of storage units, the storage units having a plurality of stripes each containing a plurality of data blocks and an associated error-correction block, the controller including means for operatively coupling the controller to the array of storage units and means for: a. reconstructing the data block of the failed storage unit for each stripe in the array and storing the reconstructed data block on the replacement storage unit in the corresponding stripe; b. writing a new data block during the reconstruction, by: (1) if the data block to be modified and its associated error-correction block are not located on the replacement storage unit, then: (a) updating the associated error-correction block in the stripe containing the data block to be modified; (b) writing the updated error-correction block and the new data block in the stripe containing the data block to be modified; (2) if the data block to be modified or its associated error-correction block are located on the replacement storage unit, then: (a) accessing all of the other data blocks in the stripe containing the data block to be modified; (b) computing a error-correction block from the accessed blocks and the new data block; (c) writing the computed error-correction block and the new data block in the stripe containing the data block to be modified.
References Cited (Backward Citations)
US3893178A
Cited
US4092732A
Cited
US4467421A
Cited
US4562576A
Cited
US4817035A
Cited
US4849929A
Cited
US4667326A
Cited
US4754397A
Cited
US4768193A
Cited
US4722085A
Cited
US4761785A
Cited
US4761785B1
Cited
US4775978A
Cited
US4870643A
Cited
US4899342A
Cited
US4993030A
Cited
US4914656A
Cited
US4989206A
Cited
US5088081A
Cited
US5134619A
Cited
US5130992A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-05-03 | 1996-11-02 | 1997-05-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-05-03 | 2000-11-02 | 2001-05-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-05-03 | 2004-11-02 | 2005-05-04 | $7700.00 | Window Closed / Lapsed |