Systems and methods for efficient data ingestion and query processing

• US 9,442,967 B2
• Filed: 07/25/2013
• Issued: 09/13/2016
• Est. Priority Date: 07/25/2013
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Barykin, Oleksandr, Metzler, Josh
• Primary Examiner(s): Kerzhner, Aleksandr
• Assistant Examiner(s): Cheung, Eddy
• Application Number:
  US13/951,431
• Publication Number:
  US 20150032725A1
• Time in Patent Office: 1,146 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

A query may be provided to aggregators at hierarchical levels in an in-memory data storage module. The query may be provided to leaf nodes of the in-memory data storage module. The leaf nodes may execute the query, returning results of the query to the aggregators. One or more aggregations may be performed based on the results. In an embodiment, log entries associated with a logged event may be serialized and divided into distributed chunks for storage in the leaf nodes. A leaf node, from the leaf nodes, having storage capacity for a distributed chunk may be identified. The distributed chunk may be stored in the leaf node.

Claims

1. A system comprising:

at least one processor; and

a memory storing instructions configured to instruct the at least one processor to perform;

serializing log entries associated with at least one logged event;

dividing the serialized log entries into one or more distributed chunks for storage in one or more leaf nodes of an in-memory data storage module, wherein storage of at least one of the distributed chunks is striped across at least two randomly selected leaf nodes, and wherein a corresponding space limit of each of the one or more leaf nodes is adjusted based at least in part on a type of data being stored at the leaf node;

providing a query to aggregators at hierarchical levels in the in-memory data storage module, wherein the aggregators are configured to pre-aggregate at least some data stored in the one or more leaf nodes of the in-memory data storage module in anticipation of the query;

providing the query to leaf nodes of the in-memory data storage module;

executing the query on the leaf nodes;

returning results of the query to the aggregators;

performing one or more aggregations on the results of the query; and

updating a query cache that corresponds to the query to include data describing the results.

2. The system of claim 1, wherein the aggregators comprise one or more of a root data aggregator, an intermediate data aggregator, or a leaf data aggregator.

3. The system of claim 1, wherein the providing the query to leaf nodes comprises identifying a plurality of leaf data aggregators to provide the query to the plurality of leaf nodes.

4. The system of claim 1, wherein the instructions are configured to instruct the at least one processor to perform receiving the query using a web application programming interface (API) or a structured query language (SQL) interface.

5. The system of claim 1, wherein the performing one or more aggregations comprises instructing at least one of the aggregators to perform leaf data aggregation.

6. The system of claim 1, wherein the performing one or more aggregations comprises instructing at least one of the aggregators to perform intermediate data aggregation.

7. The system of claim 1, wherein the performing one or more aggregations comprises instructing at least one of the aggregators to perform root data aggregation.

8. The system of claim 1, wherein the performing one or more aggregations comprises determining at least one of a count, a minimum value, a maximum value, a sum, an average, a percentile, or a histogram.

9. The system of claim 1, wherein the instructions are configured to instruct the at least one processor to perform validating the query.

10. The system of claim 9, wherein the validating the query comprises determining whether the query includes a request for a time range of data.

11. The system of claim 9, wherein the validating the query comprises determining whether the query correctly calls an aggregation function.

12. The system of claim 9, wherein the validating the query comprises determining whether semantic parameters of the query are valid.

13. The system of claim 1, wherein the leaf nodes are configured to expire data based on an age criterion or a space criterion.

14. The system of claim 1, wherein the instructions are configured to instruct the at least one processor to perform:

randomly selecting a first leaf node and a second leaf node from the leaf nodes;

determining the first leaf node has greater storage capacity than the second leaf node; and

selecting the first leaf node for storage of the distributed chunk.

15. The system of claim 1, wherein the logged event comprises one or more of a performance event on a computing system, user interaction with the computing system, or a behavioral event on the computing system.

16. The system of claim 1, wherein the system is incorporated into a social networking system.

17. A computer implemented method comprising:

serializing log entries associated with at least one logged event;

dividing the serialized log entries into one or more distributed chunks for storage in one or more leaf nodes of an in-memory data storage module, wherein storage of at least one of the distributed chunks is striped across at least two randomly selected leaf nodes, and wherein a corresponding space limit of each of the one or more leaf nodes is adjusted based at least in part on a type of data being stored at the leaf node;

providing, by a computer system, a query to aggregators at hierarchical levels in the in-memory data storage module, wherein the aggregators are configured to pre-aggregate at least some data stored in the one or more leaf nodes of the in-memory data storage module in anticipation of the query;

providing, by the computer system, the query to leaf nodes of the in-memory data storage module;

executing, by the computer system, the query on the leaf nodes;

returning, by the computer system, results of the query to the aggregators;

performing, by the computer system, one or more aggregations on the results of the query; and

updating a query cache that corresponds to the query to include data describing the results.

18. A non-transitory computer storage medium storing computer-executable instructions that, when executed, cause a computer system to perform a computer-implemented method comprising:

serializing log entries associated with at least one logged event;

dividing the serialized log entries into one or more distributed chunks for storage in one or more leaf nodes of an in-memory data storage module, wherein storage of at least one of the distributed chunks is striped across at least two randomly selected leaf nodes, and wherein a corresponding space limit of each of the one or more leaf nodes is adjusted based at least in part on a type of data being stored at the leaf node;

providing a query to aggregators at hierarchical levels in the in-memory data storage module, wherein the aggregators are configured to pre-aggregate at least some data stored in the one or more leaf nodes of the in-memory data storage module in anticipation of the query;

providing the query to leaf nodes of the in-memory data storage module;

executing the query on the leaf nodes;

returning results of the query to the aggregators;

performing one or more aggregations on the results of the query and

updating a query cache that corresponds to the query to include data describing the results.