Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-07-24
2004-06-15
Millin, Vincent (Department: 3624)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C711S114000
Reexamination Certificate
active
06751637
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is related to the field of file systems using disk arrays for storing information.
2. Background Art
A computer system typically requires large amounts of secondary memory, such as a disk drive, to store information (e.g. data and/or application programs). Prior art computer systems often use a single “Winchester” style hard disk drive to provide permanent storage of large amounts of data. As the performance of computers and associated processors has increased, the need for disk drives of larger capacity, and capable of high speed data transfer rates, has increased. To keep pace, changes and improvements in disk drive performance have been made. For example, data and track density increases, media improvements, and a greater number of heads and disks in a single disk drive have resulted in higher data transfer rates.
A disadvantage of using a single disk drive to provide secondary storage is the expense of replacing the drive when greater capacity or performance is required. Another disadvantage is the lack of redundancy or back up to a single disk drive. When a single disk drive is damaged, inoperable, or replaced, the system is shut down.
One prior art attempt to reduce or eliminate the above disadvantages of single disk drive systems is to use a plurality of drives coupled together in parallel. Data is broken into chunks that may be accessed simultaneously from multiple drives in parallel, or sequentially from a single drive of the plurality of drives. One such system of combining disk drives in parallel is known as “redundant array of inexpensive disks” (RAID). A RAID system provides the same storage capacity as a larger single disk drive system, but at a lower cost. Similarly, high data transfer rates can be achieved due to the parallelism of the array.
RAID systems allow incremental increases in storage capacity through the addition of additional disk drives to the array. When a disk crashes in the RAID system, it may be replaced without shutting down the entire system. Data on a crashed disk may be recovered using error correction techniques.
RAID has six disk array configurations referred to as RAID level
0
through RAID level
5
. Each RAID level has advantages and disadvantages. In the present discussion, only RAID levels
4
and
5
are described. However, a detailed description of the different RAID levels is disclosed by Patterson, et al. in
A Case for Redundant Arrays of Inexpensive Disks
(RAID), ACM SIGMOD Conference, June 1998. This article is incorporated by reference herein.
FIG. 1
is a block diagram illustrating a prior art system implementing RAID level
4
. The system comprises one parity disk
112
and N data disks
114
-
118
coupled to a computer system, or host computer, by communication channel
130
. In the example, data is stored on each hard disk in 4 KByte blocks or segments. Disk
112
is the Parity disk for the system, while disks
114
-
118
are Data disks
0
through N−1. RAID level
4
uses disk striping that distributes blocks of data across all the disks in an array as shown in FIG.
1
. This system places the first block on the first drive and cycles through the other N−1 drives in sequential order. RAID level
4
uses an extra drive for parity that includes error-correcting information for each group of data blocks referred to as a stripe. Disk striping as shown in
FIG. 1
allows the system to read or write large amounts of data at once. One segment of each drive can be read at the same time, resulting in faster data accesses for large files.
In a RAID level
4
system, files comprising a plurality of blocks are stored on the N data disks
114
-
118
in a “stripe.” A stripe is a group of data blocks wherein each block is stored on a separate disk of the N disks. In
FIG. 1
, fast and second stripes
140
and
142
are indicated by dotted lines. The first stripe
140
comprises Parity
0
block and data blocks
0
to N−1. In the example shown, a first data block
0
is stored on disk
114
of the N disk array. The second data block
1
is stored on disk
116
, and so on. Finally, data block N−1 is stored on disk
118
. Parity is computed for stripe
140
, using techniques well-known to a person skilled in the art, and is stored as Parity block
0
on disk
112
. Similarly, stripe
142
comprising N−1 data blocks is stored as data block N on disk
114
, data block N+1 on disk
116
, and data block
2
N−1 on disk
118
. Parity is computed for stripe
142
and stored as parity block
1
on disk
112
.
As shown in
FIG. 1
, RAID level
4
adds an extra parity disk drive containing error-correcting information for each stripe in the system. If an error occurs in the system, the RAID array must use all of the drives in the array to correct the error in the system. Since a single drive usually needs to be accessed at one time, RAID level
4
performs well for reading small pieces of data. A RAID level
4
array reads the data it needs with the exception of an error. However, a RAID level
4
array always ties up the dedicated parity drive when it needs to write data into the array.
RAID level
5
array systems use parity as do RAID level
4
systems. However, it does not keep all of the parity sectors on a single drive. RAID level
5
rotates the position of the parity blocks through the available disks in the disk array of N+1 disks. Thus, RAID level
5
systems improve on RAID
4
performance by spreading party data across the N+1 disk drives in rotation, one block at a time. For the first set of blocks, the parity block might be stored on the first drive. For the second set of blocks, a RAID level
5
system would be stored on the second disk drive. This is repeated so that each set has a parity block, but not all of the parity information is stored on a single disk drive. Like a RAID level
4
array, a RAID level
5
array just reads the data it needs, barring an error. In RAID level
5
systems, because no single disk holds all of the parity information for a group of blocks, it is often possible to write to several different drives in the array at one instant. Thus, both reads and writes are performed more quickly on RAID level
5
systems than RAID
4
array.
FIG. 2
is a block diagram illustrating a prior art system implementing RAID level
5
. The system comprises N+1 disks
218
coupled to a computer system or host computer
120
by communication channel
130
. In stripe
240
, parity block
0
is stored on the first disk
212
. Data block
0
is stored on the second disk
214
, data block
1
is stored on the third disk
216
, and so on. Finally, data block N−1 is stored on disk
218
. In stripe
212
, data block N is stored on the first disk
212
. The second parity block
1
is stored on the second disk
214
. Data block N+1 is stored on disk
216
, and so on. Finally, data block
2
N−1 is stored on disk
218
. In M-
1
stripe
244
, data block MN-N is stored on the first disk
212
. Data block MN-N+1 is stored on the second disk
214
. Data block MN-N+2 is stored on the third disk
216
, and so on. Finally, parity block M-
1
is stored on the nth disk
218
. Thus,
FIG. 2
illustrates that RAID level
5
systems store the same parity information as RAID level
4
systems, however, RAID level
5
systems rotate the positions of the parity blocks through the available disks
212
-
218
.
In RAID level
5
, parity is distributed across the array of disks. This leads to multiple seeks across the disk. It also inhibits simple increases to the size of the RAID array since a fixed number of disks must be added to the system due to parity requirements.
A prior art file system operating on top of a RAID subsystem, tends to treat the RAID array as a large collection of blocks wherein each block is numbered sequentially across the RAID array. The data blocks of a file are then scattered across the data disks to fill each stripe as fully as possible, thereby placing each data block i
Hitz David
Lau James
Malcolm Michael
Rakitzis Byron
Colbert Ella
Millin Vincent
Network Appliance Inc.
Swernofsky Law Group PC
LandOfFree
Allocating files in a file system integrated with a raid... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Allocating files in a file system integrated with a raid..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Allocating files in a file system integrated with a raid... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3347895