Distributed storage resource scheduler and load balancer

• US 8,935,500 B1
• Filed: 11/10/2011
• Issued: 01/13/2015
• Est. Priority Date: 09/24/2009
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Gulati, Ajay, Ahmad, Irfan, Waldspurger, Carl A., Kumar, Chethan
• Primary Examiner(s): Shah, Sanjiv
• Assistant Examiner(s): Waddy, Jr., Edward
• Application Number:
  US13/293,516
• Time in Patent Office: 1,160 Days
• Field of Search: 711/165, 711147-153, 711170-173, 718/105, 718/104
• US Class Current: 711/165
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 11/3485 for I/O devices
• CPC Class Codes: G06F 2201/815 Virtual
• CPC Class Codes: G06F 2206/1012 Load balancing
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Distributed storage resources having multiple storage units are managed based on data collected from online monitoring of workloads on the storage units and performance characteristics of the storage units. The collected data is sampled at discrete time intervals over a time period of interest, such as a congested time period. Normalized load metrics are computed for each storage unit based on time-correlated sums of the workloads running on the storage unit over the time period of interest and the performance characteristic of the storage unit. Workloads that are migration candidates and storage units that are migration destinations are determined from a representative value of the computed normalized load metrics, which may be the 90th percentile value or a weighted sum of two or more different percentile values.

Claims

1. A method of managing distributed storage resources including at least a first storage unit and a second storage unit, comprising:

while the first storage unit and the second storage unit are online, monitoring workloads associated with objects stored in the first storage unit and the second storage unit at multiple points in time over a time interval, and monitoring performance of the first storage unit and the second storage unit, each of the monitored workloads being a function of time-correlated samples of measured data including the number of outstanding input output requests to an associated object and an average size of input output requests to the associated object;

computing normalized load metrics for the first storage unit based on time-correlated sums of the workloads monitored on the first storage unit over the time interval, each of the workloads monitored on the first storage unit over the time interval being associated with a respective one of the objects stored in the first storage unit, and the monitored performance of the first storage unit, wherein each of the time-correlated sums of the workloads monitored on the first storage unit is computed at a respective point in time as a summation of the workloads monitored on the first storage unit at the respective point in time;

computing normalized load metrics for the second storage unit based on time-correlated sums of the workloads monitored on the second storage unit over the time interval, each of the workloads monitored on the second storage unit over the time interval being associated with a respective one of the objects stored in the second storage unit, and the monitored performance of the second storage unit, wherein each of the time-correlated sums of the workloads monitored on the second storage unit is computed at a respective point in time as a summation of the workloads monitored on the second storage unit at the respective point in time; and

identifying one or more of the objects as candidates for migration between the first storage unit and the second storage unit based on the computed normalized load metrics of the first storage unit and the second storage unit.

2. The method of claim 1, wherein the performance of the first storage unit is dependent on a relationship between the number of outstanding input-output requests to the first storage unit and an average latency of input-output requests to the first storage unit at multiple points in time, and the performance of the second storage unit is dependent on a relationship between the number of outstanding input-output requests to the second storage unit and an average latency of input-output requests to the second storage unit at multiple points in time.

3. The method of claim 2, further comprising:

determining that the distributed storage resources are in a congested state at a point in time when one of the storage units at said point in time has an average latency that is greater than a threshold latency,

wherein the time interval covers the points in time during which the distributed storage resources are in the congested state.

4. The method of claim 1, further comprising:

conditionally rejecting an identified object as a candidate for migration between the first storage unit and the second storage unit.

5. The method of claim 4, wherein the rejecting occurs if the first storage unit and the second storage unit are determined to share a physical storage array.

6. The method of claim 4, wherein the first storage unit is a source storage unit and the second storage unit is a destination storage unit, and the rejecting occurs if an average latency associated with the second storage unit is higher than an average latency associated with the first storage unit.

7. The method of claim 4, wherein the rejecting occurs if the first storage unit and second storage unit are determined to share physical hardware resources.

8. The method of claim 4, wherein the first storage unit is a source storage unit and the second storage unit is a destination storage unit, and further comprising:

computing normalized load metrics for the second storage unit based on time-correlated sums of workloads monitored on the second storage unit over another time interval during which the distributed storage resources are determined to be in a less congested state,

wherein the rejecting occurs if a predetermined number of the normalized load metrics computed for the second storage unit over said another time interval exceeds a threshold value.

9. The method of claim 1, wherein the identifying is performed based on a representative normalized load metric of the first storage unit and a representative normalized load metric of the second storage unit.

10. The method of claim 9, wherein the representative normalized load metric is equal to an N-th percentile value of the computed normalized load metrics.

11. The method of claim 9, wherein the representative normalized load metric is equal to a weighted sum of two or more different percentile values of the computed normalized load metrics.

12. The method of claim 1, wherein the workloads are monitored for read requests.

13. The method of claim 1, wherein the workloads are monitored for write requests.

14. The method of claim 1, wherein the measured data further includes a percentage of reads in the input-output requests to the associated object.

15. The method of claim 1, wherein the measured data further include a value representative of the randomness of the input-output requests to the associated object.

16. The method of claim 1, wherein the objects comprise disk images of virtual machines.

