Expiration of persistent data structures that satisfy search queries

• US 10,216,779 B2
• Filed: 01/27/2016
• Issued: 02/26/2019
• Est. Priority Date: 10/05/2006
• Status: Active Grant

• Current Assignee: Splunk Inc.
• Original Assignee: Splunk Inc.
• Inventors: Swan, Erik M., Carasso, R. David, Das, Robin Kumar, Greene, Rory, Hall, Bradley, Mealy, Nicholas Christian, Murphy, Brian Philip, Sorkin, Stephen Phillip, Stechert, Andre David, Baum, Michael Joseph
• Primary Examiner(s): Uddin, Mohammed R
• Application Number:
  US15/008,425
• Publication Number:
  US 20160154836A1
• Time in Patent Office: 1,126 Days
• Field of Search: 707770, 707722, 707737, 707741, 707752, 707753, 707746, 707999003
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2291 User-Defined Types; Storage management thereof
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Methods and apparatus consistent with the invention provide the ability to organize, index, search, and present time series data based on searches. Time series data are sequences of time stamped records occurring in one or more usually continuous streams, representing some type of activity. In one embodiment, time series data is organized into discrete events with normalized time stamps and the events are indexed by time and keyword. A search is received and relevant event information is retrieved based in whole or in part on the time indexing mechanism, keyword indexing mechanism, or statistical indices calculated at the time of the search.

Claims

1. A method, comprising:

receiving raw data from one or more sources in an information technology environment;

segmenting the raw data into a plurality of events by determining a beginning and an ending of each event in the plurality of events in the raw data, wherein each event in the plurality of events includes a portion of the raw data, wherein each event represents one or more lines of data among a plurality of lines of data in the raw data;

associating a time stamp with each event in the plurality of events;

indexing each time stamped event in the plurality of events;

creating a plurality of persistent data structures that are used to perform lookups in a search process, store the raw data of each event with its segmentation, and store metadata related to the indexed events;

wherein each persistent data structure in the plurality of persistent data structures is immutable and corresponds to a specific time interval, wherein events stored in a particular persistent data structure have associated time stamps that fall within a particular time interval corresponding to the particular persistent data structure;

wherein a process periodically wakes up and tests the plurality of persistent data structures to determine whether information associated with a persistent data structure meets expiration criteria, wherein the persistent data structure is tested upon reaching a user defined fill capacity and is not accepting further events;

in response to determining that information associated with the persistent data structure meets the expiration criteria, relocating the persistent data structure to offline storage and moving the persistent data structure out of active status.

2. The method of claim 1, wherein each event in the plurality of keyword-searchable events is created using feature extraction to detect the beginning and ending of events within the raw data.

3. The method of claim 1, wherein a beginning of each subsequent event in the raw data is detected to determine the boundaries between events in the raw data.

4. The method of claim 1, wherein the raw data is segmented into events by examining punctuation within the raw data.

5. The method of claim 1, wherein the received raw data includes machine data.

6. The method of claim 1, further comprising:

mapping events in the plurality of events to keywords in a keyword index.

7. An apparatus, comprising:

a raw data receiver, implemented at least partially in hardware, that receives raw data from one or more sources in an information technology environment;

an event creator, implemented at least partially in hardware, that data segments the raw data into a plurality of events by determining a beginning and an ending of each event in the plurality of events in the raw data, wherein each event in the plurality of events includes a portion of the raw data, wherein each event represents one or more lines of data among a plurality of lines of data in the raw data;

a time stamp processor, implemented at least partially in hardware, that associates a time stamp with each event in the plurality of events;

an event indexer, implemented at least partially in hardware, that indexes each time stamped event in the plurality of events;

a persistent data structure creation device, implemented at least partially in hardware, that creates a plurality of persistent data structures that are used to perform lookups in a search process, store the raw data of each event with its segmentation, and store metadata related to the indexed events;

wherein each persistent data structure in the plurality of persistent data structures is immutable and corresponds to a specific time interval, wherein events stored in a particular persistent data structure have associated time stamps that fail within a particular time interval corresponding to the particular persistent data structure;

a persistent data structure monitoring device, implemented at least partially in hardware, that periodically wakes up and tests the plurality of persistent data structures to determine whether information associated with a persistent data structure meets expiration criteria, wherein the persistent data structure is tested upon reaching a user defined fill capacity and is not accepting further events;

wherein the persistent data structure monitoring device determines that information associated with the persistent data structure meets the expiration criteria and relocates the persistent data structure to offline storage and moving the persistent data structure out of active status.

8. The apparatus of claim 7, wherein each event in the plurality of events is created using feature extraction to detect the beginning and ending of events within the raw data.

9. The apparatus of claim 7, wherein a beginning of each subsequent event in the raw data is detected to determine the boundaries between events in the raw data.

10. The apparatus of claim 7, wherein the raw data is segmented into events by examining punctuation within the raw data.

11. The apparatus of claim 7, wherein the received raw data includes machine data.

12. The apparatus of claim 7, further comprising:

a keyword mapper, implemented at least partially in hardware, that maps events in the plurality of events to keywords in a keyword index.

13. One or more non-transitory computer-readable storage media,

storing one or more sequences of instructions, which when executed by one or more

processors cause performance of:

receiving raw data from one or more sources in an information technology environment;

segmenting the raw data into a plurality of events by determining a beginning and an ending of each event in the plurality of events in the raw data, wherein each event in the plurality of events includes a portion of the raw data, wherein each event represents one or more lines of data among a plurality of lines of data in the raw data;

associating a time stamp with each event in the plurality of events;

indexing each time stamped event in the plurality of events;

creating a plurality of persistent data structures that are used to perform lookups in a search process, store the raw data of each event with its segmentation, and store metadata related to the indexed events;

wherein each persistent data structure in the plurality of persistent data structures is immutable and corresponds to a specific time interval, wherein events stored in a particular persistent data structure have associated time stamps that fall within a particular time interval corresponding to the particular persistent data structure;

wherein a process periodically wakes up and tests the plurality of persistent data structures to determine whether information associated with a persistent data structure meets expiration criteria, wherein the persistent data structure is tested upon reaching a user defined fill capacity and is not accepting further events;

in response to determining that information associated with the persistent data structure meets the expiration criteria, relocating the persistent data structure to offline storage and moving the persistent data structure out of active status.

14. The one or more non-transitory computer-readable storage media of claim 13, wherein each event in the plurality of events is created using feature extraction to detect the beginning and ending of events within the raw data.

15. The one or more non-transitory computer-readable storage media of claim 13, wherein a beginning of each subsequent event in the raw data is detected to determine the boundaries between events in the raw data.

16. The one or more non-transitory computer-readable storage media of claim 13, wherein the raw data is segmented into events by examining punctuation within the raw data.

17. The one or more non-transitory computer-readable storage media of claim 13, wherein the received raw data includes machine data.

18. The one or more non-transitory computer-readable storage media of claim 13, wherein the one or more sequences of instructions, which when executed by the one or more processors cause further performance of:

mapping events in the plurality of events to keywords in a keyword index.