Execution flow shape compression for aggregate data reporting in an application manager

• US 8,316,354 B2
• Filed: 12/15/2005
• Issued: 11/20/2012
• Est. Priority Date: 12/15/2005
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Inventors: Vanrenen, Gabriel J., Cobb, Jeffrey R., Puryear, Daryl L.
• Primary Examiner(s): Zhen, Li B
• Assistant Examiner(s): Pan, Hang
• Application Number:
  US11/304,153
• Publication Number:
  US 20070169052A1
• Time in Patent Office: 2,532 Days
• Field of Search: 717/127, 717/128, 717/124
• US Class Current: 717/128
• CPC Class Codes: G06F 11/28 by checking the correct order of processing G06F11/08 - G06F11/26 take precedence; monitoring patterns of pulse trains H03K5/19

Abstract

Data relating to execution flows at a computer system is compressed and aggregated across multiple execution flows by categorizing each execution flow into an execution flow shape. The execution flows may represent sequences of software components that are invoked. The execution flow shapes are developed by observing the execution flows at the computer system and applying lossy compression rules, such as representing multiple iterations of a loop as a single iteration, skipping certain types of software components, such as those having a specified call stack depth, treating some of the software components as being optional, and ignoring recursive calls by the software components. The aggregation and compression allow the information from all execution flows to be combined into a small enough data set that can be reported without consuming unduly large processing overhead while still preserving as many of the interesting aspects of the execution flows as possible.

Claims

1. A computer-implemented method for monitoring execution flows, comprising:

observing an execution flow at a computer system, the execution flow comprises a sequence of invoked components, the sequence of invoked components comprises an ordered set of identifiers of the invoked components, and each invoked component is instrumented;

applying lossy compression rules to the ordered set of identifiers of the invoked components to provide a compressed sequence of invoked components, the ordered set of identifiers of the invoked components represents first and second iterations of a loop, and the applying lossy compression rules to the ordered set of identifiers of the invoked components comprises representing the first and second iterations of the loop by a single iteration of the loop in the compressed sequence of invoked components; and

defining an execution flow shape based on the compressed sequence of invoked components, the ordered set of identifiers of the invoked components identifies;

(a) a first instance of a first invoked component which represents the first invoked component starting execution in the first iteration of the loop, followed by (b) a first instance of a second invoked component which is called by the first instance of the first invoked component, followed by (c) a second instance of the first invoked component which represents the first invoked component finishing execution in the first iteration of the loop, and which represents the first invoked component starting execution in a second iteration of the loop, followed by (d) a second instance of the second invoked component which is called by the second instance of the first invoked component, followed by (e) a third instance of the first invoked component which represents the first invoked component finishing execution in the second iteration of the loop.

2. The computer-implemented method of claim 1, wherein:

the lossy compression rules result in different sequences of invoked components being represented by a same compressed sequence of invoked components.

3. The computer-implemented method of claim 1, further comprising:

marking one of the invoked components as a skipped component, such that no invoked component is added to the execution flow when the skipped component starts executing and until the skipped component finishes executing.

4. The computer-implemented method of claim 1, wherein:

for the sequence of invoked components, the lossy compression rules indicate that invoked components which have a specified call stack depth are to be ignored by not being provided in the compressed sequence of invoked components.

5. The computer-implemented method of claim 1, further comprising:

marking one of the invoked components as an optional component;

wherein, based on the lossy compression rules, a first execution flow comprising the optional component is classified into a same execution flow shape as a second execution flow which does not have the optional component, but is otherwise the same as the first execution flow.

6. The computer-implemented method of claim 1, wherein:

for the sequence of invoked components, the lossy compression rules indicate that a component which recursively calls itself is automatically compressed into a single pair of start and finish nodes in the execution flow shape.

7. The computer-implemented method of claim 1, further comprising:

aggregating data from a plurality of execution flows by categorizing each of the execution flows into a corresponding execution flow shape selected from a plurality of execution flow shapes.

8. The computer-implemented method of claim 1, wherein:

the execution flow spans one of a thread and a process.

