Storage device array and methods for striping and unstriping data and for adding and removing disks online to/from a raid storage array

• US 5,875,456 A
• Filed: 08/17/1995
• Issued: 02/23/1999
• Est. Priority Date: 08/17/1995
• Status: Expired due to Term

• Current Assignee: Xenogenic Development Limited Liability Company (Intellectual Ventures LLC)
• Original Assignee: Nstor Corporation
• Inventors: Stallmo, David C., Hall, Randy K.
• Primary Examiner(s): Gossage, Glenn
• Application Number:
  US08/516,232
• Time in Patent Office: 1,286 Days
• Field of Search: 395/441, 395/182.04, 395/182.03, 395/182.05, 395/183.18, 395/439, 395/489, 371/10.2, 711/114, 711/112, 711/162, 711/170
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 2211/1023 Different size disks, i.e. non uniform size of disks in RAID systems with parity
• CPC Class Codes: G06F 2211/103 Hybrid, i.e. RAID systems with parity comprising a mix of RAID types
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A Redundant Array of Independent Disks (RAID) system that is adaptable to host Input/Output traffic, wherein the RAID configuration is hidden from the host computer, and wherein the system uses various methods for striping and organizing data across the array when disks are added or removed. The system dynamically determines the RAID configuration used to store host data. To maximize response time and avoid a write penalty, small write operations are mapped into RAID 1 configurations, and medium and large write operations are mapped into RAID 3 configurations. The data are migrated into RAID 5 configurations as a background operation, to minimize the disk space lost. The system hides configuration changes necessary for the addition and/or removal of disks to/from the disk array by unstriping data, adding or deleting (removing) a disk and then restriping data over all the disks. The methods may include steps of dividing data blocks into a plurality of square portions, and exchanging data in sets of blocks of each of the square portions, with the exchanging step including locating a diagonal set of blocks within a selected square portion, and exchanging all sets of blocks equidistant from the diagonal, on opposite sides of the diagonal, and in a line perpendicular to the diagonal. While these changes are in progress, the disk array remains on-line and most host data is available for access and modification.

Claims

1. A method for striping and un-striping data on a plurality of storage devices, wherein a stripe of data is a set of one or more contiguous data blocks on each storage device, said method for striping and un-striping comprising the steps of:

(a) dividing data blocks on said plurality of storage devices into a plurality of square portions, wherein a square portion comprises a number of stripes equal to a quantity of said plurality of storage devices; and

(b) exchanging data in sets of blocks of each of said plurality of square portions comprising the steps of

(b1) selecting a square portion,

(b2) locating a diagonal set of blocks within said square portion selected in step (b1), wherein said diagonal set of blocks starts at a first set of blocks in a first stripe of said square portion selected in step (b1) and said diagonal set of blocks ends at a last set of blocks in a last stripe of said square portion selected in step (b1), and

(b3) exchanging all sets of blocks equidistant from said diagonal set of blocks, on opposite sides of said diagonal set of blocks, and in a line perpendicular to said diagonal set of blocks.

2. The method of claim 1 wherein one of said plurality of storage devices comprises a parity device and wherein said parity device is excluded from said quantity of said plurality of storage devices in step (a), and further wherein data blocks of said parity device are not exchanged in step (b).

3. The method of claim 2 further comprising the step of:

(c) exchanging data in data blocks of said parity device with data in data blocks of each of said plurality of square portions, comprising the steps of

(c1) selecting a square portion,

(c2) numbering said stripes within said square portion selected in step (c1) and numbering each storage device,

(c3) selecting a stripe from said square portion selected in step (c1),

(c4) exchanging a set of data blocks of said parity device with a set of data blocks in said stripe selected in step (c3) said set of data blocks in said stripe selected in step (c3) being contained within a device having a number equal to a number of said stripe selected in step (c3),

(c4) repeating steps (c3) and (c4) for each stripe of said square portion selected in step (c1), and

(c5) repeating steps (c1) through (c4) for each square portion within said plurality of square portions.

4. A method for adding or removing a storage device from an array of storage devices accessible from a host computer system, wherein data stored by said host computer system on each one of said storage devices is distributed across all storage devices in said array, said method comprising the steps of:

(a) dividing data blocks on said storage devices into a plurality of square portions, wherein a square portion comprises a number of stripes equal to a quantity of said storage devices in said array, and wherein a stripe is a set of one or more contiguous data blocks on each storage device in said array;

(b) exchanging data in sets of blocks of each of said plurality of square portions comprising the steps of

(b1) selecting a square portion,

(b2) locating a diagonal set of blocks within said square portion selected in step (b1), wherein said diagonal set of blocks within said square portion selected in step (b1) starts at a first set of blocks in a first stripe of said square portion selected in step (b1) and said diagonal set of blocks ends at a last set of blocks in a last stripe of said square portion selected in step (b1), and

(b3) exchanging all sets of blocks equidistant from said diagonal set of blocks located in step (b2), on opposite sides of said diagonal set of blocks located in step (b2), and in a line perpendicular to said diagonal set of blocks located in step (b2);

(c) adding or removing a storage device; and

(d) exchanging data in said sets of blocks of each of said plurality of square portions comprising the steps of

(d1) selecting a square portion,

(d2) locating a diagonal set of blocks within said square portion selected in step (d1), wherein said diagonal set of blocks within said square portion selected in step (d1) starts at a first set of blocks in a first stripe of said square portion selected in step (d1) and ends at a last set of blocks in a last stripe of said square portion selected in step (d1), and

(d3) exchanging all sets of blocks equidistant from said diagonal set of blocks located in step (d2), on opposite sides of said diagonal set of blocks located in step (d2), and in a line perpendicular to said diagonal set of blocks located in step (d2).

5. The method of claim 4 wherein one of said storage devices in said array comprises a parity device and wherein said parity device is excluded from said quantity of said storage devices in step (a), and further wherein data blocks of said parity device are not exchanged in steps (b) and (d).

6. The method of claim 5 wherein step (b) further comprises the following step (b0) performed before step (b1) and wherein step (d) further comprises the following step (d4) performed after step (d3):

(b0) exchanging data in data blocks of said parity device with data in data blocks of each of said square portions, comprising the steps of

(b0a) numbering each storage device,

(b0b) selecting a square portion from said plurality of square portions,

(b0c) numbering said stripes within said square portion selected in step (b0b),

(b0d) selecting a stripe from said square portion selected in step (b0b),

(b0e) exchanging a set of data blocks of said parity device with a set of data blocks in said stripe selected in step (b0d), said set of data blocks in said stripe selected in step (b0d) being contained within a device having a number equal to a number of said stripe selected in step (b0d),

(b0f) repeating steps (b0d) and (b0e) for each stripe of said square portion selected in step (b0b), and

(b0g) repeating step (b0b) through step (b0f) for each of said plurality of square portions; and

(d4) exchanging data in data blocks of said parity device with data in data blocks of each of said square portions, comprising the step of

(d4a) numbering each storage device,

(d4b) selecting a square portion from said plurality of square portions,

(d4c) numbering said stripes within said square portion selected in step (d4b),

(d4d) selecting a stripe from said square portion selected in step (d4b),

(d4e) exchanging a set of data blocks of said parity device with a set of data blocks in said stripe selected in step (d4d), said set of data blocks in said stripe selected in step (d4d) being contained within a device having a number equal to a number of said stripe selected in step (d4d),

(d4f) repeating steps (d4d) and (d4e) for each stripe of said square portion selected in step (d4b), and

(d4g) repeating step (d4b) through step (d4f) for each of said plurality of square portions.