Dynamic information storage or retrieval – Information location or remote operator actuated control – Selective addressing of storage medium
Reexamination Certificate
1999-08-18
2002-08-06
Tran, Thang V. (Department: 2653)
Dynamic information storage or retrieval
Information location or remote operator actuated control
Selective addressing of storage medium
C711S111000, C711S112000
Reexamination Certificate
active
06430118
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to data storage devices and, more particularly, to data storage devices in which each segment of data is divided into one or more data sub-segments and a parity sub segment and in which each sub-segment is stored on a separate storage device.
2. Description of Related Art
User data, such as a video stream, is often divided into segments, each segment containing a portion of the user data.
In turn, each segment is often divided into one or more data sub-segments and a parity sub-segment. Each data sub-segment contains a portion of the user data contained in the segment. The parity sub-segment contains information necessary for recreating an unavailable data sub-segment in conjunction with the available data sub-segments.
Each of the sub-segments that comprise a particular segment of user data (i.e., the data sub-segments and the parity sub-segment) are typically stored on a separate storage device, and all of the storage devices operate under a common control. One such configuration is known as a RAID, the acronym standing for a redundant array of inexpensive drives.
A RAID has several advantages. By breaking a segment of user data into a plurality of sub-segments and by simultaneously reading or writing those sub-segments, the speed at which the segment of data can be read or written is effectively multiplied by the number of separate storage devices. If a storage device containing a data sub-segment malfunctions during a read operation, the corresponding parity segment contained on another storage device, in conjunction with the available data sub-segments can advantageously be used to recreate the data sub-segment that was stored on the malfunctioning drive. To further enhances performance, the parity sub-segments are often stored on different storage devices.
Increasing the rate at which data can be read from a RAID continues to be of growing importance. Unfortunately, it also continues to be of great difficulty due to the intrinsic nature of the storage devices.
These storage devices are typically hard disk drives. When data residing in a particular track is desired, the head is moved over that track and must wait for the disk to rotate until the beginning of the sector containing the desired data arrives underneath the head. These delays are known as skew and latency delays.
Other delays are sometimes caused by multiple storage devices attempting to simultaneously access a common bus. These delays are known as bus contention delays.
The effect of these delays is often cumulative. Moreover, the drive array controller typically waits until all of the storage devices report the availability of their requested sub-segments before signaling the computer that the desired data segment is available. Since the cumulative delays of each storage device are typically different, the controller is usually unable to signal the availability of the desired data segment until very slowest of all of the storage devices is ready. Average access time is thus reduced, particularly when each data segment is subdivided into a large number of sub-segments.
SUMMARY OF THE INVENTION
The invention utilizes parity data to enhance performance in a data storage system.
In one embodiment of the invention, a plurality of storage devices are used to store the data sub-segments and the parity sub-segment. Each storage device is configured to store one of the sub-segments of each segment. Each storage device also has an input for receiving a request for a sub-segment stored on the device and an output that indicates when a requested sub-segment is available for delivery from the storage device;.
A controller is connected to the inputs of the storage devices for causing each of the devices to begin accessing the sub-segment stored on the device that corresponds to a desired segment of the user data, in response to a request for that segment.
A data ready generator is also provided that is connected to the outputs of the storage devices. The generator indicates when all but one of the outputs indicate that the requested sub-segment stored on the device is available for delivery.
With this embodiment, the needed data segment becomes available, even before the storage device that is taking the most time to access its respective sub-segment has succeeded. If the slowest storage device contains a data sub-segment, that data sub-segment is recreated from the parity sub-segment and the other data sub-segments that are currently available.
In an alternate embodiment of the invention, the identity of the slowest drive is predicted before any of the drives are instructed to seek their respective sub-segments. In this embodiment, the predicted slowest drive is never instructed in the first instance to seek its respective sub-segment. In this embodiment, the predicted slowest drive is freed up even sooner, further enhancing average performance.
REFERENCES:
patent: 5237689 (1993-08-01), Behnke
patent: 5386402 (1995-01-01), Iwata
patent: 5805979 (1998-09-01), Anderson
patent: 5893139 (1999-04-01), Kamiyama
patent: 5933840 (1999-08-01), Menon et al.
patent: 6108748 (2000-08-01), Ofek et al.
patent: 6112255 (2000-08-01), Dunn et al.
patent: 6151641 (2000-11-01), Herbert
patent: 6275898 (2001-08-01), DeKoning
patent: 6341317 (2002-01-01), D'Errico et al.
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
Tran Thang V.
LandOfFree
Data storage utilizing parity data to enhance performance does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data storage utilizing parity data to enhance performance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data storage utilizing parity data to enhance performance will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2886630