PARALLEL DATA STREAM PROCESSING SYSTEM

• US 20110213802A1
• Filed: 02/24/2011
• Published: 09/01/2011
• Est. Priority Date: 02/26/2010
• Status: Active Grant

• Current Assignee: eBay Inc.
• Original Assignee: eBay Inc.
• Inventors: Singh, Gyanit, Chiu, Chi-Hsien, Sundaresan, Neelakantan
• Granted Patent: US 9,805,101 B2
• Time in Patent Office: Days
• US Class Current: 707/774
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases

Abstract

A method and a system process a stream of data in parallel across a plurality of nodes. The log processing system has a log module, a query language module, and a query processing module. The log module receives and organizes the stream of data into a sequential and nested data structure. The query language operator module defines operators that operate on the sequential and nested data structure. The query processing module processes in parallel across a plurality of nodes a query based on an operator on the stream of data.

Claims

1. A log processing system, comprising:

a processor-implemented log module configured to receive and organize a stream of data into a sequential and nested data structure;

a processor-implemented query language operator module configured to define operators that operate on the sequential and nested data structure; and

a processor-implemented query processing module configured to process in parallel across a plurality of nodes a query based on an operator on the stream of data.

2. The system of claim 1 wherein the nested data structure comprises an atom, a tuple, a map, and a bag, wherein the atom includes a single value, wherein the tuple includes a sequence of atoms, wherein the map includes a collection of key and value pairs, wherein the bag includes a collection of tuples.

3. The system of claim 2 wherein the sequential data structure comprises an ordered plurality of tuples.

4. The system of claim 2 wherein the stream of data comprises user activity logs, the user activity logs comprising a plurality of sessions, each session comprising a plurality of activities ordered by time, each session represented as an ordered bag identified by a session identifier.

5. The system of claim 1 wherein the operators comprise at least one of an input operator, an output operator, a relational operator, and a stream operator,

wherein the input operator is configured to load session logs corresponding to a date range,

wherein the output operator is configured to save session logs in a storage device,

wherein the relational operator is configured to operate on the sequential and nested data structure based on relation conditions, the relational operator comprising a filter operator, a project operator, a group operator, a join operator, an order operator, a split operator, and a union operator,

wherein the stream operator is configured to operate on the sequential and nested data structure to generate streams that match a pattern, the stream operator comprising a start operator, a stop operator, and a pattern operator.

6. The system of claim 1 wherein the processor-implemented query processing module comprises a parallel implementation module configured to split a collection of tuples from the stream of data into a plurality of substream of data without splitting the individual tuples, the plurality of substreams processed in parallel across the plurality of nodes.

7. The system of claim 6 wherein a substream of data comprises a nestled tuple, wherein the stream of data is grouped into subsequences, wherein the parallel implementation module is configured to perform a sequence operation on the subsequences in parallel without splitting the subsequences.

8. A computer-implemented method, comprising:

receiving a stream of data;

organizing the stream of data in a sequential and nested data structure;

defining operators to operate on the sequential and nested data structure; and

processing in parallel across a plurality of nodes a query based on an operator on the stream of data.

9. The computer-implemented method of claim 8 wherein the nested data structure comprises an atom, a tuple, a map, and a bag, wherein the atom includes a single value, wherein the tuple includes a sequence of atoms, wherein the map includes a collection of key and value pairs, wherein the bag includes a collection of tuples.

10. The computer-implemented method of claim 9 wherein the sequential data structure comprises an ordered plurality of tuples.

11. The computer-implemented method of claim 9 wherein the stream of data comprises user activity logs, the user activity logs comprising a plurality of sessions, each session comprising a plurality of activities ordered by time, each session represented as an ordered bag identified by a session identifier.

12. The computer-implemented method of claim 8 wherein the operators comprise at least one of an input operator, an output operator, a relational operator, and a stream operator,

wherein the input operator is configured to load session logs corresponding to a date range,

wherein the output operator is configured to save session logs in a storage device,

wherein the relational operator is configured to operate on the sequential and nested data structure based on relation conditions, the relational operator comprising a filter operator, a project operator, a group operator, a join operator, an order operator, a split operator, and a union operator,

wherein the stream operator is configured to operate on the sequential and nested data structure to generate streams that match a pattern, the stream operator comprising a start operator, a stop operator, and a pattern operator.

13. The computer-implemented method of claim 8 wherein processing further comprises splitting a collection of tuples from the stream of data into a plurality of substream of data without splitting the individual tuples, the plurality of substreams processed in parallel across the plurality of nodes.

14. The computer-implemented method of claim 13 wherein a substream of data comprises a nestled tuple, wherein the stream of data is grouped into subsequences, wherein the parallel implementation module is configured to perform a sequence operation on the subsequences in parallel without splitting the subsequences.

15. A non-transitory computer-readable storage medium storing a set of instructions that, when executed by a processor, cause the processor to perform operations, comprising:

receiving a stream of data;

organizing the stream of data in a sequential and nested data structure;

defining operators to operate on the sequential and nested data structures; and

processing in parallel across a plurality of nodes a query based on an operator on the stream of data.

16. The non-transitory computer-readable storage medium of claim 15 wherein the nested data structure comprises an atom, a tuple, a map, and a bag, wherein the atom includes a single value, wherein the tuple includes a sequence of atoms, wherein the map includes a collection of key and value pairs, wherein the bag includes a collection of tuples.

17. The non-transitory computer-readable storage medium of claim 16 wherein the sequential data structure comprises an ordered plurality of tuples.

18. The computer-implemented method of claim 16 wherein the stream of data comprises user activity logs, the user activity logs comprising a plurality of sessions, each session comprising a plurality of activities ordered by time, each session represented as an ordered bag identified by a session identifier.

19. The computer-implemented method of claim 15 wherein the operators comprise at least one of an input operator, an output operator, a relational operator, and a stream operator,

wherein the input operator is configured to load session logs corresponding to a date range,

wherein the output operator is configured to save session logs in a storage device,

wherein the relational operator is configured to operate on the sequential and nested data structure based on relation conditions, the relational operator comprising a filter operator, a project operator, a group operator, a join operator, an order operator, a split operator, and a union operator,

wherein the stream operator is configured to operate on the sequential and nested data structure to generate streams that match a pattern, the stream operator comprising a start operator, a stop operator, and a pattern operator.

20. The computer-implemented method of claim 15 wherein processing further comprises splitting a collection of tuples from the stream of data into a plurality of substream of data without splitting the individual tuples, the plurality of substreams processed in parallel across the plurality of nodes.

21. The computer-implemented method of claim 20 wherein a substream of data comprises a nestled tuple, wherein the stream of data is grouped into subsequences, wherein the parallel implementation module is configured to perform a sequence operation on the subsequences in parallel without splitting the subsequences.