System and method for reconstructing data in a storage array system

Claim 2

In an array of storage devices attached to at least one host computer system, having a plurality of parity stripes, each parity stripe comprising a set of date blocks and corresponding one or more parity blocks arranged on separate storage devices such that each data block can be reconstructed using the remaining data blocks of the set of data blocks and the parity block for the stripe, and wherein when an old data block is updated with an updated data block, a corresponding old parity block is updated with an updated parity block, a method for reconstructing an unavailable data block comprising the steps of: (a) a first initiator issuing a first initiator command to each storage device to read the remaining blocks of the parity stripe; (b) coordinating on each storage device using a command queue prioritization scheme each of said first initiator commands with any update command received from a second initiator, so that the set of data blocks and the parity block are consistent; and (c) the first initiator logically combining the remaining blocks of the parity stripe read from the storage devices to produce a reconstructed data block.

Claim 3

The method of claim 1, wherein each storage device comprises a processor, memory, parity generator and storage medium, further comprising the step of: the host computer system issuing a reconstruction command for reconstructing the unavailable data block to a storage device which acts as the first initiator.

Claim 4

The method of claim 2, further comprising the steps of: the first initiator storage device performing an XOR operation on the remaining blocks in the parity stripe to reconstruct the unavailable data block.

Claim 5

The method of claim 2, further comprising the step of the first initiator storage device writing the reconstructed data block to the storage media of the first initiator storage device.

Claim 6

The method of claim 2, further comprising the steps of: the first initiator issuing a command to itself to read one of the remaining blocks of the parity stripe; and the first initiator storage device sending the reconstructed data block to the host computer system.

Claim 7

The method of claim 1, wherein the first and second initiators are first and second storage controllers, each storage controller acting as an independent initiator for reconstruction and updating of data blocks.

Claim 8

The method of claim 1, further comprising the steps of: delaying the reconstruction until there are no updates in progress for any of the remaining data blocks in the set of data blocks; and ensuring that the parity block is not updated by subsequently received update commands until after the parity block is read for the reconstruction.

Claim 9

The method of claim 1, further comprising the steps of: a) the first initiator issuing a command to read the parity block; b) queuing the command to read the parity block ahead of any later received commands to update the parity block; c) preventing the execution of subsequently received commands to update the parity block until after the remaining data blocks in the set of data blocks are read for the reconstruction; d) the first initiator issuing commands to read each remaining data block in the set of data blocks after the command to read the parity block is queued; e) queuing the commands to read the remaining data blocks in the set of data blocks ahead of any currently queued or subsequently received commands to update the data blocks; and f) waiting until there are no update commands for any of the remaining data blocks being executed before executing steps (a) through (e).

Claim 10

The method of claim 1, further comprising the steps of: quiescing all update activity for the remaining data blocks in the set of data blocks; and ensuring that the remaining data blocks are not updated by subsequently received update commands until after the remaining blocks in the parity stripe are read for the reconstruction.

Claim 11

The method of claim 1, further comprising the steps of: a) the first initiator issuing a command to read the parity block for the reconstruction after all update commands for the remaining data blocks have completed; and b) ensuring that subsequently received update commands for the remaining data blocks are not executed until after all of the remaining data blocks have been read for the reconstruction.

Claim 12

The method of claim 10, further comprising the step of: queuing the commands to read the remaining data blocks for the reconstruction ahead of any subsequently received command to update the remaining data blocks and behind any previously received commands to update the remaining data blocks.

Claim 13

The method of claim 1, further comprising the steps of: quiescing all update activity for the parity stripe data blocks; ensuring that the parity block is not updated by subsequently received update commands until after the remaining blocks of the parity stripe are read for the reconstruction.

Claim 14

The method of claim 1, further comprising the steps of: a) the first initiator issuing a command to read the parity block for the reconstruction after all update commands for the remaining data blocks have completed; and b) ensuring that subsequently received update commands for the parity block are not executed until after all of the remaining blocks of the parity stripe have been read.

Claim 15

The method of claim 13, further comprising the step of: queuing the commands to read the remaining data blocks ahead of any subsequently received command to update the remaining data blocks and behind any previously received commands to update the remaining data blocks.

Claim 16