17. The method of claim 1, wherein the objects comprise portions of disk images of virtual machines.

18. A method of migrating workloads between a first storage unit and a second storage unit of a shared storage system that includes physically separate storage arrays, comprising:

while the first storage unit and the second storage unit are online, monitoring workloads associated with objects stored in the first storage unit and the second storage unit at multiple points in time over a time interval, each of the monitored workloads being a function of time-correlated samples of measured data including the number of outstanding input output requests to an associated object and an average size of input output requests to the associated object;

computing normalized load metrics for the first storage unit based on time-correlated sums of the workloads monitored on the first storage unit over the time interval, each of the workloads monitored on the first storage unit over the time interval being associated with a respective one of the objects stored in the first storage unit, and a monitored performance of the first storage unit, wherein each of the time-correlated sums of the workloads monitored on the first storage unit is computed at a respective point in time as a summation of the workloads monitored on the first storage unit at the respective point in time;

computing normalized load metrics for the second storage unit based on time-correlated sums of the workloads monitored on the second storage unit over the time interval, each of the workloads monitored on the second storage unit over the time interval being associated with a respective one of the objects stored in the second storage unit, and a monitored performance of the second storage unit, wherein each of the time-correlated sums of the workloads monitored on the second storage unit is computed at a respective point in time as a summation of the workloads monitored on the second storage unit at the respective point in time; and

migrating one of the workloads between the first storage unit and the second storage unit based on the computed normalized load metrics of the first storage unit and the second storage unit.

19. The method of claim 18, further comprising:

determining whether the first storage unit and the second storage unit share a physical storage array.

20. The method of claim 19, further comprising:

running a controlled workload on the first storage unit and the second storage unit together and then separately, and

monitoring response times of the first storage unit and the second storage unit as the controlled workload is run on them together and then separately,

wherein the determining of whether the first storage unit and the second storage unit share the physical storage array is based on the monitored response times.

21. The method of claim 19, further comprising:

running a controlled workload on a physical storage array; and

monitoring latencies of input-output requests,

wherein the determining of whether the first storage unit and the second storage unit share the physical storage array is based on the monitored latencies.

22. The method of claim 21, wherein the controlled workload includes a plurality of random reads across the physical storage array.

23. The method of claim 21, wherein the controlled workload includes file creation and writes to the created file.

24. A non-transitory computer-readable storage medium comprising instructions which, when executed in a computing device coupled to distributed storage resources including at least a first storage unit and a second storage unit, causes the computing device to carry out the steps of:

while the first storage unit and the second storage unit are online, monitoring workloads associated with objects stored in the first storage unit and the second storage unit at multiple points in time over a time interval, and monitoring performance of the first storage unit and the second storage unit, each of the monitored workloads being a function of time-correlated samples of measured data including the number of outstanding input output requests to an associated object and an average size of input output requests to the associated object;

computing normalized load metrics for the first storage unit based on time-correlated sums of the workloads monitored on the first storage unit over the time interval, each of the workloads monitored on the first storage unit over the time interval being associated with a respective one of the objects stored in the first storage unit, and the monitored performance of the first storage unit, wherein each of the time-correlated sums of the workloads monitored on the first storage unit is computed at a respective point in time as a summation of the workloads monitored on the first storage unit at the respective point in time;

computing normalized load metrics for the second storage unit based on time-correlated sums of the workloads monitored on the second storage unit over the time interval, each of the workloads monitored on the second storage unit over the time interval being associated with a respective one of the objects stored in the second storage unit, and the monitored performance of the second storage unit, wherein each of the time-correlated sums of the workloads monitored on the second storage unit is computed at a respective point in time as a summation of the workloads monitored on the second storage unit at the respective point in time; and

identifying one or more of the objects as candidates for migration between the first storage unit and the second storage unit based on the computed normalized load metrics of the first storage unit and the second storage unit.

25. The non-transitory computer-readable storage medium of claim 24, further comprising instructions which, when executed in a computing device, causes the computing device to carry out the steps of:

determining that the distributed storage resources are in a congested state at a point in time when one of the storage units at said point in time has an average latency that is greater than a threshold latency,

wherein the time interval covers the points in time during which the distributed storage resources are in the congested state.

26. A non-transitory computer-readable storage medium comprising instructions which, when executed in a computing device coupled to distributed storage resources including at least a first storage unit and a second storage unit, causes the computing device to carry out the steps of:

while the first storage unit and the second storage unit are online, monitoring workloads on the first storage unit and the second storage unit at multiple points in time over a time interval, each of the monitored workloads being a function of time-correlated samples of measured data including the number of outstanding input output requests to an associated object and an average size of input output requests to the associated object;

computing normalized load metrics for the first storage unit based on time-correlated sums of the workloads monitored on the first storage unit over the time interval;

computing normalized load metrics for the second storage unit based on time-correlated sums of the workloads monitored on the second storage unit over the time interval; and

migrating one of the workloads between the first storage unit and the second storage unit based on the computed normalized load metrics of the first storage unit and the second storage unit.

27. The non-transitory computer-readable storage medium of claim 26, further comprising instructions which, when executed in a computing device, causes the computing device to carry out the steps of:

determining whether the first storage unit and the second storage unit share a physical storage array.