Technique to avoid cascaded hot spotting

• US 7,975,102 B1
• Filed: 08/06/2007
• Issued: 07/05/2011
• Est. Priority Date: 08/06/2007
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Jernigan, Richard Parvin IV, Schmersal, Bryan Todd, Hyer, Robert Wyckoff Jr.
• Primary Examiner(s): Elmore; Reba I
• Application Number:
  US11/834,412
• Time in Patent Office: 1,429 Days
• Field of Search: 711/114, 711/216
• 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 method for striping a data container across a striped volume set, the method comprising the steps of:

using a locate function that accepts, as an input, an inode number of the data container and an offset value indicating an offset into the data container for striping, as follows;

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

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 data container by indexing, using the inode number, into an array having values that are selected to be mutually prime with the size of the ordered list of volumes;

calculating a second hash value of the inode associated with the data container;

calculating a final value by multiplying the intermediate value by at least one hash value modulo the number of volumes of the striped volume set; and

identifying a volume containing a desired data container by utilizing the calculated final value for indexing into the striping table to identify and locate a volume that provides a new location to commence striping the data container across a striped volume set, wherein hot spotting is avoided.

2. The method of claim 1, wherein the second hash value comprises an offset divided by a stripe width multiplied by a constant value.

3. A method for striping one or more data containers across a striped volume set serviced by at least one node having a processor, the method comprising:

associating the striped volume set with at least one striping rule, and defining at least one striping rule utilizing an inode number of the data container, offset value within the data container, a number of volumes in the striped volume set and an ordered set of volumes within the striped volume set, and generating a hash value to identify a data placement pattern to utilize;

associating a first data container with a first data placement pattern based on a first inode number associated with the first data container; and

associating a second data container with a second data placement pattern based on a second inode number associated with the second data container, the second data placement pattern different from the first data placement pattern to reduce a possibility of hotspots arising due to each data container using the same data placement pattern within the striped volume set.

4. The method of claim 3 wherein defining the at least one striping rule further comprises utilizing an inode number of the data container, offset value within the data container, a number of volumes in the striped volume set and an ordered set of volumes within the striped volume set.

5. The method of claim 3 further comprising generating a hash value to identify a data placement pattern to utilize.

6. The method of claim 5 wherein generating the hash value further comprises using an inode number of the data container to index into a table containing possible hash values.

7. The method of claim 6 wherein the numbers are mutually prime.

8. The method of claim 3 wherein the first and the second data placement patterns are selected from a set of data placement patterns.

9. The method of claim 8 wherein the set of data placement patterns contain an equal number of elements as a hash table used to identify a data placement pattern.

10. The method of claim 3 wherein the first and second data containers comprise files.

11. A method for striping a data container across a striped volume set, the method comprising:

using a locate function to accept, as an input, an inode number of the data container and an offset value indicating an offset into the data container for striping, as follows;

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

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

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

calculating, by the processor, a final value by multiplying the intermediate value by the hash value modulo the 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 data container across a striped volume set wherein hotspotting is avoided.

12. The method of claim 11 wherein calculating the hash value comprises using an inode number to index into a table containing possible hash values.

13. The method of claim 11 wherein the numbers are selected to be mutually prime.

14. The method of claim 11 wherein calculating the first value further comprises caching the calculated first value in a configuration table.

15. The method of claim 14 wherein caching the calculated first value further comprises using one or more storage devices to store configuration information provided by one or more management processes.

16. The method of claim 11 wherein identifying the volume further comprises using the final value to index into an array of volumes to identify the volume containing the desired data.

17. The method of claim 11 wherein the data container comprises a file.

18. A system for striping a data container across a striped volume set, the system comprising:

a storage operating system, comprising a processor, configured to associate the striped volume set with at least one striping rule, wherein the data container being striped defines the at least one striping rule wherein said striping rule utilizes an inode number at said data container, offset value within the data container, a number of volumes in the striped volume set and an ordered set of volumes within the striped volume set, and generating a hash value to identify a data placement pattern; and

wherein the at least one striping rule comprises a first data placement pattern to associate with a first data container based on a first inode number associated with the first data container and a second data placement pattern to associate with a second data container based on a second inode number associated with the second data container, the second data placement pattern different from the first data placement pattern to reduce a possibility of hotspots arising due to each data container using the same data placement pattern within the striped volume set.

19. The system of claim 18 wherein the striping rule further comprises an inode number of the data container, offset value within the data container, a number of volumes in the striped volume set and an ordered set of volumes within the striped volume set.

20. The system of claim 18 wherein a hash value is generated to identify a data placement pattern to utilize.

21. The system of claim 19 wherein the hash value further comprises an inode number of the data container used to index into a table containing possible hash values.

22. The system of claim 21 wherein the numbers are mutually prime.

23. The system of claim 18 wherein the first and the second data placement patterns are selected from a set of data placement patterns.

24. The system of claim 23 wherein the set of data placement patterns contain an equal number of elements as a hash table used to identify a data placement pattern.

25. The system of claim 18 wherein the first and second data containers comprise files.

26. A non-transitory computer readable medium containing executable program instructions executed by a processor, comprising:

program instructions that calculate a first value by adding an inode number to an offset value divided by a stripe width modulo a striping table size associated with a striped volume set;

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

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

program instructions that calculate a second hash value of the inode associated with the data container; and

program instructions for identifying a volume containing a desired data container by utilizing the calculated final value for indexing into the striping table to identify and locate a volume that provides a new location to commence striping the data container across a striped volume set, wherein hot spotting is avoided.

27. A system for striping a data container across a striped volume set serviced by at least one node comprising a processor, the system comprising:

means for calculating a first value by adding an inode number to an offset value divided by a stripe width modulo a striping table size;

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

means for calculating a first hash value of an inode associated with the data container;

means for calculating a second hash value of the inode associated with the data container;

means for calculating a final value by multiplying the intermediate value by at least one hash value modulo the number of volumes of the striped volume set; and

means for identifying a volume containing a desired data container utilizing the calculated final value for indexing into the striping table to identify and locate a volume that provides a new location to commence striping the data container across a striped volume set.

28. A system for striping a data container across a striped volume set, the system comprising:

a storage operating system, comprising a processor, configured to associate the striped volume set with at least one striping rule, wherein the data container being striped defines the at least one striping rule wherein said striping rule utilizes an inode number at said data container, offset value within the data container, a number of volumes in the striped volume set and an ordered set of volumes within the striped volume set, and generating a hash value to identify a data placement pattern; and

wherein the at least one striping rule comprises a first data placement pattern to associate with a region of a first data container based on a first hash value associated with the region of the first data container and a second data placement pattern to associate with another region of the first data container based on a second hash value associated with the another region of the first data container, the second data placement pattern is different from the first data placement pattern to reduce a possibility of hotspots arising due to each data container using the same data placement pattern within the striped volume set.