Patent Publication Number: US-8112679-B2

Title: Data reliability bit storage qualifier and logical unit metadata

Description:
RELATED APPLICATIONS 
     This is a continuation application that claims the benefit of the earlier filing date of application Ser. No. 10/669,196. 
    
    
     FIELD 
     The present embodiments relate generally to storage systems. In particular, the present embodiments relate to RAID storage systems. 
     BACKGROUND 
     Disc drives are typically used in a stand-alone fashion, such as in a personal computer (PC) configuration where a single disc drive is utilized as the primary data storage peripheral. However, in applications requiring vast amounts of data storage capacity, data reliability or high input/output (I/O) bandwidth, a plurality of drives can be arranged into a multi-drive array, sometimes referred to as RAID (“Redundant Array of Inexpensive (or Independent) Discs”). 
     One impetus behind the development of such multi-drive arrays is the disparity between central processing unit (CPU) speeds and disc drive I/O speeds. An array of smaller, inexpensive drives functioning as a single storage device will usually provide improved operational performance over a single, expensive drive. 
     SUMMARY 
     In some embodiments a method is provided that includes the steps of storing first metadata only at the same addressable storage location of a computer readable medium as that where associated first user data is stored, and after the storing first metadata step, satisfying a read request for the first user data by retrieving the first user data from the addressable location of the computer readable medium where the first metadata is stored if the first metadata has a first value, and by reconstructing the first user data from other metadata stored at another addressable location of the computer readable medium than where the first metadata is stored if the first metadata has a second value. 
     In some embodiments an apparatus is provided that has a computer readable medium having a plurality of addressable storage locations. The apparatus further has circuitry configured to store first metadata only at the same addressable storage location as that where associated first user data is stored, and after storing the first metadata satisfying a read request for the first user data by retrieving the first user data from the addressable location where the first metadata is stored if the first metadata has a first value and by deriving the first user data from other metadata stored at another addressable location than where the first metadata is stored if the first metadata has a second value. 
     In some embodiments a method is provided that includes the steps of storing first metadata only at the same addressable storage location of a computer readable medium as that where associated first user data is stored, and after the storing first metadata step, satisfying a read request for the first user data by retrieving the first user data from the addressable location of the computer readable medium where the first metadata is stored if the first metadata has a first value, and by regenerating the first user data from other metadata stored at another addressable location of the computer readable medium than where the first metadata is stored if the first metadata has a second value. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of a storage system. 
         FIG. 2  is a block diagram of the controller shown in  FIG. 1 . 
         FIGS. 3A and 3B  show one method of storing block metadata. 
         FIGS. 4A and 4B  show illustrative embodiments of the present invention. 
         FIGS. 5A-5C  are used to explain a method of storing block metadata according to embodiments of the present invention. 
         FIGS. 6A and 6B  are used to explain another method of storing block metadata according to embodiments of the present invention. 
         FIG. 7  shows another use of embodiments of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS 
     While embodiments of the present invention are susceptible of many different forms, there are shown in the drawings and are described below in detail specific embodiments of the invention with the understanding that the present disclosure is to be considered as an exemplification of the principles of the claimed invention and is not to be limited to the specific embodiments described and shown. 
       FIG. 1  is a block diagram of a storage system  100  that can incorporate embodiments of the present invention. Storage system  100  includes a disc array  110  that has a controller  120  and a disc array group  130 . The controller  120  communicates via a bus  145  to an operating environment, such as a host computer or an area network (local, wide and storage). Controller  120  provides an array management function that includes presenting disc array group  130  as one or more virtual discs to the operating environment. Controller  120  can provide additional functions, such as capacity management, host communication, cache management and other functions common for such a storage system. Controller  120  communicates with each of discs  1 ,  2  and  3  by respective buses  125 A,  125 B and  125 C. 
       FIG. 2  shows a block diagram of controller  120 . A bus  205  couples a processor  200 , a non-volatile memory  210 , a DRAM  220  and a path controller  230 . Path controller  230  is coupled to a cache memory  240 , a device interface  250  and an operating environment interface  260  by respective buses  245 ,  255  and  265 . Device interface  250  is coupled to disc array group  130  by buses  125 A,  125 B and  125 C. Operating environment interface  260  is coupled to the operating environment by bus  145 . Controller  120  can be implemented as a single integrated circuit. One alternative is path controller  230 , device interface  250  and operating environment interface  260  are a single integrated circuit, with the other blocks being separate integrated circuits. The present embodiments are not limited to the physical implementation of controller  120 , nor are they limited to the blocks shown in  FIG. 2  or the shown interconnection. Another controller  120  or portions of it can be used in storage system  100  to, among other reasons, provide additional redundancy. 
     As background, data are stored on a storage device such as a disc drive. The data may become corrupted because of physical defects on the media of the storage device. The data may also be corrupted for other reasons beside physically defective media. One example is when the data has been lost from a “write back” cache and which data was lost is known. Another example is when data cannot be reconstructed for an inoperative disk drive because the redundant copy is on physically defective media. In these cases, the data are not good or reliable even though the media where the data resides is not defective. Therefore, Data Reliability Qualifier (DRQ) bits are used to signal storage system  100  that the data are not reliable. The storage system then can force an error message to the operating environment when the data is accessed. For purposes of the present embodiments, data is used in a general sense to include actual user, system and operating environment data; system and operating environment information not generally available to a user; programs; etc. 
       FIG. 3A  illustrates a disc array group  300  that is used in a RAID configuration. The disc array group  300  includes devices  310 ,  320 ,  330  and  340 . The devices are preferred disc drives. Devices  310 ,  320 ,  330  and  340  store data blocks  1 - 12  in a RAID 5 configuration as shown. There are four RAID slivers illustrated, with one sliver illustrated as blocks  1 ,  2 ,  3  and P 1 . The data blocks are stored in respective portions  314 ,  324 ,  334  and  344  of devices  310 ,  320 ,  330  and  340 . Portions  318 ,  328 ,  338  and  348  store metadata information about the data blocks. In particular, portions  318 ,  328 ,  338  and  348  store so-called “Forced Error” (“FE”) bits. These FE-bits are used to signify if the data in the associated data blocks on the respective drives are unreliable. For example, an FE bit in portion  318  of drive  310  is associated with data block  1 . 
       FIG. 3B  shows an FE-bit table  350  that can be stored in the controller  120 , specifically cache memory  240  in  FIG. 2 . In operation, controller  120  will access FE-bit table  350  when the operating environment requests access to the drive array group  300 . In this way, controller  120  will know whether the data in the requested data block is unreliable. If an FE bit is set for an accessed data block, controller  120  will send an error message to the operating environment. When writing new data to a block designated as having unreliable data. controller  120  clears the corresponding FE-bit in FE-bit table  350 , writes the data to the device and also writes the associated FE-bit stored on the device. However, storing the FE-bits independently on each device perturbs the use of storage space, particularly the distribution of parity and data in a RAID system with redundancy. Also, writing the data blocks and the FE-bits independently requires extra I/Os to the devices. Likewise, the FE-bit table  350  ultimately uses storage space on media or requires a system where power may never fail, and updating it independently requires additional overhead. 
     The present embodiments remove the need for the FE-bit table  350  and the portions  318 ,  328 ,  338  and  348  of devices  310 ,  320 ,  330  and  340  in  FIG. 3A . Referring to  FIG. 4A , a storage scheme of the present embodiments is illustrated. A data block  400  is shown that includes a data portion  410  and appended information  420 . An example of appended information  420  is a “Data Integrity Field” (“DIF”) that includes a “Reference Tag” (“REF TAG”), usually a “Virtual Block Address” (“VBA)” or a “Logical Block Address” (“LBA”), portion  422 , a “Metadata Tag” (“META TAG”), usually a “Logical Unit ID” with other possible “metadata” flags, portion  424 , and a check sum (“CHECK SUM”) portion  426 . Reference Tag portion  422  contains information that identifies the logical or virtual address for data portion  410 . Check sum portion  426  contains information that is used to detect errors in data portion  410 . Metadata Tag portion  424  contains additional portions  424 A and  424 B. Portion  424 B can contain information about the device, such as a device identifier (“Logical Unit ID”). Portion  424 A, according to the present embodiments, contains a “Data Reliability Qualifier” or DRQ-bit that qualifies not only the data in data portion  410  but all redundant copies of that data. The DRQ flag is logically appended to the contents of the data block and maintained with identical redundancy as the bits in the data portion. It should be viewed as a copy of “logical metadata” in the same sense as the data portion is considered a copy, with possible redundancy, of a “logical block” of a “logical unit” created using any of the techniques known as “virtualization”. Portion  424 A can contain additional metadata bits that qualify the data. Some of these bits may also be “logical metadata” and maintained with identical redundancy to the data bits. Some of these bits may be “physical metadata” and apply only to the particular copy to which they are appended. For example, portion  424 A can contain a “Parity” flag bit, set to “0” (or “FALSE”) for data blocks  400 , that indicates that the block in question contains some form of parity for other user data blocks. 
       FIG. 4B  shows a storage scheme for the parity data according to the present embodiments. A data parity block  450  includes a parity data portion  460  and appended information  470 . Appended information  470  includes a “Reference Tag” (“REF TAG”), usually a “Parity Virtual Block Address” (“Parity VBA)”; portion  472 , a “Metadata Tag” (“META TAG”), usually a “Logical Unit ID” with other possible “metadata” flags, portion  474  and a check sum (“CHECK SUM”) portion  476 . Reference Tag portion  472  when qualified by a “Parity” flag in Metadata Tag portion  474  contains information that identifies the so-called “sliver” for which parity data portion  460  provides redundancy. In particular, the “Parity Virtual Block. Address” in the DIF of the parity block may specify the “Virtual Block Address” (“VBA”) of the data block with the lowest such address of the RAID “sliver” (where address in this context means address in the virtual unit). Check sum portion  476  contains information that is used to detect errors in parity data portion  460 . Metadata Tag portion  474  contains additional portions  474 A and  474 B. Portion  474 B can contain information about the device, such as a device identifier (“Logical Unit ID”). Portion  474 A, according to the present embodiments, can contain a hit that is a function of the other DRQ-bits in portions  424 A. The DRQ parity bit can be generated by an exclusive-OR function of all the other data block DRQ-bits. To illustrate, the 1-hit portions  424 A can be exclusive-ORed together to generate the single DRQ parity bit that will saved in portion  474 A. Generally, then, the DRQ parity bit is created as a function of the other DRQ bits in portions  424 A in the same sliver. 
     As is apparent, the present embodiments have several advantages over the scheme described in  FIGS. 3A and 3B . First, the additional accessing of a device to write FE-bit information is not required since the separate FE-bit portions  318 ,  328 ,  338  and  348  are eliminated. Furthermore, the need to store the FE-bit table is eliminated. Since the FE-bit table maintenance can consume a substantial amount of processing overhead, such elimination will save critical path CPU cycles. Also, considering that the DRQ bit is automatically retrieved when the data is, there is no real performance degradation to check for it being set, which it usually is not. 
     One use of the present embodiments will be described with reference to  FIGS. 5A-5C . In  FIG. 5A , data block  10  is illustrated as unreliable. According to the present embodiments, the associated DRQ bit is set and exclusive-ORed with the other DRQ bits stored in portions  424 A and stored in portion  474 A of the parity block P 4  stored on device  510 . When the data block  10  is subsequently read, the DRQ bit set in portion  424 A can be used to indicate its unreliability. Any attempt to reconstruct data block  10  will also reconstruct the DRQ bit in portion  424 A since the DRQ parity bit in portion  474 A along with the DRQ bits in the other data blocks  424 A allows this reconstruction using the standard exclusive-OR mechanism. 
       FIG. 5B  shows the situation where device  520  that stores block  10  is “missing.” In that case, a regeneration of data block  10  can be performed but the fact the data is unreliable will be retained via the regeneration of the associated DRQ bit because the associated DRQ parity bit information in portion  474 A of the parity block P 4  when combined with the DRQ bits of the other data block portions  424  indicates the data of data block  10  is unreliable. That is, the regenerated DRQ bit for data block  10  will be “1” (or “TRUE”). 
       FIG. 5C  shows another situation in which the present embodiments are particularly useful. In that figure, data block  10  is shown as unreliable as well as “missing” (as are all blocks on device  520 ) and data block  12  is also shown as unreliable. If an attempt to regenerate data block  10  is made, the regeneration will succeed but the regenerated data will still be shown as unreliable because the parity DRQ bit in portion  474 A of parity data block P 4  when combined with other DRQ bits in portions  424 A including the DRQ bit in data block  12  showing it as unreliable will produce a DRQ bit for data block  10  that is “1” (“TRUE”). Like data block  10 , the DRQ bit associated with data block  12  is saved to portion  424 A of data block  12  and combined with the other DRQ bits for data block portions  424  to produce the parity DRQ bit in portion  474 A of parity data block P 4 . 
     Another use of the present embodiments will be explained with reference to  FIGS. 6A and 6B .  FIG. 6A  exemplifies when a device  620  is inoperative or “missing” in a disk array group  600 . If a read request is made that resolves to device  620 , the storage system controller receives data blocks P 4 ,  11  and  12  from respective devices  610 ,  630  and  640 . The controller will perform error detection of each block to ensure that the data is “good” (reliable from the point of view of the drive). If the data is “good”, the storage system controller will exclusive-OR the parity data P 4  in device  610  with data blocks  11  and  12  in respective devices  630  and  640 . The result will be the regeneration of data block  10  that was stored on device  620 . For a write to inoperative device  620 , data blocks  11  and  12  in respective devices  630  and  640  will be exclusive-ORed with the new data. The result is new parity data that will be saved in the location of parity data block P 4  in device  610 . The new parity data block will have associated information data that includes a parity DRQ bit that is the exclusive-OR of the DRQ bits associated with data blocks  11  and  12  and the DRQ bit for data block  10  itself, which may or may not be “0” at the discretion of the issuer of the write. 
       FIG. 6B  shows when device  620  is inoperative and data block  12  of device  640  is unreliable. As described above, if a read request is made that accesses inoperative device  620 , the storage system controller receives data blocks P 4 ,  11  and  12  from respective devices  610 ,  630  and  640 . The controller will perform error detection of each block to ensure that the data is “good”. If any of the data is not “good”, then the controller informs the host environment that the read cannot be performed. Otherwise, the data block  10  is regenerated as well as its associated DRQ bit. If the regenerated DRQ bit indicates the data is reliable, then the read can succeed. The use of the data in data block  12  for regeneration is independent of the quality of that data at the “logical block” level. If the device declares it as being “good”, then it can be used for regeneration as shown in this case. 
     With further reference to  FIG. 6B , writing data will be explained. In the case where data is to be written to block  10  of missing device  620  and block  12  of device  640  is unreadable (not “good”), the data in block  10  cannot be “stored in the parity data” in block P 4  of device  610  because block  12  is unreadable. That is, the data in block  10  would normally be “stored” by generating a new parity block that is the exclusive-OR of the data in block  10  that is being written and the data in blocks  11  and  12 . Normally, this situation results in a block that cannot be written. The data in block  12 , however, can be made “good” by writing it with either “best guess” data or some pattern. The DRQ bit in the associated information data for block  12  will be set to “1” to remember that the data in block  12  is “unreliable”. Now the data in block  10  can be “stored in the parity” because the data in block  12  has been “made good.” The parity DRQ bit associated with parity block P 4  will be generated using exclusive-OR from the new DRQ bit for data block  10 , the existing DRQ bit for data block  11  and the set DRQ bit that represents the data in block  12  as unreliable. 
       FIG. 7  shows another use of the present embodiments. Shown is an array  700  that includes devices  710 ,  720 ,  730  and  740  configured as RAID 0. In other words, the data is striped but there is no parity. As such, the data is not recoverable. In the case where data block  14  (shown as the striped-out data block to in device  720 ) is unreadable (not “good”), the data block is made readable again by either writing a “best guess” of the data in data block  14 , or a pattern. Such a pattern can be all zeros. However, the data in data block  14  cannot be trusted and is, therefore, “unreliable.” So the associated DRQ bit is set to indicate that the data in data block  14  is not trustworthy. The “Data Reliability Qualifier” should be understood as “logical metadata” associated with “logical blocks” even for RAID-0, where there is no redundancy. 
     In another use of the present embodiments, when the controller receives a write long command from the host, the data does not pass through to a drive in the array. Instead, the command is converted to a regular write command, and the ‘extra’ bytes (one or two, depending upon what is supported) are stripped off. The extra bytes are treated in a binary fashion—if they are zero, the DRQ bit is assumed a “0”. If they are non-zero, the DRQ bit is assumed “1” or set. Preferably, there is no effect on the actual sector ECC in this implementation. 
     Present embodiments eliminate separate FE bit table lookup and I/Os to determine the reliability of a particular piece of data by embedding the DRQ information with the data. The equivalent to the FE bit table information exists, but in a different form—it is distributed or embedded with the data, and its redundancy and distribution is the same as that of the data. This allows the minimization of the performance overhead associated with determining the data reliability. It also allows elimination of the storage mapping complexity (both on disk and in controller memory) associated with a separate FE bit table when compared to other DIF-enabled systems. The DRQ bit has the same redundancy as the data, achieved by using the same parity algorithm on the DRQ hit as on the data. 
     Several variations and modifications exist for the present embodiments. Although the preferred embodiments described herein are directed to a disk RAID storage system, it will be appreciated by those skilled in the art that the teachings of the present embodiments can be applied to other systems. For example, the storage devices can be magnetic, optical, tape, solid state, a SAN or JBOD, or a combination of two or more of them. Further, the present embodiments may be implemented in hardware, software or a combination of both. Also, a storage area includes without limitation a portion of a single surface of a storage medium, a surface of the storage medium, the entire storage medium, a device containing at least one storage medium and a system containing at least one device. 
     And although the DRQ bits are disclosed as part of a “Data Integrity Field,” the DRQ bit does not have to be contained like that. The DRQ bit can simply be appended (or prepended) to the data, or part of other data appended to the data. This eliminates the case where the data reliability information becomes unavailable, while the data is available (which could certainly happen with a separate FE-bit table), thus having no way to figure out which data is reliable and which is not. With these embodiments, if the data is available, then the data reliability information is available, and the data&#39;s reliability can always be determined. Generally, the present embodiments accompany data with reliability information, such as (without limitation) appending or embedding. The mechanism proposed for the specific “Data Reliability Qualifier” (DRQ) can be extended to incorporate other “logical metadata” which qualifies the data. 
     It is to be understood that even though numerous characteristics and advantages of various embodiments of the invention have been set forth in the foregoing description, together with details of the structure and function of various embodiments of the invention, this disclosure is illustrative only, and changes may be made in detail, especially in matters of structure and arrangement of parts and values for the described variables, within the principles of the present embodiments to the full extent indicated by the broad general meaning of the terms in which the appended claims are expressed.