System for determining the order and frequency in which space is allocated on individual storage devices

• US 6,829,678 B1
• Filed: 07/18/2000
• Issued: 12/07/2004
• Est. Priority Date: 07/18/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Haskin, Roger L., Wyllie, James C., Sawdon, Wayne A., Schmuck, Frank B.
• Primary Examiner(s): Peikari, B. James
• Application Number:
  US09/618,332
• Time in Patent Office: 1,603 Days
• Field of Search: 711/4, 711/111, 711/112, 711/114, 711/157, 711/170, 711/172, 711/173, 713/330
• US Class Current: 711/114
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Space is allocated on data storage devices in proportion to weights associated with the storage devices. The weights can be dynamically adjusted at any time in order to accommodate changes in the system and to better utilize the storage devices. The technique used to perform the allocating is independent of the weights used by the allocating. Further, the allocation technique can accommodate general purpose data streams having varying lengths and/or varying access patterns, as well as special purpose data streams, such as video streams.

Claims

1. A method of managing the allocation of space on data storage devices, said method comprising:

obtaining weights for at least a subset of a plurality of data storage devices, said subset comprising at least two data storage devices; and

allocating space on multiple data storage devices of said at least a subset of data storage devices in proportion to weights obtained for the multiple data storage devices, wherein said allocating is independent of access patterns of data to be accommodated by the allocated space in that said allocating is performed without a priori knowledge of said access patterns, and wherein said allocating comprises generating a data stripe order to be used in allocating said space, said data stripe order indicating an order and frequency of allocating space on said multiple storage devices.

2. The method of claim 1, wherein different allocation techniques can be used in allocating said space.

3. The method of claim 1, wherein said allocating is independent of the obtaining of said weights, wherein the allocating is performed without knowledge of at least one of what the weights represent and how the weights were obtained.

4. The method of claim 1, further comprising dynamically adjusting one or more of the weights, and allocating space on one or more data storage devices using said one or more dynamically adjusted weights.

5. The method of claim 4, wherein said one or more weights were previously obtained using a first weighting technique based on a first parameter, and wherein said dynamically adjusting comprises using at least one second weighting technique in adjusting said one or more weights, wherein said at least one second weighting technique is based on at least one second parameter, wherein one or more parameters of said at least one second parameter differ from said first parameter.

6. The method of claim 1, wherein at least one data storage device of said multiple data storage devices has one or more different characteristics than at least one other data storage device of said multiple data storage devices.

7. The method of claim 1, wherein said allocating comprises:

normalizing the weights of the multiple data storage devices to obtain multiple normalized weights; and

using said multiple normalized weights in allocating space on said multiple data storage devices.

8. The method of claim 1, wherein said generating comprises:

selecting a data storage device of said multiple data storage devices having a lowest current position, said selected data storage device being included in the data stripe order;

updating the current position of the selected data storage device; and

repeating said selecting and said updating until a desired data stripe order is generated.

9. The method of claim 8, wherein said updating the current position comprises incrementing the current position by an average allocation distance of the selected data storage device.

10. The method of claim 9, further comprising determining said average allocation distance, said determining comprising dividing a sum of normalized weights of said multiple data storage devices by a normalized weight of said selected data storage device.

11. The method of claim 8, wherein said allocating further comprises resetting a current position of one or more data storage devices of said multiple data storage devices.

12. The method of claim 1, further comprising normalizing one or more of the weights obtained for the multiple data storage devices, wherein at least one normalized weight is used in said generating.

13. The method of claim 12, wherein said generating comprises:

selecting a data storage device of said multiple data storage devices to be included in said data stripe order, said selecting comprising summing at least one integer portion of at least one normalized weight of the one or more normalized weights until a selected number is reached, wherein the data storage device associated with the last integer portion summed is the selected data storage device; and

repeating said selecting until a desired data stripe order is generated.

14. The method of claim 13, wherein the selected number is a random number chosen between 1 and a number of allocations remaining in a cycle of allocations.

15. The method of claim 14, further comprising determining a total number of allocations in said cycle of allocations, said determining comprising summing integer portions of normalized weights associated with the multiple data storage devices.

16. A method of managing the allocation of space on data storage devices, said method comprising:

obtaining weights for at least a subset of a plurality of data storage devices; and

generating a data stripe order using one or more of the weights, said data stripe order indicating an order and frequency of allocating space on multiple data storage devices of said plurality of data storage devices, and wherein the generating is independent of a weighting assignment used in obtaining said weights.

