Compression techniques for encoding stack trace information

• US 10,467,123 B2
• Filed: 05/05/2017
• Issued: 11/05/2019
• Est. Priority Date: 05/09/2016
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Chan, Eric S.
• Primary Examiner(s): Zhen, Wei Y
• Assistant Examiner(s): Ung, Lanny N
• Application Number:
  US15/588,523
• Publication Number:
  US 20170322861A1
• Time in Patent Office: 914 Days
• Field of Search: 717128
• CPC Class Codes: G06F 11/3037 where the computing system component is a memory, e.g. virtual memory, cache accessing, addressing or allocating within memory systems or architectures G06F12/00; checking stores for correct operation G11C29/00
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 11/3442 for planning or managing the needed capacity
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 11/3471 Address tracing
• CPC Class Codes: G06F 11/36 Preventing errors by testing or debugging software
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 2201/86 Event-based monitoring
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5005 to service a request
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/5022 Mechanisms to release resources
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/505 : considering the load
• CPC Class Codes: G06F 9/5055 : considering software capabilities, i.e. software resources associated or available to the machine
• CPC Class Codes: G06F 9/5083 : Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 41/5009 : Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]

Abstract

Embodiments provide a thread classification method that represents stack traces in a compact form using classification signatures. Some embodiments can receive a stack trace that includes a sequence of stack frames. Some embodiments may generate, based on the sequence of stack frames, a trace signature that represents the set. Some embodiments may receive one or more subsequent stack traces. For each of the one or more subsequent stack traces, some embodiments may determine whether a subsequent trace signature has been generated to represent the sequence of stack frames included within the subsequent stack trace. If not, some embodiments may generate, based on the trace signature and other subsequent trace signatures that were generated based on the trace signature, the subsequent trace signature to represent the subsequent sequence of stack frames.

Claims

1. A computer-implemented method comprising:

receiving, by a computer, a first stack trace including a first sequence of stack frames;

generating, based at least in part on the first sequence of stack frames, a first trace signature that represents the first sequence of stack frames;

receiving, by the computer, one or more subsequent stack traces; and

for at least one of the one or more subsequent stack traces;

determining whether a subsequent trace signature has been generated to represent a subsequent sequence of stack frames included by the at least one of the one or more subsequent stack traces; and

based at least in part on determining that the subsequent trace signature has not been generated;

determining, from at least one of the one or more subsequent stack traces, a second stack trace signature including a second sequence of stack frames;

determining that the first sequence of stack frames and the second sequence of stack frames share a matching sequence of stack frames;

determining a second trace signature based at least in part of the matching sequence of stack frames; and

generating, based at least in part on the second trace signature and other subsequent trace signatures that were generated based at least in part on the second trace signature, the subsequent trace signature to represent the subsequent sequence of stack frames.

2. The computer-implemented method of claim 1,

wherein generating the second trace signature comprises:

determining that a non-matching subsequence of stack frames included in first sequence of stack frames differs from a non-matching subsequence of stack frames included in the second sequence of stack frames;

generating a first segment signature that represents the matching subsequence of stack frames;

generating a second segment signature that represents the non-matching subsequence of stack frames included in the second sequence of stack frames; and

generating the second trace signature, wherein the second trace signature includes the first segment signature and the second segment signature.

3. The computer-implemented method of claim 2, wherein generating the second trace signature further comprises:

generating a third segment signature that classifies the non-matching subsequence of stack frames included in the first sequence of stack frames; and

modifying the first trace signature to include the first segment signature and the third segment signature.

4. The computer-implemented method of claim 2, wherein the first trace signature is associated with a first counter that is incremented when any stack trace including the first sequence of stack frames is received and the second trace signature is associated with a second counter that is incremented when any stack trace including the second sequence of stack frames is received.

5. The computer-implemented method of claim 4,

wherein the first segment signature is associated with a third counter that is incremented when any stack trace including the matching subsequence of stack frames is received;

wherein the second segment signature is associated with a fourth counter that is incremented when any stack trace including the non-matching subsequence of stack frames included in the second sequence of stack frames is received;

wherein the third counter is copied from the first counter when the first segment signature is generated; and

wherein the fourth counter is copied from the second counter when the second segment signature is generated.

6. The computer-implemented method of claim 1, wherein the first trace signature corresponds to a tuple, wherein the tuple includes a binary tree that includes a node as a root node of the binary tree, wherein the node represents the first sequence of stack frames.

