Technique to avoid cascaded hot spotting

• US 8,560,773 B1
• Filed: 05/26/2011
• Issued: 10/15/2013
• Est. Priority Date: 08/06/2007
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Hyer, Robert Wyckoff Jr., Jernigan, Richard Parvin IV, Schmersal, Bryan Todd
• Primary Examiner(s): Elmore, Reba I
• Application Number:
  US13/116,356
• Time in Patent Office: 873 Days
• Field of Search: 711/114, 707/609
• US Class Current: 711/114
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

The present invention overcomes the disadvantages of the prior art by providing a technique that stripes data containers across volumes of a striped volume set (SVS) using one of a plurality of different data placement patterns to thereby reduce the possibility of hotspots arising due to each data container using the same data placement pattern within the SVS. The technique is illustratively implemented by calculating a first index value, an intermediate index value and calculating a hash value of an mode associated with a data container to be accessed within the SVS. A final index value is calculated by multiplying the intermediate index value by the hash value, modulo the number of volumes of the SVS. Further, a Locate( ) function may be used to compute the location of data container content in the SVS to which a data access request is directed to ensure consistency of such content.

Claims

1. A system for striping a plurality of data containers across a striped volume set, comprising:

a plurality of nodes interconnected as a cluster, each node having a processor, a network element, and a data element;

the network element of each node configured to receive data access requests directed to a striped volume set, the network element further configured to;

use a locate function to identify a volume using an inode number and offset values indicating an offset into each data container for striping;

use a volume location database to identify the data element hosting the identified volume for each data container; and

forward the received data access requests to the identified data element for each data container; and

the identified data element configured to process a first data access request associated with a first data container using a first data placement pattern used to stripe the first data container across the striped volume set, wherein the first data placement pattern is selected based on a first inode number associated with the first data container,

the identified data element further configured to process a second data access request associated with a second data container using a second data placement pattern used to stripe the second data container across the striped volume set, wherein the second data placement pattern is based on a second inode number associated with the second data container and wherein the second data placement pattern is different from the first data placement pattern.

2. The system as defined in claim 1 wherein the first data placement pattern is used alternately with the second data placement pattern for striping into the first data container to reduce hotspots arising due to each data container using a same data placement pattern.

3. The system as defined in claim 1 wherein the first data container and second data container comprise files.

4. The system as defined in claim 1 wherein the network element is further configured to:

calculate a first value by adding the first inode number to a first offset value divided by a stripe width modulo a size of a striping table;

calculate an intermediate value by indexing the first value into an ordered list of volumes;

calculate a hash value of an inode associated with the first data container by indexing, using the first inode number, into an array having values that are selected to be mutually prime with a size of the ordered list of volumes;

calculate a final value by multiplying the intermediate value by the hash value modulo a number of volumes of the striped volume set; and

index into the striping table using the final value to identify and locate the volume that provides a new location to commence striping the first data container across the striped volume set wherein hotspotting is avoided.

5. The system as defined in claim 1 wherein the first data placement pattern and the second data placement patterns are selected from a set of data placement patterns.

6. The system as defined in claim 5 wherein the set of data placement patterns contains an equal number of items used by a hash table to identify a selected data placement pattern.

7. The system as defined in claim 1 wherein the network element is further configured to associate the striped volume set with at least one striping rule, and the at least one striping rule utilizing the first inode number of the first data container, and at least one of a first offset value into the first data container, a number of volumes in the striped volume set and an ordered set of volumes within the striped volume set to generate a hash value to identify the first data placement pattern.

8. The system as defined in claim 7 wherein to generate the hash value further comprises using the first inode number of the first data container to index into a table containing available hash values.

9. The system as defined in claim 8 wherein the first inode number and the second inode number are mutually prime.

10. A non-transitory computer readable medium containing executable program instructions executed by a processor in a computer network configured as a cluster of a plurality of nodes, comprising:

program instructions that configure a network element of each node to receive data access requests directed to a striped volume set, program instructions that further configure the network element to;

use a locate function to identify a volume using an inode number and offset values into each data container for striping;

use a volume location database to identify a data element hosting the identified volume, of the striped volume set, for each data container;

forward the received data access requests to the identified data element for each data container;

process a first data access request using a first data placement pattern used to stripe a first data container across the striped volume set, wherein the first data placement pattern is selected based on a first inode number associated with the first data container; and

process a second data access request using a second data placement pattern used to stripe a second data container across the striped volume set, wherein the second data placement pattern is selected based on a second inode number associated with the second data container, and wherein the second data placement pattern is different form the first data placement pattern so as to avoid hot spotting.

11. The computer readable medium of claim 10, wherein the program instructions that configure the network element further comprise program instructions that:

calculate a first value by adding the first inode number to a first offset value associated with the first data container, divided by a stripe width modulo a size of a striping table;

calculate an intermediate value by indexing the first value into an ordered list of volumes;

calculate a hash value of an inode associated with the first data container by indexing, using the first inode number, into an array having values that are selected to be mutually prime with a size of the ordered list of volumes;

calculate a final value by multiplying the intermediate value by the hash value modulo a number of volumes of the striped volume set; and

index into a striping table using the final value to identify and locate the volume that provides a new location to commence striping the first data container across the striped volume set wherein hotspotting is avoided.

12. The computer readable medium of claim 10 wherein the program instructions that configure the network element further comprise:

program instructions that associate the striped volume set with at least one striping rule that utilizes the first inode number of the first data container, a first offset value into the first data container, a number of volumes in the striped volume set and an ordered set of volumes within the striped volume set to generate a hash value to identify the first data placement pattern.

13. The computer readable medium of claim 10 wherein the first data placement pattern is used alternately with the second data placement pattern for striping into the first data container to reduce hotspots arising due to each data container using a same data placement pattern.

14. A method of striping a data container across a striped volume set, comprising:

coupling a network element to a data element, of a node having a processor, that serves data access requests for a striped volume set, the network element configured to associate a first data container with a first data placement pattern, utilized to stripe the first data container across the striped volume set, based on a first inode number associated with the first data container;

configuring the network element to further associate a second data container with a second data placement pattern, utilized to stripe the second data container across the striped volume set, based on a second inode number associated with the second data container, the second data placement pattern different from the first data placement pattern, wherein the first data placement pattern is used alternately with the second data placement pattern for striping into the first data container to reduce hotspots arising due to each data container using a same data placement pattern.

15. The method of striping a data container across a striped volume set as defined in claim 14 further comprising:

configuring the striped volume set with at least one striping rule, and the at least one striping rule utilizes the first inode number of the first data container, an offset value into the first data container, a number of volumes in the striped volume set and an ordered set of volumes within the striped volume set to generate a hash value to identify the first data placement pattern.

16. The method of striping a data container across a striped volume set as defined in claim 15 further comprising:

calculating a first value by adding the first inode number to said offset value divided by a stripe width modulo a size of a striping table;

calculating an intermediate value by indexing the first value into an ordered list of volumes;

calculating, a hash value of an inode associated with the first data container by indexing, using the first inode number, into an array having values that are selected to be mutually prime with a size of the ordered list of volumes;

calculating, by the processor, a final value by multiplying the intermediate value by the hash value modulo a number of volumes of the striped volume set; and

indexing into the striping table using the final value to identify and locate a volume that provides a new location to commence striping the first data container across the striped volume set wherein hotspotting is avoided.