Abstract:
A shared device environment having multiple nodes ( 4   a   -4   c ), each node containing a computer ( 6   a   -6   c ), an adaptor ( 8   a   -8   c ) and multiple storage devices ( 10   a   -10   c ). Adaptors ( 8   a   -8   c ) facilitate read access to storage devices ( 10   a   -10   c ) such that the data records accessed are the latest version data records. Adaptors ( 8   a   -8   c ) are operative to provide the latest version of data blocks requested by computers ( 6   a   -6   c ) by first searching the read cache of each adaptor for data blocks requested by computers ( 6   a   -6   c ). If the requested data blocks are not found in the read cache of any adaptors, then data structures ( 155, 156  and  158 ) within the adaptors are searched for any data blocks waiting to be added to the read cache of any adaptors. If no data blocks are found, then the read access is conducted directly from the storage device itself.

Description:
This application is a divisional of application Ser. No. 09/129,067, filed Aug. 4, 1998 now U.S. Pat. No. 6,446,237. The application is incorporated herein by reference. 
     CROSS-REFERENCE TO RELATE APPLICATIONS 
     This application is related to the following co-pending and commonly-assigned patent applications, all of which are filed on the same date herewith, and all of which are incorporated herein by reference in their entirety: 
     “Distributed Storage System Using Front-End And Back-End Locking,” by Jai Menon, Divyesh Jadav, Kal Voruganti, U.S. Pat. No. 6,272,662, issued Aug. 7, 2001; “System for Updating Data in a Multi-Adaptor Environment,” by Jai Menon, Divyesh Jadav, Deepak Kenchammana-Hosekote, U.S. Pat. No. 6,332,197, issued Dec. 18, 2001; “System For Changing The Parity Structure Of A Raid Array,” by Jai Menon, Divyesh Jadav, Deepak Kenchammana-Hosekote, U.S. Pat. No. 6,279,138, issued Aug. 21, 2001; “Updating Data and Parity With and Without Read Caches,” by Jai Menon, U.S. Pat. No. 6,446,220, issued Sep. 3, 2002; and “Updating and Reading Data and Parity Blocks in a Shared Disk System with Request Forwarding,” by Jai Menon and Divyesh Jadav, U.S. Pat. No. 6,128,762. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a system for updating data, reading data, and handling storage device and adaptor failures in a shared disk system. 
     2. Description of the Related Art 
     In Redundant Arrays of Independent Disks (RAID) systems, data files and related parity are striped across multiple disk drives. In storage subsystems which manage numerous hard disk drives as a single direct access storage device (DASD), the RAID logic is implemented in the controller of the subsystem. RAID storage methodologies have also been implemented in software for execution on a single host computer. This allows the single host computer, such as a personal computer, to implement RAID storage techniques on local hard disk drive space. Such software RAID methodologies are described in “Algorithms for Software and Low Cost Hardware RAIDS,” by Jai Menon, Jeff Riegel, and Jim Wyllie, document no. 1063-6390 (IEEE 1995), which is incorporated herein by reference in its entirety. 
     One problem with the single storage subsystem is the risk of failure. Techniques have been developed to improve failback and recovery in case of failures in the hardware controller. One such failback technique is the Fast Write Technique which provides two separate controllers on different power boundaries that control the flow of data from host systems to DASDs. If one controller fails, the other controller can continue writing data to the DASD. Typically a non-volatile storage unit (NVS) is included with each separate controller, such that each NVS connected to a controller backs up the data the other controller is writing to DASD. Such failback systems employing the two-controller failsafe structure are described in U.S. Pat. Nos. 5,636,359, 5,437,022, 5,640,530, and 4,916,605, all of which are assigned to International Business Machines, Corporation (IBM), the assignee of the subject application, and all of which are incorporated herein by reference in their entirety. 
     RAID systems can also be implemented in a parallel computing architecture in which there is no central controller. Instead, a plurality of independent controllers that control local hard disk storage devices are separate nodes that function together in parallel to implement RAID storage methodologies across the combined storage space managed by each node. The nodes are connected via a network. Parity calculations can be made at each node, and not centrally. Such parallel RAID architecture is described in “The TickerTAIP Parallel RAID Architecture,” by Pei Cao, Swee Boon Lim, Shivakumar Venkatarman, and John Wilkes, published in ACM Transactions on Computer Systems, Vol. 12, No. 3, pgs. 236-269 (August, 1994), which is incorporated herein by reference in its entirety. 
     One challenge in shared disk systems implementing a parallel, shared disk RAID architecture is to provide a system for insuring that data is properly updated to disks in the system, that a write or update request invalidates stale data so such stale data is not returned, and that a read request returns the most current data. 
     SUMMARY OF THE INVENTION 
     To overcome the limitations in the prior art described above, preferred embodiments of the present invention disclose a system for updating data at a data block. A first processing unit receives update data. The data block to update is located in a first storage device and a second storage device stores parity data for the data block. A parity group comprises a data block and corresponding parity data for the data block. The first processing unit obtains the data at the data block and calculates partial parity data from the data at the data block and the update data. The first processing unit stores the partial parity data in a storage area and writes the update data to the data block in the first storage device. The first processing unit further updates parity data for parity groups for which partial parity data is maintained by obtaining control of access to the parity group to update from a second processing unit if the first processing unit does not control access to the parity group. When the first processing unit controls access to the parity group, the first processing unit calculates new parity data from the partial parity data and the parity data in the second storage device, and writes the new parity data to the second storage device. 
     Further embodiments concern processing a request to read data. A first processing unit receives a request to read a data block in a storage device from a requestor. The first processing unit returns the data from a first cache after determining that the requested data is in the first cache. The first processing unit requests permission from a second processing unit to transfer the data in a second cache to the first cache after determining that the data is in the second cache. The first processing unit transfers the data from the second cache to the first cache and returns the data to the requestor after receiving permission from the second processing unit. After receiving a message from the second processing unit denying permission, the first processing unit reads the data block in the first storage device and returns the read data to the requester. 
     Preferred embodiments of message exchanging insure that the first processing unit does not provide data in a read cache that is stale in view of data updates performed by the second processing unit. Moreover, with the preferred embodiments, access to data blocks is controlled. Controlling access helps insure that parity updates are properly handled, data in memory locations is invalidated so that stale or outdated data is not returned to a later read request, stale data is not destaged to a storage device, and a read request returns the latest version of the data block. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Referring now to the drawings in which like reference numbers represent corresponding parts throughout: 
     FIG. 1 illustrates a preferred hardware and software environment in which preferred embodiments of the present invention are implemented; 
     FIG. 2 illustrates a preferred hardware and software architecture of an adaptor in accordance with preferred embodiments of the present invention; 
     FIGS. 3 a, b  illustrates embodiments of how data and parity blocks are arranged on storage devices; 
     FIG. 4 illustrates a flowchart showing logic to update a data block in accordance with preferred embodiments of the present invention; 
     FIG. 5 illustrates a flowchart showing logic to update parity in accordance with preferred embodiments of the present invention; 
     FIG. 6 illustrates a flowchart showing logic to update a data block in the event of a disk failure; 
     FIG. 7 illustrates a flowchart showing logic to rebuild a failed drive and handle update requests; 
     FIG. 8 illustrates a memory area of the adaptor, including data structures in accordance with preferred embodiments of the present invention; 
     FIG. 9 illustrates a flowchart showing logic to handle a read request in accordance with preferred embodiments of the present invention; 
     FIG. 10 illustrates a flowchart showing logic to update a data block using data structures in accordance with preferred embodiments of the present invention; and 
     FIGS. 11 a, b  illustrate flowcharts showing permission exchange logic to grant permission to an adaptor to add data to its read cache in accordance with preferred embodiments of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     In the following description, reference is made to the accompanying drawings which form a part hereof, and which is shown, by way of illustration, several embodiments of the present invention. It is understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the present invention. 
     Hardware and Software Environment 
     FIG. 1 illustrates a shared device environment comprised of nodes  4   a, b, c . Each node includes a computer  6   a, b, c , i.e., central processing unit, and an adaptor card  8   a, b, c . A plurality of storage devices  10   a, b, c  interface via a network  12  to the adaptor cards  8   a, b, c  and attached computers  6   a, b, c . The computer  6   a, b, c  may be a personal computer, workstation, mainframe, etc. The adaptor cards  8   a, b, c  interface with their respective computers  6   a, b, c  via a PC bus, such as the PCI bus, and include one or more disk interface ports, such as SCSI or Serial Storage Architecture (SSA) ports. The adaptor cards  8   a, b, c  include logic to execute the RAID algorithms. The storage devices  10   a, b, c  may be any suitable non-volatile storage device known in the art, including hard disk drives, magnetic tape, optical disks, non-volatile RAM, holographic units, etc. The nodes  4   a, b, c  and storage devices  10   a, b, c  interface via the network  12 , which is preferably a high speed interconnect, such as SCSI, SSA, SNA, SAN, FDDI, etc. Additionally, the network  12  may be a SCSI or SSA bus. In further embodiments more nodes than shown may be included in the shared device system  2 . Each node may include multiple adaptors, multiple processors and/or local (non-shared) storage devices. 
     FIG. 1 further illustrates an additional network  13  providing an additional communication line among the computers  6   a, b, c . This additional network  13  may be comprised of any suitable network known in the art, e.g., ETHERNET, LAN, etc. 
     In preferred embodiments, the computers  6   a, b, c  run parallel processing software, such as the ORACLE PARALLEL SERVER™, the MICROSOFT® Wolfpack Clustering System or any other clustering software. ORACLE PARALLEL SERVER is a trademark of Oracle Corporation; MICROSOFT is a registered trademark of Microsoft Corporation. This parallel processing software allows the computers  6   a, b, c  to share storage devices  10   a, b, c  such that any node  4   a, b, c  may access any block in any of the storage devices  10   a, b, c . This parallel architecture allows data to be distributed across different storage devices  10   a, b, c  throughout the shared device system  2 . The parallel processing software, implemented in the computers  6   a, b, c , may perform logical locking to insure that only one write request is made to a block in any of the storage devices  10   a, b, c , at any given time and to insure that an application does not attempt to read a block being modified by another application. To perform logical locking under control of the parallel processing software, the computers  6   a, b, c  would exchange messages, data, and information via the additional network  13 . The adaptors  8   a, b, c  perform physical locking. 
     FIG. 2 illustrates a preferred embodiment of the adaptors  8   a, b, c . Each adaptor  8   a, b, c  includes a processor  14   a, b, c , a non-volatile RAM  16   a, b, c  for storing control information, a read cache  18   a, b, c , and a write cache  20   a, b, c . The read  18   a, b, c  and write  20   a, b, c  caches may be comprised of volatile memory, such as RAM, or a non-volatile memory unit, e.g., non-volatile RAM. In certain embodiments, the read cache  18   a, b, c  and write cache  20   a, b, c  may be areas within the same memory device or located within separate memory devices. In further embodiments, there may be no read  18   a, b, c  and/or nvrite  20   a, b, c  caches. In preferred embodiments, the write caches  20   a, b, c  contain dirty blocks, which is data intended for a block in the storage device  10   a, b, c  that is more recent than the block actually maintained in the storage device  10   a, b, c . Once the data is written from the write cache  20   a, b, c  to the storage device  10   a, b, c , the copy of the data in the cache is “clean.” Because the write cache  20   a, b, c  only maintains “dirty” blocks, the clean copy in the cache after the update is considered to be in the read cache  18   a, b, c , not the write cache  10   a, b, c  anymore. The components of the adaptors  8   a, b, c  may be implemented as PC cards such the PC ServeRAID SCSI adaptor from IBM. Alternatively, components and functionality of the adaptors  8   a, b, c  could be implemented in the computers  6   a, b, c.    
     In certain embodiments, the read cache  18   a, b, c  may be implemented in a volatile memory device, e.g., DRAM, RAM, etc., and the write cache  20   a, b, c  may be attached to a battery  22  which makes the write cache  20   a, b, c  a non-volatile memory device. In such case, an update to a block is initially written in both the RAM (read cache) and the battery  22  backed up write cache  20   a, b, c . Once the dirty data is destaged to the storage device  10   a, b, c , the copy from the write cache  20   a, b, c  is marked as invalid for later removal, leaving only the clean copy in the RAM, i.e., read cache. In alternative embodiments, the dirty data may be sent to all other adaptors in the system to invalidate any stale data in their caches. In embodiments with only a single memory device for the read  18   a, b, c  and write  20   a, b, c  caches, the data is considered to be in the write cache  20   a, b, c  prior to destaging and in the read cache  18   a, b, c  after destaging even though the data remains in the same memory device. 
     In preferred embodiments, the adaptors  8   a, b, c  must satisfy all of the following correctness conditions: 
     (1) a request to write a data block from adaptor  8   a  simultaneous with a request to write another data block from adaptor  8   b , where the two data blocks have the same parity block, causes a correct parity update in the sequence which the updates were made; 
     (2) a write request through one adaptor  8   a  for a block in the read  18   b  or write  20   b  cache at another adaptor  8   b  causes the invalidation of data in cache  18   b  or  20   b  so that stale data is not returned to a subsequent read request or later destaged to the storage device  10   b  from old data in caches  18   b ,  20   b ; and 
     (3) a read request through one adaptor  8   a  for a block cached at adaptor  8   b  in read  18   b  or write  20   b  cache, returns the latest version of the data block from adaptor  8   b.    
     Those skilled in the art will recognize that alternative conditions to the three mentioned above may also be satisfied. 
     Parity in a RAID Environment 
     FIG. 3 a  illustrates a  4 +P RAID disk array in which a parity block P i  protects four data blocks D i  in four storage devices. Each vertical column represents a storage device. A parity group is a row in the illustration of FIG. 3 a  that consists of four data blocks D i , one in each storage device, and a parity block P i  maintaining parity information for the four data blocks D i . A parity value P i  is the exclusive OR of the data blocks D i  in the same parity group of a given i. If a disk fails, then the data can be recreated by processing the parity block (P i ) and the remaining data blocks D i  for the parity group. FIG. 3 a  further shows the rotation of parity in that parity blocks P 5  through P 8  are on a different disk, storage device  4 , than the previous parity blocks which are on storage device  5 . 
     In preferred embodiments, a parity block can be updated with the following exclusive OR operation, where the new parity (P i ′)=(old data (D i ) XOR new data (D i ′) XOR old parity (P i ). 
     In certain embodiments, data may be stored in “stripe units” on the storage devices. FIG. 3 b  illustrates a “stripe unit” of data. A stripe unit consists of multiple consecutive blocks of data on a storage device. The “stripe unit” shown in FIG. 3 b  has two consecutive blocks of data, blocks  1  and  2 . A “stripe” consists of multiple stripe units. The “stripe” shown in FIG. 3 b  has five stripe units. In the exemplar of FIG. 3 b , a stripe unit includes blocks from two parity groups throughout each storage device. In alternative embodiments a “stripe unit” and “stripe” could be defined in alternative manners, e.g., including more than two blocks of data, depending on the number of storage devices and parity groups. 
     In alternative embodiments, other parity schemes may be utilized, such as mirrored RAID, bit-interleaved parity, block-interleaved distributed-parity or P+Q redundancy, etc. These various RAID schemes are discussed in “RAID: High-Performance, Reliable Secondary Storage,” by Peter M. Chen, Edward K. Lee, Garth A. Gibson, Randy H. Katz, and David A. Patterson, published in ACM Computing Surveys, Vol. 26, No. 2, pgs. 145-185 (June, 1994), which publication is incorporated herein by reference in its entirety. 
     Updating Data Blocks In the Same Parity Groups 
     FIGS. 4 and 5 illustrate logic implemented in the adaptors  8   a, b, c , to update parity P i  when simultaneously updating different data blocks D i  in the same parity group. The logic of FIGS. 4 and 5 utilizes the NVRAM  16  to store partial parity data that keeps track of changes that must be made to the parity groups as a result of updating data. With respect to FIG. 4, control begins at block  30  which represents an adaptor, e.g., updating adaptor  8   a , receiving a request to update a block of data from D to D′ on a disk, e.g., block B in disk i. Disk i may be one of the storage devices  10   a, b, c  or a storage subunit within one of the storage devices  10   a, b, c . Control transfers to block  32  which represents the updating adaptor  8   a  reading the old data D from block B in disk i via the network  12 . Control then transfers to block  34  which represents the updating adaptor  8   a  calculating partial parity for the data update from the update D′ and old data D. In preferred embodiments, partial parity is calculated as D xor D′. However, in alternative embodiments, alternative means known in the art for calculating parity may be used. 
     After calculating the partial parity, control transfers to block  36  which represents the updating adaptor  10   a  storing the partial parity in the NVRAM  16   a . The updating adaptor  10   a  would further store information indicating the parity group number to which the partial parity applies. Control then transfers to block  38  which represents the updating adaptor  8   a  writing the updated data D′ to block B on disk i. At block  40 , the updating adaptor  8   a  returns DONE to the system. 
     In preferred embodiments, the updating adaptor  8   a  does not immediately update the parity P′ after updating the data. The adaptor  8   a  would perform a parity flushing algorithm to update the parity at a later time, such as when the NVRAM  16   a  includes a predetermined threshold of partial parities. FIG. 5 illustrates logic implemented in the adaptors  8   a, b, c  to update parity P′ based on partial parity data maintained in the NVRAM  16   a . Control begins at block  50  which represents an adaptor, e.g., adaptor  8   a , initiating an operation to flush parity from the NVRAM  16   a . Control transfers to block  52  which represents the adaptor  8   a  determining from the partial parity data in the NVRAM  16   a  the parity group numbers for those parity groups that need to be updated, i.e., inconsistent parity groups. Methods for identifying inconsistent parity groups are known in the art and described in U.S. Pat. No. 5,574,882, entitled “System and Method for Identifying Inconsistent Parity in an Array of Storage,” assigned to IBM, which patent is incorporated herein by reference in its entirety. 
     Control then transfers to block  54  which is a decision block representing the flushing adaptor  8   a  determining whether it has ownership of the locks of all the inconsistent parity groups. Only adaptors  8   a, b, c  having the lock for a parity group or data block, or other stored unit, can access such unit. The lock system arbitrates access to stored units to insure that data consistency is maintained for read and write operations. If the flushing adaptor  8   a  has ownership of locks for all the inconsistent parity groups in its NVRAM  16 , then control transfers to block  56 ; otherwise, control transfers to block  58 . Block  58  represents the adaptor  8   a  sending a message including a list of the inconsistent parity groups for which partial parity data is maintained, for which adaptor  8   a  does not have lock ownership, to the other adaptor, e.g.,  8   b . The adaptor  8   a  may send a message as a single message or as multiple messages. In a two adaptor  8   a, b  system, the flushing adaptor  8   a  would request ownership from the second adaptor  8   b  as there is only one other possible owner of the lock. However, in the N adaptor case, the flushing adaptor  8   a , would have to send a message to all other N- 1  adaptors in the system to obtain lock ownership. 
     Control transfers to block  60  which represents the flushing adaptor  8   a  waiting for a response from the other adaptor(s) granting ownership of the lock for the parity group. After receiving ownership at block  60  or if the adaptor  8   a  already had ownership at block  54 , control transfers to block  56  which represents the flushing adaptor  8   a  going to the inconsistent parity group in the NVRAM, i.e., first partial parity entry. Control then transfers to block  62  which represents the adaptor  8   a  reading old parity P from block B in disk j. Control transfers to block  64  which represents the adaptor  8   a  applying the partial parity (D xor D′) to the old parity P read at block  62  and calculating the new parity P′. Control transfers to block  66  which represents the adaptor  8   a  writing the new parity P′ back to block B on disk j to replace the old parity P. 
     Control then transfers to block  68  which is a decision block representing the flushing adaptor  8   a  determining whether there are any additional inconsistent parity groups not yet updated maintained in the NVRAM  16   a . If so, control transfers to block  70  to proceed to the next inconsistent parity group and partial parity data in the NVRAM  16   a , and update the parity for that inconsistent parity group by proceeding to blocks  62  et seq. Otherwise, if there are no further inconsistent parity groups, control transfers to block  72  which represents the completion of the parity flushing operation. 
     In further embodiments, if an adaptor receives an update of data from D to D′ and subsequently receives another update from D′ to D″, before the adaptor updates the parity, the adaptor can store a combined partial parity of the two updates (D′ xor D″) instead of separately storing two partial parities D xor D′ and D′ xor D″. In this way, the updating adaptor  8   a  can save space in its NVRAM  16   a  by combining partial parities. If, in alternative embodiments, the adaptor  8   a  stores two or more partial parities in NVRAM  16   a , e.g., D xor D′ and D′ xor D″, then the adaptor  8   a  can apply all partial parities to the parity block before writing the new parity to the parity block. For instance, the adaptor can calculate D xor D′ xor D″ xor P. In this way, the adaptor  8   a  can optimize writes to the parity block in the disk j. However, in optimizing writes to the disk, the adaptor does not optimize partial parity storage space in the NVRAM  16  because it does not combine partial parities into a single partial parity entry. 
     Handling Disk Failure 
     If a disk fails, the adaptors must do parity flushing using partial parity data in their NVRAMs  16   a, b, c . To rebuild the data, input/output requests to the shared data would be halted, and an adaptor would rebuild the lost data to a spare disk using a RAID algorithm known in the art. FIG. 6 illustrates preferred logic to update data and parity blocks in the event one of the storage devices  10   a, b, c  has failed. Read and write activity may be stopped until the parity flushing and rebuild are complete. Alternatively, read and write activity may continue during parity flushing and rebuild operations. 
     Control begins at block  80  which represents an adaptor, e.g., updating adaptor  8   a , receiving an update to block B on disk i from D to D′. As before, parity data P is maintained in disk j at block B. Control transfers to block  82  which represents the updating adaptor  8   a  determining if a failure bit set in the system  2  indicates that a disk failed. When a disk fails, which may be a storage device  10   a, b, c  or a component of a storage device  10   a, b c , a failure bit somewhere in the system  2  may be set to indicate such failure. If the adaptor  8   a  determines that the failure bit indicates that a disk failed, then control transfers to block  84 ; otherwise, control transfers to block  83  which represents the adaptor  8   a  executing a an algorithm for the non-failure case, such as the algorithms described with respect to FIGS. 4 and 5. Block  84  is a decision block representing the updating adaptor  8   a  determining whether adaptor  8   a  has ownership of the lock for the parity group including block B. If so, control transfers to block  86 ; otherwise, control transfers to block  88 . If the updating adaptor  8   a  does not have lock ownership, block  86  represents the updating adaptor  8   a  sending a message to the other adaptor(s) requesting lock ownership. Control transfers to block  90  which represents the updating adaptor  8   a  waiting for a response from the other adaptor(s) granting ownership. After receiving the grant of lock ownership, control transfers to block  91  which represents the updating adaptor  8   a  locking the parity groups to prevent other adaptors from performing I/O operations on data blocks within the locked parity groups. If the updating adaptor had ownership at block  84  or after locking the parity groups at block  91 , control transfers to block  88  which is a decision block representing the updating adaptor determining whether disks i and j are operational. If so, control transfers to block  92 ; otherwise control transfers to block  94 . 
     If the disks i and j are operational, then at block  92 , the updating adaptor  8   a  sends a message to the other adaptors(s) to flush their parity from the inconsistent parity groups in their NVRAMs  16   a, b, c . Control transfers to block  96  which represents the updating adaptor  8   a  waiting for confirmation that the other adaptor(s) have flushed parity. After receiving such confirmation, control transfers to block  98  which represents the updating adaptor  8   a  flushing the inconsistent parity groups from the NVRAM  16   a . The adaptor  8   a  may use the flushing logic described with respect to FIG.  5 . Control transfers to block  100  which represents the updating adaptor  8   a  reading the old data D from disk i and old parity P from disk j. The adaptor  8   a  then computes the new parity P′ at block  102  from (P XOR D XOR D′). Control transfers to block  104  to write the new parity P′ to disk j and the new data D′ to disk i. Control then transfers to block  106  to return DONE to the system when the new data is updated to disk i. Control transfers to block  107  to unlock the parity groups after both the new data D′ and new parity P′ are updated at disks i and j. Thus, DONE can be returned to the system before the parity group is unlocked. 
     If one of disks i and j have failed, then at block  94 , the adaptor  8   a  determines whether disk i failed. If so, control transfers to block  108 ; otherwise, control transfers to block  110 . Blocks  108 ,  112 , and  114  represent the updating adaptor  8   a  insuring that the other adaptor(s) flush their inconsistent parity before flushing parity from NVRAM  16   a . Control transfers to block  116  which represents the updating adaptor  8   a  reading old parity P and all data at block B in the other disks in the parity group, except for the data in block B of the failed disk i. The updating adaptor  8   a  then calculates old data D in the failed disk i from all the data read from block B in the other disks in the parity group and the old parity (P) in disk j. Control then transfers to block  118  which represents the updating adaptor  8   a  calculating the new parity P′ from XORing the rebuilt old data D, new data D′, and old parity P. Control then transfers to block  120  which represents the updating adaptor  8   a  starting the process of writing the new data D′ to a spare disk, if a spare disk is available, and the new parity P′ to disk j. Control then transfers to block  106  to return DONE when the writing of the new data D′ is complete and to block  107  to unlock the parity group when the writing of the new parity P′ to disk j is complete. 
     If, at block  94 , the updating adaptor  8   a  determined that disk j failed, i.e., disk i did not fail, then at block  110 , the updating adaptor  8   a  calculates the new parity P′ from the new data D′ and the data at block B in all disks in the parity group, including the old data D in disk i. As discussed, in preferred embodiments, parity is calculated by XORing the values. Control then transfers to block  122  which represents the updating adaptor  8   a  beginning the process of writing the new data D to block B in disk i and new parity P′ to a spare disk. Control then transfers to block  106  et seq. 
     The logic of FIG. 6 to update a data block can be used in handling read requests to the data block B to which the data must be updated before flushing and rebuilding of the failed disk are complete. If disk i is not failed, then the requested data can be read from block B at disk i. If disk i failed, then the receiving adaptor would perform the logic of blocks  108  through  116  to calculate the data D on the failed disk i, and return the requested data D to the requestor. 
     Handling Adaptor Failure 
     If an adaptor fails, e.g., adaptor  8   a , the NVRAM  16   a  of the failed adaptor can be moved to a new adaptor because the NVRAM contains information concerning lock ownership and partial parties. If the NVRAM of the failed adaptor  8   a  cannot be removed or has failed, then parity must be entirely rebuilt. In such case, all the partial parities in NVRAMs would be discarded, and all the adaptors would go into a mode where update requests are handled by updating data to the data disks. In this mode, the adaptors may suspend generating partial parity data. One of the surviving adaptors would execute a rebuild algorithm to rebuild parity from all the data. The surviving adaptor would have to obtain lock ownership before rebuilding the parity data. After the rebuild, adaptors can return to saving partial parity information in NVRAM. The adaptors may return to calculating and saving partial parity data on a parity group by parity group basis. 
     As soon as a drive, i.e., storage device, fails, a degraded mode is entered if there are no spare disks or a rebuild mode is entered if there are spare disks onto which to rebuild the data in the failed disk. FIG. 7 illustrates logic implemented in the adaptors  8   a, b, c  that is executed when a drive fails. After a drive fails, the adaptors begin transmitting information on inconsistent parity groups to the other adaptor(s). In this way, each adaptor has a view of the inconsistent parity groups so that in the event that one of the adaptors fails, the information on such inconsistent parity groups maintained by the failed adaptor will not be lost. The surviving adaptor(s) would know which groups are inconsistent and, thus, be able to rebuild the data without the failed adaptor. 
     Logic begins at block  130  which represents a part or whole of a storage device  10   a, b, c  failing. Control transfers to block  132  which represents an adaptor  8   a, b, c  transmitting information on inconsistent parity groups in the NVRAM  16   a, b, c  to the other adaptors. In this way, the adaptors exchange information on the inconsistent parity groups maintained in their NVRAMs  16   a, b, c . Control transfers to block  134  which represents an adaptor  8   a, b, c  flushing the first inconsistent parity group from NVRAM  16   a, b, c  in the manner described with respect to blocks  62 - 66  in FIG.  5 . Control then transfers to a parallel mode to simultaneously process tasks beginning at blocks  138  and  146  in a multi-tasking manner. 
     Block  138  represents an adaptor  8   a, b, c  sending a message to the other adaptors indicating the parity group just flushed or made consistent. This allows the adaptors to have a current view of inconsistent parity groups across all other adaptor(s). Control transfers to block  140  which represents the adaptor  8   a, b, c  rebuilding the data or parity data in the just flushed parity group to a spare disk. Control then transfers to block  142  which represents the adaptor  8   a, b, c  determining whether there are further inconsistent parity groups in the NVRAM  16   a, b, c . If so, control transfers to block  144  which represents the adaptor  8   a, b, c  flushing the next inconsistent parity group from the NVRAM  16   a, b, c  and proceeding back to blocks  138  et seq. If there are no further inconsistent parity groups, control transfers to block  145  to end the flushing task. 
     Block  146  represents the adaptors waiting to receive an update to a data block. After receiving such update, control transfers to block  148  which represents the updating adaptor sending a message to the other adaptor(s) indicating the update and the blocks to update. The updating adaptor may also transmit the updated data. Control transfers to block  150  which represents the adaptor updating both data and parity. Control then transfers to block  152  which represents the updating adaptor sending a message to the other adaptor(s) indicating the completion of the update. In this way, if an adaptor fails, the surviving adaptor(s) know which parity groups are inconsistent and the parity group where failure occurred. 
     In another embodiment, the adaptors  8   a, b, c  may maintain a list of flushed parity groups that recently became consistent. To maintain such a list, additional messages must be generated to inform other adaptors when a parity group is updated and made consistent. Maintaining such a list reduces the workload in case an adaptor fails because the surviving adaptor(s) have a view of parity groups recently flushed and made consistent. This additional embodiment including the list of consistent groups involves a modification of the logic of FIGS. 4 and 5 for updating and flushing parity. The modification involves adding a step prior to block  32  in FIG. 4 to have the updating adaptor send a message to the other adaptor(s) with the parity group being updated and the list of recently flushed parity groups. The updating adaptor would then wait for a response from the other adaptor(s) acknowledging receipt of the message. When parity flushing, the algorithm of FIG. 5 would be modified to add a parity group to the list of recently flushed parity groups after completion of parity flushing of the inconsistent parity group in the NVRAM between blocks  66  and  68 . 
     Update Requests With Read Caches 
     If the adaptors  8   a, b, c  include read caches  18 , then the algorithms should satisfy two correctness conditions: (1) when an update occurs to different blocks having the same parity block, parity is likewise updated and (2) an update request through one adaptor, e.g., adaptor  8   a , which is cached at another adaptor, e.g., adaptor  8   b , causes the invalidation of the caches in the other adaptor  8   b  so that the adaptor  8   b  does not return or destage stale data. 
     In the embodiments utilizing read caches  18   a, b, c , the adaptors  8   a, b, c  maintain a data structure indicating data cached at other remote adaptors. Preferred embodiments are described with respect to a two adaptor  8   a, b  system. However, the logic could be extended to an N adaptor case. FIG. 8 illustrates a RAM  154   a, b, c  within each adaptor  8   a, b, c  storing three data structures. The first data structure  155  is a list of data blocks waiting to be added to the read cache  18   a, b, c . Until the adaptor  8   a, b, c  adds the data blocks to the read cache  18   a, b, c  they are maintained in the adaptors RAM  154   a, b, c . Data structure  156   a, b, c  is a list of blocks recently updated by the adaptor  8   a, b, c  and data structure  158   a, b, c  is a list of blocks in the other adapter&#39;s read cache  18   a, b, c , i.e., a directory of the other adaptor&#39;s read cache. Each adaptor  8   a, b, c  also maintains a list of inconsistency groups in its NVRAM  16   a, b, c.    
     FIG. 9 illustrates logic implemented in the adaptors  8   a, b  to handle a read request using the data structures  155 ,  156 ,  158 . Control begins at block  160  which represents an adaptor, e.g., receiving adaptor  8   a , receiving a read request for block B from disk i. Control transfers to block  162  which represents the receiving adaptor  8   a  determining whether the block is in its read cache  18   a . If so, control transfers to block  164  to return the data from the read cache  18   a  to the user, and complete the program. Otherwise, if the data is not in the read cache  18   a , control transfers to block  166  which represents the receiving adaptor  8   a  determining whether the requested block B is in the data structure  155   a  indicating blocks to add to the read cache  18   a . If the data is in the data structure  155   a , then a copy of the data is maintained in a wait buffer portion of the RAM  154 . Data is held in this wait buffer area until the other adaptor grants permission to add the data to the read cache  18   a . If so, control transfers to block  168 ; otherwise, control transfers to block  170 . Block  168  represents the adaptor  8   a  determining whether the remote adaptor  8   b  has provided permission to add the block to the read cache  18   a . Permission may be granted according to the permission exchange algorithm described with respect to FIGS. 11 a, b.    
     If permission was granted, control transfers to block  172 , which represents the receiving adaptor  8   a  adding the data in the wait buffer to the read cache  18   a  and returning the data just added to the read cache  18   a  to the user. If permission has not yet been granted, control transfers to block  174  which represents the adaptor  8   a  waiting for a response to the permission request from the remote adaptor  8   b . Once the response is provided, control transfers to block  176 , which represents the receiving adaptor  8   a  determining if permission was granted. If so, control transfers to block  172  to return the data to the user for those blocks where permission was granted. For those blocks where permission was denied or where the requested block was not in the data structure  155   a , control transfers to block  170  which represents the receiving adaptor  8   a  reading the block B from disk i. Control then transfers to block  180  which represents the adaptor  8   a  determining whether the read block is listed in the data structure  155   a  indicating blocks to add to the read cache  18   a . If so, control transfers to block  182 ; otherwise, control transfers to block  184 . 
     Block  182  represents the receiving adaptor  8   a  adding the data read from disk i to the wait buffer in the RAM  154   a . Control then transfers to block  186  which represents the adaptor  8   a  returning the block to the user. If the block is not in the data structure  155   a  indicating blocks to add, then at block  184 , the adaptor  8   a  appends information on the blocks to the data structure  155   a  indicating blocks to add, and then proceeds to blocks  182  et seq. to return the data to the user. 
     In this way, a read request is processed in either two ways. If the data is in the read cache  18   a , read the data from the cache  18   a  and send it to the user. If the data is in the disk i, then read from disk, send to the user, and then add to the list of blocks  155   a  to add to the cache  18   a . However, the requested data cannot go into the read cache until the remote adaptor  8   b  provides permission pursuant to the permission exchange algorithm discussed in FIGS. 11 a, b  or other permission exchange algorithms known in the art. The permission exchange algorithm of FIGS. 11 a, b  insures that an adaptor with data in the wait buffer will not add that data to its read cache if the granting adaptor has recently updated to that data block on disk i. 
     FIG. 10 illustrates logic implemented in the adaptors  8   a, b  to handle an update request of a block B in disk i, wherein disk j maintains parity data, using the data structures  155 ,  156 ,  158 . Control begins at block  190  with an adaptor, e.g., updating adaptor  8   a , receiving a request to update block B in disk i. Control transfers to block  192  which represents the updating adaptor  8   a  determining whether the old version D of the data to update is in the read cache  18   a . If so, control transfers to block  194  to read the old data from disk i. If the data is in the read cache  18   a  at block  192  or if the data D is read from the disk i at block  194 , then control transfers to block  196 , which represents the updating adaptor  8   a  determining whether the data structure  158   a  indicating the blocks in the remote adaptor&#39;s  8   b  read cache  18   b  includes the block to update. If so, control transfers to block  198 ; otherwise, control transfers to block  200 . Thus, with the data structure  158   a, b, c , an adaptor  8   a, b, c  can determine the contents of the read cache  18   a, b, c  of another adaptor without messaging the adaptor. 
     If the remote adaptor  8   b  includes the block to update in its read cache  18   b , then at block  198 , the updating adaptor  8   a  sends a message to the remote adaptor  8   b  to invalidate the data block B to update from the remote read cache  18   b . Otherwise, at block  200 , the updating adaptor  8   a  adds block B to the data structure  158   a  indicating the block as recently updated. From block  198  or  200 , control transfers to block  202  which represents the updating adaptor  8   a  calculating partial parity, e.g., D xor D′, and invalidating the old data D from its read cache  18   a  if the old data D is in the read cache  18   a . Control then transfers to block  206  which represents the updating adaptor  8   a  saving the partial parity and parity group number for the partial parity data in the NVRAM  16   a . Control then transfers to block  208  which represents the updating adaptor  8   a  writing the new data D′ to block B in disk i. 
     From block  208 , control transfers to block  210  which represents the updating adaptor  8   a  determining whether a message was sent to the remote adaptor  8   b  at block  198 . If so, control transfers to block  212 ; otherwise, control transfers to block  214 . At block  212 , the updating adaptor  8   a  waits for a response from the remote adaptor  8   b  to its message to invalidate the data sent at block  198 . Upon receiving the response, control transfers to block  216  which represents the updating adaptor  8   a  updating the data structure  158  indicating the remote adaptor&#39;s  8   b  read cache  18   b  to indicate that the data block B was removed. From blocks  210  or  216 , control transfers to block  214  to return DONE to the user. 
     FIGS. 11 a  and  b  are flowcharts illustrating logic implemented in adaptors  8   a, b , respectively, when a requesting adaptor, e.g., adaptor  8   a , requests permission from a remote adaptor  8   b  to add a block of data to its read cache  18   a . The logic of FIG. 11 a  describes operations performed by the requesting adaptor  8   a  seeking permission to add data blocks to read cache  18   a . The logic of FIG. 11 b  describes operations performed by the remote adaptor  8   b  to determine whether to grant permission to the requesting adaptor  8   a . The purpose of the permission requesting algorithm is to insure that the requesting adaptor  8   a  does not add stale data to its read cache  18   a . With respect to FIG. 11 a , control begins at block  220  which represents the requesting adaptor  8   a  selecting a block to remove from the read cache  18   a  for each block the adaptor  8   a  intends to add to the read cache  18   a . Control transfers to block  222  which represents the adaptor  8   a  removing the selected blocks from the read cache  18   a . Control then transfers to block  224  which represents the requesting adaptor  8   a  sending a message to the other adaptor  8   b  with a list of blocks the requesting adaptor  8   a  intends to add to the read cache  18   a  and the list of blocks removed. 
     Control transfers to block  226  which represents the requesting adaptor  8   a  waiting for a response from the granting adaptor  8   b . Control transfers to block  228  which represent the requesting adaptor  8   a  adding those blocks to which permission was granted to the read cache  18   a . Those blocks where permission was denied are not added. Control transfers to block  230  which represents the adaptor  8   a  setting the data structure  155   a  indicating blocks to add to the read cache  18   a  to NULL. 
     With reference to FIG. 11 b , control begins at block  232  which represents the granting adaptor  8   b  receiving the list of blocks the requesting adaptor  8   a  seeks to add to the read cache  18   a . Control transfers to block  234  which represents the granting adaptor  8   b  processing the data structure  156   b  indicating the list of recently updated blocks to determine whether any blocks the requesting adaptor  8   a  intends to add were recently updated. At block  234 , the granting adaptor  8   b  determines whether the requesting adaptor  8   a  intends to add data to its read cache  18   a  that is outdated in view of data the granting adaptor  8   b  recently updated. Control transfers to block  236  which represents the granting adaptor  8   b  sending a message to the requesting adaptor  8   a  denying permission to add those blocks included in the data structure  156   b  indicating blocks the granting adaptor  8   b  recently updated and permitting the requesting adaptor  8   a  to add those blocks not in the data structure  156   b  of recently updated blocks. Control transfers to block  240  which represents the granting adaptor  8   b  setting the data structure  156   b  indicating recently updated blocks to NULL. 
     Conclusion 
     This concludes the description of the preferred embodiments of the invention. The following describes some alternative embodiments for accomplishing the present invention. 
     In preferred embodiments, adaptors  8   a, b, c  interface the nodes  4   a, b, c  to allow sharing of storage resources. The adaptors  8   a, b, c  were described as having specific components, such as a processor  14   a, b, c , NVRAM  16   a, b, c , read cache  18   a, b, c , write cache  20   a, b, c , and NVS unit  22   a, b, c . In alternative embodiments, some or all the components of the adaptors  8   a, b, c  may be located elsewhere in the node  4   a, b, c  or share resources with the computer  6   a, b, c . In yet further embodiments, there may be a central computing resource or node that monitors or controls intercommunication between the nodes  4   a, b, c.    
     The write cache  20   a, b, c  and read cache  18   a, b, c  may be memory locations within a single memory device or memory locations within a separate memory device, comprised of any suitable memory device known in the art, including volatile and non-volatile memory devices. 
     The logic of FIGS. 4-7 and  9 - 11  is for illustrative purposes. Additional or alternative steps may be performed in addition to those illustrated in the logic. Further, the order of the steps in the preferred logic may also vary. 
     Updated parity P′ was calculated by taking the exclusive OR (XOR) of the old data D, new data D′, and old parity P. However, those skilled in the art will appreciate that alternative methods known in the art for determining parity may be used in addition to the exclusive or operation (XOR) described herein. 
     The preferred embodiments may be implemented as a method, apparatus or article of manufacture using standard programming and/or engineering techniques to produce software, firmware, hardware, or any combination thereof. The term “article of manufacture” (or alternatively, “computer program product”) as used herein is intended to encompass one or more computer programs and data files accessible from one or more computer-readable devices, carriers, or media, such as a magnetic storage media, “floppy disk,” CD-ROM, a file server providing access to the programs via a network transmission line, holographic unit, etc. Of course, those skilled in the art will recognize many modifications may be made to this configuration without departing from the scope of the present invention. 
     In summary, preferred embodiments in accordance with the present invention provide a system for updating data at a data block. A first processing unit receives update data. The data block to update is located in a first storage device and a second storage device stores parity data for the data block. A parity group comprises a data block and corresponding parity data for the data block. The first processing unit obtains the data at the data block and calculates partial parity data from the data at the data block and the update data. The first processing unit stores the partial parity data in a storage area and writes the update data to the data block in the first storage device. The first processing unit further updates parity data for parity groups for which partial parity data is maintained by obtaining control of access to the parity group to update from a second processing unit if the first processing unit does not control access to the parity group. When the first processing unit controls access to the parity group, the first processing unit calculates new parity data from the partial parity data and the parity data in the second storage device, and writes the new parity data to the second storage device. 
     The foregoing description of the preferred embodiments of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. It is intended that the scope of the invention be limited not by this detailed description, but rather by the claims appended hereto. The above specification, examples and data provide a complete description of the manufacture and use of the composition of the invention. Since many embodiments of the invention can be made without departing from the spirit and scope of the invention, the invention resides in the claims hereinafter appended.