Patent Publication Number: US-8527996-B2

Title: Method and system for performing a combination of throttling server, throttling network and throttling a data storage device by employing first, second and third single action tools

Description:
FIELD OF THE INVENTION 
     The present invention relates to a data processing method and system for managing operations in a data center to enforce service level agreements, and more particularly to a technique for throttling different operations of applications that share resources. 
     BACKGROUND OF THE INVENTION 
     An enterprise data center environment has multiple applications that share server, network, and storage device resources. Most application deployments are preceded by a planning phase ensuring an initial resource allocation optimization based on the application service level agreement (SLA). With growing virtualization of server, network, and storage resources, there is continuous optimization in data center operations that may invalidate the initial resource allocation optimization. Application performance degradation is caused by interference from other applications sharing finite resources. Known throttling techniques to address application performance degradation provide insufficient coordination of different types of operation throttling. Furthermore, known throttling techniques fail to adequately take into account sub-workloads (e.g., data replication, data backup, and archiving) and workload dependencies. Thus, there exists a need to overcome at least one of the preceding deficiencies and limitations of the related art. 
     SUMMARY OF THE INVENTION 
     In one embodiment, the present invention provides a computer-implemented method of throttling a plurality of operations of a plurality of applications that share a plurality of resources. The method comprises: 
     receiving an observed workload that is observed on a data storage system and a predicted workload that is predicted to be on the data storage system; 
     computing a difference between the observed workload and the predicted workload; 
     determining whether or not the difference exceeds a predefined threshold for distinguishing between a first mode (normal mode) of a multi-strategy finder and a second mode (unexpected mode) of the multi-strategy finder; 
     a processor of a computer system determining a final schedule of one or more actions that improve a utility of the data storage system, wherein, if the difference does not exceed the predefined threshold, determining the final schedule includes applying a recursive greedy pruning-lookback-lookforward process to construct and prune each tree of a plurality of trees, wherein a result of the recursive greedy pruning-lookback-lookforward process applied to a tree of the plurality of trees is a first set of one or more actions occurring in a sub-window of a window of time for improving the utility, and wherein the first set of one or more actions is included in the final schedule, wherein, if the difference exceeds the predefined threshold, determining the final schedule includes applying a defensive action selection process that includes selecting and invoking a first action based on the first action being a least costly action of a plurality of candidate actions until a cumulative utility loss for continuing the first action exceeds a cost of invoking a next action, wherein the next action is a next least costly action of the plurality of candidate actions, and wherein the first action is included in the final schedule; and 
     performing the one or more actions according to the final schedule, wherein the one or more actions includes a throttling action selected from the group consisting of: throttling a server, throttling a network, throttling a data storage device, and combinations thereof. 
     Systems, program products and processes for supporting computing infrastructure corresponding to the above-summarized methods are also described and claimed herein. 
     The present invention provides a technique for guaranteeing service level agreements by implementing multi-strategy throttling that may include a combination of central processing unit throttling, network throttling, and input/output throttling to provide end-to-end optimization. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of a system for throttling a plurality of operations of a plurality of applications sharing a plurality of resources, in accordance with embodiments of the present invention. 
         FIG. 2  is a flowchart of a process for throttling a plurality of operations of a plurality of applications sharing a plurality of resources, where the process is implemented in the system of  FIG. 1 , in accordance with embodiments of the present invention. 
         FIG. 3  is a flowchart of a process for determining a throttling plan included in the process of  FIG. 2 , in accordance with embodiments of the present invention. 
         FIGS. 4A-4B  depict a flowchart of a process for applying a recursive greedy pruning with look-back and look-forward optimization included in the process of  FIG. 3 , in accordance with embodiments of the present invention. 
         FIGS. 5A-5B  depict a flowchart of a process for applying a defensive action selection algorithm included in the process of  FIG. 3 , in accordance with embodiments of the present invention. 
         FIG. 6  depicts an example of an action schedule generation tree utilized in the process of  FIGS. 4A-4B , in accordance with embodiments of the present invention. 
         FIG. 7  is a computer system that includes the multi-strategy finder included in the system of  FIG. 1  and that implements the processes of  FIG. 2 ,  FIG. 3 ,  FIGS. 4A-4B  and  FIGS. 5A-5B , in accordance with embodiments of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Overview 
     Embodiments of the present invention present an integrated server-storage-network throttling method and system that enforces run-time service level agreements (SLAs) and priorities associated with applications and that accounts for multiple sub-workloads (e.g., data replication for disaster recovery, data backup, and data archiving for compliance or for long-term data preservation of business intelligence). The throttling technique described herein may guarantee service level agreements (SLAs) for a highest priority application by implementing a multi-actuator selection strategy (a.k.a. multi-strategy throttling), where the operation of an application is throttled by a combination of central processing unit (CPU) throttling at a server, network throttling, and input/output (I/O) throttling to provide end-to-end optimization. Further, the throttling technique described herein may use light-weight monitoring of individual devices to limit the overhead of monitoring the foreground application. Still further, embodiments of the present invention provide incremental active perturbation to determine the dependencies between application workloads. Finally, the optimization space provided by the throttling system described herein may recommend plan changes for sub-workloads (e.g., in terms of start of backup time widows and data mirroring batch sizes). 
     Multi-Strategy Throttling System 
       FIG. 1  is a block diagram of a system for throttling a plurality of operations of a plurality of applications sharing a plurality of resources, in accordance with embodiments of the present invention. System  100  includes a multi-strategy finder  102  that is implemented by a software program whose instructions are carried out by a computer system (see  FIG. 7 ). In one embodiment, multi-strategy finder  102  provides multi-strategy throttling of application operations. Multi-strategy finder  102  receives input from input modules  104 . Input modules  104  include system states sensors  106 , time-series forecasting  108 , utility functions  110 , component models  112  and business constraints  114 . A utility evaluator  116  determines an overall utility value (a.k.a. system utility) for system  100  and sends the system utility to multi-strategy finder  102 . Each single action tool of single action tools  118 - 1 , . . . ,  118 -N determines the optimal invocation parameters for a corrective action in a given system state and sends the determined invocation parameters to multi-strategy finder  102 . Multi-strategy finder  102  generates an action schedule  120  that includes a schedule of corrective actions. System  100  can be deployed, for example, in file systems, storage resource management software and storage virtualization boxes. 
     The above-mentioned components of system  100  are described in more detail below: 
     Multi-Strategy Finder: Multi-strategy finder  102  improves storage system utility for a given optimization window and business-level constraints. Multi-strategy finder  102  interacts with the single action tools  118 - 1 , . . . ,  118 -N and generates a time-based corrective action schedule (i.e., action schedule  120 ) with details of what corrective action(s) to invoke, when to invoke the corrective action(s) and how to invoke the corrective action(s). Generating the corrective action schedule  120  is accomplished by the multi-strategy finder  102  feeding the single-action tools  118 - 1 , . . . ,  118 -N with different system states and collecting individual action options. The multi-strategy finder  102  then analyzes the selected corrective action invocation parameters using the utility evaluator  116 . The multi-strategy finder  102  operates both reactively (i.e., in response to an SLO being violated), as well as proactively (i.e., before an SLO violation occurs). 
     In one embodiment, the multi-strategy finder  102  generates the corrective action schedule by performing the steps of an algorithm presented below:
         Generate and analyze the current state (S 0 ) as well as look-ahead states (S 1 , S 2 , . . . ) according to the forecasted future.   Feed the system states along with the workload utility functions and performance models to the single action tools and collect their invocation options.   Analyze the cost-benefit of the action invocation options by using the utility evaluator  116  (see  FIG. 1 ).   Prune the solution space and generate a schedule  120  (see  FIG. 1 ) of what actions to invoke, when to invoke the actions, and how to invoke the actions.       

     The details of the algorithm implemented by the multi-strategy finder  102  are presented below in the section entitled MULTI-STRATEGY THROTTLING PROCESS. 
     System states: System state sensors  106  monitor the state S (a.k.a. system state) of system  100 . System state sensors  106  may be implemented as hardware or software components. As used herein, the system state includes the run-time details of the system  100  and is defined as a triplet S=&lt;C, W, M&gt;, where C is the set of components in the system  100 , W is the workloads, and M is the current mapping of workloads to the components. 
     Time Series Forecasting: Time series forecasting  108  determines values indicating time-series forecasting of workload request rates. The forecasting of future workload demands is based on extracting patterns and trends from historical data. The time series analysis of historic data performed by time-series forecasting  108  may utilize well-known approaches such as a neural network model or an autoregressive integrated moving average (ARIMA) model. The general form of time series functions is as follows:
 
 y   t+h   =g ( X   t ,θ)+ε t+h   (1)
 
