System and method for reconstructing data in a storage array system

• US 6,092,215 A
• Filed: 09/29/1997
• Issued: 07/18/2000
• Est. Priority Date: 09/29/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hodges, Paul, Shomler, Robert Wesley
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): ELISCA, PIERRE E
• Application Number:
  US08/940,105
• Time in Patent Office: 1,023 Days
• Field of Search: 711/114, 711/115, 711/117, 714/725, 714/770, 714/800, 714/801, 714/802, 714/803, 714/804, 714/52, 714/6, 714/7, 370/216
• US Class Current: 714/6.12
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1054 Parity-fast hardware, i.e. dedicated fast hardware for RAID systems with parity

Abstract

A system and method are provided for coordinating command for updating and reconstructing data in an array of storage devices connected to a computer system when multiple initiators issue commands. Sets of data blocks and corresponding parity blocks are arranged on a plurality of storage devices, such that a data block can be reconstructed using a set of data blocks and at least one parity block. When a new data block is written to the disk drive, a corresponding old parity block is write updated with an updated parity block. When reconstructing an unavailable data block an initiator issues a read command to each storage device having a data block or a parity block used for reconstructing the unavailable data block. Each read command is enqueued on a command queue for each storage device in a priority order coordinating each read command with any write update command for the same block so that a new data block and an old parity block are not read as part of the same parity stripe and vice versa.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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).

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

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

18. 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.

19. 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.

20. 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.