Dynamic parity distribution technique

• US 7,921,257 B1
• Filed: 12/27/2007
• Issued: 04/05/2011
• Est. Priority Date: 11/03/2003
• Status: Expired due to Term

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: English, Robert M., Kleiman, Steven R., Corbett, Peter F.
• Primary Examiner(s): PATEL, HETUL B
• Application Number:
  US11/965,406
• Time in Patent Office: 1,195 Days
• Field of Search: 711/114
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks

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.

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.

2. The method of claim 1, further comprising:

dividing each storage device of the array into blocks, wherein the next allocated stripe contains at least one block from each storage device.

3. The method of claim 2, further comprising:

allocating the data to one or more blocks across the next allocated stripe.

4. The method of claim 3, further comprising:

computing the redundant information for the next allocated stripe based on contents of other blocks in the stripe.

5. The method of claim 4, wherein the redundant information is parity.

6. The method of claim 4, wherein the redundant information is computer based algebraic and algorithmic calculations in response a layout of the allocated data.

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.

8. The system of claim 7, further comprising:

a storage module within the storage operating system, wherein the storage module is configured to select the one or more blocks to store redundant information.

9. The system of claim 8, further comprising:

each storage device of the array is divided into blocks, wherein the next allocated stripe contains at least one block from each storage device.

10. The system of claim 9, further comprising:

the storage operating system is further configured to allocate the data to one or more blocks across the next allocated stripe.

11. The system of claim 10, further comprising:

the storage module is further configured to compute the redundant information for the next allocated stripe based on contents of other blocks in the stripe.

12. The system of claim 11, further comprising:

the redundant information is parity.

13. The system of claim 11, further comprising:

the redundant information is computed based on algebraic and algorithmic calculations in response a layout of the allocated data.

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.

15. The method as in claim 14, further comprising:

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; and

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.

16. The method as in claim 14, further comprising:

assigning a storage block to hold parity on a storage device which has more storage blocks assigned to hold data than other storage devices in order to balance the load of data across the plurality of storage devices.

17. The method as in claim 14, further comprising:

organizing the storage blocks in stripes across the plurality of storage devices.

18. The method as in claim 14, further comprising:

providing an indication of which storage blocks are to hold parity to a subsystem which writes to the storage devices.

19. The method as in claim 14, further comprising:

using a magnetic disk as the each storage device of the plurality of storage devices.

20. The method as in claim 14, further comprising:

using a RAID system of disks as the plurality of storage devices.

21. The method as in claim 14, further comprising:

using any type of attached array of writeable storage device media as the each storage device.

22. The method as in claim 14, further comprising:

using magnetic tape as the each storage device.

23. The method as in claim 14, further comprising:

using optical memory as the each storage device.

24. The method as in claim 14, further comprising:

using electronic random access memory as the each storage device.

25. The method as in claim 14, further comprising:

using micro-electro mechanical media as the each storage device.

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.

27. The apparatus as in claim 26, further comprising:

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.

28. The apparatus as in claim 26, further comprising:

a storage block assigned to hold parity on a storage device which has more storage blocks assigned to hold data than other storage devices in order to balance the load of data across the plurality of storage devices.

29. The apparatus as in claim 26, further comprising:

the storage blocks organized in stripes across the plurality of storage devices.

30. The apparatus as in claim 26, further comprising:

an indication of which storage blocks are to hold parity given to a subsystem which writes to the storage devices.

31. The apparatus as in claim 26, further comprising:

a magnetic disk used as the each storage device of the plurality of storage devices.

32. The apparatus as in claim 26, further comprising:

a RAID system of disks used as the plurality of storage devices.

33. The apparatus as in claim 26, further comprising:

any type of writeable storage device media used as the plurality of storage devices.

34. The apparatus as in claim 26, further comprising:

magnetic tape used as the each storage device.

35. The apparatus as in claim 26, further comprising:

optical memory used as the plurality of storage devices.

36. The apparatus as in claim 26, further comprising:

electronic random access memory used as the plurality of storage devices.

37. The apparatus as in claim 26, further comprising:

micro-electro mechanical media used as the plurality of storage devices.

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.