On-line reconstruction of a failed redundant array system
First Claim
1. A method for on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block, comprising the steps of:
- a. reconstructing each data block of the failed storage unit for each stripe in the array;
b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe;
c. if the array receives a read request for a data block during reconstruction, then;
(1) if the requested data block is located on the replacement storage unit, then;
(a) accessing all other corresponding 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;
(a) accessing the requested data block directly.
1 Assignment
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).
170 Citations
56 Claims
-
1. A method for on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block, comprising the steps of:
-
a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a read request for a data block during reconstruction, then; (1) if the requested data block is located on the replacement storage unit, then; (a) accessing all other corresponding 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; (a) accessing the requested data block directly. - View Dependent Claims (2, 3, 4, 8, 9, 10, 11, 12, 13, 14)
-
-
5. A method for on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block, comprising the steps of:
-
a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a write request 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 other corresponding 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 (6)
-
-
7. A method for on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block, comprising the steps of:
-
a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a write request 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 other corresponding 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 of a failed data storage unit to a replacement storage unit in a redundant array of storage units, the storage units having at least one stripe 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 each data block of the failed storage unit for each stripe in the array and storing each 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 other corresponding 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. - View Dependent Claims (16, 17, 18, 22, 23, 24, 25, 26, 27, 28)
-
-
19. A controller for on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units, the storage units having at least one stripe 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 each data block of the failed storage unit for each stripe in the array and storing each 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 other corresponding 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. - View Dependent Claims (20)
-
-
21. A controller for on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units, the storage units having at least one stripe 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 each data block of the failed storage unit for each stripe in the array and storing each 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 other corresponding 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.
-
-
29. A control program tangibly stored on a storage device readable by a programmable control device when coupled to the storage device, such that the control device is configured and operated by the control program when the storage device is read by the control device, the configured control device being operated to perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block the control program being configured to operate the control device to perform the function of:
-
a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a read request for a data block during reconstruction, then; (1) if the requested data block is located on the replacement storage unit, then; (a) accessing all other corresponding 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; (a) accessing the requested data block directly. - View Dependent Claims (30, 31, 32, 36, 37, 38, 39, 40, 41, 42)
-
-
33. A control program tangibly stored on a storage device readable by a programmable control device when coupled to the storage device, such that the control device is configured and operated by the control program when the storage device is read by the control device, the configured control device being operated to perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block the control program being configured to operate the control device to perform the function of:
-
a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a write request 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 other corresponding 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 (34)
-
-
35. A control program tangibly stored on a storage device readable by a programmable control device when coupled to the storage device, such that the control device is configured and operated by the control program when the storage device is read by the control device, the configured control device being operated to perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block the control program being configured to operate the control device to perform the function of:
-
a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a write request 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 other corresponding 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.
-
-
43. A storage device readable by a programmable control device when coupled to the storage device, the storage device containing a control program tangibly stored thereon, such that the control device is operated by the control program when the storage device is read by the control device, the control device being operated to perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block, the control program being configured to operate the control device to perform the function of:
-
a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a read request for a data block during reconstruction, then; (1) if the requested data block is located on the replacement storage unit, then; (a) accessing all other corresponding 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; (a) accessing the requested data block directly. - View Dependent Claims (44, 45, 46, 50, 51, 52, 53, 54, 55, 56)
-
-
47. A storage device readable by a programmable control device when coupled to the storage device, the storage device containing a control program tangibly stored thereon, such that the control device is operated by the control program when the storage device is read by the control device, the control device being operated to perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block, the control program being configured to operate the control device to perform the function of:
-
a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a write request 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 other corresponding 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 (48)
-
-
49. A storage device readable by a programmable control device when coupled to the storage device, the storage device containing a control program tangibly stored thereon, such that the control device is operated by the control program when the storage device is read by the control device, the control device being operated to perform on-line reconstruction of a failed data storage unit to a replacement storage unit in a redundant array of storage units coupled to the control device, the storage units having at least one stripe containing a plurality of data blocks and at least one associated error-correction block, the control program being configured to operate the control device to perform the function of:
-
a. reconstructing each data block of the failed storage unit for each stripe in the array; b. storing each reconstructed data block on the replacement storage unit in the corresponding stripe; c. if the array receives a write request 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 other corresponding 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.
-
Specification