Automated and adaptive threshold setting

[0001] This application is a continuation in part application of U.S. patent application Ser. No. 11/146627, entitled “Automated and adaptive Threshold setting,” filed on Jun. 7, 2005 now abandoned. This application is also related to U.S. patent application Ser. No. 11/088,054, entitled “Root-Cause Analysis of Network Performance Problems,” filed on Mar. 23, 2005. These related applications are assigned to the assignee of the present patent application and is incorporated herein by reference.

[0002] The present invention relates generally to computer system management, and particularly to methods and systems for automated and adaptive setting of system component performance thresholds.

[0003] Computer systems commonly use performance thresholds for monitoring and managing the performance of system components. Threshold violations are recorded and analyzed as possible indicators of system faults. Various methods for setting and managing component performance thresholds (referred to herein as “component thresholds” for brevity) are known in the art. For example, Hellerstein et al. describe a method for predicting threshold violations in “A Statistical Approach to Predictive Detection,” Computer Networks, (35:1), 2001, pages 77-95, which is incorporated herein by reference. The method models the stationary and non-stationary behavior of threshold metrics and computes the probability of threshold violations. Another use of predictive algorithms for predicting failures in computer systems is described by Vialta et al. in “Predictive Algorithms in the Management of Computer Systems,” IBM Systems Journal, (41:3), 2002, pages 461-474, which is incorporated herein by reference.

[0004] Another threshold setting method is described by Burgess in “Two-Dimensional Time-Series for Anomaly Detection and Regulation in Adaptive Systems,” Proceedings of the Thirteenth IFIP/IEEE International Workshop on Distributed Systems: Operations and Management, Montreal, Canada, October 2002, pages 169-180, which is incorporated herein by reference. The author describes a method in which a two-dimensional time approach is used to classify a periodic, adaptive threshold for service level anomaly detection. The author asserts that the method provides improved storage and computational efficiency.

[0005] Agarwal et al. describe yet another threshold scheme in “Problem Determination Using Dependency Graphs and Run-Time Behavior Models,” Proceedings of the Fifteenth IFIP/IEEE International Workshop on Distributed Systems: Operations and Management, New York, N.Y., November 2004, pages 171-182, which is incorporated herein by reference. The authors describe a method that uses dependency graphs and dynamic run-time performance characteristics of resources in an IT environment to identify the root cause of reported problems. The method uses the dependency information and the behavior models to narrow down the root cause to a small set of resources that can be individually tested, facilitating quick remediation of the problem.

[0006] Hoogenboom and Lepreau describe still another threshold management system in “Computer System Performance Problem Detection Using Time Series Model,” Proceedings of the USENIX Summer 1993 Technical Conference, Cincinnati, Ohio, June 1993, pages. 15-32, which is incorporated herein by reference. The authors describe an expert system that automatically sets thresholds, and thus detects and diagnoses performance problems in a network of Unix® computers. The system uses time series models to model the variations in workload on each host.

[0007] Some threshold schemes use a statistical model based on the historical behavior of the threshold metric. Such a scheme is described by Brutlag in “Aberrant Behavior Detection in Time Series for Network Monitoring,” Proceedings of the Fourteenth USENIX System Administration Conference (LISA 2000), New-Orleans, La., December 2000, pages 139-146, which is incorporated herein by reference. An additional threshold scheme based on a statistical model is described by Hajji et al. in “Detection of Network Faults and Performance Problems,” Proceedings of the Internet Conference 2001 (IC 2001), Osaka, Japan, November 2001, pages 159-168, which is incorporated herein by reference. Yet another statistical model is described by Thottan and Ji in “Adaptive Thresholding for Proactive Network Problem Detection,” Proceedings of the Third IEEE International Workshop on Systems Management, Newport, Rhode-Island, April 1998, pages 108-116, which is incorporated herein by reference. A further model is described by Ward et al. in “Internet Service Performance Failure Detection,” Proceedings of the 1998 Internet Server Performance Workshop, Madison, Wis., June 1998, pages 103-110, which is incorporated herein by reference.

[0008] U.S. Pat. No. 6,876,988, whose disclosure is incorporated herein by reference, describes a method and a system for computing a performance forecast for an e-business system or other computer architecture. The system obtains measured input values from a plurality of internal and external data sources to predict the system performance. The system can include both intrinsic and extrinsic variables as predictive inputs. Intrinsic variables include measurements of the system's own performance, such as component activity levels and system response time. Extrinsic variables include other factors, such as the time and date, and demographic factors that may effect or coincide with increased network traffic.

