SYSTEMS AND METHODS FOR TRIE-BASED AUTOMATED DISCOVERY OF PATTERNS IN COMPUTER LOGS

• US 20180046697A1
• Filed: 08/15/2016
• Published: 02/15/2018
• Est. Priority Date: 08/15/2016
• Status: Active Grant

• Current Assignee: Sumo Logic
• Original Assignee: Collective Sense LLC
• Inventors: MACIOLEK, Przemyslaw, CINCUNEGUI, Daniel, KOSZYKA, Krzysztof
• Granted Patent: US 10,866,972 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/2452 Query translation
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/285 Clustering or classification

Abstract

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.

Claims

1. A computer system including a processor and a datastore, the system comprising:

a log processing engine connected to the datastore and configured to;

collect logs from a plurality of applications;

tokenize the logs;

match each record of the logs, from their tokens, to a pattern in a stored trie, each pattern having a unique pattern ID;

extract free parameters and metadata from the logs; and

store the logs to the datastore as combinations of the pattern IDs, the free parameters, and the metadata.

2. The computer system of claim 1, wherein the log processing engine is further configured to:

generate a count of the instances of a particular token at a particular position in the pattern over a plurality of logs;

compare the count to a threshold value;

based on the comparing, modify the stored trie to include the particular token at the particular position; and

modify stored logs in the datastore to use a new pattern ID and new free parameters based on the modifying the modified stored trie.

3. The computer system of claim 1, wherein the tokens are character strings delimited by spaces.

4. The computer system of claim 1, further comprising a separate datastore for the stored trie.

5. The computer system of claim 4, wherein the separate datastore has faster access than the datastore.

6. A computer-based method for storing computer logs, the method comprising:

collecting logs from a plurality of applications;

tokenizing, by a processor, the logs;

matching, by the processor, each record of the logs, from their tokens, to a pattern in a stored trie, each pattern having a unique pattern ID;

extracting, by the processor, free parameters and metadata from the logs; and

storing the logs to the datastore as combinations of the pattern IDs, the free parameters, and the metadata.

7. The method of claim 6, further comprising:

generate a count of the instances of a particular token at a particular position in the pattern over a plurality of logs;

compare the count to a threshold value;

based on the comparing, modify the stored trie to include the particular token at the particular position; and

modify stored logs in the datastore to use a new pattern ID and new free parameters based on the modifying the modified stored trie.

8. The method of claim 7, wherein the tokens are character strings delimited by spaces.

9. The method of claim 6, wherein the pattern ID of the pattern is identified by a final node in the pattern.

10. The method of claim 6, further comprising:

making a query to the datastore by tokenizing a query request and matching the tokenized query request to patterns of the stored trie.