CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims priority to U.S. application Ser. No. 16/539,861, filed Aug. 13, 2019, the contents of which are incorporated herein by reference in their entirety.

TECHNICAL FIELD

The present disclosure relates to identifying structure in a data stream to transform the data stream into structured data. More specifically, this disclosure relates to tokenizing log messages and clustering the tokenized log messages to represent patterns in the log messages.

BACKGROUND

Computer systems can be used to transmit, receive, and/or process data. For instance, a server computer system can be used to receive and store resources (e.g., web content, such as a webpage), and make the content available to one or more client computer systems. Upon receiving a request for the content from a client computer system, the server computer system can retrieve the requested content, and transmit the content to the client computer system to fulfill the request.

Computer systems can be configured to monitor operations and provide data representing those operations as a response to a request for data. The data representing those operations can be in the form of data logs.

SUMMARY

The systems and methods described in this document are configured to receive a data stream including data entries (e.g., log messages) that are provided by at least one computing system and transform the data stream into a structured representation that can be queried by at least one computing system. The systems and methods are configured to receive a data stream (e.g., a sequence of characters) from at least one computing system, parse the data stream to determine the contents of the data entries, and transform the data stream into structured data that includes metadata describing the data entries. The systems and methods are configured to use the metadata to cluster the logs according to at least one metric, respond to queries about the logs, output data about the logs, and so forth.

Implementations of the subject matter described herein can provide various technical benefits. Generally, a computing system that monitors the behavior of at least one other computing system (or itself) receives a data stream (e.g., log data) that includes information representing the operation of computing system(s) being monitored. Generally, the data stream includes mostly repetitive data that provides information about the nominal operations of the computing system. A relatively small portion of the data stream can include data indicative of an anomaly in the operations of the computing system.

However, rather than discard the majority of the data stream indicating nominal operation, it may be useful to interpret portions of the data stream indicating anomalous operation of the computing system in the context of the rest of the data stream. It may be useful to structure the data stream so that the computing system can perform analyses on the data stream, respond to queries about the data stream, and so forth. Additionally, it may be useful to reduce the size of the data stream and store information about the data stream to provide a manageable amount of data for review by a system operator. For example, in circumstances in which large portions of the data stream include semi-redundant data that may differ only in unimportant ways (e.g., common log messages with different dates), it may be desirable to store only data about the semi-redundant data (such as how many messages were received) rather than the semi-redundant data itself.

However, it can be difficult to determine how to compress the data stream into a smaller representation, as each data entry can be unique (e.g., have a unique time stamp, etc.). It is not straightforward to simply combine identical data entries or similar data entries of the data stream, because while the data entries may include similar building blocks of information (e.g., have similar structure), the values of the building blocks can be entirely different. For example, two log messages can report that a first host and a second host responded to a service request without fault. It may be desirable to combine this into a representation indicating that the service is responding properly, but the varying time stamps and host identifiers in the data entries can cause the log messages to appear (facially) to be very different. It can also be difficult to identify what the building blocks of the data stream are.

To compress the data stream, the computing system determines what data should be preserved in the compressed representation of the data stream, and what data can be discarded, so that the compressed representation is still representative of the behavior of the computing system. For example, a structure of log messages can be retained by tokenizing the log message without saving the details of what is in the log message. In the above example, it can be desirable to show that the service responded to two requests without fault, but it might not be necessary to preserve the particular hostname that was associated with the response. It might also be unnecessary to preserve the time stamp associated with each message (once the data representing the time stamp is identified as being a time stamp).

To overcome the above problems and achieve these solutions, for example, the systems described herein are configured to transform the data stream, such as log data that is received by a computing system, into structured data including building blocks (e.g., tokens) that are identified in the data stream. The building blocks of the structured data are identified by parsing the data stream and determining which portions of the data stream are redundant or semi-redundant. The structured data includes metadata that enables the computing system to respond to queries about the data stream. For example, the computing system can be configured to parse received log messages to generate at least one token representing each log message. Each of the tokens are associated with metadata that describes the token.

The computing system can reduce the size of the data stream by merging portions of the data stream (e.g., clustering log messages of the data stream into data clusters). For example, log messages represented by similar or identical groups of tokens can be clustered together. The computing system can respond to queries for log messages including particular tokens, display clusters of log messages, etc. The computing system can thus output data (e.g., a list of log message clusters) that can assist an operator with identifying anomalies of the computing system. For example, a record of thousands or even millions of log messages can be compressed into hundreds or tens of clusters that represent the operations of the computing system. The cluster representation of the log messages removes redundant data that does not provide additional insight into the operations of the computing system while preserving data that can be indicative of anomalies or other interesting behavior of the computing system.

