Concentrated parity technique for handling double failures and enabling storage of more than one parity block per stripe on a storage device of a storage array
AssigneeNetApp, Inc.
InventorPeter F. Corbett
Life of this patent
Estimating the term…
Abstract
A method for constructing an extended array of storage devices that enables storage of more than one parity block per stripe on a single device of the array is disclosed. Each device is divided into blocks. The blocks are organized into stripes across the devices, wherein each stripe contains a first number of parity blocks from each of a second number of parity storage devices of the array. Data blocks are stored on a third number of data storage devices, to thereby construct the array to enable storage of more than one parity block per stripe on a single device, wherein the extended array is recoverable from any one or two storage device failures.
Claims19
A method for constructing an array of storage devices comprising:
- dividing each of the devices into blocks;
- storing data blocks on a first set of the devices;
- storing more than one parity block on each of a second set of the devices;
- forming a plurality of parity sets wherein each parity set includes a plurality of data blocks selected from less than all of the first set of devices and a parity block that is computed parity for the plurality of data blocks, and each data block belonging to two parity sets;
- and
- organizing the array so that:
- i) no data block belongs to two parity sets having parity blocks on the same device of the second set of the devices;
- and ii) the array is recoverable from any one or two device failures.
An array of storage devices, comprising:
- a plurality of storage devices, each device of the plurality of storage devices divided into blocks that stripe the data into a plurality of data blocks, the data blocks stored on data devices and parity blocks stored on parity devices;
- a storage operating system including a device storage layer configured to implement a concentrated parity technique that forms a plurality of parity sets wherein each parity set includes a plurality of data blocks selected from less than all of the data devices and a parity block that is computed parity for the plurality of data blocks, where each data block belongs to two parity set, the array organized so that:
- i) no data block belongs to two parity sets having parity blocks on a same parity devices;
- and ii) the array is recoverable from any one or two devices;
- and
- a processing element configured to execute the operating system to thereby invoke storage access operations to and from the array in accordance with the concentrated parity technique.
A computer readable medium containing executable program instructions for constructing an array of storage devices, comprising:
- program instructions that divide each device into blocks;
- program instructions that store data blocks on a first set of the devices;
- program instructions that store more than one parity block on each of a second set of devices;
- program instructions that form a plurality of parity sets wherein each parity set includes a plurality of data blocks selected from less than all of the first set of devices and a parity block that is computed parity for the plurality of data blocks, and each data block belonging to two parity sets;
- and
- program instructions that organize the array so that:
- i) no data block belongs to two parity sets having parity blocks on the same device of the second set of devices;
- and ii) the array is recoverable from any one or two device failures.
A method for storing parity for a plurality of storage devices, comprising:
- dividing each device of the plurality of devices into blocks;
- storing data into a plurality of data blocks, wherein the data blocks are stored on a first set of data devices;
- storing parity blocks on a second set of parity devices;
- organizing the plurality of data blocks and parity blocks into a plurality of parity sets, wherein each parity set includes a particular group of data blocks selected from less than all of the first set of data devices and a particular parity block that is computed parity for the group of data blocks, and each data block belongs to two parity sets;
- and
- organizing the first set of data devices and the second set of parity devices in an array so that:
- i) no data block belongs to two parity sets having parity blocks on the same parity device;
- and ii) any one or two device failures is recoverable.
A method comprising:
- dividing each device of a plurality of devices into blocks;
- storing a plurality of data blocks on a first set of data devices;
- storing more than one parity block on each of a second set of parity devices;
- forming a plurality of parity sets, wherein each parity set includes a plurality of data blocks selected from less than all of the first set of devices and a parity block that is computed parity for the plurality of data blocks, and each data block belonging to two parity sets;
- and
- organizing the first set of data devices and the second set of parity devices to construct an unbalanced stripe array so that:
- i) no data block belongs to two parity sets having parity blocks on the same parity device;
- and ii) any one or two device failures is recoverable.
Dependencies are inferred from the claim text.