Systems and methods for trie-based automated discovery of patterns in computer logs
Systems and methods for tokenization of log records for efficient data storage, log querying, and log data analytics can utilize a trie pattern conversion of the log files, storing trie data pattern IDs, free parameters, and metadata instead of the entire log record. New trie patterns can be discovered automatically by counting the occurrences of tokens matching wildcards for existing patterns.
1. A log processing system comprising:
a processor;
a datastore connected to the processor;
a module running on the processor collecting logs from a plurality of computer applications, the logs including timestamped strings listing at least one of computer hardware events, computer software events, and messages sent to or from a computer;
a module running on the processor tokenizing a log into a sequence of tokens to be used as keys in a stored trie, wherein the sequence of tokens comprises character strings delimited by spaces;
a module running on the processor, matching iteratively, token by token, the sequence of tokens to a sequence of nodes in the stored trie, wherein the sequence of nodes comprises well defined type and wild card type nodes corresponding to the tokens, each node in the sequence of nodes being single well defined, single-token wildcard, or multi-token wildcard type, wherein a last matched node in the sequence of nodes is associated with a pattern identifier of a pattern represented by the sequence of nodes, and wherein the matching is performed at least in part by i) using a node as a log token in case the log token is matched to a single well defined type node and ii) generating parameters for later storage in case the log token is matched to a wildcard type node;
a module running on the processor extracting the parameters and metadata from the log, the metadata comprising at least one of IP address, timestamp, and date;
a module running on the processor storing the log to the datastore as a combination of the pattern identifier associated with the last matched node in the sequence of nodes in the stored trie, the parameters, and the metadata, wherein the datastore contains a separate datastore for storing pattern identifiers, and in response to determining that datastore requirements are not equal for multiple possible sequences of tokens, then a sequence with a lowest datastore requirement is selected for the storing;
a module running on the processor counting instances of a given parameter of the parameters and, when a count of the given parameter goes over a pre-defined threshold number for a given log, adding a non-wildcard type node to the stored trie corresponding to the given parameter and modifying the given log and all subsequent logs to use the node as a new token before the storing to the datastore;
a module running on the processor making a query by tokenizing a query request and matching the tokenized query request to patterns of the stored trie; and
a module running on the processor updating existing logs based on the new token.
2. A computer-based method for improving the storage of computer logs, the method comprising:
collecting logs from a plurality of applications, the logs including timestamped strings listing at least one of computer hardware events, computer software events, and lists of messages sent to or from a computer;
tokenizing, by a processor, a log into a sequence of tokens to be used as keys in a stored trie, wherein the sequence of tokens comprises character strings delimited by spaces;
iteratively matching the sequence of tokens, by the processor, token by token, to a sequence of nodes in the stored trie, wherein the sequence of nodes comprises well defined type and wild card type nodes corresponding to the tokens, each node in the sequence of nodes being single well defined, single-token wildcard, or multi-token wildcard type, wherein a last matched node in the sequence of nodes is associated with a pattern identifier of a pattern represented by the sequence of nodes, and wherein the matching is performed at least in part by i) using a node as a log token in case the log token is matched to a single well defined type node and ii) generating parameters for later storage in case the log token is matched to a wildcard type node;
extracting, by the processor, the parameters and metadata from the log, the metadata comprising at least one of IP address, timestamp, and date;
storing the log as a combination of the pattern identifier associated with the last matched node in the sequence of nodes in the stored trie, the parameters, and the metadata, wherein the datastore contains a separate datastore for storing pattern identifiers, and wherein in response to determining that datastore requirements are not equal for multiple possible sequences of tokens, then a sequence with a lowest datastore requirement is selected for the storing;
counting instances of a given parameter and, when a count of the given parameter goes over a pre-defined threshold number for a given log, adding a non-wildcard type node to the stored trie corresponding to the given parameter and modifying the given log and all subsequent logs to use the node as a new token before the storing to the datastore;
making a query by tokenizing a query request and matching the tokenized query request to patterns of the stored trie; and
updating existing logs based on the new token.