A storage apparatus for a computer system comprising: a plurality of storage devices, each storage device comprising a processor, memory, a logical combination generator, and a storage media, parity stripes comprising a set of data blocks and at least one corresponding parity block being arranged on the storage media of the storage devices such that an unavailable block can be reconstructed using the remaining blocks of the parity stripe, and wherein when an old data block is updated with an updated data block, a corresponding old parity block is updated with an updated parity block; an interface connection between each of the storage devices for sending and receiving commands for reading data blocks and reading parity blocks and writing updated data blocks and writing updated parity blocks; at least two independent initiators reconstructing and updating data blocks including a reconstruction initiator for coordinating the reconstruction of the unavailable data block using the remaining blocks of the parity stripe read from respective storage devices, independent of the host system; and a command queue prioritizer for each storage device prioritizing commands from a first initiator for reconstructing the unavailable data block with commands from a second initiator for updating data blocks and parity blocks of the parity stripe, such that the data block is reconstructed without combining an updated block with an old block.

Claim 17

A storage apparatus for a computer system comprising: a plurality of storage devices, each storage device comprising a processor, memory, a logical combination generator, and a storage media, parity stripes comprising a set of data blocks and at least one corresponding parity block being arranged on the storage media of the storage devices such that an unavailable block can be reconstructed using the remaining blocks of the parity stripe, and wherein when an old data block is updated with an updated data block, a corresponding old parity block is updated with an updated parity block; an interface connection between each of the storage devices for sending and receiving commands for reading data blocks and reading parity blocks and writing updated data blocks and writing updated parity blocks; at least two independent initiators reconstructing and updating data blocks including a reconstruction initiator for coordinating the reconstruction of the unavailable data block using the remaining blocks of the parity stripe read from respective storage devices, independent of the host system; and a command queue prioritizer for each storage device prioritizing commands from a first initiator for reconstructing the unavailable data block with commands from a second initiator for updating data blocks and parity blocks of the parity stripe, such that the data block is reconstructed without combining an updated block with an old block.

Claim 18

The storage system of claim 15, wherein the initiator writes the reconstructed data block to the storage media where the unavailable data block was stored.

Claim 19

The storage system of claim 15, wherein the initiator sends the reconstructed data block to the host computer system.

Claim 20

An article of manufacture for use in an array of storage devices for reconstructing an unavailable data block, the array being attached to a host computer system, each storage device comprising, a processor, memory, and a storage media, having sets of data blocks and corresponding parity blocks arranged on the storage media such that a data block can be reconstructed using remaining set data blocks and corresponding parity block, wherein when an old data block is updated with an updated data block, a corresponding old parity block is updated with an updated parity block, said article of manufacture comprising a computer-readable storage medium having a computer program code embodied in said medium which causes the array of storage devices to: issue a reconstruction read command to each storage device having the remaining set data blocks or the corresponding parity block, to read the set data block or the corresponding parity block; queue each command on a respective queue for each storage device, in a priority order, coordinating each reconstruction read command with any write command so that only an updated data block is read with an updated parity block while an old data block is read with an old parity block to reconstruct the unavailable data block; and logically combine the remaining data blocks and the set parity block read from the storage devices to produce a reconstructed data block.

Claim 21

An article of manufacture for use in an array of storage devices for reconstructing an unavailable data block, the array being attached to a host computer system, each storage device comprising, a processor, memory, and a storage media, having sets of data blocks and corresponding parity blocks arranged on the storage media such that a data block can be reconstructed using remaining set data blocks and corresponding parity block, wherein when an old data block is updated with an updated data block, a corresponding old parity block is updated with an updated parity block, said article of manufacture comprising a computer-readable storage medium having a computer program code embodied in said medium which causes the array of storage devices to: issue a reconstruction read command to each storage device having the remaining set data blocks or the corresponding parity block, to read the set data block or the corresponding parity block; queue each command on a respective queue for each storage device, in a priority order, coordinating each reconstruction read command with any write command so that only an updated data block is read with an updated parity block while an old data block is read with an old parity block to reconstruct the unavailable data block; and logically combine the remaining data blocks and the set parity block read from the storage devices to produce a reconstructed data block.

Claim 22

The article of manufacture of claim 18, wherein the computer program code further causes the array of storage devices to write the reconstructed data block to the storage media having the data block to be reconstructed.

Claim 23

The article of manufacture of claim 18, wherein the computer program code further causes the array of storage devices to send the reconstructed data block to the host computer system.