Searching for associated events in log data

• US 8,306,967 B2
• Filed: 10/02/2007
• Issued: 11/06/2012
• Est. Priority Date: 10/02/2007
• Status: Active Grant

• Current Assignee: Cloud Software Group
• Original Assignee: Loglogic (Cloud Software Group)
• Inventors: Galitsky, Boris, Botros, Sherif
• Primary Examiner(s): PYO, MONICA M
• Application Number:
  US11/866,337
• Publication Number:
  US 20090089252A1
• Time in Patent Office: 1,862 Days
• Field of Search: 707/3, 707/4, 707/5, 707/10, 707/101, 707/102, 707999003-999005, 707999101-999102, 707/713, 707/718
• US Class Current: 707/713
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/332 Query formulation
• CPC Class Codes: G06F 16/3335 Syntactic pre-processing, e.g. stopword elimination, stemming

Abstract

To retrieve a sequence of associated events in log data, a request expression is parsed to retrieve types of dependencies between events which are searched, and the constraints (e.g., keywords) which characterize each event. Based on the parsing results, query components can be formed, expressing the constraints for individual events and interrelations (e.g., time spans) between events. A resultant span query comprising the query components can then be run against an index of events, which encodes a mutual location of associated events in storage.

Claims

1. A method comprising:

creating an index of terms in log messages for retrieving one or more events in response to an input search query, the log messages comprising one or more stored events, the input search query comprising a constant component;

parsing the input search query, including identifying the constant component from the input search query;

based on results obtained from parsing the input search query, forming a span query for associated events, the span query including a first constraint for a first event, a second constraint for a second event, and a relation between the first event and second event, the span query being selected from a group of query types consisting of a sequence of events query, a multiple restriction query, and a causation query; and

running the input search query, including performing the span query on the index to determine the first event and the second event, the second event being associated with the first event according to the relation, wherein performing the span query comprises;

performing a constant query based on the constant components of the input search query to identify one or more constant events;

retrieving events preceding the one or more constant events;

building a merged event intersection lattice for one or more merged events and a constant event intersection lattice for the identified one or more constant events, each lattice including a set of event intersections between two or more sets of events;

performing a set subtraction to determine one or more differences between the merged event intersection lattice and the constant event intersection lattice; and

outputting the one or more differences as answers to the input search query, and

wherein the method is executed by one or more computers.

2. The method of claim 1, further comprising:

grouping the determined first event and second event by attributes.

3. The method of claim 1, wherein forming the span query comprises forming a sequence of event query, forming the sequence of events query comprising:

building one or more queries for individual log messages, each query including a temporal relation between the first event and the second event; and

merging the queries for individual log messages as the span query over multiple log messages.

4. The method of claim 3, wherein performing the span query comprises performing the sequence of events query, performing the sequence of events query comprising:

performing the queries for individual log messages;

determining a time span between results of the queries for individual log messages; and

verifying that the log messages occur within the determined time span.

5. The method of claim 1, wherein forming the span query comprises forming the multiple restriction query, forming the multiple restriction query comprising:

identifying an intermediate component from the input search query;

forming a query for the intermediate component;

identifying one or more keywords using results from the query for the intermediate component; and

forming query for a final component using the identified one or more keywords; and

performing the span query comprises;

performing the query for the final component; and

merging results from the from the query for the intermediate component and results from performing the query for the final component.

6. The method of claim 1, wherein forming the span query comprises forming a causation query, forming the causation query comprising:

identifying a variable component from the input search query, the variable component operable to specify one or more keywords whose correlation with preceding events will be searched; and

merging the constant component, the variable component, and a separator component that includes one or more reserved words.

7. The method of claim 6, where performing the span query comprises:

identifying the merged events to be explained; and

for at least one of the identified merged events, retrieving events preceding the identified merged event within a time span.

8. The method of claim 1, wherein the span query includes multiple query types and at least one query type includes at least one intermediate query.

9. A system comprising:

a storage device operable for storing one or more events as log messages; and

a processor coupled to the storage device and configured to perform operations comprising;

creating an index of terms in the log messages in retrieving the one or more events in response to an input search query, the log messages comprising one or more stored events, the input search query comprising a constant component;

parsing the input search query, including identifying the constant component from the input search query;

based on results obtained from parsing the input search query, forming a span query for associated events, the span query including a first constraint for a first event, a second constraint for a second event, and a relation between the first event and second event, the span query being selected from a group of query types consisting of a sequence of events query, a multiple restriction query, and a causation query; and

