Method for writing contiguous arrays of stripes in a RAID storage system

• US 20040205387A1
• Filed: 04/02/2004
• Published: 10/14/2004
• Est. Priority Date: 03/21/2002
• Status: Active Grant

• Current Assignee: Douglas P. Doucette, Raiesh Sundaram, Srinivasan Viswanathan, Stephen H. Strange, Steven R. Kleiman
• Original Assignee: Douglas P. Doucette, Raiesh Sundaram, Srinivasan Viswanathan, Stephen H. Strange, Steven R. Kleiman
• Inventors: Sundaram, Raiesh, Kleiman, Steven R., Doucette, Douglas P., Viswanathan, Srinivasan, Strange, Stephen H.
• Granted Patent: US 7,979,633 B2
• Time in Patent Office: Days
• US Class Current: 714/6
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

The invention features a method for controlling storage of data in a plurality of storage devices each including storage blocks, for example, in a RAID array. The method includes receiving a plurality of write requests associated with data, and buffering the write requests. A file system defines a group of storage blocks, responsive to disk topology information. The group includes a plurality of storage blocks in each of the plurality of storage devices. Each data block of the data to be written is associated with a respective one of the storage blocks, for transmitting the association to the plurality of storage devices.

Claims

1. In a file server having a storage operating system, a method for managing storage of data in a plurality of storage devices, each storage device comprising a plurality of blocks for storing data, the method comprising the steps of:

generating block layout information in a file system layer of the storage operating system by determining which blocks within the plurality of blocks are allocated for storing data and which are unallocated;

transferring the block layout information from the file system layer to a RAID layer of the storage operating system; and

responsive to the block layout information, the RAID layer controlling the execution of I/O operations by identifying blocks within the plurality of blocks for use by the I/O operations so as to substantially maximize chain lengths of reads for calculation of parity and of writes for data write operations thereof while substantially minimizing cost of calculation of parity,

wherein the block identification comprises the steps of

examining all the I/O operations,

selecting a method for parity calculation which substantially minimizes cost of the parity calculation for the I/O operations, and

responsive to the block layout information and the parity calculation method selection, identifying the blocks within the plurality of blocks for use by the I/O operations.

2. A method for managing storage of data in a plurality of storage devices, each comprising a plurality of storage blocks, the method comprising the steps of:

generating block layout information; and

in response to the block layout information, controlling the execution of an I/O operation by identifying storage blocks for use by the I/O operation so as to substantially minimize cost of calculation of error correction parameters across a stripe.

3. The method of claim 2 wherein the calculation of error correction parameters comprises the calculation of parity.

4. The method of claim 3 wherein the calculation of parity comprises selecting a parity calculation operation from a group consisting of a subtraction method and a parity re-calculation method.

5. The method of claim 2 wherein the identification of storage blocks for use in the I/O operation substantially maximizes the chain length by substantially maximizing the number of blocks having a contiguous physical layout on a storage device.

6. The method of claim 2, further comprising the step of identifying storage blocks for use in the I/O operation so as to substantially maximize the chain length by substantially maximizing the number of blocks having sequential VBN'"'"'s associated with the storage blocks.

7. The method of claim 2, further comprising the step of identifying storage blocks for use in the I/O operation so as to substantially maximize the chain length by substantially maximizing the locality of the blocks of a storage device.

8. The method of claim 2 wherein the execution controlling step comprises the steps of:

examining blocks to which data is to be written prior to write operations;

selecting one of a plurality of parity calculation methodologies including

a first methodology comprising minimizing the number of blocks read, and

a second methodology comprising maximizing chain lengths of blocks read for the parity calculation.

9. The method of claim 8, wherein the execution controlling step further comprises the steps of:

implementing the selection responsive to the block layout information; and

wherein, if the selection constitutes substantially minimizing the number of read blocks,

determining on a stripe-by-stripe basis whether to calculate parity based on a subtraction method or a recalculation method,

performing any appropriate read operations to support the method selected, and

calculating parity responsive to the read blocks and the data to be written; and

wherein, if the selection constitutes substantially maximizing chain lengths of blocks read,

deciding which storage blocks to read to substantially maximize chain length while substantially minimizing the number of storage blocks read to support either a subtraction method or a recalculation method,

performing read operations on the blocks to be read, and

calculating parity responsive to the read blocks and the data to be written.

10. The method of claim 2, wherein the identification of storage blocks is based at least in part on an available resource.

11. The method of claim 2 further comprising transmitting the block layout information from a file system layer to a RAID layer.

12. The method of claim 2 wherein the generating step further comprises:

making a first determination as to whether a storage block is unallocated;

making a second determination as to a current implementation of the plurality of storage devices; and

generating the block layout information based at least in part on the first and the second determinations.

13. The method of claim 2, wherein the I/O operation is one of a plurality of I/O operations and one of the plurality of I/O operations is a read operation.

14. The method of claim 2, wherein the chain length is a chain length of a read operation for calculation of parity.

15. The method of claim 2, wherein the chain length is a chain length for a write operation for the data.

16. A method for managing storage of data in a storage system comprising a plurality of storage devices each comprising a plurality of storage blocks, the method comprising writing data to predetermined storage blocks across a plurality of stripes and to predetermined storage blocks within each storage device so as to substantially maximize chain length of storage blocks within each storage device while substantially minimizing cost of calculation of error correction parameters across each stripe of the plurality of stripes.

17-38. -38. (Cancelled)

39. A storage system comprising:

a plurality of storage devices each comprising;

a plurality of storage blocks; and

a storage manager in communication with the plurality of storage devices, the storage manager writing data to predetermined storage blocks across a plurality of stripes and to predetermined storage blocks within each storage device so as to substantially maximize chain length of storage blocks within a storage device while substantially minimizing the calculation of error correction parameters across each stripe of the plurality of stripes.

40. A system for managing the storage of data, the system comprising:

a plurality of storage devices each having a plurality of storage blocks;

a storage device manager in communication with the plurality of storage blocks;

a block layout information generator in communication with the storage device manager and the plurality of storage blocks; and

an error correction parameter calculator in communication with the plurality of storage blocks and the storage device manager,

wherein the storage device manager, in response to the block layout information from the block layout information generator, controls the execution of an I/O operation by identifying storage blocks for use by the I/O operation so as to substantially maximize chain length within the storage device while substantially minimizing the calculation by the error correction parameter calculator of error correction parameters across a stripe.

41. A method for managing storage of data in storage blocks, the method comprising the steps of:

generating block layout information;

dynamically determining a first number of error correction calculations;

dynamically determining a second number corresponding to a chain length; and

in response to the block layout information, controlling the execution of an I/O operation by identifying storage blocks for use by the I/O operation so as to have a chain length of the second number within a storage device while performing the first number of calculations of error correction parameters across a stripe.

42-44. -44. (Cancelled)