7. The computer-implemented method of claim 6,

wherein determining whether a subsequent trace signature has been generated to represent a subsequent sequence of stack frames included by the at least one of the one or more subsequent stack traces comprises determining whether one or more previously generated nodes represents the subsequent sequence of stack frames, the one or more previously generated nodes including the node;

and

wherein generating the subsequent trace signature to represent the subsequent sequence of stack frames comprises;

determining one or more subsequences of stack frames included in the subsequent sequence of stack frames that are not represented by the one or more previously generated nodes;

generating one or more additional nodes to represent the one or more subsequences of stack frames included in the subsequent sequence of stack frames;

incorporating at least one of the one or more additional nodes into one or more previously generated binary trees of one or more previously generated tuples, the one or more previously generated binary trees including the binary tree and the one or more previously generated tuples including the tuple;

generating one or more additional binary trees, wherein at least one of the one or more additional binary trees includes at least one of the one or more additional nodes; and

generating an additional tuple that includes the one or more additional binary trees, wherein the subsequent trace signature corresponds to the additional tuple.

8. The computer-implemented method of claim 7, wherein each tuple, each node, and each stack frame is uniquely identified by an integer.

9. The computer-implemented method of claim 6, wherein the tuple is a first tuple, wherein the binary tree is a first binary tree, and wherein the node is a first node;

wherein generating the second trace signature comprises;

determining that the first sequence of stack frames and the second sequence of stack frames share a matching subsequence of stack frames and that a non-matching subsequence of stack frames included in first sequence of stack frames differs from a non-matching subsequence of stack frames included in the second sequence of stack frames;

generating a second node that represents the matching subsequence of stack frames;

generating a third node that represents the non-matching subsequence of stack frames included in the second sequence of stack frames;

generating a second binary tree that includes the second node and a third binary tree that includes the third node; and

generating a second tuple that includes the second and third binary trees, wherein the second node and the third node are siblings and the second trace signature corresponds to the second tuple.

10. The computer-implemented method of claim 9, wherein generating the second trace signature further comprises:

generating a fourth node that represents the matching subsequence of stack frames;

generating a fifth node that represents the non-matching subsequence of stack frames included in the first sequence of stack frames; and

adding the fourth node and the fifth node to the first binary tree as children of the first node.

11. A system comprising:

one or more processors; and

a memory accessible to the one or more processors, the memory storing one or more instructions that, upon execution by the one or more processors, causes the one or more processors to;

receive a first stack trace including a first sequence of stack frames;

generate, based at least in part on the first sequence of stack frames, a first trace signature that represents the first sequence of stack frames, wherein the first trace signature corresponds to a first tuple, wherein the first tuple includes a first binary tree that includes a first node as a root node of the first binary tree, wherein the first node represents the first sequence of stack frames;

receive one or more subsequent stack traces including a second stack trace, the second stack trace including a second sequence of stack frames; and

for at least one of the one or more subsequent stack traces;

determine whether a subsequent trace signature has been generated to represent a subsequent sequence of stack frames included by the at least one of the one or more subsequent stack traces; and

based at least in part on determining that the subsequent trace signature has not been generated;

determine, based at least in part on the at least one of the one or more subsequent stack traces, a second stack trace signature including a second sequence of stack frames;

generate a second node based at least in part on comparing the first sequence of stack frames against the second sequence of stack frames;

generate a second tuple including a second binary tree, wherein the second binary tree includes the second node;

generate a second trace signature representing the second sequence of stack frames, the second trace signature corresponding to the second tuple; and

generate, based at least in part on the first trace signature and other subsequent trace signatures that were generated based at least in part on the first trace signature, the subsequent trace signature to represent the subsequent sequence of stack frames.

12. The system of claim 11,

wherein generating the second trace signature comprises:

determining that the first sequence of stack frames and the second sequence of stack frames share a matching subsequence of stack frames and that a non-matching subsequence of stack frames included in first sequence of stack frames differs from a non-matching subsequence of stack frames included in the second sequence of stack frames;

generating a first segment signature that represents the matching subsequence of stack frames;

generating a second segment signature that represents the non-matching subsequence of stack frames included in the second sequence of stack frames; and

generating the second trace signature, wherein the second trace signature includes the first segment signature and the second segment signature.

13. The system of claim 11, wherein generating the second trace signature comprises:

