Methods and systems that identify computational-entity transactions and corresponding log/event-message traces from streams and/or collections of log/event messages

1. An improved transaction-and-associated-trace identification subsystem, incorporated within one or more computer systems of a distributed computer system, each having one or more processors and one or more memories, that identifies transactions and associated log/event-messages traces from a collection and/or stream of log/event messages, the transaction-and-associated-trace identification subsystem comprising:

first-phase transaction-and-associated-trace identification subsystem components that generate cross-correlation values for each pair of log/event-message types in the collection or stream of log/event messages; and

second-phase transaction-and-associated-trace identification subsystem components that

identify transactions and associated log/event-message traces from the generated cross-correlation values,

store the identified transactions and associated log/event-message traces in one or more of the one or more memories, and

transmit the identified transaction and associated log/event-message traces to an analysis system that identifies patterns of transaction in collections or streams of log/event messages.

2. The improved transaction-and-associated-trace identification subsystem of claim 1 wherein the first phase identification-subsystem components

receive or access the collection or stream of log/event messages;

preprocess the log/event messages to generate a log/event-message type for each log/event message;

generate a timestamp/log-or-event-message-type pair for each log/event message;

generate a time-series-like event-message-type-occurrence signal for each log/event-message type from the timestamp/log-or-event-message-type pairs generated for the log/event-message type; and

compute a cross-correlation value for each pair of time-series-like event-message-type-occurrence signals.

3. The improved transaction-and-associated-trace identification subsystem of claim 1 wherein the second phase identification-subsystem components

select those pairs of log/event-message types for which the cross-correlation value computed from their corresponding time-series-like event-message-type-occurrence signals is greater than a threshold value;

add, to a strongly-correlated-type graph, each selected pair of log/event-message types as two nodes connected by an edge representing the cross-correlation value computed for the pair of log/event-message types;

extract a set of connected-component subgraphs from the strongly-correlated-type graph;

generate an acyclic graph corresponding to each connected-component subgraph;

extract one or more log/event-message traces from each acyclic graph;

store each identified transaction corresponding to a connected-component subgraph and associated log/event-message traces extracted from the connected-component subgraph; and

transmit the identified transaction and associated log/event-message traces to an analysis system that identifies patterns of transaction in collections or streams of log/event messages.

4. A method that identifies transactions and associated log/event-message traces in a collection or stream of log/event messages and that is implemented in one or more servers or other computer systems, each including one or more processors and one or more memories, within a distributed computer system, the method comprising:

generating cross-correlation values for each pair of log/event-message types in the collection or stream of log/event messages;

identifying transactions and associated log/event-message traces from the generated cross-correlation values;

storing the identified transactions and associated log/event-message traces in one or more of the one or more memories; and

transmitting the identified transaction and associated log/event-message traces to an analysis system that identifies patterns of transaction in collections or streams of log/event messages.

5. The method of claim 4 wherein generating cross-correlation values for each pair of log/event-message types in the collection or stream of log/event messages further comprises:

receiving or accessing the collection or stream of log/event messages;

preprocessing the log/event messages to generate a log/event-message type for each log/event message;

generating a timestamp/log-or-event-message-type pair for each log/event message;

generating, for each log/event-message type included in one or more of the timestamp/log-or-event-message-type pairs, a time-series-like log/event-message-type occurrence signal; and

computing a maximum cross-correlation coefficient for each pair of time-series-like log/event-message-type occurrence signals.

6. The method of claim 5 wherein log/event-message are generated within the distributed computer system by:

message-generation-and-reporting components of hardware components of the distributed computer system, including network routers and bridges, network-attached storage devices, network-interface controllers, and other hardware components and devices; and

message-generation-and-reporting components within computer-instruction-implemented components of the distributed computer system, including virtualization layers, operating systems, and applications running within servers and other types of computer systems.

7. The method of claim 5 wherein log/event-messages include text, alphanumeric values, or numeric values that represent different types of information, including notifications of completed actions, errors, anomalous operating behaviors and conditions, various types of computational events, and warnings.

8. The method of claim 5 wherein preprocessing a log/event message to generate a log/event-message type for the log/event message further includes;

identifying fields within the log/event message; and

altering one or more variable fields selected from the identified fields to generate a base-form corresponding to the log/event message.

9. The method of claim 8

wherein variable fields are fields with content that varies among the log/event messages in the collection or stream of log/event messages; and

wherein variable fields are altered by one of

deleting the variable field,

replacing the variable field with a character or symbol that is used for replacing the variable field in those log/event messages that contain the variable field,

replacing the variable field with multiple characters or symbols that are used for replacing the variable field in those log/event messages that contain the variable field, and

abbreviating the variable.

