Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-08-18
2002-08-27
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S111000, C711S112000, C714S006130
Reexamination Certificate
active
06442649
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to storage device arrays and, more particularly, to techniques for increasing the size of storage device arrays, while minimizing the disruption caused by the initialization of the enlarged array.
2. Description of Related Art
The use of an array of storage devices to store computer data is well known. One such device is known as RAID, an acronym for a redundant array of inexpensive drives.
RAIDs consist of a plurality of disk drives configured to operate simultaneously in harmony. In a typical configuration, a segment of data is broken into a plurality of blocks, each one of which is simultaneously written to or read from each of the drives in a RAID configuration. This effectively multiplies the speed at which the segment of data can be read or written by the number of drives in the configuration.
To protect against an error during the reading operation, a parity block is created for each set of data blocks when each is written. Typically, the parity block is stored on one of the drives in the array, while the data blocks that it protects are each stored on a different drive in the array. When it is desired to read a data block from the storage device, the parity block can be used to re-create that data block if it is unavailable, based on the information contained in the parity block and in the other data blocks that the parity block protects. Typically, an exclusive-or function is utilized to calculate the parity block in accordance with well-known techniques.
In more advanced RAID systems, such as systems that implement what is known as RAID Level 5, parity blocks are not all stored on a single drive. Instead, they are distributed across all of the drives in the RAID. As is well known, this enhances overall performance.
The computer to which the storage device array is attached is often unaware of the physical layout of the array or, more fundamentally, that there is an array of devices. It typically refers to each block of data by what is known as a “logical block address” or an “LBA.” Each data block has a different logical block address.
A RAID typically includes an address translator that translates the logical block address of each data block into each actual address in the RAID system. Each actual address, in turn, typically consists of the identity of the storage device in the array on which the block is stored, plus the exact location (logical or physical) of the block on that storage device. In order to allow the data block to be recreated if it is not available, the RAID also keeps track of the parity block that is associated with the data block, as well as the other data blocks that are protected by that parity block.
Various techniques are used to generate this address translation information. Although a map can be used, it is typically faster and more efficient to use an algorithm. Such an algorithm is typically applied to each logical block address to generate the actual address of the block in the storage array device, as well as the actual address of its corresponding parity block and the other data blocks which are protected by that parity block. Each time a data block is modified, the storage device array updates the data block which is actually stored in the array, as well as its corresponding parity block.
Another advantage of a RAID is that it readily facilitates an incremental increase in the size of the storage array, without having to require a corresponding change in the logical block addressing system of the computer to which the storage array is attached. A new storage device is simply added to the array and the algorithm which is used to derive actual data and parity block addresses from the logical block address is revised to embrace the new storage device.
Unfortunately, the updated algorithm usually generates an actual data address and actual parity address for each logical block address that is different than the ones generated by the original algorithm. As a consequence, some mechanism must be provided to rearrange all of the existing data blocks and parity blocks to the locations that conform, respectively, to the updated algorithm.
Backing up is one technique which is employed to achieve this result. Before the new storage device is added, all of the data on the storage device array is copied to a back-up device, such as a tape drive. The new storage device is added, the address translation algorithm is modified to account for the new device, and all of the data stored in the back-up device is restored to the enlarged system.
Unfortunately, this process can often take several hours and even days. In the meantime, the storage device is usually not available to the computer, causing significant interference with the normal operations of the computer. In many applications, this is highly undesirable.
SUMMARY OF THE INVENTION
The invention expands the size of a storage array on a dynamic basis, without requiring a back-up or the application of any other type of time-consuming block-reorganization technology.
In one embodiment of the invention, a storage device array for storing and retrieving a first and second set of data blocks is provided. Each data block has an intended data address. The array includes a first storage area containing two or more storage devices and a second storage area containing one or more storage devices. The array further includes an address translator for translating each intended data address into an actual data address where its data block is or will be stored in the array and into an actual parity address where each associated parity block is or will be stored in the array. Each intended address of a data block from the first set is translated into an actual data address be on one of the storage devices in the first storage area and an actual parity address on another of the storage devices in the first storage area. Each intended address of a data block from the second set is translated into an actual data address on one of the storage devices in the second storage area and an actual parity address on one of the storage devices in the first storage area.
In another embodiment of the invention, a method of storing and retrieving a first and second set of data blocks in a storage device array is provided. Each data block has an intended data address. The array contains a first storage area containing two or more storage devices and a second storage area containing one or more storage devices. The array also includes an address translator for translating each intended data address into an actual data address where its data block is or will be stored in the array and an actual parity address where its associated a parity block is or will be stored in the array. If the intended address of a data block is from the first set, the method makes the actual data address always on one of the storage devices in the first storage area and the actual parity address always on another of the storage devices in the first storage area. If the intended address is of a data block from the second set, the method makes the actual data address always on one of the storage devices in the second storage area and the actual parity address always on one of the storage devices in the first storage area.
These, as well as still further features, advantages and benefits of the present invention will now become clear upon an examination of the attached drawings and the following description of the preferred embodiments.
REFERENCES:
patent: 5758118 (1998-05-01), Choy et al.
patent: 6000010 (1999-12-01), Legg
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
Song Jasmine
Yoo Do Hyun
LandOfFree
Dynamic expansion of storage device 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 Dynamic expansion of storage device array, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic expansion of storage device array will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2879171