Method and Apparatus for Fault Tolerant Fast Writes Through Buffer Dumping

1. Field of the Invention

This invention relates to fault tolerant data storage devices, and more particularly to a method and apparatus for protecting data stored in a Write buffer of a fault tolerant data storage device.

2. Description of Related Art

A typical data processing system generally involves one or more storage units which are connected to a Central Processor Unit (CPU) either directly or through a control unit and a channel. The function of the storage units is to store data and programs which the CPU uses in performing particular data processing tasks.

Various types of storage units are used in current data processing systems. A typical system may include one or more large capacity tape units and/or disk drives (magnetic, optical, or semiconductor) connected to the system through respective control units for storing data.

However, a problem exists if one of the large capacity storage units fails such that information contained in that unit is no longer available to the system. Generally, such a failure will shut down the entire computer system.

The prior art has suggested several ways of solving the problem of providing reliable data storage. In systems where records are relatively small, it is possible to use error correcting codes which generate ECC syndrome bits that are appended to each data record within a storage unit. With such codes, it is possible to correct a small amount of data that may be read erroneously. However, such codes are generally not suitable for correcting or recreating long records which are in error, and provide no remedy at all if a complete storage unit fails. Therefore, a need exists for providing data reliability external to individual storage units.

Other approaches to such "external" reliability have been described in the art. A research group at the University of California, Berkeley, in a paper entitled "A Case for Redundant Arrays of Inexpensive Disks (RAID)", Patterson, et al., Proc. ACM SIGMOD, June 1988, has catalogued a number of differera approaches for providing such reliability when using disk drives as storage units. Arrays of disk drives are characterized in one of five architectures, under the acronym "RAID" (for Redundant Arrays of Inexpensive Disks).

A RAID 1 architecture involves providing a duplicate set of "mirror" storage units and keeping a duplicate copy of all data on each pair of storage units. While such a solution solves the reliability problem, it doubles the cost of storage. A number of implementations of RAID 1 architectures have been made, in particular by Tandem Corporation.

A RAID 2 architecture stores each bit of each word of data, plus Error Detection and Correction (EDC) bits for each word, on separate disk drives (this is also known as "bit striping"). For example, U.S. Pat. No. 4,722,085 to Flora et al. discloses a disk drive memory using a plurality of relatively small, independently operating disk subsystems to function as a large, high capacity disk drive having an unusually high fault tolerance and a very high data transfer bandwidth. A data organizer adds 7 EDC bits (determined using the well-known Hamming code) to each 32-bit data word to provide error detection and error correction capability. The resultant 39-bit word is written, one bit per disk drive, on to 39 disk drives. If one of the 39 disk drives fails, the remaining 38 bits of each stored 39-bit word can be used to reconstruct each 32-bit data word on a word-by-word basis as each data word is read from the disk drives, thereby obtaining fault tolerance.

An obvious drawback of such a system is the large number of disk drives required for a minimum system (since most large computers use a 32-bit word), and the relatively high ratio of drives required to store the EDC bits (7 drives out of 39). A further limitation of a RAID 2 disk drive memory system is that the individual disk actuators are operated in unison to write each data block, the bits of which are distributed over all of the disk drives. This arrangement has a high data transfer bandwidth, since each individual disk transfers pan of a block of data, the net effect being that the entire block is available to the computer system much faster than if a single drive were accessing the block. This is advantageous for large data blocks. However, this arrangement also effectively provides only a single read/write head actuator for the entire storage unit. This adversely affects the random access performance of the drive array when data files are small, since only one data file at a time can be accessed by the "single" actuator. Thus, RAID 2 systems are generally not considered to be suitable for computer systems designed for On-Line Transaction Processing (OLTP), such as in banking, financial, and reservation systems, where a large number of random accesses to many small data files comprises the bulk of data storage and transfer operations.

