Arrays of hard disk drives (HDDs)connected to host computer systems are commonly used for computer data storage. Disk drive arrays provide large storage capacities and high reliability at a low cost.
U.S. Pat. No. 4,870,643 teaches an array of disk drives where a set or stripe of data blocks and a parity block for the set are stored on separate disk drives, with no one disk drive having all the parity for all of the sets. In the event a disk drive fails, each block of data on the unavailable disks can be reconstructed using the remaining blocks in the set. Whenever a data block is updated with new data the associated parity is also updated. This is often referred to as a RAID level 5 system.
In Patterson et al., "A case for Redundant Arrays of Inexpensive Disks (RAID)", A. C. Sigmod Conference, Chicago, Ill., Jun. 1-3, 1988, pp. 109-116, five levels of RAID were defined. In each of the RAID levels, an array of disk drives includes redundant data which can be used to reconstruct data in the event one of the drives fails. RAID level 1 refers to data mirroring where a duplicate copy of the data on one disk drive is stored on a separate disk drive. RAID level 2 uses Hamming codes to provide error detection and correction for a data set. In a RAID level 3 system, a block of data is divided into N portions for storage on N disk drives. The portions of the data block are exclusive ORed (XOR) to produce parity which is written to a separate N+1 disk drive. In a RAID level 4 system, blocks of data are stored on separate disk drives with the parity (XOR) information for a set of blocks of data being stored on a separate dedicated disk drive. The set of blocks are referred to as a stripe of data blocks. Typically, the data blocks and the parity block of a set or stripe are written to the same logical block address on respective disk drives. A RAID level 5 system is similar to RAID level 4 system except that the parity is distributed among all of the disk drives. In RAID level 5 arrays, disk drives operate independently of each other, so that multiple read and write operations can access separate blocks of data at the same time.
The RAID advisory board in its RAID book, "A Source Book for Disk Array Technology", 5th Edition, recognizes these five levels of RAID and defines a sixth level of RAID. In RAID-6, a second independent parity block is provided for each set, so that there are N+2 member disks. This allows data on two failed disk drives to be reconstructed.
In all RAID systems, when data is written (updated), the corresponding redundant data needs to be updated as well. In RAID levels 4 through 6 systems, where the data blocks are independently accessed on separate disk drives, during a write operation, parity can be updated by XORing the old data, the new data and the old parity. Alternatively, a set of data blocks can be written together with its parity to the set of disk drives.
In most prior art RAID storage systems, a RAID controller manages the storage and retrieval of the data on the array of disk drives and the parity generation. Array management software running on one host system or in a storage sub-system manages the storage and retrieval of data to and from the storage devices. Application programs running on the host system provide a logical disk address for writing and retrieving data. The array management software translates the address and reads the contents of the requested block into the host memory. When modifying data, the array management software on the host or a storage controller reads the contents of the block to be modified and the corresponding parity block, and then calculates an exclusive OR (XOR) on the old data, old parity, and the new data. The array management software then writes the new parity back to its parity location and writes the new data to its prior location. A RAID controller can be implemented purely in software or a combination of microcode and hardware. The controller and parity generator can reside in the host computer system or in a separate storage subsystem.
More recently, array management systems have been designed where array management functions and parity generation are performed within the storage devices rather than using a separate controller. More specifically, disk drives have been designed with the XOR engine incorporated into the drive. The disk drives rely on peer-to-peer communication over an interface, such as the Small Computer Standard Interface (SCSI), to manage the implementation of the parity updates and reconstruction.
Performing XOR operations in the disk drive can result in reduced data transfers across the interconnections between the disk drives and the host system.
In a host based or sub-system based array management system, when a RAID level 5 write operation is performed, there are four data transfers that are involved and the array controller executes two XOR operations. These four transfers are: (1) transferring the old data to the controller (2) transferring the old parity to the controller (3) transferring the new data from the controller, and (4) transferring the new parity from the controller.
In a RAID system where the drives perform the XOR operations, data can pass directly from drive to drive for the XOR operations. This greatly reduces the amount of work that a separate host computer or controller has to perform and reduces the amount of data transfers over the interfaces between the drives and the controller. For a write operation (which includes updating parity) the number of data transfers is reduced from four to two. The two data transfers are (1) transfering the new data to the disk; and (2) transfering the XOR difference to the disk where the corresponding (old) parity is stored. In such an array, a new data block is transferred from the host to the disk drive where the old data block is stored. The disk drive accepts the new data, reads the corresponding old data from its disk, and performs an XOR operation to determine the XOR difference between the old data and the new data. The disk drive then acts as an initiator to transfer the old data/new data XOR difference to the disk drive that has the corresponding parity for the data block being updated. The disk drive that has the parity, accepts the XOR difference and performs an XOR operation between the XOR difference and the old parity (read from its disk) to produce the new parity. The new parity is then written back to its disk. By performing the XOR operation in the disk drives, there is also no longer a need for the array controller to perform XOR operations.
The ANSI Standards Committee established commands for implementing RAID functions on a set of disk drives having XOR function capabilities. See: "XOR commands on SCSI Disk Drives" X3T/1/96-IIIR2. Such a system is referred to as an XOR-on-the drive system. The current proposed ANSI standard for "XOR commands" on SCSI disk drives includes read (READ), data update (XDWRITE), parity update (XPWRITE), and reconstruction (REGENERATE and REBUILD) commands. The XDWRITE, REGENERATE and REBUILD commands are executed by drives acting as temporary initiators using peer-to-peer communication. There have also been enhancements to the current proposed SCSI standard. Commonly owned patent application, Hodges, "A System and Method for Distributing Parity in an Array Operation" Ser. No. 08/396,046, teaches a system where the drives store information on the RAID configuration which otherwise would be provided by the host. These enhancements use commands similar to the proposed standard.
The READ command is the most common proposed ANSI command. A host requesting a specific data block issues a READ command to the appropriate disk drive to read that block of data.
Update operations involve writing data on one drive of the array and updating corresponding parity information on a second drive. There are two commands in the proposed ANSI standard that are used to accomplish an update, XDWRITE and XPWRITE. The host issues an XDWRITE command and sends new data to the disk drive where the old data is stored. This disk drive then acts as an initiator. The initiator calculates a parity difference between the old and new data by XORing the new data with the old data read from its disk. The initiator issues an XPWRITE command sending the calculated parity difference between the new and old data to the drive containing the corresponding parity for the data. The parity drive XOR's the parity difference with the old parity, read from its disk, in order to produce the new parity, which is then written back to its disk.
Reconstruction operations involve reading data from multiple drives of the redundant array and performing an exclusive OR operation to recover data. There are two commands in the proposed ANSI standard relating to the reconstruction of data, REGENERATE and REBUILD.
The REGENERATE command is used in place of a READ command when a data drive in the array has malfunctioned. A host computer sends a known good drive the REGENERATE command with the addresses of the source drives (i.e. the drives storing the data and parity blocks of the unavailable block's stripes), the corresponding logical block addresses of the data and parity blocks, and the number of blocks to be reconstructed. The known good drive takes on the role of the initiator and sends READ commands to all of the other drives which have the corresponding data blocks and parity blocks in the same set or stripe as the data block to be regenerated, and also reads the data from its own disk. The blocks from all the drives are then sent back to the initiator drive where the blocks are exclusive ORed, and the result is then sent to the host.
The host sends a REBUILD command to a replacement drive to be rebuilt, which acts as an initiator. The drive has the addresses for the other source drives as well as the logical block addresses and the number of blocks to be rebuilt. The initiator issues READ commands to all of the source drives having data blocks or parity blocks in the parity stripe of the block to reconstructed. When the drive receives all of these blocks, it exclusive OR's the blocks and writes the result of the exclusive OR operation to its disk.
Reconstruction requires that data from all devices be read at the same logical point in time so that the data blocks of a stripe and the corresponding parity block are consistent. If reconstruction and update operations are performed on the same data blocks without specific coordination there is a possibility of incorrect reconstruction. To ensure consistency no writes may be permitted to data blocks of the stripe on any drive until all of the stripe data and parity blocks have been read from all devices for the data to be reconstructed. This is readily accomplished by a single RAID controller. A single controller can serialize accesses to its attached DASD as needed. It is more difficult in a distributed RAID controller environment such as presented by XOR-in-drive configurations. The present ANSI definitions leave the serialization and coordination of the operations to the host system. The problem of incorrect reconstruction arises when the reconstructed and updated operations are performed by two independent initiators, each initiator being unaware of what the other initiator is doing.
FIG. 1 shows an example where a disk drive controlled array tries to implement conflicting command executions for blocks in the same parity stripe. An application program running on a host 10 update writes a data block B3, stored on drive D4, while the same or a different host reads a data block B4, from the same parity stripe as block B3, that is stored on drive D5. Since the drive D5 has failed, the data block B3 will need to be reconstructed.
In order to reconstruct data block B4 stored on the failed drive, the host issues the command REGENERATE to drive D1. Drive D1 acts as an initiator for the regeneration function using the corresponding data and parity blocks from B4's parity stripe stored on drives D1, D2, D3 and D4.
Shortly after drive D1 receives the REGENERATE command, drive D4 receives an XDWRITE command to update block B3. The update write of block B3 requires the updating of the corresponding parity block for the stripe which is stored on drive D2.
As shown in FIG. 1, without the proper coordination of the execution of the commands, the regeneration operation incorrectly uses the old parity block with the new data block for a parity stripe.
Drive D1 issues commands to drives D2, D3 and D4 to read blocks P, B2, and B3 12 and reads the corresponding data block B1 from its own disk 14. When all of the data and parity blocks are received, drive D1 XORs the data and parity blocks 16.
When drive D3 receives the READ command issued from drive D1 (as part of the regeneration), there are no other commands waiting to execute, so drive D3 executes the READ command from D1 and sends the read data to drive D1 18.
Meanwhile, drive D4 executes the XDWRITE command for block B3 and acting as a second separate initiator issues an XPWRITE command to drive D2 (where the corresponding parity P is stored) 20. Drive D4 enqueues the READ command issued from drive D1 (for the regeneration) 22. After drive D4 completes the execution of the XDWRITE command by reading the old data, sending the parity difference to drive D2, and writing the updated data block to its disk 24, drive D4 then executes the READ command P from its queue (issued from drive D1) 25. At that point, drive D4 is reading the updated data block.
When drive D2 receives the READ command from drive Dl (as part of the REGENERATE function) 26 and executes it, drive D2 is reading the old parity still stored on its disk. After drive D2 has read the old parity, drive D2 executes the XPWRITE command and updates the parity 28.
Drives D2 and D4 are executing the commands in the order in which the commands are received. In so doing, the old parity and the updated data are read for the regeneration of a data block producing the incorrect data.
FIGS. 2 through 4 show further examples where competing commands from the same or different hosts for blocks in the same parity stripe can result in inconsistencies.
FIG. 2 shows REGENERATE and XDWRITE commands as described in the previous example. A host issues a REGENERATE command to a surrogate drive D1 to "read" a data block from a failed drive D5. Drive D1 issues READ commands to drives D2, D3, D4 and D5 to read the other blocks of the parity stripe for the requested block 30. At the same time, the same or different host is updating a data block from the same parity stripe stored on drive D2 32. Drive D2 updates the data block and issues an XPWRITE command to drive D4 34. Due to the uncertainty of when the commands will be executed, the READ operation for the reconstruction may return old data or updated data from drive D2 and old parity or updated parity from drive D4.
Referring to FIG. 3, a REBUILD command is issued to drive D1 which is a repaired drive. Drive D1 issues READ commands to drives D2, D3, D4 and D5 to regenerate a data block B1 36. At the same time, drive D2 receives an XDWRITE command to update a data block B2 needed for the rebuild command. The corresponding parity for blocks B1 and B2 is stored on drive D4. Drive D2 issues an XPWRITE command to drive D4 to update the parity 38. Inconsistencies can arise for the REBUILD command at drives D2 and D4 since the READ operation for the REBUILD at drive D2 may return old data or updated data while the READ operation for the REBUILD being executed at drive D4 may return old parity or updated parity.
Inconsistencies can also arise for an update write to a failed drive. Referring to FIG. 4, a data block B4 on a failed drive D5 is updated. Data block B4 is being written to a surrogate drive D1. In order to determine the updated corresponding parity, surrogate drive D1 acting as a first initiator issues READ commands to drives D2 and D3 for the other data blocks of the parity stripe 40. Drive D1 then writes the updated parity to drive D4 42. At the same time, drive D2 receives an XDWRITE for a data block in the same parity stripe and acts as a second independent initiator for this operation. The read operation issued from drive D1 to drive D2, may return old data or updated data. The parity write operation on drive D4 may be based on one or both data updates and may occur before or after the XPWRITE issued from drive D2.
The current proposed ANSI standard is predicated on the assumption that the host will ensure that no data is involved in an update and a reconstruction operation at the same time by coordinating the issuance of commands and reserving drives. This host action adds complexity to an already complex host program especially if two or more hosts are involved. A host independent solution is needed for a drive controlled array that uses XOR commands.
Accordingly, there is a need to provide a host independent procedure for reconstructing data using array commands on the drives, where each drive can act as temporary initiator for each separate command. It is necessary that such a system avoid the problem of having new data combined with old parity or old data with new parity for a reconstruction operation. Generally, there is a need to coordinate reconstruction and update commands in a RAID system having two or more initiators implementing the RAID functions, such as a system having multiple independent RAID controllers.