17. The method of claim 16, further comprising allocating space on said multiple data storage devices using said data stripe order, such that the space on each data storage device of said multiple data storage devices is consumed in proportion to the weight associated with that data storage device.

18. The method of claim 16, wherein said data stripe order is used in allocating space on each data storage device of said multiple data storage devices to accommodate general data streams, in which at least one of a length of the general data streams and access patterns of the general data streams are not known a priori.

19. The method of claim 16, wherein said generating comprises:

selecting a data storage device of said multiple data storage devices having a lowest current position, said selected data storage device being included in the data stripe order;

updating the current position of the selected data storage device; and

repeating said selecting and said updating until a desired data stripe order is generated.

20. The method of claim 19, wherein the current position of the selected data storage device is determined using the obtained weight of said data storage device, in which the obtained weight has been normalized.

21. The method of claim 16, further comprising normalizing one or more of the weights obtained for the multiple data storage devices, wherein at least one normalized weight is used in said generating.

22. The method of claim 21, wherein said generating comprises:

selecting a data storage device of said multiple data storage devices to be included in said data stripe order, said selecting comprising summing at least one integer portion of at least one normalized weight of the one or more normalized weights until a selected number is reached, wherein the data storage device associated with the last integer portion summed is the selected data storage device; and

repeating said selecting until a desired data stripe order is generated.

23. The method of claim 16, wherein said data stripe order is associated with a file.

24. The method of claim 23, further comprising generating another data stripe order for another file, wherein said data stripe order and said another data stripe order are used by one or more file systems to allocate space.

25. A system of managing the allocation of space on data storage devices, said system comprising:

means for obtaining weights for at least a subset of a plurality of data storage devices, said subset comprising at least two data storage devices; and

means for allocating space on multiple data storage devices of said at least a subset of data storage devices in proportion to weights obtained for the multiple data storage devices, wherein the allocating is independent of access patterns of data to be accommodated by the allocated space in that said means for allocating lacks a priori knowledge of said access patterns, and wherein said means for allocating comprises means for generating a data stripe order to be used in allocating said space, said data stripe order indicating an order and frequency of allocating space on said multiple storage devices.

26. The system of claim 25, wherein said means for allocating can comprise different allocation techniques to be used in allocating said space.

27. The system of claim 25, wherein said means for allocating is independent of the means for obtaining said weights, wherein the means for allocating need not have knowledge of at least one of what the weights represent and how the weights were obtained.

28. The system of claim 25, further comprising means for dynamically adjusting one or more of the weights, and means for allocating space on one or more data storage devices using the one or more dynamically adjusted weights.

29. The system of claim 28, wherein said one or more weights were previously obtained using a first weighting technique based on a first parameter, and wherein said means for dynamically adjusting comprises means for using at least one second weighting technique in adjusting said one or more weights, wherein said at least one second weighting technique is based on at least one second parameter, wherein one or more parameters of said at least one second parameter differ from said first parameter.

30. The system of claim 25, wherein at least one data storage device of said multiple data storage devices has one or more different characteristics than at least one other data storage device of said multiple data storage devices.

31. The system of claim 25, wherein said means for allocating comprises:

means for normalizing the weights of the multiple data storage devices to obtain multiple normalized weights; and

means for using said multiple normalized weights in allocating space on said multiple data storage devices.

32. The system of claim 25, wherein said means for generating comprises:

means for selecting a data storage device of said multiple data storage devices having a lowest current position, said selected data storage device being included in the data stripe order;

means for updating the current position of the selected data storage device; and

means for repeating the selecting and the updating until a desired data stripe order is generated.

33. The system of claim 32, wherein said means for updating the current position comprises means for incrementing the current position by an average allocation distance of the selected data storage device.

34. The system of claim 33, further comprising means for determining said average allocation distance, said determining comprising means for dividing a sum of normalized weights of said multiple data storage devices by a normalized weight of said selected data storage device.

35. The system of claim 32, wherein said means for allocating further comprises means for resetting a current position of one or more data storage devices of said multiple data storage devices.

36. The system of claim 35, further comprising means for normalizing one or more of the weights obtained for the multiple data storage devices, wherein at least one normalized weight is used in the generating.

37. The system of claim 36, wherein said means for generating comprises:

means for selecting a data storage device of said multiple data storage devices to be included in said data stripe order, said means for selecting comprising means for summing at least one integer portion of at least one normalized weight of the one or more normalized weights until a selected number is reached, wherein the data storage device associated with the last integer portion summed is the selected data storage device; and