where: y t+h  is the variable(s) vector to be forecast. The value t is the time when the forecast is made. X t  are predictor variables, which usually include the observed and lagged values of y t  until time t. θ is the vector of parameters of the function g and ε t+h  is the prediction error.
 
     Utility Functions: Utility functions evaluate a degree of a user&#39;s satisfaction. For system  100 , utility functions  110  associates workloads performance with a utility value, which reflects a user&#39;s degree of satisfaction. The utility function  110  for each workload can be (1) provided by administrators; (2) defined in terms of priority value and SLOs; or (3) defined by associating a monetary value (e.g., dollar value) to the level of service delivered (e.g., $1000/GB if the latency is less than 10 ms, otherwise $100/GB). 
     Component Models: A component model predicts values of a delivery metric as a function of workload characteristics. System  100  accommodates component models  112  for any system component. In particular, a component model  112  for a storage device takes the form: Response_time=c(req_size, req_rate, rw_ratio, random/sequential, cache_hit_rate), where req_size is the size of an I/O request, req_rate is the number of I/O requests received per unit of time (e.g., per second), rw_ratio is the ratio of read I/O requests to write I/O requests, random/sequential is the percentage of I/O requests that request random block access compared to sequential block access, and cache_hit_rate is the number of I/O requests served per unit of time from the cache instead of from the disk subsystem. 
     Because system  100  needs to explore a large candidate space in a short time, simulation-based approaches to creating component models  112  are not feasible due to the long prediction overhead. System  100  may utilize analytical models or black box approaches for creating component models  112 . In one embodiment, a regression-based approach is used to boot-strap the component models and refine the models continuously at run-time. 
     Business constraints: Business constraints  114  include specifications for administrator-defined business-level constraints (e.g., budget constraints and optimization window) and service level objectives (SLOs). 
     Utility Evaluator: Utility evaluator  116  calculates the overall utility value delivered by a storage system in a given system state. Utility evaluator  116  may use component models  112  to interpolate the I/O performance values, which in turn map to the utility delivered to the workloads. 
     In one embodiment, the calculation of the overall utility value involves obtaining the access characteristics of each workload and using the component models  112  to interpolate the average response-time of each workload. 
     In one embodiment, the utility evaluator  116  uses the throughput and response-time for each workload to calculate the utility value delivered by the storage system: 
                     U   sys     =       ∑     j   =   1     N     ⁢       UF   j     ⁡     (       Thru   j     ⁢     Lat   j       )                 (   2   )               
where N is the total number of workloads, UF j  is the utility function of workload j, with throughput Thru j  and latency Lat j .
 
     In addition, for any given workload demands D j , the system maximum utility value UMax sys  is defined as the “ideal” maximum utility value if the requests for all workloads are satisfied. Utility loss UL sys  is the difference between the maximum utility value and the current system utility value. The system maximum utility value and the utility loss may be calculated as follows: 
                       UMax   sys     =       ∑     j   =   1     N     ⁢       UF   j     ⁡     (       D   j     ,     SLO     lat   j         )           ⁢     
     ⁢       UL   sys     =       UMax   sys     -     U   sys                 (   3   )               
