Abstract:
A method and apparatus for reducing the number of I/O operations in a persistent storage system. A block of data to be written to a location on a persistent storage device is exclusive OR&#39;d (XOR&#39;d) with the block of data currently stored at the location on the device. The result of the XOR operation is examined for differences between the block of data currently stored in the location and the block of data to be written to the location. If the result of the XOR operation indicates that there is no difference between the block of data currently in the location and the block of data to be written to the location, additional I/O operations are avoided.

Description:
This application is a continuation of application Ser. No. 08/363,719, filed Dec. 23, 1994, now abandoned. 
    
    
     FIELD OF THE INVENTION 
     The invention relates to the field of data storage devices and more specifically to techniques for reducing the number of I/O operations to a data storage device. 
     BACKGROUND OF THE INVENTION 
     Referring to FIG. 1, an implementation of a RAID (Redundant Array of Independent Disks) 4 or 5 type subsystem 10 typically includes a plurality of disk drives 18, 20, 22, 24, 26 in communication with a RAID controller 30 by way of one or more buses 31, 31&#39;. Upon the receipt of a write or read command from a host computer 32, to which the RAID controller 30 is in electrical communication by way of a bus 34 or busses (34, 34&#39;), the RAID controller 30 writes blocks of data to or reads blocks of data from, respectively, the controllers 6, 8, 12, 14 and 16 of disk drives 18, 20, 22, 24, 26. Depending upon the RAID implementation level (4, or 5) the blocks of data and the parity of the blocks of data are distributed among the disks 18, 20, 22, 24, 26 as required by the implemented RAID level specification. 
     Regardless of which disk 18, 20, 22, 24, 26 actually stores each block of data and which disk 18, 20, 22, 24, 26 actually stores the parity of the blocks of data, the value of the parity is generated by exclusive ORing (XORing) the corresponding data block on each of the disk drives 18, 20, 22, 24, 26. Thus for example if disk drives 18, 20, 22, and 24 are used to store the blocks of data, and if disk drive 26 is used to store the parity of the blocks of data, the parity stored on disk drive 26 would be generated by the expression: 
     
         P.sub.26 =DATA.sub.18 ⊕DATA.sub.20 ⊕DATA.sub.22 ⊕DATA.sub.24 
    
     where P n  is the parity stored on the nth disk drive, DATA m  is the block of data stored on the mth disk drive and ⊕ is the exclusive OR (XOR) operation. Thus, if one of the disk drives, for example 18, fails so that its data becomes unreadable, each data block that is stored on that disk drive 18 may be recovered from the corresponding data blocks stored on the remaining disk drives 20, 22, 24 and the parity stored on disk drive 26. 
     Although such a RAID implementation helps assure the integrity of the data stored on the subsystem, disk subsystems in RAID 4 and 5 implementations typically require four disk operations, as illustrated in FIG. 2, when a block of data, D new , is written to a disk location. Referring to FIG. 2, when the block of data, D new , is to be written to a location on disk, the block of data previously at the location on the disk, D old , is read (Step 2). The old parity data, P old , for the previously stored blocks of data including D old  is read from the disk containing the parity (Step 4). D new  and D old  are exclusive OR&#39;d to generate a difference pattern which is indicative of the differences between D new  and D old  and the difference pattern is exclusive ORed with the old parity data, P old , to calculate the new parity data, P new  (Step 6). Two write operations are required to write both P new  and D new  to the proper disks (Steps 8 and 10). Thus a total of four disk I/O operations are required to write each new block of data. 
     It should be noted that although the description above corresponds to FIG. 2 as shown, the order in which D old  and P old  are read from the data disk and the parity disk, respectively, may be interchanged. Likewise, the order in which D new  and P new  are written to the data disk and the parity disk, respectively, may also be interchanged. Once the old data, D old , has been read from the data disk, the order in which P old  is read from the parity disk and D new  is written to the data disk may be interchanged. Finally, although the XOR operation has been described in terms of generating a difference pattern from D old  and D new , the calculation of P new  may be accomplished from D old , D new , and P old  without performing this interim step. These changes do not affect either the functionality of the XOR operation or the number of disk I/O operations required to write each new block of data. 
     If the block of data previously stored on disk, D old , is the same as the new data to be written to disk, D new , then it is unnecessary to read the old parity data, P old , from the disk or to write the new data, D new , or the new parity, P new , to the disk. Thus three additional I/O operations have occurred which are not necessary. These extra I/O operations are referred to as &#34;the write penalty&#34;. As a result of the write penalty, channel bandwidth between the disk drives 18, 20, 22, 24, 26 and the RAID controller 30 is wasted transferring data which is not required; memory is wasted within the RAID controller storing data which is not required; and processing cycles of the RAID controller are wasted as a result of managing the extra I/O operations. Additionally, disk latency penalties are likely to be incurred since the disk may have to undergo at least an additional revolution prior to writing the data to the disk due to the increased time required to receive and process the extra data. 
     SUMMARY OF THE INVENTION 
     The invention relates to a method and apparatus for reducing the number of I/O operations by a RAID controller in a persistent storage system. In one embodiment, a RAID controller managing a plurality of persistent storage devices is in electrical communication with a processor executing a user&#39;s process. When a block of data is to be written to a predetermined location on a persistent storage device used for storing data, such as a magnetic disk, the block of data is transferred to a RAID controller from the user&#39;s processor. The RAID controller then issues a read request to the persistent storage device used for storing data (referred to hereinafter, without loss of generality, as a data disk) to retrieve the data stored at the predetermined location of the data disk. The data disk returns the previously stored data and the RAID controller performs an exclusive OR (XOR) operation between the block of data currently stored at that location on the data disk and the block of data to be written to the data disk to thereby generate a change pattern. If the change pattern is all zeros, no further I/O operation need take place since the previous data and the new data are the same. If the change pattern is non-zero, the RAID controller reads the parity data from the persistent storage device used to store parity data (referred to hereinafter, without any loss of generality, as a parity disk) corresponding to the previously written data and calculates the new parity data corresponding to the new data by XORing the change pattern with the old parity data. The new data is then written to the data disk and the new parity is then written to the parity disk. 
     In another embodiment, when a write request is issued to the RAID controller by the host computer, the RAID controller writes the data to the data disk controller. The data disk controller then reads the data previously stored at the predetermined location on the data disk and XORs the new data and the previously stored data to generate a change pattern. The change pattern is then returned to the RAID controller which determines whether there are any differences between the data at the storage location on the data disk and the new data to be written to the storage location. If there are no differences, no further I/O is required. If there are differences, the RAID controller writes the change pattern to the parity disk controller which then reads the parity value for the previously stored data. The parity disk controller then generates a new parity value by XORing the old parity value and the change pattern. The new data is then written to the data disk by the data disk controller and the new parity value is written to the parity disk by the parity disk controller. 
     In still another embodiment, when a write request is issued to the RAID controller by the host computer, the RAID controller first writes the data to the data disk controller. The data disk controller then reads the data previously stored at the predetermined location on the data disk and XORs the new data and the previously stored data to generate a change pattern. The data disk controller then determines whether there are any differences between the data at the storage location on the data disk and the new data to be written to the storage location. As before, if there are no differences, no further I/O is required. If there are differences, the appropriate change patterns, along with a change mask, are then returned to the RAID controller to indicate the result of the operation. The change mask indicates which blocks of data have changed in the original write request. For example, consider a change mask for a four block write operation indicated by the values Cm 1 , Cm 2 , Cm 3  and Cm 4 . If the change mask=1001, the setting of Cm 1  and Cm 4  equal to one in the mask indicates that the change patterns returned to the RAID controller correspond to blocks one and four of the write operation. Thus, the change patterns CP 1  and CP 4  would be the only change information to be sent back to the RAID controller. The parity disk controller reads the parity value for the previously stored data and generates a new parity value by XORing the old parity value and the change pattern. The new data and new parity value are then written to the parity storage media by the data and parity disk controllers, respectively. 
     In still yet another embodiment, when the RAID controller is instructed by the host computer to write a block of data to a data disk, the RAID controller sends the data to the data disk controller. The data disk controller then calculates the change pattern by XORing the new data with the data that is presently stored at the location on the data disk. The data disk controller also calculates a change mask. If the change pattern is not all zero, the data disk controller then writes the new data to the data disk and sends the change patterns along with the change mask directly to the parity disk controller thus completely eliminating the RAID controller from handling the remainder of the I/O operations. 
     The XOR operation may be accomplished in hardware, firmware or software with XOR logic. The examination of the result for changes may be performed by a latch whose output is set to zero at a disk block boundary and which is set to 1 and remains 1 once a difference between the block of data previously stored and the new data to be stored has been detected. 
    
    
     DESCRIPTION OF THE DRAWINGS 
     The above and further advantages of this invention may be better understood by referring to the following description taken in conjunction with the accompanying drawing, in which: 
     FIG. 1 is an embodiment of a RAID disk subsystem in conjunction with a host computer as known to the prior art; 
     FIG. 2 is an embodiment of a method for writing data to disk in a RAID disk subsystem as known to the prior art; 
     FIG. 3 is an embodiment of the presently disclosed method for writing data to disk in a RAID disk subsystem; 
     FIG. 4 is another embodiment of the presently disclosed method for writing data to disk in a RAID disk subsystem; 
     FIG. 5 is yet another embodiment of the presently disclosed method for writing data to disk in a RAID disk subsystem; 
     FIG. 6 is still yet another embodiment of the presently disclosed method for writing data to disk in a RAID disk subsystem; and 
     FIG. 7 is a block diagram of an embodiment of a hardware implementation of the apparatus of the invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Referring to FIG. 3, when a request to write a block of data to a predetermined location on a data disk, is received by a RAID controller, an I/O disk operation is performed by the RAID controller to read the block of data currently stored in the predetermined location on the data disk (Step 12). The new block of data to be written, D new , is then exclusive OR&#39;d (XOR&#39;d) by the RAID controller with the block of data read from the predetermined location on the data disk, D old , to generate a change pattern (C p ) (Step 14). That is: 
     
         C.sub.p =D.sub.new ⊕D.sub.old 
    
     The XOR operation produces a non-zero result in the change pattern (C p ) for each bit location at which the new block of data differs from the previously stored block of data. The change pattern (C p ) generated by the XOR operation is then examined to determine whether the new block of data to be written and the block of data currently written on the data disk are the same (Step 16). If the change pattern is all zeros, the new block of data and the previously written block of data are the same and nothing further need be done (Step 17). 
     If the change pattern (C p ) contains at least one non-zero bit, the pattern indicates a difference between the block of data previously stored in the location and the new block of data to be written to that location, so the RAID controller reads the parity corresponding to the previously stored block of data, (P old ), from the parity disk (Step 18). The parity data for the currently stored data on the parity disk (P old ) is XOR&#39;d with the change pattern (C p ) by the RAID controller to generate the new parity (P new ) (Step 20). That is: 
     
         P.sub.new =P.sub.old ⊕C.sub.p 
    
     In a third I/O operation, the new block of data (D new ) is written to the predetermined location on the data disk (Step 22) and a fourth I/O operation writes the parity of the new block of data (P new ) to the parity disk storing the parity data (Step 24). 
     Therefore, in the case in which the data to be written is the same as the data stored at the predetermined location on the data disk, only one disk I/O operation need be performed; i.e., a read of the data from the location on the disk to which the new data is to be written. This results in a significant decrease in I/O activity (one I/O operation versus four I/O operations in the prior art) when the new block of data to be written, D new , and the block of data currently stored on the data disk, D old , are the same. 
     Another embodiment, as depicted in FIG. 4, is possible when the disk controller electronics co-resident with the disk are capable of performing XOR operations under the control of the RAID controller. When the RAID controller is instructed by the host computer to write a block of data, D new , to a data disk, the RAID controller sends the data to the data disk controller (Step 30). The data disk controller then calculates the change pattern, C p , by XORing the new data received from the RAID controller, D new , with the data that is presently stored at that location on the data disk, D old  (Step 32). That is: 
     
         C.sub.p =D.sub.old ⊕D.sub.new 
    
     The RAID controller then reads the change pattern, C p , from the data disk controller (Step 34). The RAID controller then examines the change pattern to determine if the data has changed (Step 36). If the change pattern C p  is equal to 0, indicating that the data at the location on the data disk, D old , and the data to be written to the location on the data disk, D new , are the same, then no further I/O operations need take place (Step 38). 
     However, if the change pattern C p  contains at least one non-zero entry, the data disk controller writes the new data, D new , to the data disk. The RAID controller then sends C p  to the parity disk thereby instructing the parity disk to calculate a new parity value, P new  (Step 40). The parity disk, in response, calculates the new parity value, P new , by XORing the old parity value, P old , from disk with the change pattern, C p  (Step 42). That is: 
     
         P.sub.new =P.sub.old ⊕C.sub.p 
    
     The parity disk controller then writes the new parity value, P new , to parity disk. 
     Another embodiment, is depicted in FIG. 5, in which the disk controller co-resident with the disk is capable of performing XOR operations and analyzing the result of the XOR operation. When the RAID controller is instructed by the host computer to write a block of data, D new , to a data disk, the RAID controller sends the data to the data disk controller (Step 46). The data disk controller then calculates the change pattern, C p , by XORing the new data received from the RAID controller, D new , with the data that is presently stored at that location on the data disk, D old  (Step 48). That is: 
     
         C.sub.p =D.sub.old ⊕D.sub.new 
    
     If the change pattern, C p , is not all zero, the data disk controller then writes the new data to the data disk. The change pattern, C p , along with the change mask is returned to the RAID controller from the data disk controller (Step 50) and is then transferred to the parity disk controller (Step 52). If the change pattern, C p , is not all zeros, the parity disk controller calculates a new parity value, P new  by XORing the old parity value, P old , from disk with the change pattern, C p  (Step 54), as before, and then writes the new parity value, P new , to the parity disk. 
     In yet another embodiment shown in FIG. 6, the data disk controller co-resident with the disk are capable of performing XOR operations; analyzing the result of the XOR operations for changes; and communicating with the parity disk controller that contains the parity information corresponding to the data located on the data disk. In this embodiment, when the RAID controller is instructed by the host computer to write a block of data, D new , to a data disk, the RAID controller sends the data to the data disk controller (Step 60). The data disk controller then calculates the change pattern, C p , by XORing the new data received by the RAID controller, D new , with the data that is presently stored at the location on the data disk, D old  and calculates the change mask Cm (Step 68). That is: 
     
         C.sub.p =D.sub.old ⊕D.sub.new 
    
     If the change pattern, C p , is zero, no further I/O operations are needed (Step 70). 
     However, if the change pattern, C p , is not all zero, the data disk controller then writes the new data to the data disk and sends the change patterns, C p , along with the change mask, Cm 1  . . . n, directly to the parity disk controller of the parity disk which contains the corresponding parity blocks (Step 74). This method completely eliminates the RAID controller from handling the remainder of the I/O operations. The parity disk controller of the parity disk which contains the parity information then calculates the new parity, P new , by reading the old parity, P old , and XORing it with the change pattern, C p , that was received from the data disk controller (Step 78). The new parity is then written to the parity disk. 
     It should be noted that in any embodiment in which the RAID controller transfers the change pattern, C p , to the disk controller to instruct the disk controller to write a new block of data, it is also possible for the RAID controller to use the change mask, Cm, to create a skip mask to permit a large number of data blocks to be queued. A skip mask is an n-bit word in which each bit which is set in the word corresponds to a block of new data which is to be written to or read from a disk. That is, a bit in the skip mask is set to 1 if the block of data to which the bit corresponds is to be written to disk and is 0 if the block is not to be written to disk. 
     Thus, for example, if the data disk controller returns, to the RAID controller, a series of change patterns (for example C p1  -C p5 ) in which C p1 , C p2 , and C p5  are non-zero and hence correspond to new blocks of data which are to be written to the disk and in which C p3  and C p4  are zero and correspond to new data blocks which need not be written to disk, due to the fact that the data has not changed, the RAID controller would then create a skip mask in which the first, second and fifth bits are one. In this example the skip mask which is created would be 11001. 
     The RAID controller issues a write command to the parity disk controller along with the skip mask and the change parameters C p1 , C p2 , and C p5 . The parity disk controller then uses the skip mask to select the old parity values P old-1 , P old-2 , and P old-5  which are to be read from the parity disk. The parity disk controller then uses the change parameters C p1 , C p2 , and C p5  and the old parity values P old-1 , P old-2 , and P old-5  to calculate the new parity values P new-1 , P new-2 , and P new-5 . 
     A hardware embodiment of the invention, is shown in FIG. 7. In this embodiment, hardware is used to detect the presence of a non-zero result following the XOR operation. The use of hardware may be more desirable in applications where higher speed is required. The faster speed of calculation available in hardware permits a calculation to be made before the disk has an opportunity to complete a revolution. This lessens the chance that another complete revolution will be missed before the required data location appears beneath the read head of the disk again. 
     A block of data to be written, D new , is received into memory 50 from the host 32 by way of the host channel 60. Likewise the previously written block of data, D old , is received into memory 50 from the disk by way of the device channel 64. An n-byte wide bus 68 provides a data path to transfer D new  and D old  from the memory 50 to registers 70, 74, respectively. The registers 70, 74 in turn provide the input signals 78, 80, respectively to XOR logic 84 which performs the XOR operation. 
     The output 90 of the XOR logic 84 is both the input 94 to change detection logic 98 and the input 102 to change pattern register 106. Change pattern register 106 holds the results of the XOR operation which are written back into memory. 
     The change detection logic 98, which in one embodiment is an n-byte latch, is cleared by CLR line 120 at the start of each new block. The output 124 of the change detection logic 98 will therefore remain set even if subsequent zeros are generated by the XOR logic 84 and appear on the input 94 of the change detection logic 98. Such change detection logic 98 can be scaled to any n-bit implementation, including, but not limited to, 8, 16 or 32 bit implementations and implementations in which n is odd. 
     The output 124 from the change detection logic 98 is the input 130 to change mask generator 134. The change mask generator 134 sets a bit for each block in a group of blocks which must be written. The output 140 is the input to a skip mask register 148 which maintains the skip mask until it is written to a location 154 in memory 50. 
     Having shown the preferred embodiment, those skilled in the art will realize variations from the disclosed embodiments are possible. Therefore, it is the intention to limit the invention only as indicated by the appended claims.