Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-03-14
2003-05-20
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S112000, C714S006130, C714S052000, C714S770000, C714S784000
Reexamination Certificate
active
06567891
ABSTRACT:
RELATED PATENT APPLICATIONS
This patent application is related to U.S. patent applications with Ser. Nos. 09/808,713, filed Mar. 14, 2001; 09/808,910 filed Mar. 14, 2001; 09/808,711 filed Mar. 14, 2001, each of which is incorporated herein by reference and for all purposes.
TECHNICAL FIELD
This invention relates to parity operations in redundant disk drive systems, and particularly to improved stripe-based processing methods and arrangements in such systems.
BACKGROUND
Modem, high-capacity data storage systems often utilize a plurality of physical disk drives for redundant storage of data. Such arrangements speed-up data access and protect against data loss that might result from the failure of any single disk.
There are two common methods of storing redundant data. According to the first or “mirror” method, data is duplicated and stored on two separate areas of the storage system. In a disk array, for example, identical data is stored on two separate disks. This method has the advantages of high performance and high data availability. However, the mirror method is also relatively expensive, effectively doubling the cost of storing data.
In the second or “parity” method, a portion of the storage area is used to store redundant data, but the size of the redundant storage area is less than the remaining storage space used to store the original data. For example, in a disk array having six disks, five disks might be used to store data, with the sixth disk being dedicated to storing redundant data, which is referred to as “parity” data. The parity data allows reconstruction of the data from one data disk, using the parity data in conjunction with the data from surviving disks. The parity method is advantageous because it is less costly than the mirror method, but it also has lower performance and availability characteristics in comparison to the mirror method.
This invention involves storing redundant data according to parity techniques. In conventional disk arrays utilizing parity storage, the space on the storage disks are configured into multiple storage stripes, where each storage stripe extends across the storage disks. Each stripe consists of multiple segments of storage space, where each segment is that portion of the stripe that resides on a single storage disk of the disk array.
FIG. 1
illustrates a conventional disk array
12
having six storage disks
13
. In this simplified example, there are five storage stripes extending across the storage disks.
FIG. 1
highlights data and storage segments of a single one of these five stripes. Data segments of the indicated stripe are indicated by cross-hatching. The corresponding parity segment of this same stripe is illustrated in solid black. Generally, of the six segments comprising any given stripe, five of the segments are data segments and the sixth segment is a parity segment.
This type of parity storage is referred to as 5+1 parity storage, indicating that there are five data segments for every single parity segment. This scheme is more generally referred to as N+1 grouping, where N is the actual number of data segments in a data stripe.
N+1 redundancy grouping such as illustrated in
FIG. 1
protects against the loss of any single physical storage device. If the storage device fails, its data can be reconstructed from the surviving data. The calculations performed to recover the data are straightforward, and are well known. Generally, a single parity segment P is calculated from data segments D
0
through D
N−1
in accordance with the following equation:
P=x
0
+x
1
+x
2
+x
N−
1
where x
0
through x
N−1
correspond to the data from data segments D
0
through D
N−1
. After the loss of any single data segment, its data can be recovered through a straightforward variation of the same equation.
In many systems, however, it is becoming important to protect against the loss of more than a single storage device. Thus, it is becoming necessary to implement N+2 grouping in redundant storage systems.
While N+2 redundancy grouping enhances data protection, it also involves more complex calculations-both in initially calculating parity segments and in reconstructing any lost data segments.
A general form of the N+2 parity computation is as follows:
P=p
0
x
0
+p
1
x
1
+p
2
x
2
+p
N−1
x
N−1
Q=q
0
x
0
+q
1
x
1
+q
2
x
2
+q
N−1
x
N−1
where:
P is the value of a first parity segment;
Q is the value of a second parity segment;
x
0
through x
N−1
are the values of the data segments
p
0
through p
N−1
and q
0
through q
N−1
are constant coefficients that are particular to a given parity scheme.
These equations form a two-equation system that, by the rules of linear algebra, can potentially solve for any two unknowns x
a
through X
b
, which represent the data from a single stripe of any two failed storage devices. One requirement is that the two sets of coefficients p
i
and q
i
be linearly independent. This requirement is met, for example, if p
0
=1, p
1
=1, p
2
=1; etc.; and q
0
=1, q
1
=2, q
2
=3; etc. Other examples are also possible.
The mathematics of N+2 parity are well known and are not the primary subject of this description. However, it is apparent from the brief description given above that N+2 parity computations are significantly more complex than N+1 parity computations. In actual implementations of N+2 disk arrays, this complexity threatens to limit the data throughput of storage device controllers and, consequently, of the overall disk array.
Of particular interest herein, is the need to identify potential performance bottlenecks in the processing of stripe-based data and provide solutions that significantly increase the throughput of the overall system.
SUMMARY
In accordance with certain aspects of the present invention, a performance bottleneck has been identified as occurring during conventional processing of stripe-based data. As such, improved methods and arrangements are provided to address the bottleneck and help increase the throughput of the overall stripe-based data processing system.
The above stated needs and others may be met, for example, by a method that includes selectively reading data segments or strips within a stripe-based data storage array, and while reading subsequent data strips, calculating at least one intermediate parity value based on previously read data strips and temporarily storing this latest intermediate parity value in a local buffer. Upon determining a final parity value for the strip, writing the final parity value to an external memory. Then, upon determining a final parity value for an entire stripe, writing the final parity value to a corresponding parity value data segment in on an applicable disk drive. The method can be employed in a variety of stripe-based data storage arrays. By way of example, the method can be employed in an N+2 disk array to determine P and Q parity values. One of the benefits to this method is that each data segment need only be read from the disk one time, and further, only the final calculated value of each parity value is written to the applicable disks. Hence, the overall system performance is increased by eliminating the need to reread data segments and write/rewrite intermediate parity values to the external memory.
REFERENCES:
patent: 5134619 (1992-07-01), Henson et al.
patent: 5734859 (1998-03-01), Yorimitsu et al.
patent: 5954822 (1999-09-01), Yashiro et al.
patent: 6148430 (2000-11-01), Weng
patent: 6151641 (2000-11-01), Herbert
patent: 6341342 (2002-01-01), Thompson et al.
Oldfield Barry J
Rust Robert A.
Dinh Ngoc V
Hewlett--Packard Development Company, L.P.
Yoo Do Hyun
LandOfFree
Methods and arrangements for improved stripe-based processing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and arrangements for improved stripe-based processing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and arrangements for improved stripe-based processing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3072311