Method and apparatus for reduction of I/O operations in persistent storage system

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'd (XOR'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.

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'. 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'), 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: 
EQU P.sub.26 =DATA.sub.18 .sym.DATA.sub.20 .sym.DATA.sub.22 .sym.DATA.sub.24 
where P.sub.n is the parity stored on the nth disk drive, DATA.sub.m is the 
block of data stored on the mth disk drive and .sym. 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.sub.new, is written to a disk location. Referring to FIG. 
2, when the block of data, D.sub.new, is to be written to a location on 
disk, the block of data previously at the location on the disk, D.sub.old, 
is read (Step 2). The old parity data, P.sub.old, for the previously 
stored blocks of data including D.sub.old is read from the disk containing 
the parity (Step 4). D.sub.new and D.sub.old are exclusive OR'd to 
generate a difference pattern which is indicative of the differences 
between D.sub.new and D.sub.old and the difference pattern is exclusive 
ORed with the old parity data, P.sub.old, to calculate the new parity 
data, P.sub.new (Step 6). Two write operations are required to write both 
P.sub.new and D.sub.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.sub.old and P.sub.old are read from the 
data disk and the parity disk, respectively, may be interchanged. 
Likewise, the order in which D.sub.new and P.sub.new are written to the 
data disk and the parity disk, respectively, may also be interchanged. 
Once the old data, D.sub.old, has been read from the data disk, the order 
in which P.sub.old is read from the parity disk and D.sub.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.sub.old and D.sub.new, the calculation of P.sub.new may be accomplished 
from D.sub.old, D.sub.new, and P.sub.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.sub.old, is the same as 
the new data to be written to disk, D.sub.new, then it is unnecessary to 
read the old parity data, P.sub.old, from the disk or to write the new 
data, D.sub.new, or the new parity, P.sub.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 "the write penalty". 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'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'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.sub.1, Cm.sub.2, Cm.sub.3 and 
Cm.sub.4. If the change mask=1001, the setting of Cm.sub.1 and Cm.sub.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.sub.1 and CP.sub.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.

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.sub.new, is then 
exclusive OR'd (XOR'd) by the RAID controller with the block of data read 
from the predetermined location on the data disk, D.sub.old, to generate a 
change pattern (C.sub.p) (Step 14). That is: 
EQU C.sub.p =D.sub.new .sym.D.sub.old 
The XOR operation produces a non-zero result in the change pattern 
(C.sub.p) for each bit location at which the new block of data differs 
from the previously stored block of data. The change pattern (C.sub.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.sub.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.sub.old), from the parity disk (Step 18). The 
parity data for the currently stored data on the parity disk (P.sub.old) 
is XOR'd with the change pattern (C.sub.p) by the RAID controller to 
generate the new parity (P.sub.new) (Step 20). That is: 
EQU P.sub.new =P.sub.old .sym.C.sub.p 
In a third I/O operation, the new block of data (D.sub.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.sub.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.sub.new, and the block of data currently stored on the data disk, 
D.sub.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.sub.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.sub.p, by XORing the new data received from the RAID 
controller, D.sub.new, with the data that is presently stored at that 
location on the data disk, D.sub.old (Step 32). That is: 
EQU C.sub.p =D.sub.old .sym.D.sub.new 
The RAID controller then reads the change pattern, C.sub.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.sub.p is equal to 0, indicating that the data at the location on 
the data disk, D.sub.old, and the data to be written to the location on 
the data disk, D.sub.new, are the same, then no further I/O operations 
need take place (Step 38). 
However, if the change pattern C.sub.p contains at least one non-zero 
entry, the data disk controller writes the new data, D.sub.new, to the 
data disk. The RAID controller then sends C.sub.p to the parity disk 
thereby instructing the parity disk to calculate a new parity value, 
P.sub.new (Step 40). The parity disk, in response, calculates the new 
parity value, P.sub.new, by XORing the old parity value, P.sub.old, from 
disk with the change pattern, C.sub.p (Step 42). That is: 
EQU P.sub.new =P.sub.old .sym.C.sub.p 
The parity disk controller then writes the new parity value, P.sub.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.sub.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.sub.p, by XORing the new data received from the RAID controller, 
D.sub.new, with the data that is presently stored at that location on the 
data disk, D.sub.old (Step 48). That is: 
EQU C.sub.p =D.sub.old .sym.D.sub.new 
If the change pattern, C.sub.p, is not all zero, the data disk controller 
then writes the new data to the data disk. The change pattern, C.sub.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.sub.p, is not all zeros, 
the parity disk controller calculates a new parity value, P.sub.new by 
XORing the old parity value, P.sub.old, from disk with the change pattern, 
C.sub.p (Step 54), as before, and then writes the new parity value, 
P.sub.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.sub.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.sub.p, by XORing the new data received by 
the RAID controller, D.sub.new, with the data that is presently stored at 
the location on the data disk, D.sub.old and calculates the change mask Cm 
(Step 68). That is: 
EQU C.sub.p =D.sub.old .sym.D.sub.new 
If the change pattern, C.sub.p, is zero, no further I/O operations are 
needed (Step 70). 
However, if the change pattern, C.sub.p, is not all zero, the data disk 
controller then writes the new data to the data disk and sends the change 
patterns, C.sub.p, along with the change mask, Cm.sub.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.sub.new, by reading the old 
parity, P.sub.old, and XORing it with the change pattern, C.sub.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.sub.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.sub.p1 -C.sub.p5) 
in which C.sub.p1, C.sub.p2, and C.sub.p5 are non-zero and hence 
correspond to new blocks of data which are to be written to the disk and 
in which C.sub.p3 and C.sub.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.sub.p1, C.sub.p2, and 
C.sub.p5. The parity disk controller then uses the skip mask to select the 
old parity values P.sub.old-1, P.sub.old-2, and P.sub.old-5 which are to 
be read from the parity disk. The parity disk controller then uses the 
change parameters C.sub.p1, C.sub.p2, and C.sub.p5 and the old parity 
values P.sub.old-1, P.sub.old-2, and P.sub.old-5 to calculate the new 
parity values P.sub.new-1, P.sub.new-2, and P.sub.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.sub.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.sub.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.sub.new and D.sub.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.