SYSTEMS AND METHODS FOR EFFICIENT DATA INGESTION AND QUERY PROCESSING

• US 20150032725A1
• Filed: 07/25/2013
• Published: 01/29/2015
• 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
• Granted Patent: US 9,442,967 B2
• Time in Patent Office: Days
• US Class Current: 707/722
• 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;

providing a query to aggregators at hierarchical levels in an in-memory data storage module;

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; and

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

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:

serializing log entries associated with a logged event; and

dividing the serialized log entries into distributed chunks for storage in the leaf nodes of the in-memory data storage module.

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

identifying a leaf node, from the leaf nodes, having storage capacity for a distributed chunk;

storing the distributed chunk in the leaf node.

16. The system of claim 14, 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.

17. The system of claim 14, 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.

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

19. A computer implemented method comprising:

providing, by a computer system, a query to aggregators at hierarchical levels in an in-memory data storage module;

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; and

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

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

providing a query to aggregators at hierarchical levels in an in-memory data storage module;

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; and

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