Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-10-28
2002-07-23
Verbrugge, Kevin (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
Reexamination Certificate
active
06425052
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to computer data storage systems, and more particularly to arrays of storage devices that employ mirroring and striping of data, such as certain Redundant Array of Independent Disks (RAID) systems, and to mechanisms for load balancing in such storage systems when operating in a degraded mode such as when reconstructing a failed storage device.
2. Description of the Related Art
A continuing desire exists in the computer industry to consistently improve the performance of computer systems over time. For the most part this desire has been achieved for the processing or microprocessor components of computer systems. Microprocessor performance has steadily improved over the years. However, the performance of the microprocessor or processors in a computer system is only one component of the overall performance of the computer system. For example, the computer memory system must be able to keep up with the demands of the processor or the processor will become stalled waiting for data from the memory system. Generally computer memory systems have been able to keep up with processor performance through increased capacities, lower access times, new memory architectures, caching, interleaving and other techniques.
Another critical component to the overall performance of a computer system is the I/O system performance. For most applications the performance of the mass storage system or disk storage system is the critical performance component of a computer's I/O system. For example, when an application requires access to more data or information than it has room in allocated system memory, the data may be paged in/out of disk storage to/from the system memory. Typically the computer system's operating system copies a certain number of pages from the disk storage system to main memory. When a program needs a page that is not in main memory, the operating system copies the required page into main memory and copies another page back to the disk system. Processing may be stalled while the program is waiting for the page to be copied. If storage system performance does not keep pace with performance gains in other components of a computer system, then delays in storage system accesses may overshadow performance gains elsewhere.
One method that has been employed to increase the capacity and performance of disk storage systems is to employ an array of storage devices. An example of such an array of storage devices is a Redundant Array of Independent (or Inexpensive) Disks, RAID. A RAID system improves storage performance by providing parallel data paths to read and write information over an array of disks. By reading and writing multiple disks simultaneously the storage system performance may be greatly improved. For example, an array of four disks that can be read and written simultaneously may provide a data rate almost four times that of a single disk. However, using arrays of multiple disks comes with the disadvantage of increasing failure rates. In the example of a four disk array above, the mean time between failure (MTBF) for one of the four disks of the array will be one-fourth that of a single disk. It is not uncommon for storage device arrays to include many more than four disks, shortening the mean time between failure from years to months or even weeks. RAID systems address this reliability issue by employing parity or redundancy so that data lost from a device failure may be recovered.
One common RAID technique or algorithm is referred to as RAID
1
. In a RAID
1
system all data is mirrored within the storage system. In other words, a duplicate copy of all data is maintained within the storage system. Typically, a RAID
1
system performs mirroring by copying data onto two separate disks. Thus a typical RAID
1
system requires twice the number of disks. In general, one disadvantage of RAID
1
systems is that they may not provide for load balancing over multiple disks within the system. For example, the data used by a given application may be located all on one disk of the RAID
1
system. If the bulk of storage system accesses are being generated by that one application, then the storage system load will be concentrated on a single device, thus negating the performance advantage of having an array of disks.
RAID
0
is an example of a RAID algorithm used to improve performance by attempting to balance the storage system load over as many of the disks as possible. RAID
0
implements a striped disk array in which data is broken down into blocks and each block is written to a separate disk drive. Thus technique may be referred to as striping. Typically, I/O performance is improved by spreading the I/O load across multiple drives since blocks of data will not be concentrated on any one particular drive. However, a disadvantage of RAID
0
systems is that they do not provide for any data redundancy and are thus not fault tolerant.
RAID
5
is an example of a RAID algorithm that provides some fault tolerance and load balancing. In RAID
5
systems both data and parity information are striped across the storage device array. RAID
5
systems can withstand a single device failure by using parity information to rebuild a failed disk. However, write performance may suffer in RAID
5
systems due to the overhead of calculating parity information. However, only one additional disk is required to store parity information as opposed to the 2X number of disks required for typical RAID
1
systems.
Another RAID technique referred to as RAID
10
or RAID
0
+1 attempts to combine the advantages of both mirroring and striping.
FIG. 1
illustrates how data is stored in a typical RAID
10
system. Data is stored in stripes across the devices of the array.
FIG. 1
shows data stripes A, B, . . . X stored across n storage devices. Each stripe is broken into stripe units, where a stripe unit is the portion of a stripe stored on each device.
FIG. 1
also illustrates how data is mirrored on the array. For example, stripe unit A(
1
) is stored on devices
1
and
2
, stripe unit A(
2
) is stored on devices
3
and
4
, and so on. Thus, devices
1
and
2
form a mirrored pair, as do devices
3
and
4
, etc. As can be seen from
FIG. 1
, this type of system will always require an even number of storage devices (2X the number of drives with no mirroring). This may a disadvantage for some users who have a system containing an odd number of disks. The user may be required to either not use one of his disks or buy an additional disk.
A storage array is said to enter a degraded mode when a disk in the array fails. This is because both the performance and reliability of the system (e.g. RAID) may become degraded. Performance may be degraded because the remaining copy (mirror copy) may become a bottleneck. To reconstruct a failed disk onto a replacement disk may require a copy operation of the complete contents of the mirror disk for the failed disk. The process of reconstructing a failed disk imposes an additional burden on the storage system. Also, reliability is degraded since if the second disk fails before the failed disk is replaced and reconstructed the array may unrecoverably lose data. Thus it is desirable to shorten the amount of time it takes to reconstruct a failed disk in order to shorten the time that the system operates in a degraded mode.
In the example of
FIG. 1
, if device
1
fails and is replaced with a new device, the data that was stored on device
1
is reconstructed by copying the contents of device
2
(the mirror of device
1
) to the new device. During the time the new device is being reconstructed, if device
2
fails, data may be completely lost. Also, the load of the reconstruction operation is unbalanced. In other words, the load of the reconstruction operation involves read and write operations between only device
2
and the new device.
Turning now to
FIG. 2
, an example of a storage array is shown that attempts to overcome some of the disadvantages associated with the array of FIG.
Kowert Robert C.
Sun Microsystems Inc.
Verbrugge Kevin
LandOfFree
Load balancing configuration for storage arrays employing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Load balancing configuration for storage arrays employing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Load balancing configuration for storage arrays employing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2905715