10. The method of claim 8 wherein generating a timestamp/log-or-event-message-type pair for a log/event message further includes:

extracting a timestamp from the log/event message;

generating a base-form corresponding to the log/event message;

using, for the timestamp element of the timestamp/log-or-event-message-type pair, one of

the extracted timestamp, and

a numeric or alphanumeric value to which the extracted timestamp is mapped; and

using, for the log-or-event-message-type element of the timestamp/log-or-event-message-type pair, one of

the base-form, and

a numeric or alphanumeric value to which the base-form is mapped.

11. The method of claim 5 wherein generating, for a particular log/event-message type included in one or more of the timestamp/log-or-event-message-type pairs, a time-series-like log/event-message-type occurrence signal further comprises:

for each timestamp/log-or-event-message-type pair, generated from a log/event message in the collection or stream of log/event messages, that includes the particular log/event-message type,

determining a time interval corresponding to the timestamp included in the timestamp/log-or-event-message-type pair, and

incrementing an occurrence-count value for that time interval in the time-series-like log/event-message-type occurrence signal.

12. The method of claim 11 wherein the time intervals within the time-series-like log/event-message-type occurrence signal are of a single, fixed length in a range of ten milliseconds to a second.

13. The method of claim 5 wherein computing a maximum cross-correlation coefficient for each pair of time-series-like log/event-message-type occurrence signals further comprises:

for each pair of time-series-like log/event-message-type occurrence signals,

for each time shift τ in a set of time shifts,

computing a cross-correlation coefficient for a superposition of the first time-series-like log/event-message-type occurrence signal of the pair with the second time-series-like log/event-message-type occurrence signal of the pair shifted in time by τ; and

selecting, as the maximum cross-correlation coefficient for the pair, the largest cross-correlation coefficient computed for a superposition of the first time-series-like log/event-message-type occurrence signal of the pair with the second time-series-like log/event-message-type occurrence signal of the pair.

14. The method of claim 13 wherein a cross-correlation coefficient is a metric, the value of which reflects the similarity of two time-series-like log/event-message-type occurrence signals for which the cross-correlation coefficient is computed.

15. The method of claim 4 wherein identifying transactions and associated log/event-message traces from the generated cross-correlation values further comprises:

selecting those pairs of log/event-message types for which the cross-correlation value computed from their corresponding time-series-like log/event-message-type occurrence signals is greater than a threshold value;

adding, to a strongly-correlated-type graph, each selected pair of log/event-message types as two nodes connected by an edge representing the cross-correlation value computed for the pair of log/event-message types;

extracting a set of connected-component subgraphs from the strongly-correlated-type graph;

generating an acyclic graph corresponding to each connected-component subgraph; and

extracting one or more log/event-message traces from each acyclic graph.

16. The method of claim 15 wherein a strongly-correlated-type graph includes nodes, or vertices, that each represents a log/event-message type and edges that each represents a greater-than-threshold cross-correlation value computed for the log/event-message types represented by a first and second node connected by the edge.

17. The method of claim 15

wherein each node of a connected-component subgraph is connected by an edge to at least one other node of the subgraph; and

wherein no node of the connected-component subgraph is connected by an edge to a node not contained in the connected-component subgraph.

18. The method of claim 15 wherein generating an acyclic graph corresponding to each connected-component subgraph further comprises:

choosing, as the root node of the acyclic graph, a node of the connected-component subgraph representing a log/event-message type based on the log/event-message type occurring more frequently in the collection or stream of log/event message than the other log/event-message types represented by other nodes of the connected-component subgraph as well as time ordering of the occurrences of log/event-message types; and

carrying out a recursive depth-first search of the remaining nodes of the connected-component subgraph, with any node encountered in the recursive depth-first search without a connection to a node not already included in the acyclic graph included in in the acyclic graph as a leaf node and with non-leaf nodes encountered in the search added to the acyclic graph as non-root, non-leaf interior nodes of the acyclic graph.

19. The method of claim 15 wherein extracting one or more log/event-message traces from an acyclic graph further comprises:

generating a trace for each leaf node of the acyclic graph by traversing the acyclic graph from the leaf node back to the root node.

20. A physical data-storage device that stores computer instructions that, when executed by processors within one or more computer systems of a distributed computer system, control the one or more computer systems to identify transactions and associated log/event-message traces in a collection or stream of log/event messages by:

generating cross-correlation values for each pair of log/event-message types in the collection or stream of log/event messages;

identifying transactions and associated log/event-message traces from the generated cross-correlation values;

storing the identified transactions and associated log/event-message traces in one or more of one or more memories; and

transmitting the identified transaction and associated log/event-message traces to an analysis system that identifies patterns of transaction in collections or streams of log/event messages.