9. The computer-implemented method of claim 1, wherein:

data representing a portion of the execution flow is compressed before the execution flow has completed executing.

10. The computer-implemented method of claim 1, wherein:

the executions flow is compressed after it has completed executing.

11. The computer-implemented method of claim of claim 1, wherein:

the invoked components are used in an e-commerce process; and

the ordered set of identifiers of the invoked components comprises names of the invoked components corresponding to their function in the e-commerce process.

12. The computer-implemented method of claim 1, wherein:

the invoked components comprise a Java Server Page, an Enterprise Java Bean and a servlet.

13. The computer-implemented method of claim 1, wherein:

the invoked components comprise a Java Database Connectivity component.

14. The computer-implemented method of claim 1, further comprising:

marking one of the invoked components as an optional component;

wherein, based on the lossy compression rules, multiple iterations of the loop are identified when the first iteration of the loop comprises the optional component and is detected, after which the second iteration of the loop does not comprise the optional component and is detected.

15. The computer-implemented method of claim 1, wherein:

in the ordered set of identifiers of the invoked components, the identifiers comprises an identifier for each start and finish of each invoked component.

16. A computer-implemented method for monitoring execution flows, comprising:

observing a sequence of software components which are invoked for an execution flow at a computer system, identifiers of the invoked software components are provided in the sequence, and each invoked software component is instrumented;

providing an ordered set of the invoked software components based on the observing;

in the ordered set, choosing a first occurrence of a first chosen software component as a potential loop start component, and testing whether the first occurrence of the first chosen software component is actually a loop start component, the testing comprises the steps of;

(a) locating second and third occurrences of the first chosen software component in the ordered set, (b) determining whether the second occurrence of the first chosen software component represents an end of a first iteration of a loop and a start of a second iteration of the loop, and (c) determining whether the third occurrence of the first chosen software component represents an end of the second iteration of the loop;

said step (b) comprises determining whether software components which are intermediate to the first and second occurrences of the first chosen software component are consistent with the first iteration of the loop, and said step (c) comprises determining whether software components which are intermediate to the second and third occurrences of the first chosen software component are consistent with the second iteration of the loop; and

if the testing indicates that the first occurrence of the first chosen software component is actually a loop start component, collapsing the first and second iterations of the loop to a single iteration.

17. The computer-implemented method of claim 16, further comprising:

defining an execution flow shape based on the sequence of software components and the single iteration.

18. The computer-implemented method of claim 16, wherein the collapsing comprises replacing the first and second iterations by the single iteration in the sequence of software components, the loop is an innermost nested loop, and the method further comprises:

identifying and collapsing a successive higher level loop in the sequence of software components which comprises the single iteration replacing the first and second iterations.

19. The computer-implemented method of claim 16, wherein:

the observing comprises observing respective sequences of software components which are invoked for the execution flow.

20. The computer-implemented method of claim 16, wherein:

the collapsing comprises replacing the first and second iterations by the single iteration in the sequence of software components.

21. The computer-implemented method of claim 16, further comprising:

if at least one of;

the step (b) determines that the second occurrence of the first chosen software component does not represent the end of the first iteration of the loop and the start of the second iteration of the loop, and the step (c) determines that the third occurrence of the first chosen software component does not represent the end of the second iteration of the loop;

in the ordered set, choosing a first occurrence of a second chosen software component as a potential loop start component, and testing whether the first occurrence of the second chosen software component is actually a loop start component by;

(d) locating second and third occurrences of the second chosen software component in the ordered set, (e) determining whether the second occurrence of the second chosen software component represents an end of a first iteration of another loop and a start of a second iteration of the another loop, and determining whether the third occurrence of the second chosen software component represents an end of the second iteration of the another loop; and

if the testing whether the first occurrence of the second chosen software component is actually a loop start component indicates that the first occurrence of the second chosen software component is actually a loop start component, collapsing the first and second iterations to a single iteration.

22. An apparatus for monitoring execution flows, comprising:

a storage device comprising processor readable code; and

a processor in communication with the storage device, the processor executes the processor readable code to;