where the SLO lat     j    is the latency requirement of workload j. In addition, as used herein, cumulative utility value for a given time window is defined as the sum of the utility value across the given time window.
 
     Single action tools: Single action tools  118 - 1 , . . . ,  118 -N may leverage existing tools for individual throttling tools that decide throttling at different points in the invocation path (i.e., CPU throttling, network throttling, and storage throttling). The single action tools  118 - 1 , . . . ,  118 -N automate invocation of a single corrective action. Each of these single action tools may include the logic for deciding the action invocation parameter values, and an executor to enforce these parameters. 
     The single action tools  118 - 1 , . . . ,  118 -N take the system state from system states  106 , performance models and utility functions  110  as input from the multi-strategy finder  102  and outputs the invocation parameter values of a corrective action. For example, in the case of migration, a single action tool decides the data to be migrated, the target location, and the migration speed. Every corrective action has a cost in terms of the resource or budget overhead and a benefit in terms of the improvement in the performance of the workloads. The action&#39;s invocation parameter values are used to determine the resulting performance of each workload and the corresponding utility value. 
     Multi-Strategy Throttling Process 
       FIG. 2  is a flowchart of a process for throttling a plurality of operations of a plurality of applications sharing a plurality of resources, where the process is implemented in the system of  FIG. 1 , in accordance with embodiments of the present invention. The prioritized throttling of operations of applications requesting shared devices begins at step  200 . In step  202 , a computer system (e.g., computer system  700  in  FIG. 7 ) implementing a multi-strategy throttling process receives SLOs associated with an enterprise. After activities (i.e., enterprise activities) associated with the enterprise are identified, the computer system receives the identifications of the enterprise activities in step  204 . In step  206 , the computer system receives performance requirements of the enterprise activities, where the performance requirements are based on the SLOs received in step  202 . In step  208 , the computer system receives priorities of enterprise activities within each software application and between software applications that share computing devices. The shared devices include one or more servers, a network, and one or more computer data storage devices. 
     In step  210 , the computer system uses a light-weight monitoring model to monitor the shared devices. In step  212 , if the computer system determines that none of the shared devices are saturated, then the process of  FIG. 2  loops back to step  210  via the No branch of step  212 , and the monitoring of the shared devices continues. 
     In step  212 , if the computer system determines that one of the shared devices is saturated, then the Yes branch is taken and step  214  is performed. Although not shown in  FIG. 2 , step  214  is also performed if the computer system determines (e.g., in a daemon process) that a SLO received in step  202  is violated. In step  214 , the computer system identifies application-to-device dependencies. Also in step  214 , the computer system extracts content-level configuration (e.g., in terms of replication or archiving) for the dependent applications. 
     In step  216 , the computer system determines a throttling plan for a CPU of a server, network, and a storage device in an invocation path of an application that requests the saturated device. Also in step  216 , the computer system determines a sub-workload configuration for the application. 
     In step  218 , the computer system applies selective active perturbation to detect workload dependencies. 
     In step  220 , the computer system executes the throttling plan determined in step  216  and recommends configuration changes (e.g., changes to backup window time and data mirroring batch sizes). The process of  FIG. 2  ends at step  222 . 
       FIG. 3  is a flowchart of a process for determining a throttling plan included in the process of  FIG. 2 , in accordance with embodiments of the present invention. The process of  FIG. 3  is one embodiment of determining a throttling plan in step  216  in  FIG. 2 . The process of  FIG. 3  begins at step  300 . In step  302 , multi-strategy finder  102  (see  FIG. 1 ) determines a difference between an observed workload and a predicted workload. Step  304  is an inquiry step in which the multi-strategy finder  102  (see  FIG. 1 ) determines whether the difference determined in step  302  exceeds a predefined threshold value. The threshold value may be defined by an administrator prior to the start of the process of  FIG. 3 . 
     If multi-strategy finder  102  (see  FIG. 1 ) determines in step  304  that the difference determined in step  302  does not exceed the predefined threshold, then the No branch of step  304  is taken and step  306  is performed. The difference not exceeding the predefined threshold indicates that there is no unexpected variation between the observed and forecasted workloads. In step  306 , multi-strategy finder  102  (see  FIG. 1 ) starts operating in a first mode (i.e., the corrective action(s) in final action schedule  120  (see  FIG. 1 ) are to be invoked proactively in response to forecasted workload growth). The first mode is referred to herein as the normal mode. 
     In the normal mode, multi-strategy finder  102  (see  FIG. 1 ) uses an approach similar to the divide-and-conquer concept, which breaks the optimization window into smaller unequal sub-windows and uses a recursive greedy pruning with look-back and look-forward optimization approach (a.k.a. recursive greedy pruning-lookback-lookforward process) to select actions within each sub-window. The motivation of divide-and-conquer is to reduce the problem complexity and to treat the near-term fine-grained prediction periods differently from the long-term coarse-grained prediction periods. The action selection for each sub-window is performed in a sequential fashion, i.e., the resulting system state of one sub-window acts as the starting state for the next consecutive window. In step  308 , multi-strategy finder  102  (see  FIG. 1 ) applies a recursive greedy pruning algorithm with look-back and look-forward optimization (see the process in  FIGS. 4A-4B ) to select action(s) to be included in the action schedule  120  (see  FIG. 1 ). 
     In step  310 , multi-strategy finder  102  (see  FIG. 1 ) determines a final action schedule  120  (see  FIG. 1 ) that specifies what action(s) to perform, when to perform the action(s) and what invocation parameter values are used to perform the action(s). The action(s) specified in the final action schedule  120  (see  FIG. 1 ) includes throttling a CPU, network, and/or a data storage device in the invocation path of the application that requests the saturated device (see the Yes branch of step  212  in  FIG. 2 ). In one embodiment, multi-strategy finder  102  (see  FIG. 1 ) selects a combination of actions to be included in the final action schedule so that overall system utility is improved or, equivalently, system utility loss is reduced. The process of  FIG. 3  ends at step  312 . 
     Returning to step  304 , if multi-strategy finder  102  (see  FIG. 1 ) determines that the difference determined in step  302  exceeds the predefined threshold value, then the Yes branch of step  304  is taken and step  314  is performed. Determining that the difference exceeds the predefined threshold value indicates an unexpected variation between the observed and forecasted workloads. 
     In step  314 , multi-strategy finder  102  (see  FIG. 1 ) starts operating in a second mode (i.e., the corrective action(s) in the final action schedule  120  (see  FIG. 1 ) are to be invoked reactively in response to unexpected variations in the workloads). The second mode is referred to herein as the unexpected mode. 
     In the unexpected mode, multi-strategy finder  102  (see  FIG. 1 ) selects actions defensively and tries to avoid invoking expensive actions because the excessive workload variation could cease soon after the action in invoked, making the overhead wasted. This attempt to avoid invoking expensive actions needs to be balanced with the potential risk of the high workload variation persisting and thus incurring continuous utility loss, which may add up over time. This analysis is formulated herein as a decision-making problem with an unknown future and an algorithm based on the “ski-rental” online algorithm is applied to select actions. In step  316 , multi-strategy finder  102  (see  FIG. 1 ) selects action(s) to be included in schedule  120  (see  FIG. 1 ) by applying a defensive action selection algorithm (see the process of  FIGS. 5A-5B ), which is based on the “ski rental” (a.k.a. rent/buy) online algorithm (i.e., the break-even algorithm for solving the ski rental problem). 
     Although not shown in  FIG. 3 , multi-strategy finder  102  (see  FIG. 1 ) continuously compares the observed workload values against the predicted workload values (see steps  302  and  304 ). If the difference is larger than the predefined threshold then the multi-strategy finder moves into the unexpected mode. While in the unexpected mode, the multi-strategy finder continuously updates its predictor function based on newly observed workload values. When the predicted workload values and observed workload values are close enough for a sufficiently long period, the multi-strategy finder transitions to the normal mode. 
     Normal Mode 
     In real-world systems, it may be required to invoke more than one action concurrently. For example, if data migration is selected, it might be required to additionally throttle the lower priority workloads until all data are migrated. The multi-strategy finder  102  (see  FIG. 1 ) uses look-back and look-forward optimizations (see steps  412 - 418  in  FIG. 4B ) to improve the action plan. The look-back and look-forward optimizations are with reference to the selected action&#39;s finish time finish i . Look-back optimization seeks action options in the time window [start i , finish i ] (i.e., before the selected action finishes). Look-forward optimization examines possible actions in the window [finish i , end i ] (i.e., after the selected action finishes). Time finish i  is chosen as the splitting point because (1) the system state is permanently changed after the action finishes, making the cost-benefit of action options changed and (2) any action scheduled before the selected action finishes needs to satisfy the above-mentioned no-conflict constraint. The look-back and look-forward optimizations each split the time window recursively and seek actions to improve the system utility further (see steps  412  and  416  in  FIG. 4B ). In the construction of the tree, the action candidates for look-back and look-forward optimizations are represented as left and right children respectively (see, e.g., the circles labeled  3  and  4  in tree  600  in  FIG. 6 ) (see steps  414  and  418  in  FIG. 4B ). The process of greedy pruning with look-back and look-forward optimization is recursively performed to construct action schedule  120  (see  FIG. 1 ) until the GreedyPrune function finds no action option. 
     The pseudocode for look-forward and look-back optimization is given in function Lookback and Lookforward, respectively, as presented below: 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 Function Lookback(i) { 
               
               
                   
                  Foreach (Corrective_actions) { 
               
               
                   
                  If(!(Conflict(Existing actions)) { 
               
               
                   
                   Find action option in (start_i, finish_i); 
               
               
                   
                   Add to Left_Children(i)); 
               
               
                   
                  } 
               
               
                   
                  } 
               
               
                   
                  GreedyPrune(Left_Children(i)); 
               
               
                   
                  If (Left_Children(i)!=NULL) { 
               
               
                   
                  Lookback(Left_Children(i)); 
               
               
                   
                  Lookforward(Left Children(i)); 
               
               
                   
                  } 
               
               
                   
                 } 
               
               
                   
                 Function Lookforward(i) { 
               
               
                   
                  Foreach (Corrective_actions) { 
               
               
                   
                  Find action option in (finish_i, end_i); 
               
               
                   
                  Add to Right_Children(i); 
               
               
                   
                  } 
               
               
                   
                  GreedyPrune(Right_Children(i)) 
               
               
                   
                  If (Right_Children(i)!=NULL) { 
               
               
                   
                  Lookback(Right_Children(i)); 
               
               
                   
                  Lookforward(Right_Children(i)); 
               
               
                   
                  } 
               
               
                   
                 } 
               
               
                   
                   
               
            
           
         
       
     
     As described above, multi-strategy finder  102  (see  FIG. 1 ) generates the schedule of corrective actions  120  (see  FIG. 1 ) using a recursive approach (see the pseudocode for Function TreeSchedule presented below). The final action schedule for each sub-window is obtained by sorting the unpruned nodes (see, e.g., the circles labeled  2 ,  3  and  4  in tree  600  in  FIG. 6 ) in the tree according to the node&#39;s action invocation time (i.e., invoke i ). 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 Function TreeSchedule( ) { 
               
               
                   
                  Foreach (Corrective_actions) { 
               
               
                   
                  Find action option in [T_k, T_{k+1}]; 
               
               
                   
                  Add to Children(root); 
               
               
                   
                  } 
               
               
                   
                  GreedyPrune(Children(root)); 
               
               
                   
                  If (Children(root) !=NULL) { 
               
               
                   
                  Lookback(Children(root)); 
               
               
                   
                  Lookforward(Children(root)); 
               
               
                   
                  } 
               
               
                   
                 } 
               
               
                   
                   
               
            
           
         
       
     
     Finally, each sub-window generated in step  404  (see  FIG. 4A ) is processed sequentially. That is, the resulting system state of sub-window [T k ,T k+1 ] is the starting state of sub-window [T k+1 , T k+2 ], and the action schedules are composed into the final action schedule according to the action invocation time. 
       FIGS. 4A-4B  depict a flowchart of a process for applying the above-mentioned recursive greedy pruning with look-back and look-forward optimization, which is included in the process of  FIG. 3 , in accordance with embodiments of the present invention. The process for applying a recursive greedy pruning with look-back and look-forward optimization is included in step  308  of  FIG. 3  and starts at step  400  in  FIG. 4A . 
     In step  402 , multi-strategy finder  102  (see  FIG. 1 ) receives the current system state from system states sensors  106  (see  FIG. 1 ), a workload prediction from time series forecasting  108  (see  FIG. 1 ), utility functions  110  (see  FIG. 1 ), and available budget for new hardware from business constraints  114  (see  FIG. 1 ), and the length of an optimization window of time (a.k.a. decision window). 
     In step  404 , multi-strategy finder  102  (see  FIG. 1 ) divides the optimization window to generate smaller, unequal sub-windows of time. For instance, a one year optimization window is split into sub-windows of 1 day, 1 month, and 1 year. The number and length of the sub-windows may be configured by an administrator. 
     Within each sub-window [T k , T k+1 ] generated in step  404 , the goal of the process of  FIGS. 4A-4B  is to find actions that maximize the cumulative system utility in the sub-window. Maximizing the cumulative system utility is formulated as a tree-construction algorithm as described below (see also  FIG. 6 ). 
     In step  406 , multi-strategy finder  102  (see  FIG. 1 ) generates a tree where the root corresponds to an entire sub-window [T k , T k+1 ] generated in step  404  and the branches originating from the root represent candidate corrective actions (i.e., action options) returned by single action tools  118 - 1 , . . . ,  118 -N (see  FIG. 1 ). For m possible action options there will be m branches originating from the root of the tree. The resulting node i for each candidate corrective action has the following information:
         The selected candidate action and its invocation parameters.   The action invocation time and finish time [invoke i , finish i ],   The decision window start and end time [start i , end i ]. For nodes originating from the root, the value of the decision window start and end time is [T k , T k+1 ].   The initial state S i  and resulting state S i+1      The predicted cumulative utility loss UL i , defined as the sum of system utility loss from start i  to end i  if action i is invoked.       

     In step  408 , multi-strategy finder  102  (see  FIG. 1 ) selects a first-level node (i.e., selects an action represented by the selected first-level node) in the tree, where the selected node represents the action has the lowest utility loss UL i . Also in step  408 , multi-strategy finder  102  (see  FIG. 1 ) prunes the other m−1 branches (i.e., the branches that do not include the selected node) (see, e.g., the circles crossed out in tree  600  in  FIG. 6 ). In step  410 , the selected action represented by the selected node is included in schedule  120  (see  FIG. 1 ) by multi-strategy finder  102  (see  FIG. 1 ) only if the selected action provides an improvement in system utility that exceeds a predetermined threshold. The threshold is configurable such that a higher value leads to more aggressive pruning. The greedy pruning procedure included in step  408  is referred to as function Greedy Prune in the pseudocode presented below. 
     Step  412  in  FIG. 4B  follows step  410  in  FIG. 4A . In step  412 , multi-strategy finder  102  (see  FIG. 1 ) recursively searches for candidate actions in the time window [start i , finish i ] to further improve system utility by look-back optimization. The candidate actions considered in the search in step  412  satisfy a no-conflict restraint. That is, the candidate actions considered in the search do not conflict with any existing selected action (i.e., any action selected by step  408 ). As used herein, two actions are in conflict if one of the following conditions are true:
         The two actions depend on the same resource.   Action j overlaps with an action k already in the schedule  120  (see  FIG. 1 ), and action j violates the precondition for action k. For example, migration action  1  of moving data A from LUN 1  to LUN 2  will invalidate action  2  of moving data A from LUN 1  to LUN 3  because the pre-condition of action  2  that data A was on LUN 1  is no longer true.       

     In step  414 , for the candidate action(s) found by the search in step  412  are represented as left children node(s) in the tree. 
     In step  416 , multi-strategy finder  102  (see  FIG. 1 ) recursively searches for candidate actions in the time window [finish i , end i ] to further improve system utility by look-forward optimization. 
     In step  418 , candidate action(s) found by the search in step  416  are represented as right children node(s) in the tree. 
     The process of  FIGS. 4A-4B  ends at step  420 . 
     Unexpected Mode 
     Optimizing for the unexpected mode is challenging because it is difficult to predict the duration for which workload variation will persist. The multi-strategy finder  102  (see  FIG. 1 ) uses a defensive action selection strategy similar to the one used in online decision making scenarios that address the “ski rental: to rent or to buy” problem. In the ski rental problem, there is a choice of whether to buy skis (e.g., at a cost of $150) or to rent skis (e.g., at a cost of $10 per ski trip) that has to be made without the knowledge of the future (i.e., without knowing how many times one will go skiing). If one skis less than 15 times, then renting is better; otherwise, buying is better. In the absence of the knowledge of the future, the commonly used strategy is the “to keep renting until the amount paid in renting equals the cost of buying, and then buy.” This commonly-used strategy for the ski rental problem is always within a factor of two of the optimal, regardless of how many times one goes skiing, and is provably the best possible in the absence of knowledge about the future. 
     The multi-strategy finder  102  (see  FIG. 1 ) follows an online strategy (i.e., a defensive action selection strategy) similar to the above-mentioned strategy for addressing the ski rental problem. Multi-strategy finder  102  (see  FIG. 1 ) selects the least costly action until the cumulative utility loss for staying with that selected action exceeds the cost of invoking a next least expensive action. When multi-strategy finder  102  (see  FIG. 1 ) is in the unexpected mode, the multi-strategy finder first finds all candidate action under the assumption that the system state and workload demands will remain the same. For each candidate A i , the cost is initialized as the extra utility loss and hardware cost (if any) paid for the action invocation, as shown in Equation (4): 
     
       
         
           
             
               
                 
                   
                     Cost 
                     ⁡ 
                     
                       ( 
                       
                         A 
                         i 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         t 
                         = 
                         0 
                       
                       
                         leadtime 
                         ⁡ 
                         
                           ( 
                           
                             A 
                             i 
                           
                           ) 
                         
                       
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           
                             U 
                             sys 
                           
                           ⁡ 
                           
                             ( 
                             
                               no_action 
                               , 
                               t 
                             
                             ) 
                           
                         
                         - 
                         
                           
                             U 
                             sys 
                           
                           ( 
                           
                             
                               A 
                               i 
                             
                             ⁢ 
                             
                               _ 
                               ⁢ 
                               ongoing 
                             
                           
                           ⁢ 
                           
                               
                           
                           ) 
                         
                         + 
                         
                           HW_Cost 
                           ⁢ 
                           
                             ( 
                             
                               A 
                               i 
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     In equation (4), U sys (noaction,t) is the system utility value at time t if no corrective action is taken and U sys (A i     —   ongoing,t) is the system utility at time t if A i  is ongoing. For example, for throttling, Cost(A i ) will be zero because the leadtime is zero. For migration, the Cost(A i ) is the total utility loss over leadtime(A i ) due to allocating resources to move data around. 
     Multi-strategy finder  102  (see  FIG. 1 ) selects the action with minimum cost and invokes it immediately. Over time, the cost of each action candidate (including both the selected one and unchosen ones) is updated continuously to reflect the utility loss experienced if A i  had been invoked. Equation (5) gives the value of Cost(A i ) after t intervals: 
                     Cost   ⁡     (     A   i     )       =       Cost   ⁡     (     A   i     )       +       ∑     j   =   0     t     ⁢     UL   ⁡     (       A   i     ,   j     )                   (   5   )               
This cost updating procedure continues until following situations happen:
         Another action k has a lower cost than the previously invoked action. Multi-strategy finder  102  (see  FIG. 1 ) invokes action k immediately and continues the cost updating procedure. For example, if the system experiences utility loss with throttling, but has no utility loss after migration, the cost for the throttling action will continuously grow and the cost of migration will stay the same over time. At some point in time, the cost of throttling will exceed the cost of migration and the migration option will be invoked by then.   System goes back to a good state for a period of time. The multi-strategy finder  102  (see  FIG. 1 ) will stop the action selection procedure because the exception condition has ceased.   The system collects enough new observations and transitions back to the normal mode.       

       FIGS. 5A-5B  depict a flowchart of a process for applying the above-mentioned defensive action selection algorithm included in the process of  FIG. 3 , in accordance with embodiments of the present invention. The process for applying a defensive action selection algorithm is included in step  316  (see  FIG. 3 ) and starts at step  500  in  FIG. 5A . 
     In step  502 , multi-strategy finder  102  (see  FIG. 1 ) determines candidate actions under the assumption that the system state and workload demands remain the same. 
     In step  504 , multi-strategy finder  102  (see  FIG. 1 ) determines a cost of each candidate action determined in step  502 . Cost determined in step  504  is initialized as the extra utility loss and hardware cost (if any) paid for the action invocation. 
     In step  506 , multi-strategy finder  102  (see  FIG. 1 ) selects the candidate action having the minimum cost of the costs determined in step  504 . Also, in step  506 , multi-strategy finder  102  (see  FIG. 1 ) invokes the selected candidate action. 
     In step  508 , multi-strategy finder  102  (see  FIG. 1 ) continuously updates the cost of each candidate action to reflect utility loss experienced if the candidate action had been invoked. 
     In inquiry step  510 , multi-strategy finder  102  (see  FIG. 1 ) determines whether another action k has a lower cost than the previously invoked action (i.e., the action invoked in step  506 ). If multi-strategy finder  102  (see  FIG. 1 ) determines in step  510  that action k has a lower cost than the previously invoked action, then the Yes branch is taken and step  512  is performed. In step  512 , multi-strategy finder  102  (see  FIG. 1 ) invokes action k. Following step  512 , the process loops back to step  508 . 
     Returning to step  510 , if multi-strategy finder  102  (see  FIG. 1 ) determines that no other action has a lower cost than the previously invoked action (i.e., the action invoked in step  506 ), then the No branch is taken and step  514  in  FIG. 5B  is performed. 
     In inquiry step  514 , multi-strategy finder  102  (see  FIG. 1 ) determines whether or not the system returns to an acceptable state and remains in the acceptable state for at least a predefined period of time (i.e., the difference between observed and predicted workloads becomes less than the predefined threshold value and remains less than the predefined threshold value for a predefined period of time). If multi-strategy finder  102  (see  FIG. 1 ) determines in step  514  that the system returns to the acceptable state for at least the predefined period of time, then the Yes branch of step  514  is taken and step  516  is performed. In step  516 , multi-strategy finder  102  (see  FIG. 1 ) stops the defensive action selection procedure. The process of  FIGS. 5A-5B  ends at step  518 . 
     Returning to step  514 , if multi-strategy finder  102  (see  FIG. 1 ) determines that the system does not return to the acceptable state for at least the predefined period of time, then the No branch of step  514  is taken and step  520  is performed. 
     In inquiry step  520 , multi-strategy finder  102  (see  FIG. 1 ) determines whether or not newly observed workload values indicate that the multi-strategy finder should return to the normal mode. If multi-strategy finder  102  (see  FIG. 1 ) determines in step  520  that newly observed workloads indicate a return to the normal mode, then the Yes branch of step  520  is taken and the process continues with step  306  in  FIG. 3 . 
     Otherwise, if multi-strategy finder  102  (see  FIG. 1 ) determines in step  520  that newly observed workloads do not indicate a return to the normal mode, the No branch of step  520  is taken and the process loops back to step  508  in  FIG. 5A . 
       FIG. 6  depicts an example of an action schedule generation tree  600  utilized in the process of  FIGS. 4A-4B , in accordance with embodiments of the present invention. The root of the tree  600  is labeled “1” and corresponds to an entire sub-window generated in step  404  (see  FIG. 4A ). The pruning performed in step  408  (see  FIG. 4A ) is illustrated by the circles labeled “X” in the first level of tree  600  below the root. The node selected in step  408  (see  FIG. 4A ) is the circle labeled “2” in tree  600 . Again, in the construction of the tree  600 , the candidate actions for look-back and look-forward optimizations in steps  412 - 418  (see  FIG. 4B ) are represented as left and right children, respectively (see, e.g., the circles labeled  3  and  4  in tree  600 ) (see steps  414  and  418  in  FIG. 4B ). The final action schedule for each sub-window is obtained by sorting the actions represented by the unpruned nodes in tree  600  (i.e., the circles labeled  2 ,  3  and  4  in tree  600 ), according to each unpruned node&#39;s action invocation time (i.e., invoke i ). 
     Risk Modulation 
     Risk modulation deals with the future uncertainty and action invocation overhead. In the discussion above relative to  FIG. 3 ,  FIGS. 4A-4B  and  FIGS. 5A-5B , action selection was made based on the cumulative utility loss UL i . The accuracy of UL i  depends on the accuracy of future workload forecasting, performance prediction and cost-benefit effect estimation of actions. Inaccurate estimation of UL i  may result in decisions leading to reduced overall utility. To account for the impact of inaccurate input information, risk modulation is performed on the UL i  for each action option. Here, risk describes: (1) the probability that the utility gain of an action will be lost (in the future system-states) as a result of volatility in the workload time series functions (e.g., the demand for W 1  was expected to be 10K IOPS after 1 month, but it turns out to be 5K, making the utility improvement of buying new hardware wasted) and (2) the impact of making a wrong action decision (e.g., the impact of a wrong decision to migrate data when the system is 90% utilized is higher than that of when the system is 20% loaded). 
     There are several techniques for measuring risk. Actions for assigning storage resources among workloads are analogous to portfolio management in which funds are allocated to various company stocks. In economics and finance, the Value at Risk (VaR) is a technique used to estimate the probability of portfolio losses based on the statistical analysis of historical price trends and volatilities in trend prediction. In the context of the system described herein, VaR represents the probability with a 95% confidence, that the workload system will not grow in the future, making the action invocation unnecessary.
 
VaR(95% confidence)=−1.65σ×√{square root over ( T )}  (6)
 
where, σ is the standard deviation of the time series request-rate predictions and T is the number of days in the future for which the risk estimate holds. For different sub-windows, the prediction standard deviation may be different (e.g., a near-term prediction is likely to be more precise than a long-term one).
 
     The risk value RF(A i ) of action i is calculated by:
 
RF( A   1 )=−(1+α)*VaR  (7)
 
where α reflects the risk factors of an individual action (based on its operational semantics) and is defined as follows:
 
               α   thr     =   0                 α   mig     =       bytes_moved     total_bytes   ⁢   _on   ⁢   _source       *   Sys_Utilization                   α   hw     =       hardware_cost   total_budget     *     (     1   -   Sys_Utilization     )             
where Sys_Utilization is the system utilization when the action is invoked.
 
     For each action option returned by the single action tools  118 - 1 , . . . ,  118 -N (see  FIG. 1 ), the multi-strategy finder  102  (see  FIG. 1 ) calculates the risk factor RF(A i ) and scales the cumulative utility loss UL i  according to Equation (8) and the action selection is performed based on the scaled UL* i  (For example, in the GreedyPrune function).
 
UL* i =(1+RF( A   i ))×UL i   (8)
 
Computer System
 
       FIG. 7  is a computer system that includes the multi-strategy finder of the system of  FIG. 1  and that implements the processes of  FIG. 2 ,  FIG. 3 ,  FIGS. 4A-4B  and  FIGS. 5A-5B , in accordance with embodiments of the present invention. Computer system  700  generally comprises a central processing unit (CPU)  702 , a memory  704 , an I/O interface  706 , and a bus  708 . Further, computer system  700  is coupled to I/O devices  710  and a computer data storage unit  712 . CPU  702  performs computation and control functions of computer system  700 . CPU  702  may comprise a single processing unit, or be distributed across one or more processing units in one or more locations (e.g., on a client and server). In one embodiment, computer system  700  is carries out instructions of programs that implement one or more components of system  100  (see  FIG. 1 ), including multi-strategy finder  102  (see  FIG. 1 ). 
     Memory  704  may comprise any known computer readable storage medium, which is described below. In one embodiment, cache memory elements of memory  704  provide temporary storage of at least some program code (e.g., program code  714 ) in order to reduce the number of times code must be retrieved from bulk storage while instructions of the program code are carried out. Moreover, similar to CPU  702 , memory  704  may reside at a single physical location, comprising one or more types of data storage, or be distributed across a plurality of physical systems in various forms. Further, memory  704  can include data distributed across, for example, a local area network (LAN) or a wide area network (WAN). 
     I/O interface  706  comprises any system for exchanging information to or from an external source. I/O devices  710  comprise any known type of external device, including a display device (e.g., monitor), keyboard, mouse, printer, speakers, handheld device, facsimile, etc. Bus  708  provides a communication link between each of the components in computer system  700 , and may comprise any type of transmission link, including electrical, optical, wireless, etc. 
     I/O interface  706  also allows computer system  700  to store and retrieve information (e.g., data or program instructions such as program code  714 ) from an auxiliary storage device such as computer data storage unit  712  or another computer data storage unit (not shown). Computer data storage unit  712  may comprise any known computer readable storage medium, which is described below. For example, computer data storage unit  712  may be a non-volatile data storage device, such as a magnetic disk drive (i.e., hard disk drive) or an optical disc drive (e.g., a CD-ROM drive which receives a CD-ROM disk). 
     Memory  704  may store computer program code  714  that provides the logic for multi-strategy throttling included in one or more of the processes in  FIGS. 2 ,  3 ,  4 A- 4 B and  5 A- 5 B. In one embodiment, program code  714  is included in multi-strategy finder  102  (see  FIG. 1 ). Further, memory  704  may include other systems not shown in  FIG. 7 , such as an operating system (e.g., Linux) that runs on CPU  702  and provides control of various components within and/or connected to computer system  700 . In one embodiment, memory  704  stores program code that provides logic for utility evaluator  116 . In one embodiment, memory  704  stores program code that provides logic for one or more single action tools  118 - 1 , . . . ,  118 -N (see  FIG. 1 ). 
     Memory  704 , storage unit  712 , and/or one or more other computer data storage units (not shown) that are coupled to computer system  700  may store input received from input modules  104  (see  FIG. 1 ). 
     As will be appreciated by one skilled in the art, the present invention may be embodied as a system, method or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “module” or “system” (e.g., system  100  in  FIG. 1  or computer system  700 ). Furthermore, an embodiment of the present invention may take the form of a computer program product embodied in one or more computer readable medium(s) (e.g., memory  704  or computer data storage unit  712 ) having computer readable program code (e.g., program code  714 ) embodied or stored thereon. 
     Any combination of one or more computer readable medium(s) (e.g., memory  704  and computer data storage unit  712 ) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared or semiconductor system, apparatus, device or any suitable combination of the foregoing. A non-exhaustive list of more specific examples of the computer-readable storage medium includes: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any tangible medium that can contain or store a program (e.g., program  714 ) for use by or in connection with a system, apparatus, or device for carrying out instructions. 
     A computer readable signal medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electromagnetic, optical, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with a system, apparatus, or device for carrying out instructions. 
     Program code (e.g., program code  714 ) embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing. 
     Computer program code (e.g., program code  714 ) for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java®, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. Instructions of the program code may be carried out entirely on a user&#39;s computer, partly on the user&#39;s computer, as a stand-alone software package, partly on the user&#39;s computer and partly on a remote computer or entirely on the remote computer or server, where the aforementioned user&#39;s computer, remote computer and server may be, for example, computer system  700  or another computer system (not shown) having components analogous to the components of computer system  700  included in  FIG. 7 . In the latter scenario, the remote computer may be connected to the user&#39;s computer through any type of network (not shown), including a LAN or a WAN, or the connection may be made to an external computer (e.g., through the Internet using an Internet Service Provider). 
     Aspects of the present invention are described herein with reference to flowchart illustrations (e.g.,  FIG. 2 ,  FIG. 3 ,  FIGS. 4A-4B , and  FIGS. 5A-5B ) and/or block diagrams of methods, apparatus (systems) (e.g.,  FIG. 1  and  FIG. 7 ), and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions (e.g., program code  714 ). These computer program instructions may be provided to a processor (e.g., CPU  702 ) of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which are carried out via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. 
     These computer program instructions may also be stored in a computer readable medium (e.g., memory  704  or computer data storage unit  712 ) that can direct a computer (e.g., computer system  700 ), other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks. 
     The computer program instructions may also be loaded onto a computer (e.g., computer system  700 ), other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus, or other devices to produce a computer implemented process such that the instructions which are carried out on the computer, other programmable apparatus, or other devices provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. 
     Any of the components of an embodiment of the present invention can be deployed, managed, serviced, etc. by a service provider that offers to deploy or integrate computing infrastructure with respect to the process of throttling a plurality of operations of a plurality of applications that share a plurality of resources. Thus, an embodiment of the present invention discloses a process for supporting computer infrastructure, comprising integrating, hosting, maintaining and deploying computer-readable code (e.g., program code  714 ) into a computer system (e.g., computer system  700 ), wherein the code in combination with the computer system is capable of performing a process of throttling a plurality of operations of a plurality of applications that share a plurality of resources. 
     In another embodiment, the invention provides a business method that performs the process steps of the invention on a subscription, advertising and/or fee basis. That is, a service provider, such as a Solution Integrator, can offer to create, maintain, support, etc. a process of throttling a plurality of operations of a plurality of applications that share a plurality of resources. In this case, the service provider can create, maintain, support, etc. a computer infrastructure that performs the process steps of the invention for one or more customers. In return, the service provider can receive payment from the customer(s) under a subscription and/or fee agreement, and/or the service provider can receive payment from the sale of advertising content to one or more third parties. 
     The flowcharts in  FIG. 2 ,  FIG. 3 ,  FIGS. 4A-4B  and  FIGS. 5A-5B  and the block diagrams in  FIG. 1  and  FIG. 7  illustrate the architecture, functionality, and operation of possible implementations of systems, methods, and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code (e.g., program code  714 ), which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be performed substantially concurrently, or the blocks may sometimes be performed in reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustrations, and combinations of blocks in the block diagrams and/or flowchart illustrations, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions. 
     While embodiments of the present invention have been described herein for purposes of illustration, many modifications and changes will become apparent to those skilled in the art. Accordingly, the appended claims are intended to encompass all such modifications and changes as fall within the true spirit and scope of this invention.