determining that the first sequence of stack frames and the second sequence of stack frames share a matching sequence of stack frames; and

generating the second trace signature based at least in part of the matching sequence of stack frames.

14. The system of claim 11,

wherein determining whether a subsequent trace signature has been generated to represent a subsequent sequence of stack traces included by the at least one of the one or more subsequent stack traces comprises determining whether one or more previously generated nodes represents the subsequent sequence of stack frames, the one or more previously generated nodes including the first node;

and

wherein generating the subsequent trace signature to represent the subsequent sequence of stack frames comprises;

determining one or more subsequences of stack frames included in the subsequent sequence of stack frames that are not represented by the one or more previously generated nodes;

generating one or more additional nodes to represent the one or more subsequences of stack frames included in the subsequent sequence of stack frames;

incorporating at least one of the one or more additional nodes into one or more previously generated binary trees of one or more previously generated tuples, the one or more previously generated binary trees including the first binary tree and the one or more previously generated tuples including the first tuple;

generating one or more additional binary trees, wherein at least one of the one or more additional binary trees includes at least one of the one or more additional nodes; and

generating an additional tuple that includes the one or more additional binary trees, wherein the subsequent trace signature corresponds to the additional tuple.

15. A non-transitory computer-readable medium storing one or more instructions that, upon execution by one or more processors, cause the one or more processors to:

receive a first stack trace including a first sequence of stack frames;

generate, based at least in part on the first sequence of stack frames, a first trace signature that represents the first sequence of stack frames, wherein the first trace signature corresponds to a first tuple, wherein the first tuple includes a first binary tree that includes a first node as a root node of the first binary tree, wherein the first node represents the first sequence of stack frames;

receive, by the computer, one or more subsequent stack traces including a second stack trace, the second stack trace including a second sequence of stack frames; and

for at least one of the one or more subsequent stack traces;

determine whether a subsequent trace signature has been generated to represent a subsequent sequence of stack frames included by the at least one of the one or more subsequent stack traces; and

based at least in part on determining that the subsequent trace signature has not been generated;

determine, based at least in part on the at least one of the one or more subsequent stack traces, a second stack trace signature including a second sequence of stack frames;

generate a second node based at least in part on comparing the first sequence of stack frames against the second sequence of stack frames;

generate a second tuple including a second binary tree, wherein the second binary tree includes the second node;

generate a second trace signature representing the second sequence of stack frames, the second trace signature corresponding to the second tuple; and

generate, based at least in part on the second trace signature and other subsequent trace signatures that were generated based at least in part on the second trace signature, the subsequent trace signature to represent the subsequent sequence of stack frames.

16. The non-transitory computer-readable medium of claim 15,

wherein each of the stack trace and the one or more subsequent stack traces corresponds to a running thread executing on behalf of a multi-threaded program;

and

wherein the stack trace and the one or more subsequent stack traces are received in response to one or more thread dumps of the multi-threaded program, the one or more thread dumps being performed at different time points while the multi-threaded program is executing.

17. The non-transitory computer-readable medium of claim 15,

wherein each of the stack trace and the one or more subsequent stack traces corresponds to a running thread executing on behalf of a multi-threaded program;

wherein a plurality of stack traces are obtained from one or more thread dumps of the multi-threaded program, the one or more thread dumps being performed at different time points while the multi-threaded program is executing;

wherein the plurality of stack traces are duplicated to obtain the stack trace and the one or more subsequent stack traces, the stack trace and the one or more subsequent stack traces each including a different sequence of stack frames;

wherein a probability of occurrence is determined for each of the stack trace and the one or more subsequent stack traces; and

wherein the stack trace and the one or more subsequent stack traces are received in order of probability of occurrence.

18. The non-transitory computer-readable medium of claim 15, further comprising the one or more instructions that, upon execution by the one or more processors, cause the one or more processors to transmit the first trace signature to a computer, thereby enabling the computer to re-create the first stack trace with the first trace signature.

19. The non-transitory computer-readable medium of claim 15, wherein each stack frame includes a method name of a called method that corresponds to the stack frame and a source file name that comprises code defining the method that was called.

20. The non-transitory computer-readable medium of claim 19, wherein a set of Huffman codes are applied to one or more methods names or one or more source file names included by one or more stack frames included by the stack trace or the one or more subsequent stack traces to compress the one or more stack frames.