observe an execution flow at a computer system, the execution flow comprises a sequence of invoked components, the sequence of invoked components comprises an ordered set of identifiers of the invoked components, and each invoked component is instrumented;

apply lossy compression rules to the ordered set of identifiers of the invoked components to provide a compressed sequence of invoked components, the ordered set of identifiers of the invoked components represents first and second iterations of a loop, and the lossy compression rules represent the first and second iterations of the loop by a single iteration of the loop in the compressed sequence of invoked components; and

define an execution flow shape based on the compressed sequence of invoked components, the ordered set of identifiers of the invoked components identifies;

(a) a first instance of a first invoked component which represents the first invoked component starting execution in the first iteration of the loop, followed by (b) a first instance of a second invoked component which is called by the first instance of the first invoked component, followed by (c) a second instance of the first invoked component which represents the first invoked component finishing execution in the first iteration of the loop, and which represents the first invoked component starting execution in a second iteration of the loop, followed by (d) a second instance of the second invoked component which is called by the second instance of the first invoked component, followed by (e) a third instance of the first invoked component which represents the first invoked component finishing execution in the second iteration of the loop.

23. The apparatus of claim 22, wherein:

the processor marks one of the invoked components as a skipped component such that no invoked component is added to the execution flow when the skipped component starts executing and until the skipped component finishes executing.

24. The apparatus of claim 22, wherein:

for the sequence of invoked components, the lossy compression rules indicate that invoked components which have a specified call stack depth are to be ignored by not being provided in the compressed sequence of invoked components.

25. The apparatus of claim 22, wherein:

the processor marks one of the invoked components as an optional component; and

based on the lossy compression rules, a first execution flow comprising the optional component is classified into a same execution flow shape as a second execution flow which does not have the optional component, but is otherwise the same as the first execution flow.

26. The apparatus of claim 22, wherein:

for the sequence of invoked components, the lossy compression rules indicate that a component which recursively calls itself is automatically compressed into a single pair of start and finish nodes in the execution flow shape.

27. The apparatus of claim 22, wherein the processor:

aggregates data from a plurality of execution flows by categorizing each of the execution flows into a corresponding execution flow shape selected from a plurality of execution flow shapes.

28. The apparatus of claim 22, wherein:

in the ordered set of identifiers of the invoked components, the identifiers comprises an identifier for each start and finish of each invoked component.

29. A processor readable storage device comprising processor readable code embodied thereon which programs a processor to:

observe a plurality of execution flows at a computer system, each execution flow comprises a sequence of invoked components, the sequence of invoked components comprises an ordered set of the invoked components, and each invoked component is instrumented;

apply lossy compression rules to the ordered set of the invoked components to provide a compressed sequence of invoked components, the ordered set of the invoked components represents first and second iterations of a loop, and the lossy compression rules represent the first and second iterations of the loop by a single iteration of the loop in the compressed sequence of invoked components; and

define an execution flow shape based on the compressed sequence of invoked components, the ordered set of the invoked components identifies;

(a) a first instance of a first invoked component which represents the first invoked component starting execution in the first iteration of the loop, followed by (b) a first instance of a second invoked component which is called by the first instance of the first invoked component, followed by (c) a second instance of the first invoked component which represents the first invoked component finishing execution in the first iteration of the loop, and which represents the first invoked component starting execution in a second iteration of the loop, followed by (d) a second instance of the second invoked component which is called by the second instance of the first invoked component, followed by (e) a third instance of the first invoked component which represents the first invoked component finishing execution in the second iteration of the loop.

30. The processor readable storage device of claim 29, wherein:

the processor readable code programs the processor to mark one of the invoked components as an optional component;

the sequence of invoked components comprises multiple iterations of the loop, including a first iteration of the loop which comprises the optional component, and a second iteration of the loop which does not comprise the optional component; and

based on the lossy compression rules, the multiple iterations of the loop are represented as the single iteration of the loop in the compressed sequence of invoked components.

31. The processor readable storage device of claim 29, wherein:

the processor readable code programs the processor to mark one of the invoked components as a skipped component such that no invoked component is added to the execution flow when the skipped component starts executing and until the skipped component finishes executing.