means for repeating the selecting until a desired data stripe order is generated.

38. The system of claim 37, wherein the selected number is a random number chosen between 1 and a number of allocations remaining in a cycle of allocations.

39. The system of claim 38, further comprising means for determining a total number of allocations in said cycle of allocations, said means for determining comprising means for summing integer portions of normalized weights associated with the multiple data storage devices.

40. A system of managing the allocation of space on data storage devices, said system comprising:

means for obtaining weights for at least a subset of a plurality of data storage devices; and

means for generating a data stripe order using one or more of the weights, said data stripe order indicating an order and frequency of allocating space on multiple data storage devices of said plurality of data storage devices, and wherein the generating is independent of a weighting assignment used in obtaining said weights.

41. The system of claim 40, further comprising means for allocating space on said multiple data storage devices using said data stripe order, such that the space on each data storage device of said multiple data storage devices is consumed in proportion to the weight associated with that data storage device.

42. The system of claim 40, wherein said data stripe order is used in allocating space on each data storage device of said multiple data storage devices to accommodate general data streams, in which at least one of a length of the general data streams and access patterns of the general data streams are not known a priori.

43. The system of claim 40, wherein said means for generating comprises:

means for selecting a data storage device of said multiple data storage devices having a lowest current position, said selected data storage device being included in the data stripe order;

means for updating the current position of the selected data storage device; and

means for repeating the selecting and the updating until a desired data stripe order is generated.

44. The system of claim 43, wherein the current position of the selected data storage device is determined using the obtained weight of said data storage device, in which the obtained weight has been normalized.

45. The system of claim 40, further comprising means for normalizing one or more of the weights obtained for the multiple data storage devices, wherein at least one normalized weight is used in the generating.

46. The system of claim 45, wherein said means for generating comprises:

means for selecting a data storage device of said multiple data storage devices to be included in said data stripe order, said means for selecting comprising means for summing at least one integer portion of at least one normalized weight of the one or more normalized weights until a selected number is reached, wherein the data storage device associated with the last integer portion summed is the selected data storage device; and

means for repeating the selecting until a desired data stripe order is generated.

47. The system of claim 40, wherein said data stripe order is associated with a file.

48. The system of claim 47, further comprising means for generating another data stripe order for another file, wherein said data stripe order and said another data stripe order are used by one or more file systems to allocate space.

49. A system of managing the allocation of space on data storage devices, said system comprising:

a node adapted to obtain weights for at least a subset of a plurality of data storage devices, said subset comprising at least two data storage devices; and

said node being further adapted to allocate space on multiple data storage devices of said at least a subset of data storage devices in proportion to weights obtained for the multiple data storage devices, wherein the allocating is independent of access patterns of data to be accommodated by the allocated space in that said allocating is performed without a priori knowledge of said access patterns, and wherein the allocating comprises generating a data stripe order to be used in allocating said space, said data stripe order indicating an order and frequency of allocating space on said multiple storage devices.

50. A system of managing the allocation of space on data storage devices, said system comprising:

a node adapted to obtain weights for at least a subset of a plurality of data storage devices; and

said node being further adapted to generate a data stripe order using one or more of the weights, said data stripe order indicating an order and frequency of allocating space on multiple data storage devices of said plurality of storage devices, and wherein the generating is independent of a weighting assignment used in obtaining said weights.

51. At least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method of managing the allocation of space on data storage devices, said method comprising:

obtaining weights for at least a subset of a plurality of data storage devices, said subset comprising at least two data storage devices; and

allocating space on multiple data storage devices of said at least a subset of data storage devices in proportion to weights obtained for the multiple data storage devices, wherein said allocating is independent of access patterns of data to be accommodated by the allocated space in that said allocating is performed without a priori knowledge of said access patterns, and wherein said allocating comprises generating a data stripe order to be used in allocating said space, said data stripe order indicating an order and frequency of allocating space on said multiple storage devices.

52. The at least one program storage device of claim 51, wherein different allocation techniques can be used in allocating said space.

53. The at least one program storage device of claim 51, wherein said allocating is independent of the obtaining of said weights, wherein the allocating is performed without knowledge of at least one of what the weights represent and how the weights were obtained.

54. The at least one program storage device of claim 51, wherein said method further comprises dynamically adjusting one or more of the weights, and allocating space on one or more data storage devices using said one or more dynamically adjusted weights.