In an aspect, a process for processing a data stream to identify a structure of the data stream includes receiving the data stream including at least one log message, each log message including a sequence of characters. The process includes retrieving, from a data storage, a set of rules for encoding log message characters into at least one token. The process includes parsing the at least one log message as the at least one log message is received. Generally, parsing includes generating a plurality of tokens according to at least one rule of the set of rules. In some implementations, each token represents a corresponding portion of the sequence of characters of the at least one log message. The parsing includes forming a sequence of tokens from the plurality of tokens. The parsing includes assigning, to at least one token of the sequence of tokens, at least one attribute value describing the corresponding portion of the sequence of characters of the corresponding token to which the attribute value is assigned. The process includes assigning the sequence of tokens to a cluster. Generally, assigning the sequence of tokens to the cluster includes determining that the sequence of tokens matches a pattern by which the cluster is characterized. The clustering includes merging the sequence of tokens with the cluster. The process includes outputting a representation of the cluster including the sequence of tokens included in the cluster. Generally, the cluster is indicative of a structure of at least a portion of the data stream.

In some implementations, the process includes determining that at least the portion of the sequence of characters represented by a token of the sequence of tokens includes a variable having a predetermined type. The process includes assigning an attribute value to the token indicating the type of the variable.

In an aspect, the set of rules includes a graph including nodes and edges. Parsing the at least one log message includes initializing a position in the graph at a root node of the nodes, and for successive characters of the log message, traversing the graph from the root node along a path of the nodes and the edges until an end node is reached. The end node represents a particular token. The process includes encoding each character represented by the path of the nodes and the edges into the particular token represented by the end node.

In some implementations, the set of rules includes a lookup table including at least one entry. The at least one entry includes a mapping between a particular sequence of characters and a particular token. Parsing the at least one log message includes determining that at least a portion of the sequence of characters of the log message matches the particular sequence of characters of an entry of the lookup table, and encoding at least the portion of the sequence of characters as the particular token.

In some implementations, determining that the sequence of tokens matches a pattern by which the cluster is characterized includes determining that the sequence of tokens and the cluster each include a same number of tokens and determining that the sequence of tokens and the cluster each include mergeable attribute values in a same order.

In some implementations, assigning the sequence of tokens to the cluster includes determining that the sequence of tokens comprises a particular token at a particular position in the sequence of tokens, determining that the cluster comprises a unmergeable token at the particular position in the cluster, and sorting, in response to the determining, the sequence of tokens into a different cluster regardless of remaining tokens of the sequence of tokens.

In an aspect, an attribute value represents a category of the sequence of characters represented by the token, the category including one of a key value, a date, an index, a query, an error code, an error message, and a variable value.

In an aspect, the representation further includes a list of each cluster generated from the data stream, the list including the representation of the cluster. In some implementations, the list of each cluster generated from the data stream is ordered based on a count value associated with each cluster.

In an aspect, outputting the representation of the cluster is responsive to receiving a request for the representation of the cluster from a client device. For example, at least one token of the representation of the cluster is represented as a code word or code symbol, the code word or code symbol being selected based on an attribute value associated with the at least one token.

In some implementations, a token of the plurality of tokens represents a variable having a first value. The token is configured to be merged with a corresponding token of the cluster representing the variable having a second value, the first value being different from the second value.

In an aspect, a computing system for obtaining performance metrics for one or more computing devices includes a parsing module and a clustering module. The parsing module is configured for performing operations including receiving the data stream comprising at least one log message, each log message comprising a sequence of characters, and retrieving, from a data storage, a set of rules for encoding log message characters into at least one token. Parsing the at least one log message as the at least one log message is received, wherein parsing includes generating a plurality of tokens according to at least one rule of the set of rules. Each token represents a corresponding portion of the sequence of characters of the at least one log message, and forming a sequence of tokens from the plurality of tokens. Parsing includes assigning, to at least one token of the sequence of tokens, at least one attribute value describing the corresponding portion of the sequence of characters of the corresponding token to which the attribute value is assigned. The clustering module is configured to perform operations including assigning the sequence of tokens to a cluster. Assigning the sequence of tokens to the cluster includes determining that the sequence of tokens matches a pattern by which the cluster is characterized, and merging the sequence of tokens with the cluster. The computing system is configured to output a representation of the cluster comprising the sequence of tokens included in the cluster, the cluster indicative of a structure of at least a portion of the data stream.

In an aspect, one or more non-transitory computer readable media storing instructions that are executable by one or more processors configured to perform operations for processing a data stream to identify a structure of the data stream. The operations include receiving the data stream including at least one log message, each log message including a sequence of characters. The operations include retrieving, from a data storage, a set of rules for encoding log message characters into at least one token. The operations include parsing the at least one log message as the at least one log message is received. Generally, parsing includes generating a plurality of tokens according to at least one rule of the set of rules. In some implementations, each token represents a corresponding portion of the sequence of characters of the at least one log message. The parsing includes forming a sequence of tokens from the plurality of tokens. The parsing includes assigning, to at least one token of the sequence of tokens, at least one attribute value describing the corresponding portion of the sequence of characters of the corresponding token to which the attribute value is assigned. The operations include assigning the sequence of tokens to a cluster. Generally, assigning the sequence of tokens to the cluster includes determining that the sequence of tokens matches a pattern by which the cluster is characterized. The clustering includes merging the sequence of tokens with the cluster. The operations include outputting a representation of the cluster including the sequence of tokens included in the cluster. Generally, the cluster is indicative of a structure of at least a portion of the data stream

The details of one or more embodiments are set forth in the accompanying drawings and the description below. Other features and advantages will be apparent from the description and drawings, and from the claims.

