US 5,315,602 AGranted

Optimized stripe detection for redundant arrays of disk drives

AssigneeDigital Equipment Corporation

InventorsEric S. Noya, Randy M. Arnott, Mitchell N. Rosich

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system for reducing the number of I/O requests required to write data to an redundant array of inexpensive disks (RAID) of a computer system including a host central processor unit and a memory buffer cache. The system includes determinations for writing new data stored in the cache to the disk drives, as stripes, using the least number of I/O requests possible. The system uses the best of two alternative techniques in which the parity for the stripe can be generated. A first procedure determines the number of I/O requests that would be required to generate the parity data from the entire stripe including the new data to be written to the disk drives. A second procedure determines the number of I/O requests that would be required to generate the parity data from the new data to be written to the disk drives and the old parity data of the stripe. The system then aggregates in memory the blocks necessary to generate the parity data as either an entire stripe or as individual blocks using the technique which requires the least number of I/O requests as determined by the first and second procedures.

Claims10

Dependent claims

An apparatus for generating parity data for a plurality of disk drives, each of the plurality of disk drives divided into a plurality of blocks, the plurality of blocks further organized into a plurality of stripes, each of the plurality of stripes including one block from each of the plurality of disk drives, one of the blocks of each stripe storing parity data generated from the data stored in the other blocks of the stripe, the apparatus comprising;

memory means for storing data, said memory means partitioned into blocks compatible with the block structure of the plurality of disk drives;
means for identifying an updated memory block storing data to be written to one of the plurality of disk drives;
means for identifying a predetermined stripe, said predetermined stripe including a disk block to be overwritten by said updated memory block;
first means for determining the number of I/O requests required to aggregate in said memory means all of the data, except the parity data, of said predetermined stripe;
second means for determining the number of I/O requests required to aggregate in said memory means said block to be overwritten and the parity block of said predetermined stripe;
and
means for choosing said first means OR said second means to perform said I/O requests by choosing the means which requires the fewest number of I/O requests to aggregate in said memory means the blocks of said identified stripe necessary to generate the parity data of said predetermined stripe.

4 more elements

A method for generating parity data for a plurality of disk drives, each of the plurality of disk drives divided into a plurality of blocks, the plurality of blocks further organized into a plurality of stripes, each of the plurality of stripes including one block from each of the plurality of disk drives, one of the blocks of each stripe storing parity data generated from the data stored in the other blocks of the stripe, the method comprising the steps of;

storing data in a memory means, said memory means partitioned into blocks compatible with the block structure of the plurality of disk drives;
identifying an updated memory block storing data to be written to one of the plurality of disk drives;
identifying a predetermined stripe, said predetermined stripe including a disk block to be overwritten by said updated memory block;
determining by a first means, the number of I/O requests required to aggregate in said memory means all of the data, except the parity data, of said predetermined stripe;
determining by a second means, the number of I/O requests required to aggregate in said memory means said block to be overwritten and the parity block of said predetermined stripe;
and
aggregating in said memory means the blocks of said identified stripe necessary to generate the parity data of said predetermined stripe with the fewest number of I/O requests as determined by said second OR said first means.

4 more elements

Dependencies are inferred from the claim text.

Facts

Application: 07/929,076Filed 12 Aug 1992
Granted: 24 May 1994
Term ends: Not estimatedThe source records don’t support an estimate.

Classification8 codes

G06F 11/1076
Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's: parity data used in redundant arrays of…
G06F 3/0601
Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers: interfaces specially…
G06F 11/1008
Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's: in individual solid state devices
G06F 12/0804
Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches: with main…