Method for writing contiguous arrays of stripes in a RAID storage system
First Claim
1. A method for managing storage of data in a plurality of storage devices operatively connected to a computer, each storage device having a plurality of blocks for storing data, comprising:
- generating block layout information of a storage operating system executing on the computer by determining which blocks within the plurality of blocks are allocated for storing data and which are unallocated;
responsive to the block layout information, controlling the execution of I/O operations generated by the storage operating system by identifying a plurality of contiguous blocks within the plurality of blocks for use by the I/O operations so as to substantially maximize chain lengths of read operations for calculation of parity;
determining whether a parity subtraction method or a recalculation method requires a fewest number of read operations to calculate parity for the I/O operations;
selecting the parity subtraction method or the recalculation method for parity calculation based on which method requires the fewest number of read operations; and
responsive to the block layout information and the parity calculation method selected, identifying the contiguous blocks within the plurality of blocks for use by the I/O operations.
0 Assignments
0 Petitions
Accused Products
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.
99 Citations
25 Claims
-
1. A method for managing storage of data in a plurality of storage devices operatively connected to a computer, each storage device having a plurality of blocks for storing data, comprising:
-
generating block layout information of a storage operating system executing on the computer by determining which blocks within the plurality of blocks are allocated for storing data and which are unallocated; responsive to the block layout information, controlling the execution of I/O operations generated by the storage operating system by identifying a plurality of contiguous blocks within the plurality of blocks for use by the I/O operations so as to substantially maximize chain lengths of read operations for calculation of parity; determining whether a parity subtraction method or a recalculation method requires a fewest number of read operations to calculate parity for the I/O operations; selecting the parity subtraction method or the recalculation method for parity calculation based on which method requires the fewest number of read operations; and responsive to the block layout information and the parity calculation method selected, identifying the contiguous 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 operatively connected to a computer, each storage device comprising a plurality of storage blocks, comprising:
-
generating block layout information of a storage operating a system executing on the computer by determining which blocks within the plurality of storage blocks are allocated for storing data and which are unallocated; determining whether a first methodology or a second methodology requires a fewest number of read operations to calculate parity for I/O operations generated by the storage operating system; and in response to the block layout information and the determination, controlling execution of I/O operations by identifying a plurality of contiguous storage blocks of the plurality of storage blocks for use by the I/O operations so as to minimize a number of read operations needed for calculation of error correction parameters across a stripe disposed among the plurality of storage devices. - View Dependent Claims (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A method for managing storage of data in a storage system, comprising:
-
maintaining a plurality of storage devices of the storage system, each storage device having a plurality of storage blocks; and writing data to predetermined storage blocks of the plurality of storage blocks across a plurality of stripes and to predetermined contiguous storage blocks within the plurality of storage devices so as to maximize chain lengths of the predetermined contiguous storage blocks and minimizing a number of read operations for the calculation of error correction parameters across the plurality of stripes by determining whether a parity subtraction method or a recalculation method requires a fewest number of read operations to calculate parity, and selecting the parity subtraction method or the recalculation method for parity calculation based on which method requires the fewest number of read operations.
-
-
17. A storage system, comprising:
-
a storage adapter configured to couple the storage system to a plurality of storage devices, each storage device having a plurality of storage blocks; and a storage manager in communication with the plurality of storage devices, the storage manager configured to write data to predetermined storage blocks of the plurality of storage blocks across a plurality of stripes and to predetermined storage blocks within the plurality of storage devices so as to maximize a chain length of the plurality of storage blocks by selecting contiguous storage blocks within a first storage device of the plurality of storage devices while minimizing a number of read operations required for calculation of error correction parameters across the plurality of stripes by determining whether a parity subtraction method or a recalculation method requires a fewest number of read operations to calculate parity and selecting the parity subtraction method or the recalculation method for parity calculation based on which method requires the fewest number of read operations.
-
-
18. A system for managing data storage, comprising:
-
a plurality of storage devices operatively connected to a computer, each storage device having a plurality of storage blocks; a storage device manager of the computer in communication with the plurality of storage blocks; a block layout information generator of the computer in communication with the storage device manager and the plurality of storage blocks; and an error correction parameter calculator of the computer in communication with the plurality of storage blocks and the storage device manager, wherein the storage device manager, in response to block layout information from the block layout information generator, controls execution of an I/O operation by identifying a plurality of contiguous storage blocks on one or more storage devices of the plurality of storage devices for use by the I/O operation so as to maximize a chain length within the one or more storage devices while minimizing a number of read operations required by the error correction parameter calculator to calculate error correction parameters across a stripe of the one or more storage devices by determining whether a parity subtraction method or a recalculation method requires a fewest number of read operations to calculate parity for the I/O to operations and select the parity subtraction method or the recalculation method for parity calculation based on which method requires the fewest number of read operations.
-
-
19. A method for managing storage of data by a computer, comprising:
-
receiving a request to write the data to a plurality of storage devices connected to the computer; generating block layout information to determine which blocks within a plurality of blocks of the plurality of storage devices are allocated and which are unallocated; identifying one or more blocks of the plurality of blocks from the blocks layout information for use by a set of I/O operations; determining a first number of read operations needed to calculate parity for the data by calculating parity using a subtraction method; determining a second number of read operations needed to calculate parity for the data by calculating the parity using a recalculation method; determining which method requires a fewer number of read operations, and choosing the method that requires the fewer number of read operations; and writing the data to the identified one or more blocks, and calculating the parity for the data using the chosen method. - View Dependent Claims (20)
-
-
21. A method for managing storage of data by a computer, comprising:
-
receiving a request to write data to a plurality of storage devices operatively connected to the computer; generating block layout information to determine which blocks within a plurality of blocks of the plurality of storage devices are allocated and which are unallocated; identifying the unallocated blocks for use by a set of I/O operations to store the data; determining, in response to the blocks layout information, whether a first method to minimize a number of read blocks or whether a second method to maximize chain lengths of read blocks requires a fewer number of read operations, and selecting one of the first method and the second method that requires the fewer number of read operations responsive to the determining and responsive to the block layout information, and writing the data to the plurality of storage devices using the selected method. - View Dependent Claims (22, 23)
-
-
24. A method for managing storage of data by a computer, comprising:
-
receiving a request to write data to a plurality of storage devices operatively connected to the computer; generating block layout information to determine which blocks within a plurality of blocks of the plurality of storage devices are allocated and which are unallocated; identifying one or more unallocated blocks for use by a set of I/O operations to store the data; testing to either maximize chain lengths of read operations for calculation of parity, or testing to place the data with a high degree of locality in the plurality of storage devices, the testing comprising, determining, for both maximizing chain lengths and placing the data with the high degree of locality, a number of read operations needed to calculate parity for the data, by calculating parity using both a subtraction method of calculating parity and a recalculation method of calculating parity; first choosing to either maximize chain lengths of read operations for calculation of parity or to place the data with the high degree of locality in the plurality of storage devices, and after the first choice, secondly choosing either the subtraction method of calculating parity or the recalculation method of calculating parity by determining which of these methods requires a fewest number of read operations, choosing the method which requires the fewest number of read operations of calculating parity of the data; and writing the data to the identified blocks, and calculating parity for the data using the chosen method.
-
-
25. A computer readable media, comprising:
-
said computer readable media containing instructions for execution on a processor for a method of managing storage of data in a plurality of storage devices, each storage device having a plurality of blocks for storing data, the method comprising, generating block layout information; and in response to the block layout information, controlling execution of an I/O operation to the plurality of storage devices by identifying a plurality of contiguous storage blocks on the plurality of storage devices so as to minimize a number of read operations for calculation of error correction parameters across a stripe of the plurality of storage devices by determining whether a parity subtraction method or a recalculation method requires a fewest number of read operations to calculate parity for the I/O operations and selecting one of the parity subtraction method and the recalculation method for parity calculation based on which method requires the fewest number of read operations.
-
Specification