Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-07-17
2001-04-24
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S801000
Reexamination Certificate
active
06223323
ABSTRACT:
The present invention relates to disk array storage devices for computer systems and, more particularly, to an improved method for generating parity information in a disk array storage system.
BACKGROUND OF THE INVENTION
A disk array or RAID (Redundant Array of Inexpensive Disks) storage system comprises two or more hard disk drives, such as the commodity 3½ inch disk drives currently used in personal computers and workstations, functioning together as a single storage system. Although disk array products have been available for several years, significant improvements in the reliability and performance of small disk drives and a decline in the cost of such drives, together with end user requirements for increased system storage capacity, faster access speeds, improved reliability, and greater resistance to errors have resulted in enhanced interest in RAID systems.
Several disk array design alternatives were first described in an article titled “A Case for Redundant Arrays of Inexpensive Disks (RAID)” by David A. Patterson, Garth Gibson and Randy H. Katz; University of California Report No. UCB/CSD 87/391, December 1987. This article discusses disk arrays and the improvements in performance, reliability, power consumption and scalability that disk arrays provide in comparison to single large magnetic disks. Five disk array arrangements, referred to as RAID levels, are described. The simplest array, a RAID level 1 system, comprises one or more disks for storing data and an equal number of additional “mirror” disks for storing copies of the information written to the data disks. The remaining RAID levels, identified as RAID level 2, 3, 4 and 5 systems, segment the data into portions for storage across several data disks. One or more additional disks are utilized to store error check or parity information.
In 1993, these RAID levels were formalized in the first edition of the RAIDBook, published by the RAID Advisory Board, an association of manufacturers and consumers of disk array storage systems. In addition to the five RAID levels described by Patterson et al., the RAID Advisory Board now recognizes four additional RAID levels, including RAID level 0, RAID level 6, RAID level 10 and RAID level 53.
In order to coordinate the operation of the multitude of disk or tape drives within an array to perform read and write functions, parity generation and checking, and data restoration and reconstruction, complex storage management techniques are required. Array operation can be managed through software routines executed by the host computer system, i.e., a software array architecture, or by a dedicated hardware controller constructed to control array operations.
A RAID level 4 disk array is comprised of N+1 disks wherein N disks are used to store data, and the additional disk is utilized to store parity information. Data to be saved is divided into portions consisting of one or many blocks of data for storage among the disks. The corresponding parity information, which can be calculated by performing a bit-wise exclusive-OR of corresponding portions of the data stored across the N data drives, is written to the dedicated parity disk. The parity disk is used to reconstruct information in the event of a disk failure. Writes typically require access to two disks, i.e., one of the N data disks and the parity disk, as will be discussed in greater detail below. Read operations typically need only access a single one of the N data disks, unless the data to be read exceeds the block length stored on each disk.
A RAID level 4 system including five data and parity disk drives, DRIVE A through DRIVE E is illustrated in FIG.
1
. An array controller, not shown, coordinates the transfer of data between a host system and the array disk drives. The controller also calculates and checks parity information. Data blocks A
0
through D
4
and parity blocks P
0
through P
4
illustrate the manner in which data and parity is stored on the five array drives. Data blocks A
0
through D
4
are also identified as blocks
0
through
19
.
RAID level 5 disk arrays are similar to RAID level 4 systems except that parity information, in addition to the data, is distributed across the N+1 disks in each group. Each one of the N+1 disks within the array includes some blocks for storing data and some blocks for storing parity information. Where parity information is stored is controlled by an algorithm implemented by the user. As in RAID level 4 systems, RAID level 5 writes typically require access to two disks; however, no longer does every write to the array require access to the same dedicated parity disk, as in RAID level 4 systems. This feature provides the opportunity to perform concurrent write operations.
A RAID level 5 system including five data and parity disk drives, DRIVE A through DRIVE E is illustrated in FIG.
3
. An array controller, not shown, coordinates the transfer of data between a host system and the array disk drives. The controller also calculates and checks parity information. Data blocks A
0
through E
4
and parity blocks P
0
through P
4
illustrate the manner in which data and parity is stored on the five array drives. Data blocks A
0
through E
4
are also identified as blocks
0
through
19
.
The relationship between the parity and data blocks in both the RAID level 4 and 5 systems described above, and illustrated in
FIGS. 1 and 3
, respectively, is as follows:
PARITY P
0
=(BLOCK
0
)⊕(BLOCK
1
)⊕(BLOCK
2
)⊕(BLOCK
3
)
PARITY P
1
=(BLOCK
4
)⊕(BLOCK
5
)⊕(BLOCK
6
)⊕(BLOCK
7
)
PARITY P
2
=(BLOCK
8
)⊕(BLOCK
9
)⊕(BLOCK
10
)⊕(BLOCK
11
)
PARITY P
3
=(BLOCK
12
)⊕(BLOCK
13
)⊕(BLOCK
14
)⊕(BLOCK
15
)
As shown above, parity data can be calculated by performing a bit-wise exclusive-OR of corresponding portions of the data stored across the N data drives. However, because each parity bit is simply the exclusive-OR product of all the corresponding data bits from the data drives, new parity can be more easily determined from the old data and the old parity as well as the new data in accordance with the following equation:
new parity=old data⊕new data⊕old parity.
Although the parity calculation for RAID levels 4 or 5 shown in the above equation is much simpler than performing a bit-wise exclusive-OR of corresponding portions of the data stored across all of the data drives, a typical RAID level 4 or 5 write operation will require a minimum of two disk reads and two disk writes, in addition to the step of calculating the new parity information. This operation is referred to as a read-modify-write (RMW) operation. More than two disk reads and writes are required for data write operations involving more than one data block. Each individual disk read operation involves a seek and rotation to the appropriate disk track and sector to be read. The seek time for all disks is therefore the maximum of the seek times of each disk. A RAID level 4 or 5 system thus carries a significant write penalty when compared with a single disk storage device or with RAID level 1, 2 or 3 systems.
In addition to the advantages described above for RAID storage systems, i.e., increased system storage capacity, faster access speeds, improved reliability, RAID level 4 and 5 disk array systems also provide for concurrent read and write operations. These storage arrangements provide an increased transfer bandwidth for multiple block read and write operations, e.g., four consecutive blocks can be read or written concurrently, and also improves the performance of small transfer operations by allowing blocks residing on separate disk drives to be accessed in parallel.
An improved method for generating and maintaining parity information in a RAID level 4 or 5 system which reduces or eliminates the write penalty resulting from the manner in which parity information is traditionally calculated and maintained is desired.
OBJECTS OF THE INVENTION
It is therefore an object of the present inv
De'cady Albert
NCR Corporation
Stover James M.
Ton David
LandOfFree
Method for storing parity information in a disk array... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for storing parity information in a disk array..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for storing parity information in a disk array... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2504096