[0009] In some applications it is desirable to correlate component thresholds with service-level objectives (SLOs) of the computer system. For example, Cohen et al. describe a system analysis method of this sort in “Correlating Instrumentation Data to System States: A Building Block for Automated Diagnosis and Control,” Proceedings of the Sixth USENIX Symposium on Operating Systems Design and Implementation (OSDI '04), San-Francisco, Calif., December 2004, pages 231-244, which is incorporated herein by reference. The method uses Tree-Augmented Bayesian Networks (TANs) to identify combinations of system-level metrics and threshold values that correlate with high-level performance states.

[0010] Systems for threshold management and for correlating thresholds with SLOs are produced by Netuitive, Inc. (Reston, Va.). The company produces a software tool called “Netuitive SI” that learns the baseline behavior of a computer system. The tool issues alarms if deviations from the baseline behavior are detected. The company also produces a tool called “Netuitive Service Analyzer” that correlates SLOs with component alarms.

[0011] Hellerstein describes a quantitative performance diagnosis (QPD) algorithm, which produces explanations that quantify the impact of problem causes, in “A General Purpose Algorithm for Quantitative Diagnosis of Performance Problems,” Journal of Network and Systems Management, (11:2), June 2003, which is incorporated herein by reference.

[0012] In “Data-driven Monitoring Design of Service Level and Resource Utilization” 2005 9th IFIP/IEEE Symposium on Integrated Network Management pp. 89-101, Nice, France, May 2005, which is incorporated herein by reference, Perng, Mass., Lin and Thoenen describe a method for optimizing the setting of resource metric thresholds and service level breach point thresholds. Perng et al.'s algorithm is based on maximizing the mutual information of the time series of component and application threshold breaching, which is used to calculate optimized threshold values.

[0013] In some cases, machine learning or data mining techniques are used to model the relationship between component thresholds and SLOs. For example, Diao et al. describe methods of this sort in “Generic On-Line Discovery of Quantitative Models for Service Level Management,” Proceedings of the Eighth IFIP/IEEE International Symposium on Integrated Network Management, Colorado Springs, Colo., March 2003, pages 157-170, which is incorporated herein by reference. Other methods are described by Hellerstein and Ma in “Mining Event Data for Actionable Patterns,” Proceedings of the 26th Computer Management Group (CMG) International Conference, Orlando, Fla., December 2000, pages 307-318, which is incorporated herein by reference.

[0014] In other cases, neural networks are used to learn the relationships between measured input values. For example, U.S. Pat. Nos. 6,289,330 and 6,216,119, whose disclosures are incorporated herein by reference, describe neural network systems that receive measured input values during a time trial, combine the information with prior information and learn relationships among the variables gradually by improving the learned relationships from trial to trial.

[0015] Many computer systems are managed using performance thresholds set for the various system components. When managing computer systems, it is often desirable to correlate such component thresholds with application-level service level objectives (SLOs). This correlation enables the system to automatically set statistically-meaningful threshold values that reliably predict system-level problems. An SLO-related setting of the component thresholds redefines the normal and abnormal behavior of system components from the perspective of the applications and the service-related objectives of the computer system. Setting such meaningful values of component-level performance thresholds is a complicated task, especially in computer systems comprising multiple tiers, levels, components and applications having complex interdependencies. In conventional computer systems, component thresholds are often left constant at their default values or set empirically (and therefore sub-optimally) by a system administrator.

[0016] Embodiments of the present invention provide methods and systems for automatically and adaptively setting component thresholds, so as to correlate threshold violations and SLO violations with controllable accuracy.

[0017] In some embodiments, a threshold management unit monitors and records component threshold violations and SLO violations over time. The threshold management unit uses the collected historical data to construct a predictive model that links together the statistical behaviors of the component threshold violations and the SLO violations.

[0018] In some embodiments, the threshold management unit uses the historical data to estimate the rate of false-positive and false-negative threshold violation/satisfaction events with respect to the SLO. Using the predictive model, the threshold management unit adaptively updates the threshold value, so that the measured false-positive and false-negative rates gradually converge to predetermined desired values.

[0019] The model uses historical threshold values, paired with the corresponding SLO violation information, to calculate an updated threshold value. In some embodiments, calculating the model comprises fitting the historical data using a logistic regression process, as will be explained below. In some embodiments, the historical data is filtered and/or weighted in order to improve the accuracy of the model and accommodate different workload patterns.

[0020] An alternative method for direct setting of the component threshold is also described below.

[0021] There is therefore provided, in accordance with an embodiment of the present invention, a method for managing a computer system, including:

[0022] monitoring first violations of a service level objective (SLO) of a service running on the computer system so as to determine a first statistical behavior of the first violations;

[0023] monitoring second violations of a component performance threshold of a component of the computer system so as to determine a second statistical behavior of the second violations;

[0024] producing a model that predicts the second statistical behavior based on the first statistical behavior; and

[0025] automatically adjusting the component performance threshold responsively to the model, so as to improve a prediction of the first violations by the second violations.

[0026] In an embodiment, the computer system includes a Storage Area Network (SAN).

[0027] In another embodiment, monitoring the first and second violations includes estimating false-positive and false-negative rates of the second violations with respect to the first violations. Additionally or alternatively, automatically adjusting the threshold includes causing the estimated false-positive and false-negative rates to converge to predetermined target values. Further additionally or alternatively, automatically adjusting the threshold includes searching for a threshold value that minimizes the estimated false-positive and false-negative rates.

[0028] In yet another embodiment, producing the model includes fitting a first sequence including historical values of the first violations and a second sequence including historical values of the component performance threshold with a probability of component performance threshold violations, and automatically adjusting the component performance threshold includes calculating an updated threshold value based on the fitted sequences.

[0029] Additionally or alternatively, fitting the sequences includes applying at least one of a logistic regression process and a polynomial fitting process. Further additionally or alternatively, producing the model includes estimating a fitting quality responsively to the model and the sequences, and automatically adjusting the threshold includes determining whether to update the threshold responsively to the fitting quality. In some embodiments, fitting the sequences includes inserting dummy data points into the sequences, so as to reduce a bias in the calculated updated threshold value.

[0030] In a disclosed embodiment, fitting the sequences includes using only a part of the historical values in the sequences corresponding to at least one of recent events, periodic events, events in which the SLO is almost violated and events in which a performance metric value is within a predetermined interval. Additionally or alternatively, fitting the sequences includes applying weights to at least some of the historical values corresponding to at least one of recent events, periodic events, rare events, events in which the SLO is almost violated and events in which a performance metric value is within a predetermined interval.

[0031] There is also provided, in accordance with an embodiment of the present invention, apparatus for managing a computer system, including:

[0032] an interface, which is coupled to receive inputs indicative of first violations of a service level objective (SLO) of a service running on the computer system and of second violations of a component performance threshold of a component of the computer system; and

[0033] a processor, which is arranged to determine a first statistical behavior of the first violations and a second statistical behavior of the second violations, to produce a model that predicts the second statistical behavior based on the first statistical behavior, and to automatically adjust the component performance threshold responsively to the model, so as to improve a prediction of the first violations by the second violations.

[0034] There is additionally provided, in accordance with an embodiment of the present invention, a computer software product for managing a computerized system, the product including a computer-readable medium, in which program instructions are stored, which instructions, when read by a computer, cause the computer to monitor first violations of a service level objective (SLO) of a service running on the computerized system so as to determine a first statistical behavior of the first violations, to monitor second violations of a component performance threshold of a component of the computerized system so as to determine a second statistical behavior of the second violations, to produce a model that predicts the second statistical behavior based on the first statistical behavior, and to automatically adjust the component performance threshold responsively to the model, so as to improve a prediction of the first violations by the second violations.

[0035] There is also provided, in accordance with an embodiment of the present invention a method for performing an interactive analysis of a computer system to devise an information technology solution applicable to the computer system, the method including:

[0036] monitoring first violations of a service level objective (SLO) of a service running on the computer system so as to determine a first statistical behavior of the first violations;

[0037] monitoring second violations of a component performance threshold of a component of the computer system so as to determine a second statistical behavior of the second violations;

[0038] producing a model that predicts the second statistical behavior based on the first statistical behavior; and

[0039] automatically adjusting the component performance threshold responsively to the model, so as to improve a prediction of the first violations by the second violations.

[0040] The present invention will be more fully understood from the following detailed description of the embodiments thereof, taken together with the drawings in which:

[0048] FIG. 1 is a block diagram that schematically illustrates a computer system 20, in accordance with an embodiment of the present invention. System 20 may comprise, for example, a storage-area network (SAN) that interconnects multiple servers to multiple storage devices. Alternatively, system 20 can comprise an enterprise computer system, an electronic business system, a web-site or any other suitable computer system. In some embodiments, system 20 employs autonomous computing and/or self-management methods, as are known in the art. Software applications 24 run on system components 28. Components 28 may comprise, for example, storage devices such as disks or tapes, disk arrays and their controllers, computing platforms such as servers, and communication devices such as switches and routers. Components 28 are interconnected using suitable interconnection means, such as a backplane or a local area network (LAN), and communicate with each other and with applications 24 using suitable interfaces.

[0049] During the operation of the system, some of system components 28 monitor their performance in order to detect abnormal behavior and identify potential problems and malfunctions. In some embodiments, the performance of some system components 28 may be monitored by external means. Typically, component 28 measures and monitors one or more predefined component performance metrics (referred to herein as “component metrics” for brevity). Component metrics may comprise, for example, an access time of a disk, or an instantaneous throughput or a latency of a communication device. For each component metric, the system defines a corresponding component threshold, whose value is set using methods which will be described below. Measured metric values that do not violate the threshold are regarded as normal, whereas metric values that violate the threshold are considered abnormal behavior. (In general, a threshold set over a particular component metric may comprise an upper threshold or a lower threshold. Additionally, some component metrics may have both upper and lower thresholds defined simultaneously. In the context of the present patent application and in the claims, the term “threshold violation” refers to component metric values that are higher than an upper threshold, or to component metric values that are lower than a lower threshold, as applicable.) A threshold violation typically triggers an alert.

[0050] Typically, components 28 of system 20 provide and consume services to and from each other. The services are depicted as arrows between the components in FIG. 1. As part of the service definition, components 28 typically have service level agreements (SLAs) defined among them. Part of the SLA is a service level objective (SLO), which defines and quantifies the performance level that a particular component guarantees to other components that may consume its services. In some embodiments, the SLO is expressed as a threshold, which is defined over an application metric. An SLO for a storage service may be, for example, “the response time will not exceed 2 seconds for 95% of the transactions.” In this example the response time of the service serves as the application metric. For a communication service, an exemplary SLO may be “the average offered capacity will exceed 100 Mbps, averaged over 5 second intervals.” Other SLOs may refer to reliability levels and other parameters.

[0051] The descriptions that follow refer mainly to binary SLOs, which can be either satisfied or violated. Some systems, however, define multi-level SLOs, for example in scenarios in which the client pays for a service in accordance with the service level. The methods described below can easily be generalized to the case of multi-level SLOs.

[0052] In many practical cases, the term “service” refers to application-level services, each comprising multiple “atomic” or lower-level services, provided by multiple components 28. For example, a storage service may comprise computational and management services provided by a server, as well as atomic storage services provided by one or more storage devices. From the system's point of view, an application-level service is typically regarded as a single entity having predefined service level objectives. In the context of the present patent application and in the claims, the term “service” refers to both low-level and application-level services. The term “SLO” refers to the corresponding application-level SLO. Typically, SLO violations are detected and reported by applications 24 or by their users.

[0053] A system management module 32 defines (or is supplied with) the SLOs for the different services. Module 32 monitors the application-level SLO violations reported by applications 24. Module 32 also monitors the alerts triggered by components 28 in response to component threshold violations. Module 32 may collect and analyze data, react upon it, produce reports, interact with a system administrator and/or perform any other system management functions known in the art. System management module 32 may be implemented as a software process running on one of the servers of system 20, or on a separate computing platform.

[0054] A threshold management unit 36 monitors the operation of system components 28 and of applications 24. Unit 36 comprises a processor 38 that performs the various threshold management functions described herein, and an interface 40 that communicates with the different applications and components of system 20. In particular, the threshold management unit monitors the alerts triggered by components 28 in response to threshold violations, and the SLO violations reported by applications 24. In some cases the threshold management unit monitors the raw component metrics and application metrics as well.

[0055] The threshold management unit applies the accumulated information, using methods which will be explained below, to automatically adjust the values set to the component thresholds of components 28. Processor 38 typically sends the updated values via interface 40 to the respective components, and continues to monitor the system performance running with the updated thresholds. In some embodiments, unit 36 can be implemented as an add-on to an existing computer system, using existing component metrics and thresholds.

[0056] Typically, threshold management unit 36 comprises a general-purpose computer, which is programmed in software to carry out the functions described herein. The software may be downloaded to the computer in electronic form, over a network, for example, or it may alternatively be supplied to the computer on tangible media, such as CD-ROM. Further alternatively, unit 36 may be implemented in dedicated hardware logic, or using a combination of hardware and software elements. The threshold management unit may be a standalone unit, or it may alternatively be integrated with other computing platforms of system 20. For example, unit 36 can be implemented as part of system management module 32. Threshold management unit 36 and/or system management module 32 may be implemented as software processes running on one of the servers in system 20. Alternatively, threshold management unit 36 may be external to system 20, and it may be used to provide analysis and/or management services to system 20.

[0057] In many practical cases, it is desirable to set the component thresholds so that component threshold violations predict SLO violation events. For example, consider a database query service comprising a single SLO that states: “The average transaction processing time shall not exceed 2 seconds for 95% of the transactions.” Assume that this exemplary database query service uses several components 28, including several disks. For one of these disks, the access time of writing a data page to the disk is defined as a component metric. A component threshold is defined over this metric, so that an alert is triggered if the access time exceeds the threshold value.

[0058] From the application's point of view it is desirable that the alert be triggered if, and only if, the disk access time is likely to cause a violation of the SLO. Setting the threshold too low may cause alerts to trigger when the disk access time is still acceptable, from the SLO perspective. This “false alarm” is commonly referred to as a “false positive” event. Setting the threshold too high, on the other hand, may cause the alert not to trigger when the SLO is violated. This “misdetection” is commonly referred to as a “false negative” event. Both events are typically undesirable. A high rate of false positive events may cause unnecessary alert processing in the system management module, and may result in unnecessary corrective actions, such as component replacements. A high rate of false negative events may cause failure to identify the root cause of the SLO violations, which may result in a degraded service level.

[0059] In principle, the automatic threshold setting methods described below tie together the statistical behavior of the application level SLOs and the component level thresholds. Using these methods, the threshold management unit automatically adjusts the component thresholds so as to achieve predetermined false positive and false negative rates, with respect to the SLO violations.

[0060] In some embodiments, the threshold management unit estimates the false positive and false negative rates by jointly monitoring threshold violations (in other words—triggered alerts) and SLO violations. For example, the threshold management unit can maintain the following table that describes the possible relations between threshold violations and SLO violations:

[0061]

		SLO violated	SLO satisfied
	Threshold violated	I	II
	Threshold satisfied	III	IV

[0062] In this example, the threshold management unit uses four counters denoted I, II, III and IV to count occurrences of the four possible combinations of SLO/threshold violations, over a given number of monitoring instances. Counter I counts events, in which a threshold violation coincided with an SLO violation. Counter II counts events, in which the threshold was violated but the SLO was not. Counter III counts events in which the SLO was violated but the threshold was not. Finally, counter IV counts events, in which neither the threshold nor the SLO were violated.

[0063] A Positive Predictive Value (PPV) of the threshold, with respect to the SLO, is defined as PPV≡I/(I+II). The PPV represents the probability that the SLO is violated, given a violated threshold. A Negative Predictive Value (NPV) of the threshold, with respect to the SLO, is defined as NPV≡IV/(III+IV). The NPV represents the probability that the SLO is not violated, given a non-violated threshold.

[0064] Many practical systems comprise multiple component thresholds and multiple SLOs, some of which may be interrelated. Any of these thresholds and SLOs can be satisfied or violated at any given time. In general, a particular SLO can be affected by any number of different component metrics. Similarly, a particular component metric may affect several SLOs in the system. For simplicity of explanation, the method descriptions that follow will assume a single system component 28 denoted c having a single component metric denoted μ. A single component threshold denoted γ is defined over metric μ. A single SLO is defined for the system, over an application metric denoted ρ.

[0065] Generalization of the disclosed methods to computer systems comprising multiple SLOs and/or component thresholds is straightforward and will be apparent to those skilled in the art. Typically, the generalization of the methods involves identifying which of the multiple component metrics affect each SLO. Methods for identifying such interdependencies and identifying component metrics that are of minor importance to a particular SLO, such as dimensionality reduction methods, are known in the art.

[0066] In some systems, a particular SLO may not be reliably predicted using any single component threshold. In such cases, there may exist a combination of two or more component metrics, whose joint consideration may predict an SLO violation. This characteristic is referred to as “inseparability.” In some embodiments, the threshold management unit may use statistical methods, such as methods used in data mining applications, to determine a linear combination of component metrics that reliably predicts an inseparable SLO.

[0067] In other cases, system 20 may comprise multiple applications that share the system components and services. These applications typically comprise SLOs that should be accommodated simultaneously. In some embodiments, a single statistical model can be used to model the SLO violations of all the applications. Alternatively, each application may comprise its own model. An intermediate solution is to classify the applications into classes, each class having a separate model. In one embodiment, a “case study” method can be used, as described by Agresti in “Categorical Data Analysis,” John Wiley and Sons, Hoboken, N.J., 2002, which is incorporated herein by reference. Using this method, an empirical probability function is developed over time. The probability function predicts, for each component threshold violation, the type of application that may be affected by it. In some embodiments, the SLOs of the affected applications are combined to form a single composite SLO, and the threshold is adjusted in accordance with the composite SLO. In other embodiments, the affected SLOs remain separate, and a threshold value is defined for each SLO. In these embodiments, a vector of thresholds is typically maintained and separate alerts are generated for each application.

[0068] The following paragraphs describe a method, carried out by threshold management unit 36, for calculating a component threshold value that best predicts violations of a corresponding SLO. Three basic assumptions are made in the analysis. The first assumption is that the metrics μ and ρ defined above are stochastically monotonic. Formally, this condition implies that Pr(ρ1≦ρ2|μ1≦μ2)>Pr(ρ1>ρ2|μ1≦μ2), wherein Pr(·) denotes a probability function. ρ1 and ρ2 denote the values of application metric ρ at times t1 and t2, respectively. μ1 and μ2 denote the values of component performance metric μ at the same two time instances. A second assumption is that the SLO and component threshold are indeed interrelated, so that threshold violations are able to predict the SLO violations. For example, Breitgand et al. describe methods for extracting explicit relationships between system performance problems and component metrics in “Root-Cause Analysis of SAN Performance Problems: an I/O Path Affine Search Approach,” Proceedings of the Ninth IFIP/IEEE International Symposium on Integrated Network Management, Nice, France, May 2005, which is incorporated herein by reference. A third underlying assumption is that the behavior of the system remains stochastically stationary for sufficiently long periods of time, so that the threshold has a sufficient number of iterations for converging. These three assumptions are typically met in the majority of practical applications.

[0069] In the description that follows, a discrete time model is assumed. In other words, the threshold management unit monitors SLO and threshold violations at discrete time instances denoted τ=0,1, . . . , t. The method uses the following definitions: Γ(t)={γ(0), γ(1), . . . , γ(t)} at time denotes a time series of the values of threshold γ at time instances 0, 1, . . . , t. A(t)={a(0), a(1), . . . , a(t)} denotes a time series of binary stochastic variables describing SLO violations, wherein a(τ)=0 if the SLO is satisfied at time instance τ and a(τ)=1 if the SLO is violated at time instance τ. Y(t)={y(0), y(1), . . . , y(t)} denotes a time series of binary stochastic variables describing threshold violations, wherein y(τ)=0 if threshold γ is satisfied at time instance τ and y(τ)=1 if threshold γ is violated at time instance τ. Let α and β denote the desired PPV (the probability that the SLO is violated, given a violated threshold) and NPV (the probability that the SLO is satisfied, given a satisfied threshold) probabilities, respectively.

[0070] In some embodiments, the threshold management unit adjusts the desired value for threshold γ so that the actual PPV and NPV of the system converge over time to the desired values α and β, respectively. Once this condition is satisfied, SLO violation events can be well predicted by threshold violation events.

[0071] The disclosed method constructs a statistical predictive model that uses the time series Γ(t) and A(t) to predict the future values of Y(t). By solving a regression equation, as will be explained below, the model calculates the desired value of threshold γ at the next time interval t+1, based on the historical values of the threshold (represented by Γ(t)) and on the history of SLO violations (represented by A(t)).

[0072] Since Y(t) and A(t) are binary variables, conventional linear regression methods are typically unsuitable for fitting these variables. There are, however, several methods known in the art for analyzing and fitting categorical (i.e., discrete) data. For example, a method called “logistic regression” is described in chapter 5, pages 165-197 of the Agresti reference cited above. Logistic regression is used for performing regression analysis of categorical data.

[0073] In some embodiments, the threshold management unit uses logistic regression for predicting γ(t+1) based on Y(t) and A(t). Alternatively, other methods for fitting categorical data can be used, such as additional methods described in the Agresti reference cited above. In some embodiments, the time series are filtered and/or assigned non-uniform weighting before the fitting process. An exemplary method for filtering the data and fitting the filtered data is shown in FIG. 7 below. Using the statistical model, the threshold management unit calculates the value of threshold γ for the next time interval, as will be explained below.

[0074] FIG. 2 is a flow chart that schematically illustrates a method for adaptive threshold setting, carried out by threshold management unit 36, in accordance with an embodiment of the present invention. The method begins with unit 36 monitoring the behavior of system 20, at a monitoring step 50. In particular, the threshold management unit monitors threshold and SLO violations, and accumulates the measured time series Y(t) and A(t) described above. Unit 36 also records the time series of threshold values Γ(t). At the same time, the unit continually estimates the current PPV and NPV performance of threshold γ with respect to the SLO, as described above.

[0075] The threshold management unit checks whether an update to threshold γ is required, at an update checking step 52. Several alternative criteria can be used to determine whether a new threshold should be calculated. For example, in some embodiments a new threshold is calculated if the actual PPV or NPV of the threshold, as calculated in step 50 above, deviates from the desired value α or β. In another embodiment, the threshold management unit decides to update the threshold if a discrepancy is found between SLO and threshold violations (i.e., whenever the threshold is violated when the SLO is satisfied, and vice versa). The threshold management unit can also use different combinations of such criteria. Alternatively, any other suitable criterion can be used. In some cases, two or more such criteria are used in sequence, so as to reduce the computational complexity of update checking step 52.

[0076] If the result of update checking step 52 is negative, indicating no update is required, the threshold management unit maintains the existing threshold value for the next monitoring interval, at a threshold maintaining step 54. The threshold management unit updates time series Γ(t) so that γ(t+1)=γ(t). The method then returns to monitoring step 50 and the threshold management unit continues to monitor the system.

[0077] If, on the other hand, the outcome of update checking step 52 is positive, indicating a required threshold update, the threshold management unit performs a fitting of the historical time series, using logistic regression, at a fitting step 56. The logistic regression process performed by the unit 36 follows the methods described in chapter 5 of the Agresti reference cited above. Based on the historical time series Y(t), the threshold management unit estimates the probability
p({right arrow over (x)})=P(Y=1|{right arrow over (X)}={right arrow over (x)})=1−P(Y=0|{right arrow over (X)}={right arrow over (x)})   [1]
which is the probability that y(t+1)=1 (threshold violated at time t+1) given the historical time series Γ(t) and A(t). ({right arrow over (X)} denotes the vector of explanatory variables, in the present case comprising Γ(t) and A(t).) Since Y(t) is a vector of observations of binary stochastic variables, it is typically represented as a vector of 1's and 0's. p({right arrow over (x)}) can thus be estimated by counting the number of 1's in vector Y(t) and dividing the result by the length of the vector.

[0078] The processor then calculates the value of the logistic regression function

[0079] $\begin{array}{cc}\log \mathrm{it}\left(p\left(\stackrel{->}{x}\right)\right)=\ln \frac{p\left(\stackrel{->}{x}\right)}{1-p\left(\stackrel{->}{x}\right)},& \left[2\right]\end{array}$
as defined in the Agresti reference, cited above. Using this value, the threshold management unit calculates the linear regression between logit(p({right arrow over (x)})) and {right arrow over (x)}, given by
log it(p({right arrow over (x)}))=c+{right arrow over (b)}·{right arrow over (x)}  [3]

[0080] The values of regression coefficients c and {right arrow over (b)} are derived from the regression calculation, typically using a maximum-likelihood estimation. This process is well known in the art. As noted above, alternative fitting methods can also be used, such as the method shown in FIG. 7 below.

[0081] After performing the logistic regression, the threshold management unit evaluates the quality of the fit achieved by fitting step 56, at a confidence checking step 58. In one embodiment, the unit uses a double log likelihood (−2LL) test, which is well known in the art. The −2LL test is described, for example, by Kleinbaum and Klein in “Logistic Regression, a Self-Learning Text,” Springer Verlag, Second edition, July 2002, chapter 5, page 130. Alternatively, any other suitable method for quantifying the quality of the fit can be used to implement confidence checking step 58. Typically, the quality or confidence of the fit is compared with a predetermined confidence level. If the quality of the fit is insufficient, the method returns to step 54 without changing the threshold value.

[0082] If the quality of the logistic regression fit achieved by fitting step 56 is sufficient, the threshold management unit uses this fit to calculate an updated value for threshold γ, at a threshold calculation step 60. Equation [3] above can be written as

[0083] $\begin{array}{cc}p\left(\stackrel{->}{x}\right)=\frac{1}{1+e^{\left(-c-\stackrel{->}{b}·\stackrel{->}{x}\right)}}& \left[4\right]\end{array}$

[0084] Since in the present case the explanatory variables are x1≡a(t) and x2≡γ(t), equation [4] can be written as

[0085] $\begin{array}{cc}p\left(t+1\right)=\frac{1}{1+e^{\left(-c-b_1·a\left(t+1\right)-b_2·\gamma \left(t+1\right)\right)}}& \left[5\right]\end{array}$

[0086] If the SLO is violated at time t+1, then a(t+1)=1, and equation [5] can be written as

[0087] $\begin{array}{cc}p\left(t+1\right)=\frac{1}{1+e^{\left(-c-b_1-b_2·\gamma \left(t+1\right)\right)}}& \left[6\right]\end{array}$

[0088] It can be shown that as t→∞, p(t+1)→PPV. If, on the other hand, the SLO is satisfied at time t+1, then a(t+1)=0, and equation [5] can be written as

[0089] $\begin{array}{cc}p\left(t+1\right)=\frac{1}{1+e^{\left(-c-b_2·\gamma \left(t+1\right)\right)}}& \left[7\right]\end{array}$

[0090] It can be similarly shown that as t→∞, 1−p(t+1)→NPV.

[0091] Given the two relations given in equations [6] and [7] above, and the desired PPV and NPV values α and β, the value of threshold γ at time t+1 can be predicted by solving equation [6] for γ(t+1) as follows
γ(t+1)=[ln(α/(1−α))−c−b1]/b2
The current NPV (denoted β′) is then calculated using equation [7] and can be compared with the desired NPV value β. Using the desired PPV α and the attained current NPV β′ yields:

[0092] $\begin{array}{cc}\gamma \left(t+1\right)=\frac{\ln \frac{\alpha }{1-\alpha }-\ln \frac{{\beta }^{\prime }}{1-{\beta }^{\prime }}-2·c-b_1}{2·b_2}& \left[8\right]\end{array}$

[0093] The threshold management unit thus calculates the updated value γ(t+1) using the above equations, based on the desired PPV and current NPV values α and β′, and on the regression coefficients b1, b2 and c, derived by the logistic regression process at fitting step 56.

[0094] Having calculated the new threshold γ(t+1), the threshold management unit sets this value in the system, at a threshold setting step 62. The method then loops back to monitoring step 50. The threshold management unit continues to monitor the system, which now operates with the updated threshold. In the subsequent iteration of monitoring step 50, the threshold management unit augments time series Γ(t), Y(t) and A(t) with the newly-calculated threshold γ(t+1) and the new observations of the threshold and SLO violations, respectively. In the subsequent iteration of fitting step 56, the threshold management unit derives new values of c, b1 and b2 using a logistic regression on the updated time series. The process continues iteratively in this manner. Using the iterative threshold setting method described above, the actual PPV and NPV values of the threshold γ with respect to the SLO gradually converge to the desired values α and β, respectively.

[0095] An exemplary flow of the method described in FIG. 2 is given by the following pseudo-code (wherein ATS stands for Automatic Threshold Setting. The symbol Σ denotes the required confidence level. α and β are set to predetermined values, such as α=0.95, β=0.85. The symbols , and denote the logical disjunction, conjunction and negation operators, respectively.)

[0096]

	1.	ATS (α, β, Σ) {
	2.	initialize γ(0)	//Set to a random value,
			unless a default value is
			known.
	3.	while (TRUE) {	//main event loop
	4.	given SLO observation at time t, do {	//event
			arrived
	5.	boolean v← isViolated(SLO)
	6.	if ((vΛ(μ(t)<γ(t)))v(  vΛ(μ(t)>γ(t))))
	7.	if ((current PPV<α)v(current NPV<β)) {
	8.	fit logistic regression.
	9.	if Σ was achieved (use -2LL to test)
	10.	compute γ(t+1)
	11.	}
	12.	else
	13.	γ(t+1)←γ(t)
	14.	}//end: do
	15.	}//end: while (main loop)
	16.	}//end: ATS

[0097] As can be seen from equation [8] above, the value of γ(t+1) implicitly depends on the previous values γ(0), γ(1), . . . , γ(t). The dependence is carried through the regression coefficients b1, b2 and c, which are derived from the previous iteration of fitting the historical threshold values. In some cases, this dependence may introduce a bias into the regression model, which typically slows its convergence and introduces an error into the resulting threshold values. To overcome this bias effect, in some embodiments the threshold management unit inserts dummy data points into time series Γ(t) before performing fitting step 56. The dummy data points are typically interleaved with the real threshold values. In one embodiment, the dummy values are generated at random, using a uniform distribution, from the range [max( μ−3σ, 0), μ+3σ], wherein μ denotes the sample mean of metric μ, and σ denotes the sample variance of the metric. Other suitable distribution functions can also be used. The introduction of the dummy points into the calculation helps to reduce the bias and improves the model fit.

[0098] In some embodiments, some of the data points of time series A(t) and Y(t) are given different weights, in order to improve the fitting accuracy in the logistic regression. For example, data points corresponding to older observations may be given lower weight in comparison to more recent data points. In another exemplary scenario, SLOs and metrics of some systems exhibit periodic behavior corresponding to certain hours in a day or days in a month. Such periodic behavior is described, for example, in the Burgess paper cited above. Assigning weights in accordance with such repetitive patterns can also improve the model fit.

[0099] The inventors have implemented the adaptive threshold setting method described above using an experimental SAN system.

[0100] FIG. 3 is a block diagram that schematically illustrates the experimental setup, in accordance with an embodiment of the present invention. The experimental system comprises a tested application 70 and multiple workload applications 72. The workload applications were used to generate Input-Output (I/O) transactions and load the system. Applications 70 and 72 were simulated using conventional I/O benchmark software tools, namely Iometer and Iozone.

[0101] Applications 70 and 72 run on a workstation running under a Windows 2000™ operating system 74. The applications consumed I/O services from a Redundant Array of Independent Disks (RAID) disk array 76 through a Logical Volume Manager (LVM) 78 produced by Veritas Software Corporation (Mountain View, Calif.).

[0102] A component metric μ and a corresponding threshold γ were defined for one of the logical disk volumes, measuring the response time of the logical volume. An application metric ρ measured the response time of the tested application. An SLO was defined over ρ specifying the maximum allowable response time for a storage transaction.

[0103] Approximately 190,000 data points were measured for the component metric using LVM 78, and 375 data points were measured for the application metric. The data was then analyzed using a MATLAB™ program that implemented the method described in FIG. 2 above. Each application metric measurement was paired with the corresponding component metric measurement. The data pairs were classified as being either false-positive, false-negative, true-positive or true-negative events. If either a false-positive or a false-negative event was detected, and the target PPV or NPV values were not satisfied at a particular time instance, a new component threshold was calculated, based on the data points preceding this time instance. The threshold calculation followed the method described in FIG. 2 above. A target confidence level of Σ=0.95 was used in the logistic regression fitting. If such a confidence value was not attained, the threshold was reset to a random value, ignoring the historical values.

[0104] FIG. 4 is a plot that schematically illustrates the application metric and component metric behavior, in accordance with an embodiment of the present invention. Data points 80 show the logical volume (LV) response time (i.e., the component metric μ). Data points 82 show the corresponding response time of the application (i.e., the application metric ρ). Data points 80 exhibit a layered behavior, which implies the existence of several different modes of system behavior that do not necessarily cause SLO violation. In other words, the component metric value does not explicitly predict the SLO violations. This observation demonstrates the importance of adaptive threshold setting. It can also be observed that the application and component metrics are stochastically monotonic, since high values of data points 80 typically coincide with high values of data points 82.

[0105] FIG. 5 is a scatter plot that schematically illustrates the application metric and a component metric behavior, in accordance with another embodiment of the present invention. FIG. 5 shows the application metric ρ (the application response time) plotted against the variance of the logical volume response time. Examining FIGS. 4 and 5, it can be appreciated that the application metric has a more structured and distinct dependence on the variance of the LV response time than on the raw LV response time. This dependence implies that using the variance of the LV response time as a component metric, rather than the response time itself, is a better choice for predicting SLO violations.

[0106] FIG. 6 is a plot that schematically illustrates a component metric and a component threshold, in accordance with an embodiment of the present invention. Data points 86 show the variance of the LV response time, plotted against time. Comparing data points 86 to data points 80 of FIG. 4, it can be seen that the variance of the LV response time is indeed a better component metric, exhibiting less noise and better structure.

[0107] A plot 88 shows the values assigned to threshold γ by the adaptive threshold setting process. The SLO definition in this example regarded any application response time greater than 1700 ms an SLO violation. (Using this value, approximately 40% of the data points correspond to SLO violations.) Plot 88 shows several intervals in which the threshold value does not change, since the exemplary simulation calculates a new threshold only when a false-positive or false-negative event is detected and the PPV/NPV values deviate from the specified target values.

[0108] Using the LV response time as a component metric, PPV levels of approximately 89% and NPV levels of approximately 91% were achieved. Higher PPV values could be reached at the expense of degraded NPV, and vice versa. Using the variance of the LV response time as the metric, the achievable PPV was improved to approximately 93%.

[0109] The threshold adaptation rate was also measured. Typically, the threshold converged to its final value in approximately 10 iterations. These exemplary tests demonstrate the effectiveness of the disclosed method in automatically and adaptively setting the component threshold to values that closely predict SLO violation events.

[0110] In some practical scenarios, the accuracy of the logistic regression fitting process can be improved by considering several additional factors:

• • [0111] Some historical events are often less relevant than others to the prediction. Assigning a higher weight to meaningful events can improve the fit.
  • [0112] In some cases, relatively rare events, such as extreme SLO violations, can provide valuable insight to the operation of the system and should not be ignored or averaged-out by the regression process.
  • [0113] The quantitative value of SLO and component threshold violations (as opposed to the binary information—violated/satisfied) often carries valuable information that can be used.
  • [0114] Events in which an SLO is almost violated are often meaningful and can be used to improve the prediction.

[0115] Some applications use pre-correction and weighting techniques in order to take these factors into account. For example, Tomz et al. describe such methods in “Logistic Regression in Rare Events Data,” Journal of Computational and Graphical Statistics, (12:1), March 2003, pages 246-247, which is incorporated herein by reference.

[0116] FIG. 7 is a plot that schematically illustrates an exemplary method for filtering application metric and component metric data points, in accordance with an embodiment of the present invention. Data points 94 represent correlated application metric and component metric observations, as described above. The data points are plotted in a two-dimensional coordinate system, in which the horizontal axis corresponds to the value of the component metric, and the vertical axis corresponds to the value of the application metric. A horizontal SLO line 96 represents the application metric value regarded as SLO violation threshold.

[0117] In some embodiments, the threshold management unit performs an alternative implementation of fitting step 56 of the method of FIG. 2 above. Instead of using logistic regression, the threshold management unit fits a quadratic polynomial to the ensemble of data points 94. In general, a quadratic polynomial fit more easily accommodates rare, widely deviating events than a linear fit. A curve 98 shows -the best-fit quadratic polynomial. The polynomial intersects SLO line 96 at an intersection point denoted “R” in the figure. A filtering interval 100 having a predetermined size denoted “d” is defined, so that the interval ends at intersection point R.

[0118] The threshold management unit selects a sub-set of the data points whose horizontal coordinate (i.e., their component metric value) falls within the filtering interval. The threshold management unit then calculates the updated threshold value, in accordance with the fitted polynomial. In this embodiment, however, only the selected sub-set of data points is used in the calculation. The selection is made so that the filtering interval comprises data points that are relatively close to the SLO violation threshold. Typically, some of these data points are located above line 96, corresponding to SLO violations. The remaining data points correspond to normal system behavior, although some of them typically correspond to “near SLO violations.” The selection process thus implicitly weights and filters the data points.

[0119] FIG. 8 is a plot that schematically illustrates an alternative method for setting a threshold, in accordance with an embodiment of the present invention. The historical events of system 20 are plotted as data points 94, using the same coordinate system as FIG. 7 above. SLO line 96 marks the threshold value of application metric p that is regarded as an SLO violation. The component threshold γ is represented as a vertical line 102. Lines 96 and 102 divide the two-dimensional plane into four quadrants. It can be seen that the data points located in a quadrant 104 correspond to true negative events (i.e., events in which both the component threshold and the SLO are satisfied). Similarly, the data points located in a quadrant 106 correspond to true positive events, or events in which both the component threshold and the SLO are violated. The remaining two quadrants correspond to the false-positive and false-negative events.

[0120] Using this representation, the threshold management unit can search for the optimal value of threshold γ. In one embodiment, the unit searches for the location of line 102 that maximizes the number of data points in quadrants 104 and 106, and minimizes the number of data points in the remaining quadrants. In other words, the threshold value maximizes the combined number of true-positive and true-negative events, while minimizing the number of false-positive and false-negative events at the same time. Heuristically, a threshold value that satisfies this condition is a good predictor of SLO violations.

[0121] In another embodiment, the threshold can use the representation of FIG. 8 to estimate the PPV and NPV values of the system. The PPV value can be estimated by dividing the number of data points 94 in quadrant 106 by the total number of data points on the right hand side of threshold line 102. Similarly, the NPV of the system can be estimated by dividing the number of data points 94 in quadrant 104 by the total number of data points on the left hand side of threshold line 102. These estimates can be used by the threshold management unit to optimize the value of threshold γ with respect to the rate of true-positive and true-negative events. In these embodiments, the threshold management unit can use an exhaustive search strategy, or any other suitable search method.

[0122] Although the embodiments described above relate, by way of example, to faults in a computer system, the principles of the present invention may similarly be applied to other systems in which component performance is monitored and managed using metrics and thresholds. Such systems may comprise, for example, medical systems, industrial systems, communication systems and others.

[0123] It will thus be appreciated that the embodiments described above are cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention includes both combinations and sub-combinations of the various features described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art.