Segment data visibility and management in a distributed database of time stamped records

• US 10,324,942 B2
• Filed: 07/28/2014
• Issued: 06/18/2019
• Est. Priority Date: 07/26/2013
• Status: Active Grant

• Current Assignee: Rill Data, Inc.
• Original Assignee: Snap, Inc.
• Inventors: Yang, Fangjin, Tschetter, Eric
• Primary Examiner(s): Burke, Jeff A
• Application Number:
  US14/444,888
• Publication Number:
  US 20150032775A1
• Time in Patent Office: 1,786 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2477 Temporal data queries

Abstract

A distributed database of time stamped records can be used to store time series data such as events occurring on the Internet. A distributed database of time stamped records can store segments of data that contain events for different time intervals. The volume of events occurring on the Internet introduces a “Big Data” variable that makes collections of data sets so large and complex they are difficult to manage. Disclosed are systems and methods to manage segments of a distributed database of time stamped records for optimal size (for storage and performance reasons etc.) and for proper visibility to data when different segments contain data for overlapping time periods.

Claims

1. A non-transitory computer readable medium comprising computer executable instructions stored thereon to cause one or more processors to perform data storage and retrieval operations from a computer memory configured according to a distributed database of time stamped records collected into data segments, each data segment including data from a data source collected over a time interval, each data segment associated to a creation time that the data segment was created, each data segment stored on one of a plurality of query nodes, the operations comprising:

building a timeline data structure for the data source and for a timeline view interval, the building of the timeline data structure comprising;

identifying, data segments that include data from the data source that was collected over a time interval included in the timeline view interval;

identifying, among the identified data segments, overlapping data segments that include overlapping portions of data collected over an overlapping time interval;

selecting the overlapping portion that is included in the overlapping segment having the most recent creation time; and

building the timeline data structure with the selected overlapping portion and with portions of the identified data segments that do not overlap with any portion of any other of the identified data segments.

2. The non-transitory computer readable medium of claim 1, wherein the operations further include:

receiving a query request at a broker node from a query client;

identifying, using the timeline data structure, data segments that include a most recent set of available data applicable to the query request;

retrieving the identified data segments;

generating a query response by consolidating the most recent set of available data included in the retrieved data segments; and

returning a query response to the query client.

3. The non-transitory computer readable medium of claim 1, wherein each query node is either a historical node or a real-time node.

4. The non-transitory computer readable medium of claim 2, wherein retrieving the identified data segments further comprises checking a cache for the identified data segments.

5. The non-transitory computer readable medium of claim 4, wherein the query request is not sent to query nodes for segments located in the cache.

6. The non-transitory computer readable medium of claim 4, wherein the cache is local to the broker node.

7. The non-transitory computer readable medium of claim 2, wherein the query client comprises a graphical user interface on a client computer.

8. The non-transitory computer readable medium of claim 2, wherein the query client comprises a computer process executing on a computer different from the broker node.

9. A non-transitory computer readable medium comprising computer executable instructions stored thereon to cause one or more processing units to perform data storage and retrieval operations from a computer memory configured according to a distributed database of time stamped records collected into data segments, the operations comprising:

determining, from among the data segments, a plurality of merger segments to merge into a single merged segment based on at least one of a size of each of the merger segments, a size of a resulting merged segment, and machine resources providing infrastructure to the distributed database of time stamped records, each merger segment comprising segment data in the form of at least one of a dimension and a metric;

determining at least one overlapping dimension included in every one of the plurality of merger segments to merge;

combining merger segment data for each of the at least one overlapping dimension;

determining at least one non-overlapping dimension that is not included in at least one of the plurality of merger segments to merge; and

assigning a null value for each non-overlapping dimension.

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

define a merged time interval spanning from an earliest start time of the plurality of merger segments to a latest finish time of the plurality of merger segments.

11. The non-transitory computer readable medium of claim 9, wherein each created segment has a unique version associated to a creation time that the data segment was created.

12. A method for storing and retrieving data from a computer memory, comprising:

configuring said computer memory according to a distributed database of time stamped records collected into data segments;

determining, from among the data segments, a plurality of merger segments to merge into a single merged segment based on at least one of a size of each of the merger segments, a size of a resulting merged segment, and machine resources providing infrastructure to the distributed database of time stamped records, wherein each merger segment comprises segment data in the form of at least one of a dimension and a metric;

determining at least one overlapping dimension included in every one of the plurality of merger segments to merge;

combining merger segment data for each of the at least one overlapping dimension;

determining at least one non-overlapping dimension that is not included in at least one of the plurality of merger segments to merge;

assigning a null value for each non-overlapping dimension

associating the merged segment with a time stamp corresponding to a time that the plurality of merger segments was merged into the single merged segment.

13. The method of claim 12, further comprising:

determining at least one overlapping metric included in every one of the plurality of merger segments to merge;

combining merger segment data for each of the at least one overlapping metric;

determining at least one non-overlapping metric that is not included in at least one of the plurality of merger segments to merge; and

assigning a null value for each non-overlapping metric.

14. The method of claim 12, further comprising:

define a merged time interval spanning from an earliest start time of the plurality of merger segments to a latest finish time of the plurality of merger segments.

15. The method of claim 12, wherein each created segment has a unique version associated to a creation time that the data segment was created.