32. The processor readable storage device of claim 29, wherein:

for the sequence of invoked components, the lossy compression rules indicate that invoked components which have a specified call stack depth are to be ignored by not being provided in the compressed sequence of invoked components.

33. The processor readable storage device of claim 29, wherein:

the processor readable code programs the processor to mark one of the invoked components as an optional component; and

to define the execution flow shape, a given component which calls the optional component is treated the same as the given component.

34. The processor readable storage device of claim 29, wherein:

for the sequence of invoked components, the lossy compression rules indicate that a component which recursively calls itself is automatically compressed into a single pair of start and finish nodes in the execution flow shape.

35. The processor readable storage device of claim 29, wherein the processor readable code programs the processor to:

aggregate data from a plurality of execution flows by categorizing each of the execution flows into a corresponding execution flow shape selected from a plurality of execution flow shapes.

36. The processor readable storage device of claim 29, wherein:

the execution flow spans at least one of a thread and a process.

37. The processor readable storage device of claim 29, wherein:

the processor readable code programs the processor to mark one of the invoked components as an optional component; and

based on the lossy compression rules, multiple iterations of the loop are identified when the first iteration of the loop comprises the optional component and is detected, after which the second iteration of the loop does not comprise the optional component and is detected.

38. The processor readable storage device of claim 29, wherein:

the ordered set of the invoked components comprises an identifier for each start and finish of each invoked component.

39. A computer-implemented method for monitoring execution flows, comprising:

observing a plurality of execution flows at a computer system, each execution flow comprises a sequence of invoked components, identifiers of the invoked components are provided in the sequences, and each invoked component is instrumented;

recording the sequences of invoked components of the plurality of execution flows;

for each recorded sequence of invoked components, applying lossy compression rules to the identifiers of the invoked components to provide a corresponding compressed sequence of invoked components, one of the recorded sequences of invoked components comprises an ordered set of invoked components which represents first and second instances of a loop, the ordered set comprises;

(a) a first instance of a first invoked component which represents the first invoked component starting execution in the first instance of the loop, followed by (b) a first instance of a second invoked component which is called by the first instance of the first invoked component, followed by (c) a second instance of the first invoked component which represents the first invoked component finishing execution in the first instance of the loop, and which represents the first invoked component starting execution in a second instance of the loop, followed by (d) a second instance of the second invoked component which is called by the second instance of the first invoked component, followed by (e) a third instance of the first invoked component which represents the first invoked component finishing execution in the second instance of the loop, and the lossy compression rules represent the first and second instances of the loop by a single instance of the loop in the compressed sequence of invoked components; and

defining a plurality of execution flow shapes based on the compressed sequences of invoked components.

40. An apparatus for monitoring execution flows, comprising:

at least one storage device; and

at least one processor in communication with the at least one storage device, the at least one processor;

observes a plurality of execution flows at a computer system, each execution flow comprises a sequence of invoked components, identifiers of the invoked components are provided in the sequences, and each invoked component is instrumented;

records sequences of invoked components of the plurality of execution flows;

for each recorded sequence of invoked components, applies lossy compression rules to the identifiers of the invoked components to provide a corresponding compressed sequence of invoked components, one of the recorded sequences of invoked components comprises an ordered set of invoked components which represents first and second instances of a loop, the ordered set comprises;

(a) a first instance of a first invoked component which represents the first invoked component starting execution in the first instance of the loop, followed by (b) a first instance of a second invoked component which is called by the first instance of the first invoked component, followed by (c) a second instance of the first invoked component which represents the first invoked component finishing execution in the first instance of the loop, and which represents the first invoked component starting execution in a second instance of the loop, followed by (d) a second instance of the second invoked component which is called by the second instance of the first invoked component, followed by (e) a third instance of the first invoked component which represents the first invoked component finishing execution in the second instance of the loop, and the lossy compression rules represent the first and second instances of the loop by a single instance of the loop in the compressed sequence of invoked components; and

defines a plurality of execution flow shapes based on the compressed sequence of invoked components.