Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-02-10
2001-12-11
Breene, John (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06330564
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to automating data analysis tasks and more specifically to diagnosing performance and availability problems in information systems using data structured as a multidimensional database.
BACKGROUND OF THE INVENTION
A critical element of computer operations and data management is managing performance problems, such as resolving long response times in client-server systems and low throughputs for nightly database updates. Such considerations require mechanisms for detecting, diagnosing, and resolving performance problems. The present invention addresses diagnosis of computer performance problems.
Often, diagnosis proceeds in two phases. The first is problem isolation in which the problem is localized, such as to a component (e.g., router), user, and/or time. The second phase is root-cause analysis in which the underlying cause of the problem is determined, such as identifying a business application that uses high-overhead operating system services.
Ideally, both phases of diagnosis are automated. Unfortunately, it is difficult in practice to automate root-cause analysis in that such analysis requires a detailed knowledge of the system being analyzed. The requisite knowledge is often difficult to acquire, represent, and maintain.
In contrast, problem isolation can be approached in a more general way. Consider a computer installation in which users are experiencing long response times. A commonly used approach to problem isolation is to structure measurements based on abstraction hierarchies. Each hierarchy consists of multiple levels, and within levels there are abstraction instances. Problem isolation consists of repeatedly: (a) selecting levels within abstraction hierarchies that best characterize the problem and then (b) focusing on those abstraction instances that most evidence the problem within the levels selected.
To illustrate the concept of abstraction hierarchies and to demonstrate problem isolation based on abstraction hierarchies, a running example is introduced. The example considers response time problems for which there are three abstraction hierarchies: time, configuration element, and workload. Within the time hierarchy, there are levels for shift, hour, and minute. Within shift, the abstraction instances are 1, 2, and 3. Within hour are abstraction instances of hours for a shift. For example, shift
1
has the hours 8, 9, 10, 11, 12, 1, 2, 3, and 4. Within minute are the minute values within an hour for a shift. Similarly, the configuration element hierarchy has the levels subnet and host; the workload hierarchy has levels division, department, user, and transaction.
To demonstrate problem isolation using abstraction hierarchies, the following scenario is considered for the running example, with reference to FIG.
2
:
Step 1: The analyst computes average response times for the highest level in each abstraction hierarchy. That is, the analyst computes average response times for each: (a) shift (for the time hierarchy), (b) subnet (for the configuration element hierarchy), and (c) division (for the user hierarchy).
Step 2: The analyst makes a judgment as to which abstraction hierarchy best isolates the performance problem. In the running example, the analyst selects the hierarchy with the largest range of response time values, which is the configuration element hierarchy.
Step 3: The analyst makes a judgment as to which instances in the abstraction hierarchy selected in Step 2 best localize the problem. In the running example, the analyst selects the instance with the largest value, which is 9.2.15.
Step 4. The analyst repeats the foregoing until problem isolation has been completed.
In support of the foregoing scenario, measurement data are often placed into a relational database, which allows analysts to use general purpose reporting and analysis tools. A relational database structures data into tables. The columns or attributes of a table specify information that is present in each row of the table. In the running example, a single table with a column for each level in an abstraction hierarchy is provided, specifically: shift, hour, minute, subnet, host, division, department, user, and transaction.
Although the relational model offers advantages in analysis, it does not directly support abstraction hierarchies. This drawback motivates the structuring of data into a multidimensional database (MDDB), sometimes referred to as On-line Analysis Processing (OLAP). An MDDB provides support for abstraction hierarchies and for navigations between levels in abstraction hierarchies. MDDBs have been implemented in many ways (e.g., R. Agrawal, A. Gupta, and Sunit Sarawagi, “Modeling Multidimentional Databases,” International Conference on Data Engineering, 1997, pp. 232-242; R. Kimbell, The Data Warehouse Toolkit, John Wiley and Sons, 1996; and SAS, “SAS/EIS” Software, http://www.sas.com/software/components/eis.html, 1998).
For expository convenience, an MDDB is viewed as a layer on top of a relational database (as in SAS, 1998). An MDDB cube (or slice) specifies a subset of the data within a relational table. Subcubes are structured so as to facilitate the aggregations needed to support abstraction hierarchies. Specifically, a subset of the attributes of the underlying relational table are partitioned into dimensions. Dimensions correspond to the abstraction hierarchies. Attributes within a dimension are arranged hierarchically, which corresponds to levels in the abstraction hierarchies.
Distinction is made between two kinds of dimensions. The first are category dimensions. A category dimension consists of category attributes that qualify the nature of what is measured (e.g., system, time, user). Category attributes are typically strings, time values, or integers. Second, there are metric dimensions. A metric dimension is composed of metric attributes that provide measures of interest (e.g., response times, waits, throughputs). An MDDB schema has one metric dimension and zero or more category dimensions. In the running example, the category dimensions are configuration element, time, and workload. The metric dimension consists only of response time, although there could be other attributes as well, such as wait times and service times (which are components of response times).
A cube is described by an MDDB tuple, which consists of a coordinate vector for each dimension in an MDDB schema. For the metric dimension, the coordinate vector only specifies the level considered (e.g., wait times). For a category dimension, the coordinate vector specifies the abstraction instances used for levels in the dimension hierarchy. For example, a coordinate vector for the time dimension in the running example is: shift=1, hour=8. Note that: (a) not all levels need have an abstraction instance specified, and (b) an abstraction instance is specified at level N in the hierarchy only if an abstraction instance is also specified at level N−1. An MDDB tuple contains all the coordinate vectors for each dimension.
The value of a cube is obtained by querying the underlying relational data and computing an aggregate value of the metric attribute (e.g., average response time). The rows obtained in the query are determined by the category coordinates, and the aggregation function and values used are determined by the metric coordinate. Details on how to construct such a query are contained in the aforementioned Kimbell reference.
“Drill-down” is an operation performed on a cube for one or more dimensions in the MDDB schema of that cube. Drill-down produces new cubes that have: (a) the same coordinates as the original cube for the non-drill-down dimensions and (b) a longer coordinate vector in the drill-down dimension due to the fact that an abstraction instance is specified for the next lower attribute in the drill-down dimension.
Drill-down is illustrated using the running example. Consider the cube with the coordinate vectors:
configuration element: subnet=9.2.15
time: shift=1, hour=8
user: divisio
Hellerstein Joseph L.
Yue Po Chang
Breene John
Dougherty Anne Vachon
Ellenbogen Wayne L.
International Business Machines - Corporation
Pham Linh M
LandOfFree
System and method for automated problem isolation in systems... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for automated problem isolation in systems..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for automated problem isolation in systems... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2561541