Approach based on self-evolving models for performance guarantees in a shared storage system

• US 7,640,231 B2
• Filed: 11/16/2005
• Issued: 12/29/2009
• Est. Priority Date: 11/16/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Alvarez, Guillermo A., Palmer, John D., Uttamchandani, Sandeep M., Yin, Li
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Quader; Fazlul
• Application Number:
  US11/280,012
• Publication Number:
  US 20070112723A1
• Time in Patent Office: 1,504 Days
• Field of Search: 707/2
• US Class Current: 1/1
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A technique of allocating shared resources in a computer network-based storage system comprises taking periodic performance samples on a running storage system; evaluating an objective function that takes as input the performance samples to quantify how aligned a current state of the storage system is with organizational objectives; building and maintaining models of behavior and capabilities of the storage system by using the performance samples as input; determining how resources of the storage system should be allocated among client computers in the storage system by selecting one among many possible allocations based on predictions generated by the models in order to maximize a value of the objective function; calculating a confidence statistic value for a chosen resource allocation based on an accuracy of the models; and enforcing the chosen resource allocation on the running storage system when the confidence statistic value is at or above a predetermined threshold value.

Claims

1. A computer-implemented method of allocating shared resources in a computer network-based storage system, said method comprising:

taking, using a computer, periodic performance samples on a component of a plurality of components comprising said computer network-based storage system, said computer network-based storage system running an underperforming workload, and each of said periodic performance samples including a component average latency and a component I/O request rate for said component,

wherein said underperforming workload is characterized by exceeding an upper bound on an average latency for a workload, specified by a Service Level Agreement (SLA), when said underperforming workload'"'"'s request rate does not exceed an I/O request rate, also specified by said SLA;

evaluating, using said computer, a set of functions of said computer network-based storage system using said periodic performance samples as input, said models comprising;

a component function for said component that predicts said component average latency based on other workloads running on said component;

a workload function for said component that predicts a load on said component based on I/O request rates of said other workloads; and

an action function for said component that predicts an effect of a throttling action on each other workload'"'"'s I/O request rate;

quantitatively optimizing, using said computer, a second function for said underperforming workload and each of said other workloads that predicts a current I/O request rate and a current average latency for each component of said plurality of components, based on said effect of said throttling action on said each other workloads'"'"' I/O request rate; and

throttling, using said computer, one or more of said other workload'"'"'s request rates, based on said quantitatively optimizing said second function, to free components of said computer network-based storage system, such that, said underperforming workload is transformed into a workload that satisfies said SLA.

2. The method of claim 1, further comprising:

calculating, using said computer, a confidence statistic value for allocating said shared resources based on an accuracy of said set of functions;

maintaining, using said computer, a predetermined set of system designer-defined policies for allocating said shared resources; and

using said set of system designer-defined policies, using said computer, so long as said confidence statistic value is less than a predetermined threshold value.

3. The method of claim 2, wherein said SLA of a plurality of SLAs is associated with a client computer on said computer network-based storage system, and wherein a value of said second function depends on a particular SLA being violated.

4. The method of claim 3, wherein said client computer is assigned a priority such that said second function incorporates said priority to prefer an allocation of said shared resources in which said SLA of said client computer with a higher priority is satisfied.

5. The method of claim 4, wherein said performance samples improve an accuracy of said first set of functions, based on said confidence statistic value, in a periodic and fully-automatic manner and determine when variable system conditions have caused a discontinuous change in a behavior of said computer network-based storage system.

6. The method of claim 5, wherein incremental model refinement is accomplished, using said computer, starting from any of:

a function built by taking performance samples from said computer network-based storage system in a non-production use;

a function built by taking performance samples from said computer network-based storage system in a production use while the first set of functions are not being used to allocate resources; and

a simplified representation of said behavior of said computer network-based storage system.

7. The method of claim 4, wherein said allocation of shared resources among competing client computers is made by solving a constrained optimization problem.

8. The method of claim 1, wherein transforming said underperforming workload to said workload that satisfies said SLA comprises issuing tokens to said one or more other workloads, which are throttled, corresponding to additional I/Os to a backend.

9. The method of claim 8, wherein transitions between current workload token issue rates and lower token issue rates are enforced progressively in steps whose size depends on said confidence statistical value.

10. The method of claim 9, further comprising reassessing, using said computer, token issue rates depending on a change in said current workload of said component.

11. The method of claim 10, further comprising, using said computer, analyzing a current state of performance of said computer network system after a predetermined number of throttling steps.

12. The method of claim 11, wherein token issue rates for one or more said client computers unthrottle their workloads when resources are available.

13. A program storage medium readable by a computer, tangibly embodying a program of instructions executable by said computer to perform computer-implemented method of allocating shared resources in a computer network-based storage system, said method comprising:

taking periodic performance samples on a component of a plurality of components comprising said computer network-based storage system, said computer network-based storage system running an underperforming workload, and each of said periodic performance samples including a component average latency and a component I/O request rate for said component,

wherein said underperforming workload is characterized by exceeding an upper bound on an average latency for a workload, specified by a Service Level Agreement (SLA), when said underperforming workload'"'"'s request rate does not exceed an I/O request rate, also specified by said SLA;

evaluating a set of functions of said computer network-based storage system using said periodic performance samples as input, said set of functions comprising;

a component function for said component that predicts said component average latency based on other workloads running on said component;

a workload function for said component that predicts a load on said component based on I/O request rates of said other workloads; and

an action function for said component that predicts an effect of a throttling action on each other workload'"'"'s I/O request rate;

quantitatively optimizing a second function for said underperforming workload and each of said other workloads that predicts a current I/O request rate and a current average latency for each component of said plurality of components, based on said effect of said throttling action on said each other workloads'"'"' I/O request rate

throttling one or more of said other workload'"'"'s request rates, based on said quantitatively optimizing said second function, to free components of said computer network-based storage system, such that, said underperforming workload is transformed into a workload that satisfies said SLA.

14. The program storage medium of claim 13, wherein said method further comprises:

calculating a confidence statistic value for said allocation of resources based on an accuracy of said set of models;

maintaining a predetermined set of system designer-defined policies for said allocation of shared resources; and

using said set of system designer-defined policies so long as said confidence statistic value is less than said predetermined threshold value.

15. The program storage medium of claim 14, wherein said SLA of a plurality of SLAs is associated with a client computer on said computer network-based storage system, and wherein a value of said second function depends on a particular SLA being violated.

16. The program storage medium of claim 15, wherein said client computer is assigned a priority such that said second function incorporates said priority to prefer an allocation of said shared resources in which said SLA of said client computer with a higher priority is satisfied.

17. The program storage medium of claim 16, wherein said performance samples improve an accuracy of said models, based on said confidence statistic value, in a periodic and fully-automatic manner and determine when variable system conditions have caused a discontinuous change in a behavior of said computer network-based storage system.

18. The program storage medium of claim 17, wherein incremental function refinement is accomplished using any of:

a function built by taking performance samples from said computer network-based storage system in a non-production use;

a function built by taking performance samples from said computer network-based storage system in a production use while models are not being used to allocate resources; and

a simplified representation of said behavior of said computer network-based storage system.

19. The program storage medium of claim 16, wherein said allocation of shared resources among competing client computers is made by solving a constrained optimization problem.

20. The program storage medium of claim 13, wherein transforming said underperforming workload to said workload that satisfies said SLA comprises issuing tokens to said one or more other workloads, which are throttled, corresponding to additional I/Os to a backend.

21. The program storage medium of claim 20, wherein transitions between current workload token issue rates and lower token issue rates are enforced progressively in steps whose size depends on said confidence statistical value.

22. The program storage medium of claim 21, wherein said method further comprises reassessing token issue rates depending on a change in said current workload of said component.

23. The program storage medium of claim 22, wherein said method further comprises analyzing a current state of performance of said computer network system after a predetermined number of throttling steps.

24. The program storage medium of claim 23, wherein token issue rates for one or more said client computers unthrottle their workloads when resources are available.

25. A computer-implemented system for allocating shared resources in a computer network-based storage system comprising:

a processor for taking periodic performance samples on a component of a plurality of components comprising said computer network-based storage system, said computer network-based storage system running an underperforming workload, and each of said periodic performance samples including a component average latency and a component I/O request rate for said component,

wherein said underperforming workload is characterized by exceeding an upper bound on an average latency for a workload, specified by a Service Level Agreement (SLA), when said underperforming workload'"'"'s request rate does not exceed an I/O request rate, also specified by said SLA;

a processor for evaluating a set of functions of said computer network-based storage system using said periodic performance samples as input, said set of functions comprising;

a component function for said component that predicts said component average latency based on other workloads;

a workload function for said component that predicts a load on said component based on I/O request rates of said other workloads; and

an action function for said component that predicts an effect of a throttling action on each other workload'"'"'s I/O request rate;

quantitatively optimizing a second function for said underperforming workload and each of said other workloads that predicts a current I/O request rate and a current average latency for each component of said plurality of components, based on said effect of said throttling action on said each other workloads'"'"' I/O request rate

throttling one or more of said other workload'"'"'s request rates, based on said quantitatively optimizing said second function, to free components of said computer network-based storage system, such that, said underperforming workload is transformed into a workload that satisfies said SLA.