On-line reconstruction of a failed redundant array system
First Claim
1. 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.
2 Assignments
0 Petitions
Accused Products
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).
-
Citations
17 Claims
-
1. 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. - View Dependent Claims (5, 6, 7, 8, 11, 13, 14)
-
-
2. 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. - View Dependent Claims (3, 9, 10, 12)
-
-
4. 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.
-
-
15. 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.
-
-
16. 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.
-
-
17. 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.
-
Specification