Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-04-04
2002-04-09
Peikari, B. James (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C713S002000
Reexamination Certificate
active
06370616
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to multiple data drive recovery in connection with RAID architectures, and more particularly to a memory interface controller for DATUM RAID operations with a DATUM multiplier.
2. Description of the Related Art
Due to the increasing importance of business-critical data to many companies, fault tolerance is often a priority for network storage systems. Fault tolerance, in the context of a disk array subsystem, is the ability of a disk array to continue to perform its functions even when one or more disks have failed. Parity RAID and declustering architectures are network storage solutions commonly utilized to provide fault tolerance against a single disk failure. RAID, which stands for Redundant Array of Inexpensive Disks, relates to the concept of using multiple inexpensive disks as one unit in the place of a single large disk, for improved storage reliability and system performance. This idea, which is now the industry standard, was introduced in a December 1987 article entitled“A Case for Redundant Arrays of Inexpensive Disks (RAID)” by D. Patterson, G. Gibson, and R. H. Katz.
To date, a variety of RAID architectures (industry and proprietary) have been utilized for network storage. RAID
5
, which utilizes parity information to provide redundancy and fault tolerance, is one example. RAID
5
architecture uses data striping to spread or interleave user data and redundancy information (e.g., parity) across all the disks in an array. Striping generally refers to spreading data evenly over multiple disks. In other words, a segmented data block is broken into segments of a unit length and sequential segments are written to sequential disk drives. The combination of corresponding sequential data segments across each of the disks is referred to as a stripe. In the event of a failed disk, the parity information allows for recovery or reconstruction of the data of the failed disk. Parity declustering is the uniform distribution of user data and parity data over a disk array where each stripe uses a subset of the disks.
In contrast to parity declustering and conventional RAID architectures, certain disk array architectures mask multiple simultaneous disk failures. One advantage of such architectures is handling of latent sector errors. A sector error can be discovered when an array has already suffered a failure. Another advantage of architectures capable of tolerating multiple concurrent failures is handling of communication failures since communication failures can render disks inaccessible. DATUM, which stands for Disk Arrays with optimal storage, Uniform declustering and Multiple-failure tolerance, is an example of an array architecture for masking or tolerating multiple disk failures in disk arrays. In terms of uniform declustering, the architecture basically provides an array layout of user data and redundancy data which distributes redundancy data evenly or uniformly among disks in the array. Most declustered disk array layouts that can tolerate a single failure can be characterized by certain desirable properties. For example, to recover from a single disk crash, no two units of the same stripe are matched to the same disk. Another desirable property is distributed parity, whereby all disks have the same number of parity or check units mapped to them. A further desirable property, termed distributed reconstruction, involves providing a constant number of stripes with units mapped to both disks for every pair of disks.
In terms of optimal storage, DATUM uses a theoretical minimum amount of storage space for storing redundancy data in the array. DATUM employs an information dispersal algorithm (IDA) to uniformly distribute redundancy data on all the disks. The IDA algorithm encodes a sequence E=(d
1
, d
2
, . . . , d
m
) of m integers into a sequence of m+f integers (e
1
, e
2
, . . . , e
m
, e
m+1
, . . . , e
m+f
) in such a way that any m of the m+f integers suffice to recover a sequence F. The sequence F represents m equal-sized portions of user or client data, and m+f values represents encoded data including redundancy data. The transformation of user data into encoded data by the IDA algorithm can be represented in the form of a m×(m+j) matrix T (i.e., a matrix having m linear independent columns and m+f rows). Both user data and redundancy data are organized in terms of striping units. Disk space is logically structured into striping units, where each striping unit has a fixed number of sectors. A stripe consists of a fixed number of user data stripe units and a number of redundant stripe units. Different striping units of the same stripe are mapped to different disks. In other words, units of the same strip are not stored in the same disk. Any data stripe can be reconstructed if m or more disks are correct; that is, if or fewer disks have failed. DATUM thus uses only the theoretical minimum amount of disk space to store each stripe so that its contents are recoverable even if stripe units are missing.
Aside from storage space, DATUM is also optimal with respect to write overhead. That is, DATUM performs the minimum number of disk accesses to implement small writes. A small write occurs when a single stripe unit is written by a client application. A small write for a parity redundancy RAID architecture has generally reduced disk array performance. To implement a small write with DATUM, it has been necessary to (i) read the old values of the data unit being written and the f redundant units, (ii) recompute the check stripe unit values, and (iii) write the new data stripe value as well as the f check stripe units. Since it has not been possible to write less than f +1 stripe units if the array is to tolerate up to f failures, DATUM performs the optimal number f +1 disk writes per small write operation.
DATUM is considered the first known technique for tolerating an arbitrary number of failures that is optimal with respect to both storage space and write overhead, and that distributes redundant data uniformly by using a set of layout functions that can be evaluated efficiently with very low memory requirements. With DATUM, the size of a redundant unit is independent of the number of units per stripe. Further details regarding DATUM can be found in an article entitled“Tolerating Multiple Failures in RAID Architectures with Optimal Storage and Uniform Declustering” by Guillermo A. Alvarez, Walter A. Burkhard and Flaviu Cristian, Department of Computer Science and Engineering, University of California, San Diego, which is incorporated herein by reference as if set forth in its entirety.
SUMMARY OF THE INVENTION
Briefly, a memory interface controller employs a DATUM multiplier within a destination address to perform DATUM RAID operations. If destination data is in an XOR memory address space, then the multiplier can indicate to multiply source data by the multiplier and XOR that resulting data with the destination data. The DATUM multiplier can be read in response to detection of a memory command.
The multiplier alternatively can be used in connection with an input/output bus write command to write source data from the input/output address space to an XOR memory address space. In response to such a write command, the input/output bus data in the input/output address space is multiplied by the multiplier; that resulting data is XORed with the destination data in the XOR memory address space. The multiplier in this case can be within an input/output bus address associated with the input/output bus data.
REFERENCES:
patent: 4763330 (1988-08-01), Shimizu
patent: 5206943 (1993-04-01), Callison et al.
patent: 5408644 (1995-04-01), Schneider et al.
patent: 5737744 (1998-04-01), Callison et al.
patent: 5742752 (1998-04-01), DeKoning
patent: 5896493 (1999-04-01), Rao
patent: 5950225 (1999-09-01), Kleiman
patent: 6070182 (2000-05-01), Rao et al.
patent: 6112255 (2000-08-01), Dunn et al.
patent: 6138125 (2000-10-01), DeMoss
patent: 61450
Brinkman Hubert
Callison Ryan A.
Chang Albert H.
Garza Christopher
Akin Gump Strauss Hauer & Feld & LLP
Compaq Computer Corporation
Peikari B. James
LandOfFree
Memory interface controller for datum raid operations with a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory interface controller for datum raid operations with a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory interface controller for datum raid operations with a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2892321