Abstract:
A method of efficiently preventing data loss, specifically a RAID 5 write hole, in data storage system by storing valid parity information at the storage controller level during data write operations. The method employs the use of redundant data structures that hold metadata specific to outstanding writes and parity information. The method uses the redundant data structures to recreate the write commands and data when a system failure occurs before the writes have completed.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0001]     This application claims priority under 35 USC § 119 to U.S. Provisional Application No. 60/505,020, filed Sep. 24, 2003, the entire contents of which is incorporated herein by reference. 
     
    
     FIELD OF THE INVENTION  
       [0002]     The present invention is a method of efficiently preventing data loss in a data storage system. Specifically, the invention discloses a method of protecting against a RAID 5 write hole and subsequently recovering from a failure in a networked storage system.  
       BACKGROUND OF THE INVENTION  
       [0003]     The redundant array of independent disks (RAID) configuration is designed to combine multiple inexpensive disk drives into an array to obtain performance, capacity, and reliability that exceeds that of a single large drive. The array of drives can be made to appear to the host computer as a single logical drive.  
         [0004]     There are five types of array architectures, i.e., RAID 1 through RAID 5, each providing disk fault tolerance with different compromises in features and performance. In addition to these five redundant array architectures, it has become popular to refer to a non-redundant array of disk drives as a RAID 0 array.  
         [0005]     RAIDs 2-5 employ a technique known as striping that writes a block of data across several hard disk drives. This is a method of combining multiple drives into one logical storage unit. Striping partitions the storage space of each drive into stripes, which can be as small as one sector (typically 512 bytes) or as large as several megabytes. These stripes are then interleaved in a rotating sequence, so that the combined space is composed alternately of stripes from each drive. The specific type of operating environment determines whether large or small stripes are used.  
         [0006]     Of the original five RAID types, RAID 5 has become the most popular with networked storage system integrators. It provides an excellent balance between cost and performance while providing redundant data storage. Under RAID 5, parity information is distributed across all the drives. Unlike other striped RAID architectures, RAID 5 has no dedicated parity drive; therefore, all drives contain data, and read operations can be overlapped on every drive in the array. Write operations typically access one data drive and one parity drive. However, because different records store their parity on different drives, write operations can usually be overlapped. The following is a simplified example of how RAID 5 calculates parity and restores data from a failed drive.  
         [0007]     Data reconstruction is accomplished by a RAID controller, in conjunction with array management software that examines the sum of each bit position across a slice of all the functional drives in the RAID 5 to assign an even or odd number to the missing data. The missing bit is the exclusive OR (XOR) of the other data bits in the slice including parity. This process is repeated, slice by slice, until the data is rebuilt. If a hard disk drive fails and the host calls for information on that disk, the data is built dynamically from the remaining hard disk drives and placed into memory until a replacement drive is obtained. In this manner, data loss is prevented. Consistent parity is defined as the parity as recorded on the media, and is the XOR of all the data bits as recorded on the media. If the data from one of the members becomes unavailable, that data may be reconstructed if the parity is consistent.  
         [0008]     However, if a system fails or if power is lost with multiple writes outstanding to RAID  5  hard disk drives before parity is calculated and recorded, a write hole may occur. A write hole is a state in which parity is no longer consistent and cannot be used to reconstruct the data that was in process of being stored to disk when the failure occurred. One or several writes may have been completed before the failure; however, unless all writes were completed, the parity is inconsistent. Parity is only valid when all of the data is present for its calculation. The additional loss of a drive upon system restoration compounds the problem further by creating a situation in which the data contained on the failed drive is no longer reconstructable due to inconsistent parity. In this case, both the most recent write data and the data stored on the failed device are lost.  
         [0009]     An example of a RAID 5 write hole protection scheme is identified in U.S. Pat. No. 5,744,643, entitled, “Enhanced RAID Write Hole Protection and Recovery”. The &#39;643 patent describes a method and apparatus for reconstructing data in a computer system employing a modified RAID 5 data protection scheme. The computer system includes a write back cache composed of non-volatile memory for storing writes outstanding to a device and its associated data read and for storing metadata information in the non-volatile memory. The metadata includes a first field containing the logical block number or address (LBN or LBA) of the data, a second field containing the device ID, and a third field containing the block status. From the metadata information, it is determined where the data was intended to be written when the crash occurred. An examination is made to determine whether parity is consistent across the slice; if it is not, the data in the non-volatile write back cache is used to reconstruct the write that was being performed when the crash occurred to ensure consistent parity, so that only those blocks affected by the crash have to be reconstructed.  
         [0010]     Because there are many RAID controllers available on the market, there are equally many RAID 5 write hole protection methods available. A RAID controller (or a storage controller) that includes a transaction processor may be used in conjunction with an alternative method for RAID 5 write hole protection. One transaction processor used in networked storage controllers is described in U.S. patent application Ser. No. 10/429,048, entitled “Scalable Transaction Processing Pipeline” and is hereby included by reference. The &#39;048 application describes a parallel processing system that employs data structures and specific hardware to process networked storage commands and effectively manage host access to the storage drives.  
       SUMMARY OF THE INVENTION  
       [0011]     It is therefore an object of the invention to provide a method to prevent a RAID 5 write hole in a networked storage system.  
         [0012]     It is another object of this invention to method to prevent a RAID 5 write hole while using a minimum of memory space in a transaction processing networked storage system.  
         [0013]     It is yet another object of this invention to a method to fully recover from a system failure without loss of data in a networked storage system.  
         [0014]     The present invention achieves the foregoing objective by providing a method of persistently storing new parity information in order to prevent a RAID 5 write hole.  
         [0015]     More specifically, the invention provides a method of RAID 5 write hole prevention in which a first data structure is allocated locally in memory of a master controller and a second data structure mirroring the first data structure is allocated in memory of a redundant controller. At least one partial stripe of data from the hard disk drives of the RAID system is read, the partial stripe comprising the data necessary to generate parity for a complete stripe, the parity for the stripe is generated by the master controller, and the first data structure of the master controller is mirrored to the second data structure of the redundant controller. The data and parity are then copied onto corresponding hard disk drives of said RAID, and the first and second data structures are deallocated.  
         [0016]     These and other features and advantages of the present invention will become apparent when the following description is read in conjunction with the accompanying drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0017]      FIG. 1  illustrates a storage controller architecture.  
         [0018]      FIG. 2  is a flow diagram of a method of preventing write holes in a RAID 5 architecture.  
         [0019]      FIG. 3  is a flow diagram of a method of recovering and rebuilding data after a system failure. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0020]      FIG. 1  illustrates a storage controller architecture  100  that includes a master controller  110 , a storage bus  115 , a redundant controller  120 , a storage bus  125 , a disk array  130  (RAID), an intercontroller bus  140 , a host  150 , a host bus  153 , and a host bus  157 .  
         [0021]     Disk array  130  further includes a hard disk drive  135   a , a hard disk drive  135   b , and a hard disk drive  135   n . In general, “n” is used herein to indicate an indefinite plurality, so that the number “n” referring to one component does not necessarily equal the number “n” of a different component  
         [0022]     Master controller  110  and redundant controller  120  are storage system controllers capable of managing all of the incoming, outgoing, and resident data in the architecture through specialized architectures, algorithms, and hardware. Master controller  110  and redundant controller  120  accept storage access requests from host  150  and execute storage access commands to disk array  130 . Further, master controller  110  and redundant controller  120  can communicate to each other via intercontroller bus  140 . Intercontroller bus  140  may be any type of data communication bus.  
         [0023]     Host  150  is any computational or data processing device that is capable of requesting storage access.  
         [0024]     Host bus  153  and host bus  157  may be any type of data communication bus. In alternate configurations, host bus  153  and host bus  157  may be the same connection or may be part of a switched or looped data communication protocol.  
         [0025]     Storage bus  115  and storage bus  125  may be any type of data communication bus. In alternate configurations, storage bus  115  and storage bus  125  may be part of a switched or looped communication protocol.  
         [0026]      FIG. 2  is a flow diagram of a RAID  5  write hole prevention method  200 . The description of method  200  assumes the use of multiple storage controllers as described in  FIG. 1 . Method  200  is easily applied to a single controller with cached memory; however, in a stand-alone controller configuration, the system is exposed to data loss if the stand-alone controller fails.  
         [0027]     Step  205 : Allocating Data Structure  
         [0028]     In this step, master controller  110  allocates a data structure both locally and mirrored in redundant controller  120 . Master controller  110  sets the invalid flag in its control register to indicate that the new data structures are not valid. Method  200  proceeds to step  210 .  
         [0029]     Step  210 : Reading First Partial Stripe  
         [0030]     In this step, master controller  110  reads the data to generate parity for the first stripe on hard disk drives  135  into its memory. As a result, the sectors required to generate the parity for the first stripe are resident in master controller  110  memory. This memory may be volatile, may be non-volatile, or may have a battery backup. Method  200  proceeds to step  215 .  
         [0031]     Step  215 : Reading Last Partial Stripe  
         [0032]     In this step, master controller  110  reads the data to generate parity for the last stripe into master controller  110  memory. The memory now includes all the sectors required to generate the parity for the first and last stripe. The memory also includes all the sectors required to generate parity for all middle stripes between the first and last stripe. Method  200  proceeds to step  220 .  
         [0033]     Step  220 : Generating Parity for Middle Stripes  
         [0034]     In this step, master controller  110  generates the parity for all middle stripes using the XOR function and stores the parity code in a data structure that is also in memory. Method  200  proceeds to step  225 .  
         [0035]     Step  225 : Clearing Valid Flag for Data Structure  
         [0036]     In this step, master controller  110  clears a valid flag in its control register so that, in the event of a system failure, the new data structure is not used to recover and rebuild. In that instance, the post-failure active controller rebuilds the system using the last previously valid parity from the last previously valid data structure. Method  200  proceeds to step  230 .  
         [0037]     Step  230 : Generating Parity for First and Last Partial Stripe  
         [0038]     In this step, master controller  110  performs the XOR function to generate parity for the first and last partial stripes. The parity results are also stored in the data structure. Method  200  proceeds to step  235 .  
         [0039]     Step  235 : Setting Valid Flag for Data Structure  
         [0040]     In this step, master controller  110  sets the valid flags in its control register and in the control register of redundant controller  120  indicating that, in the event of a system failure, the current data structure is valid. It also stores the valid bit, the volume and RAID group with which the data structure is associated, the Small Computer System Interface (SCSI) command data byte (CDB), the storage element number for the CDB drive write, and the number for the drive receiving that write data. All the information necessary to recover from a system failure, should a drive fail after recovery, is now persistently stored and available to rebuild the data in the drive. Method  200  proceeds to step  240 .  
         [0041]     Step  240 : Mirroring Parity for First and Last Partial Stripe  
         [0042]     In this step, master controller  110  mirrors the data structure to redundant controller  120 . The data structure includes the parity information, drives, and LBA ranges of those drives that have outstanding write commands. All of the metadata for a system rebuild is stored redundantly in this step. After mirroring the data structure, redundant controller  120  sends a status message to master controller  110  reporting that the data structure has been mirrored successfully. Method  200  proceeds to step  245 .  
         [0043]     Step  245 : Writing Dirty Data and Parity for First Partial Stripe  
         [0044]     In this step, master controller  110  initiates the process of recording the data and parity stored in memory onto corresponding hard disk drives  135  included in the first partial stripe. Method  200  proceeds to step  250 .  
         [0045]     Step  250 : Writing Data and Parity for Last Partial Stripe  
         [0046]     In this step, master controller  110  writes the data and parity stored in memory to the last partial stripe. Method  200  proceeds to step  255 .  
         [0047]     Step  255 : Writing Data and Parity for Middle Stripes  
         [0048]     In this step, master controller  110  writes the remaining data and parity to the corresponding middle stripes on their respective drives. In the event of a master controller  110  and/or a drive failure, all of the data from the middle stripes is available from redundant controller  120  memory. This data is recorded to a drive once the surviving controller and drives are available. No extra overhead is required to determine which of the outstanding writes had completed and which had not. Method  200  proceeds to step  260 .  
         [0049]     Step  260 : Deallocating Data Structure  
         [0050]     In this step, master controller  110  deallocates both the locally stored and mirrored data structure memory. Method  200  ends.  
         [0051]      FIG. 3  is a flow diagram of a method  300  of recovering and rebuilding data after a system failure.  
         [0052]     Step  310 : Locating Valid Data Structures  
         [0053]     In this step, master controller  110  or redundant controller  120  is notified that a system failure has occurred. If master controller  110  fails to come online after the system failure, redundant controller  120  assumes control of the RAID system. The controller now responsible for controlling the rebuild, referred to as the active controller, locates all the valid data structures by examining the valid bit of the data structures stored in controller memory. Method  300  proceeds to step  320 .  
         [0054]     Step  320 : Reconstructing Write Commands  
         [0055]     In this step, the active controller uses the data structure that identifies which dirty cache sectors need to be written, and the location of the stored parity information, in order to reconstruct the write data commands that may or may not have been written completely to storage devices (hard disk drives for the RAID system) prior to system failure. Method  300  proceeds to step  330 .  
         [0056]     Step  330 : Are all Drives Functional? 
         [0057]     In this decision step, the active controller determines whether all drives are functional after the system failure. If yes, method  300  proceeds to step  340 ; if no, method  300  proceeds to step  350 .  
         [0058]     Step  340 : Completing Writes to All Drives  
         [0059]     In this step, the active controller completes all the outstanding writes that were interrupted during the system failure to their respective drives. The active controller uses the reconstructed write commands and data to perform this step. Method  300  ends.  
         [0060]     Step  350 : Completing Writes to Functional Drives  
         [0061]     In this step, the active controller completes all the outstanding writes that were interrupted during the system failure to their respective drives, except for those writes outstanding to the non-functional drive(s). Method  300  proceeds to step  360 .  
         [0062]     Step  360 : Rebuilding Failed Drives  
         [0063]     In this step, the active controller finds a new drive to replace the failed drive and begins to rebuild the information from the failed drive onto the new drive. The controller uses the parity information and data from other functional drives, to accurately rebuild the failed drive. In this manner, there is no loss of data. Method  300  ends.  
         [0064]     While the invention has been described and illustrated with reference to specific exemplary embodiments, it should be understood that many modifications and substitutions can be made without departing from the spirit and scope of the invention. Accordingly, the invention is not to be considered as limited by the foregoing description but is only limited by the scope of the appended claims.