55. The at least one program storage device of claim 54, wherein said one or more weights were previously obtained using a first weighting technique based on a first parameter, and wherein said dynamically adjusting comprises using at least one second weighting technique in adjusting said one or more weights, wherein said at least one second weighting technique is based on at least one second parameter, wherein one or more parameters of said at least one second parameter differ from said first parameter.

56. The at least one program storage device of claim 51, wherein at least one data storage device of said multiple data storage devices has one or more different characteristics than at least one other data storage device of said multiple data storage devices.

57. The at least one program storage device of claim 51, wherein said allocating comprises:

normalizing the weights of the multiple data storage devices to obtain multiple normalized weights; and

using said multiple normalized weights in allocating space on said multiple data storage devices.

58. The at least one program storage device of claim 51, wherein said generating comprises:

selecting a data storage device of said multiple data storage devices having a lowest current position, said selected data storage device being included in the data stripe order;

updating the current position of the selected data storage device; and

repeating said selecting and said updating until a desired data stripe order is generated.

59. The at least one program storage device of claim 58, wherein said updating the current position comprises incrementing the current position by an average allocation distance of the selected data storage device.

60. The at least one program storage device of claim 59, wherein said method further comprises determining said average allocation distance, said determining comprising dividing a sum of normalized weights of said multiple data storage devices by a normalized weight of said selected data storage device.

61. The at least one program storage device of claim 58, wherein said allocating further comprises resetting a current position of one or more data storage devices of said multiple data storage devices.

62. The at least one program storage device of claim 51, wherein said method further comprises normalizing one or more of the weights obtained for the multiple data storage devices, wherein at least one normalized weight is used in said generating.

63. The at least one program storage device of claim 62, wherein said generating comprises:

selecting a data storage device of said multiple data storage devices to be included in said data stripe order, said selecting comprising summing at least one integer portion of at least one normalized weight of the one or more normalized weights until a selected number is reached, wherein the data storage device associated with the last integer portion summed is the selected data storage device; and

repeating said selecting until a desired data stripe order is generated.

64. The at least one program storage device of claim 63, wherein the selected number is a random number chosen between 1 and a number of allocations remaining in a cycle of allocations.

65. The at least one program storage device of claim 64, wherein said method further comprises determining a total number of allocations in said cycle of allocations, said determining comprising summing integer portions of normalized weights associated with the multiple data storage devices.

66. At least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method of managing the allocation of space on data storage devices, said method comprising:

obtaining weights for at least a subset of a plurality of data storage devices; and

generating a data stripe order using one or more of the weights, said data stripe order indicating an order and frequency of allocating space on multiple data storage devices of said plurality of data storage devices, and wherein the generating is independent of a weighting assignment used in obtaining said weights.

67. The at least one program storage device of claim 66, wherein said method further comprises allocating space on said multiple data storage devices using said data stripe order, such that the space on each data storage device of said multiple data storage devices is consumed in proportion to the weight associated with that data storage device.

68. The at least one program storage device of claim 66, wherein said data stripe order is used in allocating space on each data storage device of said multiple data storage devices, to accommodate general data streams in which at least one of a length of the general data streams and access patterns of the general data streams are not known a priori.

69. The at least one program storage device of claim 66, wherein said generating comprises:

selecting a data storage device of said multiple data storage devices having a lowest current position, said selected data storage device being included in the data stripe order;

updating the current position of the selected data storage device; and

repeating said selecting and said updating until a desired data stripe order is generated.

70. The at least one program storage device of claim 69, wherein the current position of the selected data storage device is determined using the obtained weight of said data storage device, in which the obtained weight has been normalized.

71. The at least one program storage device of claim 66, wherein said method further comprises normalizing one or more of the weights obtained for the multiple data storage devices, wherein at least one normalized weight is used in said generating.

72. The at least one program storage device of claim 71, wherein said generating comprises:

selecting a data storage device of said multiple data storage devices to be included in said data stripe order, said selecting comprising summing at least one integer portion of at least one normalized weight of the one or more normalized weights until a selected number is reached, wherein the data storage device associated with the last integer portion summed is the selected data storage device; and

repeating said selecting until a desired data stripe order is generated.

73. The at least one program storage device of claim 66, wherein said data stripe order is associated with a file.

74. The at least one program storage device of claim 73, wherein said method further comprises generating another data stripe order for another file, wherein said data stripe order and said another data stripe order are used by one or more file systems to allocate space.