A RAID 3 architecture is based on the concept that each disk drive storage unit has internal means for detecting a fault or data error. Therefore, it is not necessary to store extra information to detect the location of an error; a simpler form of parity-based error correction can thus be used. In this approach, the contents of all storage units subject to failure are "Exclusive OR'd" (XOR'd) to generate parity information. The resulting parity information is stored in a single redundant storage unit. If a storage unit fails, the data on that unit can be reconstructed on to a replacement storage unit by XOR'ing the data from the remaining storage units with the parity information. Such an arrangement has the advantage over the mirrored disk RAID 1 architecture in that only one additional storage unit is required for "N" storage units. A further aspect of the RAID 3 architecture is that the disk drives are operated in a coupled manner, similar to a RAID 2 system, and a single disk drive is designated as the parity unit.

One implementation of a RAID 3 architecture is the Micropolis Corporation Parallel Drive Array, Model 1804 SCSI, that uses four parallel, synchronized disk drives and one redundant parity drive. The failure of one of the four data disk drives can be remedied by the use of the parity bits stored on the parity disk drive. Another example of a RAID 3 system is described in U.S. Pat. No. 4,092,732 to Ouchi.

A RAID 3 disk drive memory system has a much lower ratio of redundancy units to data units than a RAID 2 system. However, a RAID 3 system has the same performance limitation as a RAID 2 system, in that the individual disk actuators are coupled, operating in unison. This adversely affects the random access performance of the drive array when data files are small, since only one data file at a time can be accessed by the "single" actuator. Thus, RAID 3 systems are generally not considered to be suitable for computer systems designed for OLTP purposes.

A RAID 4 architecture uses the same parity error correction concept of the RAID 3 architecture, but improves on the performance of a RAID 3 system with respect to random reading of small files by "uncoupling" the operation of the individual disk drive actuators, and reading and writing a larger minimum amount of data (typically, a disk sector) to each disk (this is also known as block striping). A further aspect of the RAID 4 architecture is that a single storage unit is designated as the parity unit.

A limitation of a RAID 4 system is that Writing a data block on any of the independently operating data storage units also requires writing a new parity block on the parity unit. The parity information stored on the parity unit must be read and XOR'd with the old data (to "remove" the information content of the old data), and the resulting sum must then be XOR'd with the new data (to provide new parity information). Both the data and the parity records then must be rewritten to the disk drives. This process is commonly referred to as a "Read-Modify-Write" sequence.

Thus, a Read and a Write on the single parity unit occurs each time a record is changed on any of the data storage units covered by the parity record on the parity unit. The parity unit becomes a bottle-neck to data writing operations since the number of changes to records which can be made per unit of time is a function of the access rate of the parity unit, as opposed to the faster access rate provided by parallel operation of the multiple data storage units. Because of this limitation, a RAID 4 system is generally not considered to be suitable for computer systems designed for OLTP purposes. Indeed, it appears that a RAID 4 system has not been implemented for any commercial purpose.

A RAID 5 architecture uses the same parity error correction concept of the RAID 4 architecture and independent actuators, but improves on the writing performance of a RAID 4 system by distributing the data and parity information across all of the available disk drives. Typically, "N+1" storage units in a set (also known as a "redundancy group") are divided into a plurality of equally sized address areas referred to as blocks. Each storage unit generally contains the same number of blocks. Blocks from each storage unit in a redundancy group having the same unit address ranges are referred to as "stripes". Each stripe has N blocks of data, plus one parity block on one storage unit containing parity for the remainder of the stripe. Further stripes each have a parity block, the parity blocks being distributed on different storage units. Parity updating activity associated with every modification of data in a redundancy group is therefore distributed over the different storage units. No single unit is burdened with all of the parity update activity.

For example, in a RAID 5 system comprising 5 disk drives, the parity information for the first stripe of blocks may be written to the fifth drive; the parity information for the second stripe of blocks may be written to the fourth drive; the parity information for the third stripe of blocks may be written to the third drive; etc. The parity block for succeeding stripes typically "precesses" around the disk drives in a helical pattern (although other patterns may be used).

Thus, no single disk drive is used for storing the parity information, and the bottle-neck of the RAID 4 architecture is eliminated. An example of a RAID 5 system is described in U.S. Pat. No. 4,761,785 to Clark et al.

As in a RAID 4 system, a limitation of a RAID 5 system is that a change in a data block requires a Read-Modify-Write sequence comprising two Read and two Write operations: the old parity block and old data block must be read and XOR'd, and the resulting sum must then be XOR'd with the new data. Both the data and the parity blocks then must be rewritten to the disk drives. While the two Read operations may be done in parallel, as can the two Write operations, modification of a block of data in a RAID 4 or a RAID 5 system still takes substantially longer then the same operation on a conventional disk. A conventional disk does not require the preliminary Read operation, and thus does have to wait for the disk drives to rotate back to the previous position in order to perform the Write operation. The rotational latency time alone can amount to about 50% of the time required for a typical data modification operation. Further, two disk storage units are involved for the duration of each data modification operation, limiting the throughput of the system as a whole.

Despite the Write performance penalty, RAID 5 type systems have become increasingly popular, since they provide high data reliability with a low overhead cost for redundancy, good Read performance, and fair Write performance. However, it would be desirable to have the benefits of a RAID 5 system without the Write performance penalty resulting from the rotational latency time imposed by the parity update operation.

In accordance with a number of the RAID systems currently used, an array controller is used to coordinate the Read and Write operations to and from the data storage units within the array. Data to be written to the array is typically transmitted to the array controller. The array controller then determines on which data storage unit to store the data and conducts the required Read-Modify-Write operation. Since the CPU that transmits the data to be written to the array has completed its role in the write operation after the data has been successfully received by the controller, it would be desirable for the CPU to have no further involvement in the write operation. However, because the data may be lost, and a retransmission may be required, it is essential for the CPU to await receipt of an acknowledgement that the data has been successfully stored in the array.

The present invention provides a method and apparatus for solving the error-correction block bottleneck inherent in a RAID 5 architecture. The present invention also provides a method and apparatus for ensuring that data that has been transmitted to an array controller is sufficiently protected as to allow the controller to acknowledge the completion of the Write operation to the CPU immediately after the data has been completely received in the array controller.

The present invention solves the error-correction block bottleneck inherent in a RAID 5 architecture by recognition that storage unit accesses are intermittent. That is, at various times one or more of the storage units in a RAID 5 system are idle in terms of access requests by the CPU. This characteristic can be exploited by providing a "copyback cache" storage unit as an adjunct to a standard RAID system. The present invention provides five alternative methods of operating such a system.

In each embodiment, when a Write occurs to the RAID system, the data is immediately written to the first available location in the copyback cache storage unit. Upon completion of the Write to the copyback cache storage unit, the host CPU is immediately informed that the Write was successful. Thereafter, further storage unit accesses by the CPU can continue without waiting for an error-correction block update for the data just written.

In the first embodiment of the invention, during idle time for relevant storage units of the storage system, an error-correction block (e.g., XOR parity) is computed for each "pending" data block on the copyback cache storage unit, and the data block and corresponding error-correction block are copied to their proper location in the RAID system. Optionally, if a number of pending data blocks are to be written to the same stripe, an error-correction block can be calculated from all data blocks in the stripe at one time, thus achieving some economy of time. In this embodiment, the copyback cache storage unit in effect stores "peak load" Write data and then completes the actual Read-Modify-Write operations to the RAID system during relatively quiescent periods of I/O accesses by the CPU.

In the second embodiment of the invention, after Write data is logged to the copyback cache storage unit, normal Read-Modify-Write operation by the RAID system controller continues in overlapped fashion with other CPU I/O accesses, using Write data in the array controller's buffer memory. Thus, there are at least two redundant copies of each pending data block. Performance is enhanced because the CPU can continue processing as soon as the simple Write operation to the copyback cache storage unit completes, thus eliminating the delay caused by a normal Read-Modify-Write RAID system. In this embodiment, the copyback cache storage unit acts more as a running "log" of Write data. Data integrity and redundancy is preserved since the Write data is saved to the copyback cache storage unit and thus accessible even if the Read-Modify-Write operation from the controller buffer to the RAID system never completes.

In the third embodiment of the invention, one or more logical arrays of storage units are defined. Each logical array of storage units is associated with at least one controller. When Write data is presented to a controller, the data is immediately stored in a controller buffer. Each controller buffer is associated with a unique copyback cache storage unit. A copy of the data stored in the controller buffer is written to its associated copyback cache storage unit. Thus, there are at least two redundant copies of each pending data block. The CPU is informed that the Write operation was successfully completed immediately after the data is written to the copyback cache storage unit. Data blocks are only read from a copyback cache storage unit upon a failure of the associated controller buffer. In one alternative embodiment, each copyback cache unit is logically divided into at least two logical areas, so that if a copyback cache storage unit fails, another copyback cache storage unit associated with another logical array can be shared by two logical arrays.

In the fourth embodiment of the invention, no physical storage unit is assigned as a copyback cache unit. Rather, at least one logical stripe within each of the storage units that comprise the array is reserved for storing a copy of the pending blocks of data in the controller buffer. As is the case in the third embodiment, pending data blocks are read only from the controller buffer during Read-Modify-Write operations unless the controller buffer has failed.

The copyback cache storage unit is preferably non-volatile, so that data will not be lost on a power failure. If the copyback cache storage unit is a disk drive, it may be paired with a "mirror" storage unit for additional fault tolerance. Optionally, the copyback cache storage unit may be a solid-state storage unit, which can achieve substantially faster Write and error-correction block update times than a disk drive.

The use of the copyback cache allows the acknowledgement of completion of the write operation far faster than is possible without the use of the copyback cache. However, the data is actually received within the controller buffer well before the acknowledgement is can be safely provided. That is, it is not safe to acknowledge completion of the write operation before the data has been safely written from the controller buffer to the copyback cache or otherwise to the RAID system, because a failure of the controller would cause a loss of the data. It is possible to write data to more than one controller. However, at least two controllers must receive every write command and the associated data. Such an arrangement reduces the efficiency of the RAID system.

In the fifth embodiment of the present invention, each array controller includes a DATA-RAM and a SHADOW-RAM. Both the DATA-RAM and the SHADOW-RAM are coupled to a first and second memory interface. Each memory interface has the ability to independently communicate the contents of the SHADOW-RAM over a controller-controller data link to at least one other similar array controller. The memory interface also interfaces the DATA-RAM and the SHADOW-RAM to a CPU, the data storage units of the RAID system, and the controller processor. Write data received from the CPU is stored in the two independent memories in order to ensure that pending Write data (i.e., Write data that has not yet been written to the RAID system, including any copyback cache device) will not be lost. In addition, the two memory interfaces provide redundant access routes which allow Write data to be retrieved by another array controller if the controller processor fails. A backup power source is provided to ensure that power will be available to at least one of the two memories such that the data that has been received within the controller will always be accessible. Accordingly, since the data will be accessible, even if of a failure of any single component or power source occurs, the controller may acknowledge the write operation requested by the CPU as soon as data is successfully written to both the DATA-RAM and the SHADOW-RAM.

The details of the preferred embodiment of the present invention are set forth in the accompanying drawings and the description below. Once the details of the invention are known, numerous additional innovations and changes will become obvious to one skilled in the art.

FIG. 1 is block diagram of a copyback cache RAID system in accordance with the present invention.

FIGS. 2A and 2B, is a flow-chart of Read and Write operation in accordance with a first embodiment of the present invention.

FIGS. 3A and 3B, is a flow-chart of Read and Write operation in accordance with a second embodiment of the present invention.

FIG. 4 is a block diagram of a copyback cache RAID system in accordance with an alternative embodiment of the present invention having multiple controllers.

FIGS. 5A and 5B, is a high-level flow chart representing the steps of Read and Write operations for the embodiment of the invention in which a RAID system has multiple controllers.

FIG. 6 is a high level flow chart of the steps taken in accordance with the present invention when a copyback cache storage unit becomes unavailable.

FIG. 7 is a block diagram of a RAID system in accordance with another embodiment of the present invention, in which pending data blocks are spread over a number of storage units that comprise the array.

FIG. 8 is a block diagram of a RAID system in accordance with yet another embodiment of the present invention in which each controller has two local memories, two devices for transmitting the contents of at least one of the memories, and a connection between the controllers for communicating the contents of the local memories.

Like reference numbers and designations in the various drawings refer to like elements.

Throughout this description, the preferred embodiment and examples shown should be considered as exemplars, rather than as limitations on the present invention.

FIG. 1 is block diagram of a copyback cache RAID system in accordance with the present invention. Shown are a CPU 1 coupled by a bus 2 to an array controller 3, which in the preferred embodiment is a fault-tolerant controller. The array controller 3 is coupled to each of the plurality of storage units S1-S5 (five being shown by way of example only) by an I/O bus (e.g., a SCSI bus). The array controller 3 preferably includes a separately programmable processor (for example, the MIPS R3000 RISC processor, made by MIPS of Sunnyvale, Calif.) which can act independently of the CPU 1 to control the storage units.

The storage units S1-S5 are failure independent, meaning that the failure of one unit does not affect the physical operation of other units. Optionally, the storage units S1-S5 are disk drive units including solid state storage unit buffers 7 (i.e., such as track buffers). Such solid state storage unit buffers 7 allow data to be written by a controller to a disk drive without encountering the delay associated with disk rotational latency of a disk drive. Data that is written to the solid state storage unit buffer 7 is preferably written from the solid state storage unit buffer 7 to the rotating medium of the disk drive unit as soon as possible.

Also attached to the controller 3 is a copyback cache storage unit CC, which in the preferred embodiment is coupled to the common I/O bus (e.g., a SCSI bus) so that data can be transferred between the copyback cache storage unit CC and the storage units S1-S5. The copyback cache storage unit CC is preferably non-volatile, so that data will not be lost on a power failure. If the copyback cache storage unit CC is a disk drive, it may be paired with a "mirror" storage unit CC' for additional fault tolerance. The mirror storage unit CC' is coupled to the controller 3 such that all data written to the copyback cache storage unit CC is also written essentially simultaneously to the mirror storage unit CC', in known fashion. Optionally, the copyback cache storage unit CC may be a solidstate storage unit, which can achieve substantially faster Write and error-correction block update times than a disk drive. In such a case, the solid-state storage unit preferably includes error-detection and correction circuitry, and is either non-volatile or has a battery backup on the power supply.

The storage units S1-S5 can be grouped into one or more redundancy groups. In the illustrated examples described below, the redundancy group comprises all of the storage units S1-S5, for simplicity of explanation.

The present invention is preferably implemented as a computer program executed by the controller 3. FIG. 2A and 2B is a high-level flowchart representing the steps of the Read and Write processes for a first embodiment of the invention. FIG. 3A and 3B is a high-level flowchart representing the steps of the Read and Write processes for a second embodiment of the invention. The steps shown in FIGS. 2A, 2B, 3A, and 3B are referenced below.

The Peak Load Embodiment

The controller 3 monitors input/output requests from the CPU 1 on essentially a continuous basis (Step 20). If a Write request is pending (Step 21), the data block is immediately written to the first available location in the copyback cache storage unit CC (Step 22) (the data block is also stored on the mirror storage unit CC', if present). Preferably, writing begins at the first logical block on the copyback cache storage unit CC, and continues sequentially to the end of the logical blocks. Thereafter, writing commences again at the first block (so long as no blocks are overwritten that have not been stored in the array). This preferred method minimizes time-consuming SEEK operations (i.e., physical movements of a Read/Write head in a storage unit) in the copyback cache storage unit CC.

Each data block stored on the copyback cache storage unit CC is also flagged with the location in the array where the data block is ultimately to be stored, and a pointer is set to indicate that the data block is in the copyback cache storage unit CC (Step 23). This location and pointer information is preferably kept in a separate table in memory or on the copyback cache storage unit CC. The table preferably comprises a directory table having entries that include standard information regarding the size, attributes, and status of each data block. In addition, each entry has one or more fields indicating whether the data block is stored on the copyback cache storage unit CC or in the array (S1-S5), and the "normal" location in the array for the data blocks. Creation of such directory tables is well-known in the art.

If a data block is written to the copyback cache storage unit CC while a data block to be stored at the same location in the array is still a "pending block" (a data block that has been Written to the copyback cache storage unit CC but not transferred to the array S1-S5), the directory location pointer for the data block is changed to point to the "new" version rather than to the "old" version. The old version is thereafter ignored, and may be written over in subsequent operations.

After a Write request is processed in this fashion, the controller 3 immediately sends an acknowledgement to the CPU 1 indicating that the Write operation was successful (Step 24). The monitoring process then repeats (Step 25). Further storage unit accesses by the CPU 1 can continue without waiting for an error-correction block update to the array S1-S5 for the data block just written. Thus, the Write "throughput" time of the array appears to be the same as a non-redundant system, since storage of the Write data on the copyback cache storage unit CC does not require the Read-Modify-Write sequence of a standard RAID system with respect to operation of the CPU 1.

If a Write request is not pending (Step 21), the controller 3 tests whether a Read request is pending (Step 26). If a Read request is pending, the controller 3 reads the directory table to determine the location of each requested data block (Step 27). If a requested data block is not in the array (Step 28), the controller 3 reads the block from the copyback cache storage unit CC and transfers it to the CPU 1 (Step 29). The monitoring process then repeats (Step 30). If the requested data block is in the array (Step 28), the controller 3 reads the block from the array (S1-S5) in normal fashion and transfers it to the CPU 1 (Step 31). The monitoring process then repeats (Step 32).

Some embodiments of the invention may include disk cache memory in the controller 3. Read requests may of course be "transparently" satisfied from such a cache in known fashion.

If no Write or Read operation is pending for particular storage units in the array, indicating that those storage units are "idle" with respect to CPU 1 I/O accesses, the controller 3 checks to see if any data blocks are "pending blocks" flagged to locations on the idle storage units. If no pending blocks exist (Step 33), the controller 3 begins the monitoring cycle again (Step 34).

If a pending block does exist (Step 33), the controller 3 reads a pending block from the copyback cache storage unit CC (Step 35). The controller 3 then writes the pending block to the proper location in the array, and computes and stores a new error-correction block based upon the pending block.

In the preferred embodiment of the invention, the error-correction blocks contain parity information. Thus, update of the error-correction block for the pending block can be accomplished by reading the old data block and old error-correction block corresponding to the array location indicated by the location information for the pending block stored in the directory (Step 36). The controller 3 then XOR's the old data block, the pending data block, and the old error-correction block to generate a new error-correction block (Step 37). The new error-correction block and the pending block are then written to the array S1-S5 at their proper locations (Step 38).

Optionally, if a number of pending blocks are to be written to the same stripe, error-correction can be calculated for all data blocks in the stripe at one time by reading all data blocks in the stripe that are not being updated, XOR'ing those data blocks with the pending blocks to generate a new error-correction block, and writing the pending blocks and the new error-correction block to the array. This may achieve some economy of time.

After the pending block is transferred from the copyback cache storage unit CC to the array, the directory entry for that block is modified to indicate that the data block is in the array rather than in the copyback cache storage unit CC (Step 39). Thereafter, the controller 3 begins the monitoring cycle again (Step 40).

Although the invention has been described in terms of a sequential branching process, the invention may also be implemented in a multi-tasking system as separate tasks executing concurrently. Thus, the Read and Write processes described above, as well as the transfer of pending data blocks, may be implemented as separate tasks executed concurrently. Accordingly, the tests indicated by Steps 21, 26, and 33 in FIGS. 2A and 2B may be implicitly performed in the calling of the associated tasks for Writing and Reading data blocks, and transfer of pending blocks. Thus, for example, the transfer of a pending block from the copyback cache storage unit CC to a storage unit in the array may be performed concurrently with a Read operation to a different storage unit in the array. Further, if the array is of the type that permits the controller 3 to "stack" a number of I/O requests for each storage unit of the array (as is the case with many SCSI-based RAID systems), the operations described above may be performed "concurrently" with respect to accesses to the same storage unit.

The Data Log Embodiment

As in the embodiment describe above, the controller 3 monitors input/output requests from the CPU 1 on essentially a continuous basis (Step 50). In this embodiment, the controller 3 is provided with a relatively large (for example, one megabyte or more) data buffer to temporarily store data to be written to the array. If a Write request is pending (Step 51), the data block is immediately written by the controller 3 to the first available location in the copyback cache storage unit CC (Step 52) (the data block is also stored on the mirror storage unit CC', if present). Preferably, writing begins at the first logical block on the copyback cache storage unit CC, and continues sequentially to the end of the logical blocks. Thereafter, writing commences again at the first block (so long as no blocks are overwritten that have not been stored in the array). This preferred method minimizes SEEK operations in the copyback cache storage unit CC.

In the first embodiment, SEEK operations are required to retrieve pending blocks during idle times to transfer to the array. In the second embodiment, the copyback cache storage unit CC acts as a running "log" of Write data. In contrast with the first embodiment, SEEK operations normally are necessary only to change to a next data-writing area (e.g., a next cylinder in a disk drive) when the current area is full, or to reset the Read/Write head back to the logical beginning of the storage unit after reaching the end, or to retrieve data blocks after a failure.

Each data block stored on the copyback cache storage unit CC is also flagged with the location in the array where the data block is ultimately to be stored and the location of the data block in the copyback cache storage unit CC, and a pointer is set to indicate that the data block is in the controller buffer (Step 53). As before, such location and pointer information is preferably kept in a directory table.

Because of the buffer in the controller 3, the definition of a "pending block" in the second embodiment differs somewhat from the definition in the first embodiment described above. A "pending block" is a data block that has been Written to the copyback cache storage unit CC but not transferred from the controller buffer to the array S1-S5.

If a data block is written to the copyback cache storage unit CC while a data block to be stored at the same location in the array is still a "pending block" in the controller buffer, the directory location pointers for the data block are changed to point to the "new" version rather than to the "old" version both in the copyback cache storage unit CC and in the buffer. The old version is thereafter ignored, and may be written over in subsequent operations.

After a Write request is processed in this fashion, the controller 3 immediately sends an acknowledgement to the CPU 1 indicating that the Write operation was successful (Step 54). The monitoring process then repeats (Step 55). Further storage unit accesses by the CPU 1 can continue without waiting for an error-correction block update for the data block just written. Thus, the Write response time of the array appears to be the same as a non-redundant system, since storage of the Write data on the copyback cache storage unit CC does not require the Read-Modify-Write sequence of a standard RAID system with respect to operation of the CPU 1.

If a Write request is not pending (Step 51), the controller 3 tests whether a Read request is pending (Step 56). If a Read request is pending, the controller 3 reads the directory table to determine the location of each requested data block (Step 57). If a requested data block is in the array (Step 58), the controller 3 reads the block from the array (S1-S5) in normal fashion and transfers it to the CPU 1 (Step 59). The monitoring process then repeats (Step 60).

If a requested data block is not in the array (Step 58), it is in the buffer of the controller 3. The controller 3 transfers the data block from its buffer to the CPU 1 (Step 61). This operation is extremely fast compared to the first embodiment, since the buffer operates at electronic speeds with no mechanically-imposed latency period. The monitoring process then repeats (Step 62).

If no Write or Read operation is pending for particular storage units in the array, indicating that those storage units are "idle" with respect to CPU 1 I/O accesses, the controller 3 checks to see if any data blocks in its buffer are "pending blocks" flagged to locations on the idle storage units. If no pending blocks exist (Step 63), the controller 3 begins the monitoring cycle again (Step 64).

If a pending block does exist (Step 63), the controller 3 accesses the pending block (Step 65), and then computes and stores a new error-correction block based upon the pending block. As before, in the preferred embodiment of the invention, the error-correction blocks contain parity information. Thus, update of the error-correction block for the pending block can be accomplished by reading the old data block and old error-correction block corresponding to the array location indicated by the location information for the pending block stored in the directory (Step 66). The controller 3 then XOR's the old data block, the pending data block, and the old error-correction block to generate a new error-correction block (Step 67). The new error-correction block and the pending block are then written to the array S1-S5 (Step 68).

Optionally, if a number of pending blocks are to be written to the same stripe, error-correction can be calculated for all data blocks in the stripe at one time by reading all data blocks in the stripe that are not being updated, XOR'ing those data blocks with the pending blocks to generate a new error-correction block, and writing the pending blocks and the new error-correction block to the array. This may achieve some economy of time.

After the pending block is transferred from the buffer of the controller 3 to the array, the directory is modified to indicate that the pending block is no longer valid in the copyback cache storage unit CC or in the buffer (Step 69). The old pending block is thereafter ignored, and may be written over in subsequent operations. The controller 3 then restarts the monitoring cycle (Step 70).

If a failure to the system occurs before all pending blocks are written from the buffer to the array, the controller 3 can read the pending blocks from the copyback cache storage unit CC that were not written to the array. The controller 3 then writes the selected pending blocks to the array.

Again, although the invention has been described in terms of a sequential branching process, the invention may also be implemented in a multi-tasking system as separate tasks executing concurrently. Accordingly, the tests indicated by Steps 51, 56, and 63 in FIG. 3 may be implicitly performed in the calling of the associated tasks for Writing and Reading data blocks, and transfer of pending blocks.

The present invention therefore provides the benefits of a RAID system without the Write performance penalty resulting from the rotational latency time imposed by the standard error-correction update operation, so long as a non-loaded condition exists with respect to I/O accesses by the CPU 1. Idle time for any of the array storage units is productively used to allow data stored on the copyback cache storage unit CC to be written to the array (either from the cache itself, or from the controller buffer) during moments of relative inactivity by the CPU 1, thus improving overall performance.

Furthermore, in many RAID systems, a "hot spare" storage unit is provided to immediately substitute for any active storage unit that fails. The present invention may be implemented by using such a "hot spare" as the copyback cache storage unit CC, thus eliminating the need for a storage unit dedicated to the copyback cache function. If the "hot spare" is needed for its primary purpose, the RAID system can fall back to a non-copyback caching mode of operation until a replacement disk is provided.

Overview of Copyback Cache for use with Multiple Controllers

In a RAID system having more than one array controller, a copyback cache system can be implemented to minimize the amount of time required to acknowledge a complete Write operation to the array. In one embodiment of the present invention, a controller buffer, such as a solid state buffer, is provided within each controller. Pending data blocks received by a controller are immediately stored in the controller buffer. Concurrently, a copy of the pending data block is written to a copyback cache storage unit which is preferably associated with one controller. A header and a trailer are also preferably written to the copyback cache storage unit. The header includes information that determines where the pending data block will ultimately be stored and which data blocks within the copyback cache storage unit are valid (i.e., have not yet been written to the array). The trailer is a copy of the header and is used to verify that the complete transfer occurred. As soon as the pending data block is stored in the copyback cache storage unit, the controller acknowledges successful completion of the Write operation to the CPU.

The information stored in the copyback cache storage unit is used only if there is a failure of the controller buffer. Otherwise, pending data blocks are read from the controller buffer when the pending data block is to be written to the array. Attempts to both Read and Write pending data blocks are preferably inhibited until the pending data block is written to the array. This simplifies operation of the present invention. However, in an alterative embodiment, Read and Write operations could be performed to and from the controller buffer by ensuring that the most recent information for a data block is read from the controller buffer both when transferring the pending data block from the controller buffer to the array and when satisfying a CPU Read request.

In the preferred embodiment, existing "hot spares" in a RAID system may be used as the copyback cache storage units. This allows implementation of the invention in existing systems by appropriately programming the array controller or controllers.

Operation of a RAID system having two or more controllers is similar to operation of the previously described embodiments of the present invention. However, if one of the copyback cache storage units fails or is called into service as a spare to replace a failed storage unit, then the present invention permits sharing of any of the remaining copyback cache storage units among the controllers. If only one spare unit was available to serve as a copyback cache storage unit, or if all of the spare units that were being used as copyback cache storage units have become unavailable, then in one embodiment of the present invention, a portion of each of the storage units that comprise the array is used to store a copy of each pending data block maintained in each controller buffer.

After a copy of a pending data block is stored in a storage unit, the controller associated with the logical array to which the pending data block will ultimately be stored indicates to the CPU that the Write operation is complete. In this way, there are always two copies of a pending data block before completion of a Write operation is acknowledged to the CPU.

Details of the Copyback Cache for use with Multiple Controllers

FIG. 4 is a block diagram of a copyback cache system having multiple controllers, in accordance with an embodiment of the present invention. In the system shown in FIG. 4, a CPU 1 is coupled by a bus 2 to two array controllers 403, 405 (two controllers being shown by way of example only). Each controller 403, 405 is coupled to each of a plurality of storage units S1-S3 (3 being shown by way of example only) by an I/O bus (e.g., a SCSI bus). The array of storage units S1-S3 are failure independent. The array controllers 403, 405 are each essentially identical to the array controller 3 previously discussed. Each controller 403, 405 can independently read and write to each of the storage units S1-S3. In addition, each of the controllers 403, 405 are coupled by the I/O bus to fourth and fifth storage units HS1, HS2 which comprise "hot spares" for the array. Optionally, at least one of the storage units HS1, HS2 is a disk drive unit including a solid state track buffer 407. The inclusion of solid state track buffers 407 within a storage unit HS1, HS2 allows substantially faster Write times than would be possible by direct Writes to the rotating medium of the disk drive, since the disk drive acknowledges the completion of a Write to the storage unit as soon as the data block is written to the track buffer 407.

In the preferred embodiment of the present invention, the data storage units S1-S3 are logically configured as redundant logical arrays LA1, LA2, as described in co-pending U.S. patent application Ser. No. 07/852,374. The physical storage units S1-S3 are mapped into a plurality of logical storage units LS1-LS6. Each logical storage unit LS1, LS6 comprises non-overlapping groups of data blocks. The logical storage units LS1, LS6 are logically grouped into two logical arrays LA1, LA2. The two array controllers 403, 405 correspond one-to-one with the two logical arrays LA1, LA2 and interface the logical arrays LA1, LA2 with the CPU 1. When both controllers 403, 405 are functional, each logical array LA1, LA2 is under the control of a corresponding controller 403, 405. If a controller 403, 405 fails, the other controller 405, 403 assumes operational control of both logical arrays LA1, LA2.

In this embodiment of the present invention, a first copyback cache associated with a first of the logical arrays LA1 is maintained in the combination of (1) the controller buffer 408 of the array controller 403 associated with the first logical array, and (2) the HS1 storage unit, which maintains a copy of the pending data blocks stored in the copyback cache in the controller buffer 408 of the array controller 403. Similarly, a second copyback cache is maintained in the controller buffer 408 of the array controller 405 associated with the second logical array LA2 and HS2 storage unit.

Since each logical array LA1, LA2 is controlled by only one array controller 403, 405, both controllers 403, 405 can be active simultaneously without concern that data access "collisions" will occur. Furthermore, since each controller 403, 405 is assigned a unique copyback cache storage unit HS1, HS2, each controller 403, 405 can write pending data blocks to the copyback cache storage unit HS1, HS2 associated with that controller 403, 405.

Logical Organization of Copyback Cache Storage Units

In the preferred embodiment of a multiple controller version of the present invention, each active copyback cache storage unit HS1, HS2 is divided into a number of logical areas, each corresponding to a logical array. Therefore, if there are two controllers 403, 405 (as shown in FIG. 4), there will be two logical arrays LA1, LA2 and two logical areas A1, A2 within each copyback cache storage unit HS1, HS2. The copyback cache storage units HS1, HS2 are divided into a number of logical areas A1, A2 equal to the number of logical arrays to allow each controller 403, 405 to share one copyback cache storage unit without conflicting with each other if one copyback cache storage unit becomes unavailable. In the preferred embodiment of the present invention, the logical division of the copyback cache storage units HS1, HS2 is performed whenever the system logical configuration is determined or updated.

Each logical area A1, A2 within a copyback cache storage unit HS1, HS2 is further divided into a number of entries. Each valid entry contains a header, pending data block, and trailer. The length of the data block is limited to 63 sectors in one embodiment of the present invention. However, other embodiments may limit the number of sectors per entry to greater or lesser numbers of sectors. In the present embodiment, if a data block comprises more than 63 sectors, then an acknowledge that the Write operation is complete is not returned to the CPU 1 until the Read-Modify-Write is complete.

The header in a valid entry includes the correct logical volume, sector number, and number of sectors of the associated pending data block. This information identifies the location within the array to which the associated pending data block will ultimately be written. Each entry also includes a copy of a bit map that indicates which entries are valid, and a sequence number that indicates which entry has the most up-to-date bit map to be used if the associated controller buffer 408 fails.

The bit map stored in an entry is a copy of a bit map stored within the controller buffer 408 at the time the pending data block was written to the copyback cache storage unit HS1, HS2. These bit maps each comprise one bit corresponding to each entry in an associated copyback cache storage unit HS1, HS2. When an entry is valid (i.e.,. there is a pending data block in the entry), the corresponding bit is set. When that entry becomes invalid (i.e., when the pending data block has been written completely and successfully to the storage units S1-S3 of the array), the corresponding bit is reset. The manner in which the bit maps with each entry are managed is detailed below.

The sequence number within each header indicates when the bit map in the header was generated with respect to other bit maps in other headers. Thus, by comparing the sequence numbers stored in each entry of the copyback cache storage units HS1, HS2, the most up-to-date bit map can be found. By maintaining sequence numbers associated with each bit map, old bit maps need not be updated.

Normal Operation of the Copyback Cache with Multiple Controllers

The present invention is preferably implemented as a computer program executed by each controller 403, 405. Each controller 403, 405 monitors Read and Write requests from the CPU 1 on essentially a continuous basis. Write requests are directed to either the first logical array LA1 (and thus the first controller 403) or the second logical array LA2 (and thus the second controller 405). FIG. 5A and 5B is a high level flow chart of the steps performed by controller 403, 405 when both controllers 403, 405, all storage units S1-S3, and at least two copyback cache storage units HS1, HS2 are operational. Since each controller 403, 405 performs essentially the same steps under these conditions, the steps are described below with respect to only one such controller 403.

Initially, the controller 403 determines whether a Write request has been received (STEP 501). If a Write request has been received, then the pending data block associated with the Write request is written to the controller buffer 408 (STEP 503). A header and trailer are then appended to a copy of the pending data block (STEP 505). The header includes an up-to-date version of the bit map which indicates which entries within the copyback cache storage unit HS1 are valid, including an indication that the entry to which the present pending data block is to be written is valid. The header also includes a sequence number to identify when the bit map was generated. The header, trailer, and pending data block are then written to an assigned entry within the copyback cache storage unit HS1 (STEP 507). If the header, trailer, and pending data block fit within the track buffer 407 (if a track buffer is present), then an acknowledge is sent to the CPU 1 immediately after the write to the track buffer 407 is complete. Otherwise, the acknowledge is sent only after the header, trailer, and pending data block have been completely written to the copyback cache storage unit HS1.

The controller 403 then returns to the start and again determines whether a Write request has been received (STEP 501). If no Write request has been received in (STEP 501), then the controller 403 determines whether a read request has been received (STEP 510). If a read request has been received, the controller 403 reads a location and pointer table and the bit map stored in the controller buffer 408 (STEP 512). The controller 403 determines whether the data block to be read is pending or has been successfully and completely written to a storage unit S1-S3 (STEP 514). If the data block has been completely and successfully written to a storage unit S1-S3, then the data block is read from the storage unit S1-S3 and transferred to the CPU 1 through the controller 403 (STEP 516). If, on the other hand, the data block has not yet been completely written to a storage unit S1-S3 (STEP 514), then the Read request is held up until the Write operation completes. Alternatively, the requested data can be read directly from the controller buffer 408. Once the write operation completes, the Read operation can be completed (STEP 516). Upon completion of the Read operation, the controller 403 returns to the start and again determines whether any Write requests have been received.

If no Write requests (STEP 501) or Read requests (STEP 510) have been received, then the controller 403 checks whether there are any pending data blocks in the controller buffer 408 (STEP 520). If at least one pending data block is present in the controller buffer 408, then the pending data block that was written to the controller buffer 408 first is read from the controller buffer 408 (STEP 522). The old data block is read from the storage units S1-S3 (STEP 524). The pending data block is then written to the storage unit S1-S3 (STEP 526). The controller 403 then invalidates the entry within the bit map stored in the controller buffer 408 to indicate that the data in that entry has been completely written to the storage units S1-S3 (STEP 528). The sequence number that was last used is then noted by the controller 403 (STEP 530). The old parity block is then read (STEP 532). The old parity block is XOR'd with the old data (to "remove" the information content of the old data), and the resulting sum is then XOR'd with the new data (to provide new parity information) (STEP 534). The new parity block is then written to the appropriate storage unit S1-S3 (STEP 536).

After the new parity block has been written, the controller 403 reads the last used sequence number again (STEP 538). That number is then compared with the sequence number that was previously read in STEP 532 (STEP 540). If the numbers are not the same, indicating that another pending data block has been written to the copyback cache storage unit HS1, then the controller 403 returns to the start without modifying the bit map. If the numbers are the same, then the bit map stored in the header of the entry associated with that sequence number must be updated to reset the bit associated with the entry to indicate that the entry is invalid (STEP 542). The controller 403 then returns to the start after invalidating the bit map in the copyback cache storage unit HS1. The bit map only needs to be updated when no other entry was made to the copyback cache storage trait between STEP 530 and STEP 538. Therefore, the fact that a second write is required to update the bit map is not very significant, since the fact that no other entry was made indicates that the system is not very busy. However, if the system is busy, then it is likely that another entry will occur between STEP 530 and STEP 538, and it will not be necessary to update the bit map.

In the present invention, a system parameter can be either manually set or automatically set to prevent pending data blocks from being written to a copyback cache. The present invention is automatically prevented from writing data blocks to the cache if a predetermined number of data blocks are already pending. This is preferable because the use of the copyback cache in such circumstances requires more activity than is required when data blocks are written directly into the array. Therefore, when the system is very active over a sustained period of time, the number of pending data blocks can become excessive. The benefit of the system is only obtained if there are relatively inactive periods during which the pending data blocks can be written to the array. Therefore, the present invention monitors the number of pending data blocks to ensure that the number does not become excessive. The exact number of data blocks to be considered excessive is dependent upon particular system characteristics, such as the type of I/O bus, and the seek times of the storage units.

Furthermore, the system can be manually instructed to write directly to a particular logical array LA1, LA2 (i.e., the copyback cache can be "turned off"). When the copyback cache of a logical array is turned off, new pending data blocks are no longer written to the copyback cache storage unit. As each pending data block is written to the array, the bit map in the controller buffer is updated to indicate that the entry to the copyback cache is invalid. When the last entry is invalidated, the copyback cache storage unit is returned to a "NOT USED" state (unless it is still being used by the other logical array).

During the time that the copyback cache is turned off, but entries remain valid, Reads and Writes to the pending data blocks of the valid entries are held up until the pending data blocks are written to the array.

When the copyback cache is first tumed on, the controller 403, 405 preferably searches for a storage unit in "NOT USED" state. If such a storage unit is found, then that storage unit is used as the copyback cache storage unit and the state of the storage unit is updated to "COPYBACK CACHE USED". If there are no storage units in the "NOT USED" state, then the controller 403, 405 searches for a storage unit in the "COPYBACK CACHE USED" state and determines whether that storage unit can be shared.

Operation of the Copyback Cache with Multiple Controller Upon Loss of a Copyback Cache Storage Unit

FIG. 6 is a high level flow chart of the steps taken in accordance with the present invention when a copyback cache storage unit becomes unavailable. For example, a hot spare storage unit HS1 being used as a copyback cache storage unit may become unavailable because of a failure of one of the other storage units S1-S3. In such a case, preferably, HS1 is arbitrarily selected to replace a failed storage unit S1-S3. However, in an alterative embodiment, the storage unit HS1 or HS2 containing the fewest pending data blocks may be selected to replace a failed storage unit S1-S3.

In one embodiment of the present invention, when such a failure occurs, the controller 403 associated with the storage unit HS1 that is to replace the failed storage unit determines whether any data blocks are pending (STEP 601). All pending data blocks written to the logical array LA1 associated with the copyback cache storage unit HS1 are written to the remaining operational storage units S1-S3 before any subsequent Read or Write requests to that logical array LA1 are processed (STEP 603). Once each entry in storage unit HS1 is invalid (i.e., each pending data block associated with the storage unit HS1 have been completely written to the array), the failed storage unit is rebuilt on the storage unit HS1 (STEP 605). After the failed storage unit has been rebuilt, the controller 403 determines whether there is another unused storage unit available to serve as the copyback cache storage unit for the logical array LA1 which is now without a copyback cache storage unit (STEP 607). If there is such a storage unit available, that storage unit is used (STEP 609). Otherwise, the controller 403 determines whether there is at least one copyback cache storage unit having an unused area that can be shared (STEP 611). If there is such a copyback cache storage unit, then that unit is shared, such that each logical array LA1, LA2 and associated controller is assigned a unique, non-overlapping area A1, A2 of the storage unit (STEP 613). Thus, Read and Write operations can proceed generally in the manner illustrated in the flow chart of FIG. 5. If there are no storage units to be shared, then subsequent Write requests to the affected array controller are not acknowledged to the CPU 1 until the entire Read-Modify-Write operation is completed.

For example, in the system illustrated in FIG. 4, if storage unit S1 fails, then the storage unit HS1 replaces the failed storage unit S1. Once the pending data blocks have been completely written to storage units S2 and S3, the remaining storage unit HS2 is used by both logical arrays LA1, LA2 as a copyback cache storage unit. Each of the two areas A1, A2 of the storage unit HS2 are dedicated to a corresponding logical array. Therefore, the first area A1, of the storage unit HS2 is reserved for entries that are associated with the first logical array LA1, and the second area A2 of the storage unit HS2 is reserved for entries that are associated with the second logical array LA2.

When a new storage unit is installed to replace a failed storage unit, the data from the replacement storage unit HS1 is copied to the new storage unit. The replacement storage unit HS1 is then returned to a "NOT USED" state. At that time the controller 403, 405 will return to using the storage unit HS1 as a copyback cache storage unit if there are fewer copyback cache storage units operating than there are logical arrays.

In order to ensure that the optimal number of copyback cache storage units are being used (i.e., one per logical array), when a configuration change is detected by a controller 403, 405, the controller 403, 405 turns off the copyback cache, and then turns the copyback cache back on. This causes each controller 403, 405 to search for a "NOT USED" storage unit regardless of what the controller was using as a copyback cache storage unit before the configuration change occurred.

Spread Copyback Cache Embodiment

In another embodiment of the present invention, illustrated in FIG. 7, a controller 3 spreads entries to a logical copyback cache storage unit 501 across the physical storage units that comprise the array. This embodiment operates in substantially the same way as the embodiment described in the flow chart shown in FIGS. 5A and 5B, except that the copyback cache storage unit 501 is a logical storage unit rather than a physical storage unit. The logical storage unit comprises at least one stripe of blocks. In one embodiment of the present invention, entries may be spread across the physical storage units if the storage unit being used as a copyback cache storage unit becomes unavailable. For example, a system which utilizes a hot spare as a copyback cache storage unit, as described above, may spread data across the physical storage units upon a failure of a storage unit which makes the copyback cache storage unit unavailable.

Again, although the invention has been described in terms of a sequential branching process, the invention may also be implemented in a multi-tasking system as separate tasks executing concurrently. Accordingly, the tests indicated by Steps 501, 510, and 520 in FIGS. 5A and 5B may be implicitly performed in the calling of the associated tasks for Writing and Reading data blocks, and transfer of pending blocks.

Controllers with buffer dumping capability

FIG. 8 is block diagram of a controller having buffer dumping capability in accordance with the present invention. A controller having buffer dumping capability is perferably used in a multiple controller RAID system. In accordance with the present invention in which controllers 801, 802 have buffer dumping capability, a controller 801, 802 allows fast writes to the data storage array by buffering Write data in the controller 801 and acknowledging completion of the Write operation immediately after the data has been completely written to redundant buffers 803, 804 within the controller 801. Write operations are fault tolerant (i.e., once a write operation is acknowledged by the controller 801, 802 pending Write data will not be lost due a failure of any single component within the RAID system, including the power supply). Fault tolerance is provided by redundant components, a back-up power supply, and "buffer dumping". Buffer dumping is the ability of a first controller 801, 802 to output the contents of a write buffer memory (such as a DATA-RAM 803 or a SHADOW-RAM 804) to an external device, such as a second controller 802, 801, upon detection by the second controller 802, 801 of a failure of the first controller 801, 802.

Redundant components

In accordance with one embodiment of the present invention, a RAID system preferably has two controllers 801, 802, each preferably having the following components: (1) controller processor 805; (2) DATA-RAM 803; (3) a first interface device 807; (4) a first memory interface 808, including a controller-controller interface 812; (5) a first conventional local bus 815; (6) a first controller-controller data link 823; (7) SHADOW-RAM 804; (8) a second interface device 810; (9) a second memory interface 811, including a controller-controller interface 813; (10) a second conventional local bus 817; (11) a second controller-controller data link 825; (12) an internal processor bus 806; and (13) a backup power supply 821. Since each of the array controllers 801, 802 are identical, the present description concentrates on only one such array controller. It will be understood by one of ordinary skill in the art that more than two controllers may be used to provide additional fault tolerance, and that only one such controller need have the capabilities described below. RAID systems including array controllers such as the array controller illustrated in FIG. 8 may be used with any of the above mentioned copyback cache schemes.

In a fault tolerant RAID system, a request to Write data to the array cannot be acknowledged by an array controller 801, 802 until the data is secure. Therefore, it is essential that after an acknowledgement of the Write operation has been sent to the CPU 1, no single component failure will cause data to be lost. By providing two interface devices 807, 810, two memory interfaces 808, 811, two buffer memory devices (i.e., DATA-RAM 803 and SHADOW-RAM 804), and at least two paths between each RAM 803, 804 and the data storage array, a failure of any one of these devices or paths will not prevent recovery of pending Write data. That is, a failure of one component of the RAID system will not prevent pending Write data from being read from RAM 803, 804 and stored in the appropriate storage unit within the array. In the preferred embodiment of the present invention, the DATA-RAM 803 and SHADOW-RAM 804 are each conventional dynamic random access memories (DRAM). However, in an alterative embodiment, the DATA-RAM 803 and SHADOW-RAM 804 may be any memory device which is capable of serving as a data buffer for Write data.

In the preferred embodiment, the controller processor 805 is a conventional processor (such as an LR33000 RISC processor, manufactured by LSI Logic of Milpitas, Calf.). The controller processor 805 is preferably coupled to the two redundant interface devices 807, 810 over a conventional internal processor bus 806. Each of the interface devices 807, 810 are preferably coupled to a corresponding one of the memory interfaces 808, 811 over a conventional local bus 815, 817 (such as the well known peripheral component interconnect (PCI) local bus). Each memory interface 808, 811 has an internal local bus interface adapter 831 and is directly coupled to the associated local bus 815, 817. Each local bus 815, 817 is also preferably coupled to one local bus adapter 833 for each data storage unit in the array which the array controller 801, 802 is capable of accessing. The local bus adapters 833 each communicate with the data storage units according to a peripheral bus protocol, such as the well known SCSI bus protocol. In addition, each local bus is coupled to a local bus adapter 833 dedicated to communication with the CPU 1 over a peripheral bus protocol, such as the SCSI bus protocol. It should be understood that any bus protocol may be used to communicate between any of the components of the present RAID system. That is, the present invention is independent of the protocol used on both internal local and internal peripheral buses, as well as external buses.

The redundant memory interfaces 808, 811 provide redundant apparatus for transmitting pending Write data from the RAM 803, 804 of a failed controller 801, 802 to the RAM 803, 804 within a functioning controller 802, 801, or from RAM 803, 804 of a functioning controller 801, 802 to the data storage array. Accordingly, if one of the memory interfaces 808, 811 fails, pending Write data can still be recovered from the DATA-RAM 803 or SHADOW-RAM 804.

In accordance with the preferred embodiment of the present invention, a Write request including pending Write data is transmitted across the array communications bus 835 by a CPU 1 to one of the adapters 833. The interface device 808, 811 coupled to that adapter 833 stores the pending Write data in both the DATA-RAM 803 and the SHADOW-RAM 804. Preferably, each of the adapters 833 within one controller 801, 802 are coupled to a unique data storage unit. Accordingly, only one memory interface 808, 811 can be used to convey data from the DATA-RAM 803, or SHADOW-RAM 804 to a particular data storage unit. The controller processor 805 instructs each memory interface 808, 811 to read that portion of the pending Write data that is to be stored in the data storage units accessible by the adapters 833 coupled to that memory interface 808, 811.

In an alternative embodiment, each interface device 807, 810 and associated memory interface 808, 811 is associated with one of the RAMs 803, 804, and is responsible for storing the data in that RAM 803, 804. Alternatively, one of the interface devices 807, 810 is designated as a primary interface device 807 and the other as a secondary interface device 810. The primary interface device 807 and associated primary memory interface 808 are responsible for storing data in both the DATA-RAM 803 and SHADOW-RAM 804. The secondary interface device 810 is called into service only if the primary interface device 807 fails. Such a failure may be detected in a number of ways. For example, in one embodiment of the present invention, each interface device 807, 810 is coupled to the controller processor 805 over a common internal processor bus 806. The secondary interface device 810 monitors activity on the internal processor bus 806. If the activity does not conform to a particular profile (e.g., information is not transmitted within a predetermined amount of time) then a direct query can be made as to whether the primary interface device 807 is operational. If the response (or lack thereof) indicates that the primary interface device 807 is not operational, then the primary interface device 807 is removed from service and the secondary interface device 810 takes over responsibility from the primary interface 807. In another embodiment, direct queries by each interface device of the other are made at regular intervals.

Likewise, the task of interfacing the array controller 801 with the CPU 1 and data storage units within the array can be assigned to either a primary interface device 807 or divided between the primary and secondary interface devices 807, 811. In the preferred embodiment, one of the interface devices 807 is designated as the primary interface device, and maintains responsibility for all activity. Accordingly, the other interface device 810 becomes operational only if the primary interface 810 fails.

Each memory interface 808, 811 includes a DMA controller 827, 829, a bus adapter 831, and a controller-controller data link interface 812, 813. Each memory interface 808, 811 is essentially identical. Therefore, for the sake of brevity, only one memory interface 808 is described. The bus interface adapter 831 permits the memory interface 808 to receive communications from the local bus 815. In the preferred embodiment, the interface adapter is a conventional PCI local bus adapter. The DMA controller 827 is essentially a conventional DMA controller that controls DMA operations to and from the SHADOW-RAM 804 and DATA-RAM 803. The DMA controller 827 preferably has error interrupt capability which allows an interrupt to be generated to the controller processor 805 upon a state machine error or an internal chip bus error.

In the preferred embodiment of the present invention, pending Write data can be transmitted from one array controller 801, 802 over either the primary controller-controller data link 823 or the secondary controller-controller data link 825 to another array controller 802, 801. The controller-controller interface 812 within the primary memory interface 808 is responsible for transmitting data to and from other array controllers 801, 802. If the primary memory interface 808 or the controller-controller interface 812 within the primary memory interface 808 fails, the controller-controller interface 813 within the secondary memory interface 811 takes over responsibility for transmitting pending Write data from the array controller 801, 802 to the array or the other array controller 802, 801.

In one embodiment, transfers over the primary controller-controller data link 823 are performed by the controller-controller interface 812 as serial word-length transfers (i.e., words preferably each being 32 bits) at a rate of 4,166,167 bits/sec. After removing overhead, the data rate is approximately 378 Kbytes/sec. The controller-controller interface 821 is essentially identical in operation to a conventional universal asynchronous receive/transmit (UART) device. However, in accordance with one embodiment of the present invention, the controller-controller interface 812 is a wide-format (i.e., 32 bit) device. That is, the controller-controller interface in one embodiment is designed using a 32-bit data field, rather than a more traditional 7 or 8 bit data field. The controller-controller interface 812 in accordance with one embodiment is a single, full-duplex, serial channel with a non-buffered transmitter and a single buffered receiver. The asynchronous transfer in one embodiment is formatted as follows: 1 start bit, 32 data bits, 4 embedded odd parity bits, 4 embedded even parity bits, 2 command bits, and 2 stop bits. In one embodiment, the first odd and even parity bits are transmitted immediately after the first seven bits of data. The next seven bits of data follow the first odd and even parity bits. The next seven bits of data are transmitted followed by the second odd and even parity bits. This pattern is continued until the fourth odd and even parity bits are transmitted. Transmission of both odd and even parity bits in the above sequence ensures a logic level transition at least once every 10 bits. The fourth odd and even parity bits are followed by a data/command bit and data/command check bit. The data/command and data/command check bits determine whether the data field carries a command to the DMA controller 827, 829 or data. The data/command bits are followed by the start and stop bits. The controller-controller interface 821 preferably includes standard interrupts, such as transmit error, receive error, transmit buffer empty, and receive buffer empty. These interrupts can preferably be masked. It will be clear to one of ordinary skill in the art that many other communication protocols may be used with the present invention.

In the preferred embodiment of the present invention, the conductors that couple each array controller 801, 802 to each of the data storage units of the array are redundant. Since each array controller 801, 802 must be able to address each data storage unit in the array, and further since each data storage unit has only one input port, each array controller 801, 802 is coupled at each data storage unit at a common point. In the preferred embodiment of the present invention, the array communications bus 835 is a SCSI bus. Accordingly, each array controller 801, 802 can monitor each other array controller 802, 801. Array controllers 801, 802 can also send messages to one another through the array communications bus 835.

A backup power supply 821, such as a local battery, external power supply independent of the primary power supply, or local internal independent power supply, is provided to ensure that if power fails to the array controller 801, 802, power remains available to at least the SHADOW-RAM 804 and the primary memory interface 808. In one embodiment, the backup power supply 821 may be the only source of power to the SHADOW-RAM 804 and memory interface 808. The array controller 801, 802 remains fault tolerant in such a configuration through the use of the redundant memory interface 811 and DATA-RAM 803. That is, even though the SHADOW-RAM 804 and memory interface 808 will cease functioning if the backup power supply 821 fails, all of the functions of the array controller 801, 802 are fully operational through the DATA-RAM 803 and memory interface 811 until the backup power supply 821 is made operational.

Buffer dumping

Only one controller processor 805 is provided within each array controller 801, 802. Therefore, if the controller processor 805 within an array controller 801, 802 fails, that array controller 801, 802 will not be capable of completing the Write operation to the array. However, in accordance with the present invention, the pending Write data will be available to another array controller 802, 801 through buffer dumping (i.e., DMA transfer of information from the RAM 803, 804 of the failed controller to the RAM 803, 804 of a functional controller).

In the preferred embodiment, communications between a memory interface 808, 811 of a first array controller 801, 802 and a second array controller 802, 801 required for buffer dumping can be automated. Thus, data can be read from the DATA-RAM 803 or SHADOW-RAM 804 of the first array controller 801, 802 after the controller processor 805 within the first array controller 801, 802 has failed. Accordingly, buffer dumping is possible with a minimum of a first array controller 801, 802 having an operational controller processor 805, one operational memory interface 808, 811 and one operational RAM 803, 804 and a second array controller 802, 801 having one operational memory interface 808, 811, and one operational RAM 803, 804 in an otherwise failed controller. Therefore, in accordance with the present invention, no Write data will be lost due to a failure of any single component of an array controller 801, 802 once the Write data has been received within SHADOW-RAM 804 and DATA-RAM 803 of an array controller 801, 802. Accordingly, the present invention allows a Write acknowledgment to be provided to the CPU 1 immediately after receipt of Write data in the array controller 801, 802.

Buffer dumping occurs when a functioning array controller 801, 802 detects a failure in another array controller 802, 801. In accordance with the present invention, each functioning array controller 801, 802 monitors activity on the array communications bus 815 to detect a failure of any other array controller 802, 801. Detection of failures between controllers is preferably accomplished by "keep-alive" messages. These are simple request-acknowledge operations which are passed via the adapters 833. Alternatively, keep-alive messages are provided over the controller data links 823, 825. If a "are-you-there" request is not acknowledged by one of the adapters 833, the request is retried over another adapter 833. Preferably, if no response is received over the second adapter as well, a decision is made that the other controller is inactive. In one embodiment, each controller contains a hardware "deadman timer". If the controller processor 805 stops operating, or if software "gets lost", the deadman timer will perform a hardware reset and causes the failed array controller 801 to enter "hardware isolation". The operational array controller 802 will no longer receive acknowledgements from the failed array controller 801 and the operational array controller 802 receives an "isolation interrupt" signal via a single wire from the failed array controller 801 indicating that the failed array controller 801 has gone into hardware isolation. Hardware isolation only affects the array communications busses 835 and does not isolate the controller data links 823, 825.

Normal operation of a controller capable of buffer dumping

In accordance with the present invention under normal conditions (i.e., all components of each array controller operational) Write data to be written to the RAID system is first received in an array controller 801, 802 from the CPU 1. Received Write data is concurrently and redundantly buffered in both the DATA-RAM 803 and SHADOW-RAM 804 through one of the two interface devices 807, 810 and memory interfaces 808, 811. Upon receipt of Write data from the CPU 1, the present invention stores the data in both the SHADOW-RAM 804 and DATA-RAM 803 by means of a conventional direct memory access (DMA) operation. That is, when data is received by the controller 801, 802 from the CPU 1, the Write data is coupled to a DMA controller within the primary or secondary memory interface 808, 811 together with a starting address and the number of bytes of data to be stored.

In the preferred embodiment of the present invention, only one of the memory interfaces 808, 811 responds to the incoming Write data by causing the Write data to be written in either the SHADOW-RAM 804 and DATA-RAM 803. Once the data is stored in the DATA-RAM 803 and SHADOW-RAM 804, the controller processor 805 updates a "Pending Writes" table within the DATA-RAM 803 and SHADOW-RAM 804 to reflect the fact that Write data has been received and is pending. The Pending Writes table indicates the starting address within the DATA-RAM 803 and SHADOW-RAM 804 at which the Write data was stored, the number of bytes of data in the Write data block, and that the Write data has not yet been written to the array (i.e., the Write data is pending). Once the data is read from the SHADOW-RAM 804 or DATA-RAM 803 and written to the array, the Pending Writes table is updated to indicate that block of Write data is no longer pending. Accordingly, another controller 801, 802 may read the Pending Writes table from the DATA-RAM 803 or SHADOW-RAM 804 and determine what Write data remains pending (note that in the context of the fifth embodiment of the present invention, "pending" refers to the fact that the data has been received within the controller 801, 802 and has not yet been written to the array disk drives).

Recovery operation using buffer dumping

In the preferred embodiment of the present invention, the start address and the length of the Pending Writes table are predetermined values. The present invention allows data received by a controller-controller interface 812, 813 to initiate a DMA transfer of data from the SHADOW-RAM 804. Accordingly, when an array controller 801 detects a failure of another array controller 802 the functioning array controller 801 can request that a DMA operation be performed to transfer data from the failed controller 802 beginning at the start address of the Pending Writes table and continuing for a byte count equal to the number of bytes in the Pending Writes table. Additional DMA operations can be requested which cause each pending Write data block identified in the Pending Writes table to be transferred from the failed array controller 802 to the requesting array controller 801. Accordingly, pending Write data within the failed array controller 802, 801 can be identified, read from the DATA-RAM 803 or SHADOW-RAM 804 within the failed array controller 802, 801, and written to a functioning array controller 801, 802.

When an array controller 801 requests a buffer dump from a failed array controller 802, the controller processor 805 within the requesting array controller 801, commands the primary DMA controller 827 within the requesting array controller 801 and the primary DMA controller 827 within the failed controller 802 to perform the transfer. Preferably, only the primary DMA controller 827 is commanded to the perform the transfer, unless the primary DMA controller 827 has failed. If the primary DMA controller 827 has failed, then the secondary DMA controller 829 is commanded to perform the transfer. The command to perform a transfer includes the first address within the SHADOW-RAM 804 of the failed array controller 801 and the number of bytes to be transferred to the primary DMA controller 827 of the failed controller 801. In addition to the command, the start address of the destination in the DATA-RAM 803 and SHADOW-RAM 804 of the requesting array controller 801 are provided to the primary DMA controller 827 of the requesting array controller 801.

For example, in one embodiment of the present invention, the Controller Processor 805 within the requesting array controller 801 provides the destination start address and byte count for a memory block transfer to the DMA controller 827 of the requesting array controller 801. In addition, the Controller Processor 805 within the requesting array controller 801 provides the source start address and the source byte count for a memory block transfer to the DMA controller 827 of the failed controller 802 via the data link interface 812 of the requesting controller 801, the controller data link 823, and the data link interface 812 of the failed controller 802. The controller processor 805 of the requesting controller 801 provides the source start address and source byte count to the failed controller 802 by loading a series of commands into the data link interface 812 of the requesting controller 801. This series of commands consists of single word command indicating that a DMA transfer is being requested of the failed controller 802 followed by a single word command containing the DMA source address followed by a single word command containing the DMA source byte count. These commands are sequentially loaded into the data link interface 812 of the requesting controller 801. The data link interface 812 of the failed controller 802 receives the DMA transfer command, the source start address, and the source byte count via the controller data link 823. The data link interface 812 then automatically programs the DMA controller 827 within the failed controller 802 with the source start address and source byte count. These actions cause the DMA controller 827 in the failed controller 802 to begin transferring a series of words (preferably 32 bits long) based on the source address and source byte count to the requesting controller 801 via the data link interface 812 of the failed controller 802 and the controller data link 823. The data link interface 812 of the requesting controller 801 receives the data from the controller data link 823 and the DMA controller 827 of the requesting controller 801 automatically transfers the received data to the DATA-RAM 803 of the requesting controller 801 based on the previously programmed destination address and destination byte count.

In the preferred embodiment of the present invention, the SHADOW-RAM 804 is always the preferred source for pending Write data blocks, unless the SHADOW-RAM 804 has failed. However, other schemes may be implemented in which the DATA-RAM 803 is the primary source, the source alternates between the SHADOW-RAM 804 and DATARAM 803 on each request, or any other scheme that allows pending Write data to be read without contention between the DATA-RAM 803 and SHADOW-RAM 804.

Once the request to begin a DMA operation, together with the start address and byte cotrot are transmitted from the primary controller-controller interface 812 within the requesting array controller 801 to the primary controller-controller interface 812 within the failed controller 802 over the primary controller-controller data link 823, the primary controller-controller interface 812 within the failed array controller 802 transfers the received start address and the byte count to the primary DMA controller 827. Receipt of the start address and byte count within the primary DMA controller 827 preferably causes the failed array controller 802 to begin the process of transmitting the contents of the SHADOW-RAM 804 to the requesting array controller 801. The primary DMA controller 827 accesses the SHADOW-RAM 804 at the start address and reads the data sequentially until the number of bytes requested in the byte count has been read. If an error occurs in the transmission between the failed array controller 802 and the requesting array controller 801, the controller-controller interface 812 within the requesting array controller 801 generates an interrupt to the controller processor 805. Errors selected at the failed array controller 802 cause the expected operation to cease. The requesting array controller 801 must timeout, reset the link, and retry.

In accordance with the preferred embodiment of the present invention, the first DMA request is directed to recover the Pending Writes table. Accordingly, the initial DMA request will cause the Pending Writes table within the failed array controller 802 to be transmitted from the failed controller 802 and stored in the DATA-RAM 803 and SHADOW-RAM 804 of the requesting controller 801. The DMA request is preferably handled by a primary DMA controller 827 within the primary memory interface 808 of the failed array controller 802. The secondary DMA controller 829 within the secondary memory interface 811 becomes involved only if the primary memory interface 808 has failed. Naturally, other schemes for dividing the responsibility between the primary and secondary memory interfaces 808, 811 can be used. For example, the memory interface 808, 811 which was not involved in the most recent DMA request takes responsibility for handling the next DMA request. In another embodiment, an arbitration scheme is used to determine which responds fastest to the request. It should therefore be understood that any method for arbitrating between the primary and secondary memory interfaces 808, 811 will be within the scope of the present invention.

The data that is read from the SHADOW-RAM 804 in the failed array controller 802 is then transferred back across the primary controller-controller data link 823 by the DMA controller 827 and the controller-controller data link interface 812 within the failed array controller 802. The data read from the SHADOW-RAM 804 is received by the primary controller-controller interface 812 of the requesting array controller 801. The primary controller-controller interface 812 then transfers the information to the primary DMA controller 827 within the requesting array controller 801. The primary DMA controller 827 then stores the data at the start address that was previously provided with the command.

Once the Pending Writes table is transmitted from a failed controller 801, 802 to a requesting controller 802, 801, the requesting controller 802, 801 can determine what data stored within the DATA-RAM 803 and SHADOW-RAM 804 within the failed controller 801, 802 is pending (i.e., needs to be recovered). Each pending Write data block is then requested in the same manner as described above. That is, a request is made by the array controller 801, 802 to read data from the RAM 803, 804 within the failed array controller 802, 801. The requested pending Write data is then received by the requesting array controller 801, 802 and stored in the DATA-RAM 803 and SItADOW-RAM 804 to be written to the RAID array in due course. This process is repeated for each pending Write data block within the failed array controller 801, 802. Successful completion of each DMA request by the DMA controller 827 is indicated by a status flag within the DMA controller 827. Therefore, after each attempt to read a block of data from the SHADOW-RAM 804, the status flag within the DMA controller 827 must be read to ensure that the DMA operation completed successfully.

Upon receipt within the requesting array controller 801 of all of the pending Write data blocks from the failed array controller 802, the requesting array controller 801 transmits a message to the failed array controller 802 that causes a flag to be set in the DMA controller 827 of the failed array controller 802 to indicate successful completion of the recovery process. This flag within each DMA controller 827, 829 is used by the controller processor 805 to determine upon initial application of power, whether any pending Write data blocks within the SHADOW-RAM 804 remain pending (i.e., have not yet been written to the data storage unit array).

It should be understood that buffer dumping may be performed as a time multiplexed function concurrent with other functions being performed by each array controller 801, 802. For example, new Write data can be received by the requesting array controller 801, 802 during a buffer dump by either interrupting the buffer dump until the new Write data block is completely received, or by interspersed reception of bytes of new Write data with bytes of buffer dump data. However, in the preferred embodiment of the present invention, data that is being recovered from a failed array controller 802 is completely recovered before any new data is accepted from the host. Alternatively, data that is being recovered is marked to be written to the disk array before writing any new data to the disk array which the requesting array controller 801 received from the host. This is important, since data received from the host must be written in proper sequence to ensure that data which the host expects to be present in the disk array has been written thereto.

In accordance with the present invention, the controller-controller data links 823, 825 can be used for general purpose communication,between array controllers 801, 802. For example, diagnostic information, array configuration data, or other information may be transmitted between array controllers 801, 802 without burdening any of the other communications links used by the RAID system.

Because serial dumping is critical to recovery from a failure of one of the controller processors 805, it is desirable to perform a diagnostic check of the controller-controller data links 823, 825 on a periodic basis. Since the controller-controller data links 823, 825 are robust and redundant, the likelihood that both data links 823, 825 will fail at the same time is remote. Accordingly, in the preferred embodiment of the present invention, a diagnostic check of each controller-controller data link 823-825 is performed once every 24 hours.

A number of embodiments of the present invention have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. For example, the present invention can be used in a system in which only one controller is present. In such a system, when a failure occurs which causes the controller to cease operating, a second controller can be connected as part of a "disaster recovery" procedure. The second controller takes over operation of the system and begins recovery of data in the failed controller's memory as described above. Also, in the event that each of the controllers in a multi-controller system fail, one of the failed controllers can be removed and replaced with an operational controller. The operational controller may access the data stored in the failed controllers as described above. For example, the present invention can be used with RAID 3, RAID 4, or RAID 5 systems. Furthermore, an error-correction method in addition to or in lieu of XOR-generated parity may be used for the necessary redundancy information. One such method using Reed-Solomon codes is disclosed in U.S. patent application Ser. No. 270,713, filed Nov. 14, 1988, entitled "Arrayed Disk Drive System and Method" and commonly assigned.

As another example, the copyback cache storage unit CC may be attached to the controller 3 through a dedicated bus, rather than through the preferred common I/O bus (e.g., a SCSI bus). Furthermore, any features described with respect to one embodiment may be used together in a single embodiment with features described in any other embodiment. Accordingly, even though particular combinations of features are not explicitly disclosed as being provided in one embodiment, such combinations would be within the scope of the present invention. Accordingly, it is to be understood that the invention is not to be limited by the specific illustrated embodiments, but only by the scope of the appended claims.