running the input search query, including performing the span query on the index to determine the first event and the second event, the second event being associated with the first event according to the relation, wherein performing the span query comprises;

performing a constant query based on the constant components of the input search query to identify one or more constant events;

retrieving events preceding the one or more constant events;

building a merged event intersection lattice for one or more merged events and a constant event intersection lattice for the identified one or more constant events, each lattice including a set of event intersections between two or more sets of events;

performing a set subtraction to determine one or more differences between the merged event intersection lattice and the constant event intersection lattice; and

outputting the one or more differences as answers to the input search query.

10. The system of claim 9, further comprising:

grouping the determined first event and second event by attributes.

11. The system of claim 9, wherein the input search query comprises a variable component.

12. The system of claim 9, wherein forming the span query comprises forming a sequence of event query, forming the sequence of events query comprising:

building one or more queries for individual log messages, each query including a temporal relation between the first event and the second event; and

merging the one or more queries for individual log messages as the span query over multiple log messages.

13. The system of claim 12, wherein performing the span query comprises performing the sequence of events query, performing the sequence of events query comprising:

performing the one or more queries for individual log messages; and

determining a time span between results of the one or more queries for individual log messages; and

verifying that the log messages occur within the determined time span.

14. The system of claim 12, wherein performing the sequence of events query comprises:

performing a single query which includes a time span as a constraint.

15. The system of claim 9, wherein:

forming the span query comprises forming the multiple restriction query, forming

the multiple restriction query comprising;

identifying an intermediate component from the input search query;

forming a query for the intermediate component;

identifying one or more keywords using results from the query for the

intermediate component; and

forming query for a final component using the identified one or more keywords; and

performing the span comprises;

performing the query for the final component; and

merging results from the query for the intermediate component and

results from performing the query for the final component.

16. A non-transitory computer-readable medium having instructions stored thereon, which, when executed by a processor, causes the processor to perform operations comprising:

creating an index of terms in log messages for retrieving one or more events in response to an input search query, the log messages comprising one or more stored events, the input search query comprising a constant component;

parsing the input search query, including identifying the constant component from the input search query;

based on results obtained from parsing the input search query, forming a span query for associated events, the span query including a first constraint for a first event, a second constraint for a second event, and a relation between the first event and second event, the span query being selected from a group of query types consisting of a sequence of events query, a multiple restriction query, and a causation query; and

running the input search query, including performing the span query on the index to determine the first event and the second event, the second event being associated with the first event according to the relation, wherein performing the span query comprises;

performing a constant query based on the constant components of the input search query to identify one or more constant events;

retrieving events preceding the one or more constant events;

building a merged event intersection lattice for one or more merged events and a constant event intersection lattice for the identified one or more constant events, each lattice including a set of event intersections between two or more sets of events;

performing a set subtraction to determine one or more differences between the merged event intersection lattice and the constant event intersection lattice; and

outputting the one or more differences as answers to the input search query.

17. The non-transitory computer-readable medium of claim 16, the operations further comprising:

grouping the determined the first event and second event by attributes.

18. The non-transitory computer-readable medium of claim 16, wherein the span query includes multiple query types and at least one query type includes at least one intermediate query.

19. A system comprising:

means for creating an index of terms in log messages for retrieving one or more events in response to an input search query, the log messages comprising one or more stored events, the input search query comprising a constant component;

means for parsing the input search query, including means for identifying the constant component from the input search query;

means for forming, based on results obtained from parsing the input search query, a span query for associated events, the span query including a first constraint for a first event, a second constraint for a second event, and a relation between the first event and second event the span query being selected from a group of query types consisting of a sequence of events query, a multiple restriction query, and a causation query; and

means for running the input search query, including means for performing the span query on the index to determine the first event and the second event, the second event being associated with the first event according to the relation, wherein performing the span query comprises;

performing a constant query based on the constant components of the input search query to identify one or more constant events;

retrieving events preceding the one or more constant events;

building a merged event intersection lattice for one or more merged events and a constant event intersection lattice for the identified one or more constant events, each lattice including a set of event intersections between two or more sets of events;

performing a set subtraction to determine one or more differences between the merged event intersection lattice and the constant event intersection lattice; and

outputting the one or more differences as answers to the input search query.

20. The system of claim 19, wherein the span query includes multiple query types and at least one query type includes at least one intermediate query.

21. The system of claim 19, wherein the input search query comprises a variable component.