Dynamic parity distribution technique
First Claim
1. A method for operating a computer, comprising:
- in response to a request to store data on an array of storage devices coupled to the computer, determining which blocks are unallocated to data in a next allocated stripe of the array;
keeping track of an amount of data that has been allocated on each storage device of the array;
selecting, in a non-fixed pattern, one or more of the unallocated blocks to store redundant information from among the storage devices that contain a most amount of data to equalize the amount of data on each storage device over time; and
writing the next allocated stripe across the storage devices of the array with the data in allocated blocks and the redundant information in the one or more selected unallocated blocks to thereby evenly distribute a data access load across the storage devices of the array and compensate for uneven distribution of data across the devices.
0 Assignments
0 Petitions
Accused Products
Abstract
A dynamic parity distribution system and technique distributes parity across disks of an array. The dynamic parity distribution system includes a storage operating system that integrates a file system with a RAID system. In response to a request to store (write) data on the array, the file system determines which disks contain free blocks in a next allocated stripe of the array. There may be multiple blocks within the stripe that do not contain file system data (i.e., unallocated data blocks) and that could potentially store parity. One or more of those unallocated data blocks can be assigned to store parity, arbitrarily. According to the dynamic parity distribution technique, the file system determines which blocks hold parity each time there is a write request to the stripe. The technique alternately allows the RAID system to assign a block to contain parity when each stripe is written.
-
Citations
43 Claims
-
1. A method for operating a computer, comprising:
-
in response to a request to store data on an array of storage devices coupled to the computer, determining which blocks are unallocated to data in a next allocated stripe of the array; keeping track of an amount of data that has been allocated on each storage device of the array; selecting, in a non-fixed pattern, one or more of the unallocated blocks to store redundant information from among the storage devices that contain a most amount of data to equalize the amount of data on each storage device over time; and writing the next allocated stripe across the storage devices of the array with the data in allocated blocks and the redundant information in the one or more selected unallocated blocks to thereby evenly distribute a data access load across the storage devices of the array and compensate for uneven distribution of data across the devices. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A computer storage system, comprising:
-
an array of storage devices connected to the storage system; a counter associated with each storage device of the array, the counter configured to keep track of an amount of data that has been allocated on each storage device; and a storage operating system executed by a processor on the storage system, the storage operating system configured, in response to a request to store data on the array, to (i) determine which blocks are unallocated to data in a next allocated stripe of the array, (ii) select, in a non-fixed pattern, one or more of the unallocated blocks to store redundant information from among the storage devices that contain a most amount of data to equalize the amount of data on each storage device over time, and (iii) write the next allocated stripe across the storage devices of the array with the data in allocated blocks and the redundant information in the one or more selected unallocated blocks to thereby evenly distribute a data access load across the storage devices of the array and compensate for uneven distribution of data across the devices. - View Dependent Claims (8, 9, 10, 11, 12, 13)
-
-
14. A method for storing data and parity in a computer data storage system, comprising:
-
storing the data and the parity in storage blocks on a plurality of storage devices coupled to the storage system; in response to receiving a request to write requested data to the plurality of storage devices, allocating free storage blocks on the plurality of storage devices to store the requested data and the parity computed for the requested data, the storage blocks allocated to store parity located on any of the storage devices; and writing the requested data to blocks allocated for data and writing the parity to blocks allocated for parity to dynamically distribute storage blocks holding parity across the plurality of storage devices. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
-
-
26. A computer data storage system apparatus to store data, comprising:
-
a plurality of storage devices coupled to the data storage system, the plurality of storage devices having free storage blocks allocated to store a requested data and a parity computed for the requested data, the storage blocks allocated to store parity located on any of the storage devices; and an operating system executing on the data storage system, the operating system to write the requested data to blocks allocated for data and to write the parity to blocks allocated for parity to dynamically distribute storage blocks holding parity across the plurality of storage devices. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37)
-
-
38. A computer readable storage media, comprising:
-
said computer readable storage media containing program instructions for execution on a processor for a method of storing data and parity in a computer data storage system, the program instructions for, storing the data and the parity in storage blocks on a plurality of storage devices; in response to receiving a request to write requested data to the plurality of storage devices, allocating free storage blocks on the plurality of storage devices to store the requested data and the parity computed for the requested data, the storage blocks allocated to store parity located on any of the storage devices; and writing the requested data to blocks allocated for data and writing the parity to blocks allocated for parity to dynamically distribute storage blocks holding parity across the plurality of storage devices.
-
-
39. A method for storing data and parity in a computer data storage system, comprising:
-
storing the data and the parity in storage blocks on a plurality of storage devices; in response to receiving a request to write requested data to the plurality of storage devices, allocating free storage blocks on the plurality of storage devices to store the requested data and the parity computed for the requested data, the storage blocks allocated to store parity located on any of the storage devices; maintaining a counter for each storage device of the plurality of storage devices; incrementing the counter each time that a storage block is allocated for data on the each storage device; decrementing the counter each time that an allocated storage block is freed and each time that another storage block is allocated for parity on the each storage device; maintaining a desired value of the counter in order to maintain a desired ratio of data storage blocks to non-data storage blocks on the each data storage device; and writing the requested data to blocks allocated for data and writing the parity to blocks allocated for parity to dynamically distribute storage blocks holding parity across the plurality of storage devices.
-
-
40. A computer data storage system apparatus to store data, comprising:
-
storage blocks to store the data and the parity on a plurality of storage devices; free storage blocks allocated on the plurality of storage devices to store a requested data and a parity computed for the requested data, the storage blocks allocated to store parity located on any of the storage devices; a counter for each storage device of the plurality of storage devices; the counter to be incremented each time that a storage block is allocated for data on the each storage device; the counter to be decremented each time that an allocated storage block is freed and each time that another storage block is allocated for parity on the each storage device; and a desired value of the counter selected to maintain a desired ratio of data storage blocks to non-data storage blocks on the each data storage device; and an operating system to write the requested data to blocks allocated for data and to write the parity to blocks allocated for parity to dynamically distribute storage blocks holding parity across the plurality of storage devices.
-
-
41. A method for storing data and parity in a computer data storage system, comprising:
-
storing the data and the parity in storage blocks on a plurality of storage devices; in response to receiving a request to write requested data to the plurality of storage devices, allocating free storage blocks on the plurality of storage devices to store the requested data and the parity computed for the requested data, the storage blocks allocated to store parity located on any of the storage devices; maintaining a counter for each storage device of the plurality of storage devices in order to maintain a desired ratio of data storage blocks to non-data storage blocks on the each data storage device; and writing the requested data to blocks allocated for data and writing the parity to blocks allocated for parity to dynamically distribute storage blocks holding parity across the plurality of storage devices.
-
-
42. A computer data storage system apparatus to store data, comprising:
-
storage blocks to store the data and the parity on a plurality of storage devices; free storage blocks allocated on the plurality of storage devices to store a requested data and a parity computed for the requested data, the storage blocks allocated to store parity located on any of the storage devices; a counter for each storage device of the plurality of storage devices to maintain a desired ratio of data storage blocks to non-data storage blocks on the each data storage device; and writing the requested data to blocks allocated for data and writing the parity to blocks allocated for parity to dynamically distribute storage blocks holding parity across the plurality of storage devices.
-
-
43. A computer readable storage media, comprising:
-
said computer readable storage media containing program instructions for execution on a processor for a method of storing data and parity in a computer data storage system, the program instructions for, storing the data and the parity in storage blocks on a plurality of storage devices; in response to receiving a request to write requested data to the plurality of storage devices, allocating free storage blocks on the plurality of storage devices to store the requested data and the parity computed for the requested data, the storage blocks allocated to store parity located on any of the storage devices; maintaining a counter for each storage device of the plurality of storage devices in order to maintain a desired ratio of data storage blocks to non-data storage blocks on the each data storage device; and writing the requested data to blocks allocated for data and writing the parity to blocks allocated for parity to dynamically distribute storage blocks holding parity across the plurality of storage devices.
-
Specification