Implementation of stream algebra over class instances

• US 8,775,482 B2
• Filed: 09/13/2012
• Issued: 07/08/2014
• Est. Priority Date: 07/18/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chkodrov, Gueorgui B., Ringseth, Paul F., Tarnavski, Tihomir T., Shen, Andy, Barga, Roger Shane, Goldstein, Jonathan
• Primary Examiner(s): LE, DEBBIE M
• Application Number:
  US13/614,184
• Publication Number:
  US 20130014094A1
• Time in Patent Office: 663 Days
• Field of Search: 707/797, 707/798, 707/803, 707/809
• US Class Current: 707/803
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

Creating and executing a distributed stream processing operator graph based on a query. The operator graph includes movable stream algebra operators for processing events received from high volume data streams. The operators are partially compiled and distributed to computing devices for completion of the compilation and subsequent execution. During execution, the operators maintain minimal state information associated with received events via an expiration time assigned to each of the event instances. Additional events are generated and aggregated by the operators for communication to a service responsible for the query.

Claims

1. A machine for use with a plurality of destination machines for processing high-volume continuous streams of data while maintaining minimal state information associated with the data, said machine comprising:

a subscriber processor linked to the destination machines and configured to execute computer executable instructions for;

defining an object to include an expression, said expression representing a function to be performed on events from an event stream;

generating an abstract syntax tree corresponding to the object;

serializing the generated abstract syntax tree into a message; and

sending the message representing the object to one of the plurality of destination machines, said sent message configured for use by the one destination machine for compiling the expression from the abstract syntax tree into executable code which is executable by the one destination machine on events received from the event stream.

2. The machine of claim 1 wherein each destination machine has a destination processor configured to execute computer executable instructions for receiving the message including a query, said query comprising query data and operator semantics and representing a request for data, and translating the received query into a plurality of stream algebra operators;

wherein each destination machine has a memory area for storing the plurality of stream algebra operators for building an execution plan, each of said stream algebra operators being adapted to perform one or more functions on data events from an event stream;

wherein said destination processor is configured to execute computer-executable instructions for building the execution plan using the stream algebra operators stored in the memory area; and

wherein the subscriber processor identifies the one of the plurality of destination machines to host said one of the plurality of stream algebra operators.

3. The machine of claim 2, wherein the subscriber processor is configured to execute computer-executable instructions for identifying the one of the plurality of destination machines as a function of a placement algorithm.

4. The machine of claim 3, wherein the executable code operates on the data events received from the event stream to produce locally aggregated events from each of a plurality of destination machines, and wherein the destination processor is further configured to execute computer-executable instructions for globally aggregating the received locally aggregated event in accordance with the execution plan built by the destination processor.

5. The machine of claim 4, wherein the data events comprise one or more of the following:

a class instance, a C# event, and a message, and wherein the memory area further stores an alterlifetime operator for adjusting a timestamp associated with a data event received from the event stream.

6. The machine of claim 5, wherein the data events comprise an insert event, and wherein the insert event adds information associated with the insert event to a computation state associated with one of the stream algebra operators.

7. The machine of claim 2, wherein the data events comprise one or more of the following:

a class instance, a C# event, and a message, and wherein the memory area further stores an alterlifetime operator for adjusting a timestamp associated with a data event received from the event stream.

8. The machine of claim 2, wherein the data events comprise an insert event, and wherein the insert event adds information associated with the insert event to a computation state associated with one of the stream algebra operators.

9. The machine of claim 1, wherein the subscriber processor is configured to execute computer-executable instructions for identifying the one of the plurality of destination machines as a function of a placement algorithm.

10. The machine of claim 1, wherein the executable code operates on the data events received from the event stream to produce locally aggregated events from each of a plurality of destination machines, and wherein the destination processor is further configured to execute computer-executable instructions for globally aggregating the received locally aggregated event in accordance with the execution plan built by the destination processor.

11. A computer executable method for use with a plurality of destination machines for processing high-volume continuous streams of data while maintaining minimal state information associated with the data, said computer executable method for use with a subscriber processor linked to the destination machines and configured to execute computer executable instructions, said computer executable method comprising:

defining by the subscriber processor an object to include an expression, said expression representing a function to be performed on events from an event stream;

generating an abstract syntax tree corresponding to the object;

serializing the generated abstract syntax tree into a message; and

sending by the subscriber processor the message representing the object to one of the plurality of destination machines, said sent message configured for use by the one destination machine for compiling the expression from the abstract syntax tree into executable code which is executable by the one destination machine on events received from the event stream.

12. The method of claim 11 wherein each destination machine has a destination processor configured to execute computer executable instructions for receiving the message including a query, said query comprising query data and operator semantics and representing a request for data, and translating the received query into a plurality of stream algebra operators;

wherein each destination machine has a memory area for storing the plurality of stream algebra operators for building an execution plan, each of said stream algebra operators being adapted to perform one or more functions on data events from an event stream; and

wherein said destination processor is configured to execute computer-executable instructions for building the execution plan using the stream algebra operators stored in the memory area;

said method further comprising;

identifying by the subscriber processor the one of the plurality of destination machines to host said one of the plurality of stream algebra operators.

13. The method of claim 12 further comprising identifying by the subscriber processor the one of the plurality of destination machines as a function of a placement algorithm.

14. The method of claim 13, wherein the executable code operates on the data events received from the event stream to produce locally aggregated events from each of a plurality of destination machines, and wherein the destination processor is further configured to execute computer-executable instructions for globally aggregating the received locally aggregated event in accordance with the execution plan built by the destination processor.

15. The method of claim 14, wherein the data events comprise one or more of the following:

a class instance, a C# event, and a message, and wherein the memory area further stores an alterlifetime operator for adjusting a timestamp associated with a data event received from the event stream.

16. The method of claim 15, wherein the data events comprise an insert event, and wherein the insert event adds information associated with the insert event to a computation state associated with one of the stream algebra operators.

17. The method of claim 12, wherein the data events comprise one or more of the following:

a class instance, a C# event, and a message, and wherein the memory area further stores an alterlifetime operator for adjusting a timestamp associated with a data event received from the event stream.

18. The method of claim 12, wherein the data events comprise an insert event, and wherein the insert event adds information associated with the insert event to a computation state associated with one of the stream algebra operators.

19. The method of claim 11 further comprising identifying by the subscriber processor the one of the plurality of destination machines as a function of a placement algorithm.

20. The method of claim 11, wherein the executable code operates on the data events received from the event stream to produce locally aggregated events from each of a plurality of destination machines, and wherein the destination processor is further configured to execute computer-executable instructions for globally aggregating the received locally aggregated event in accordance with the execution plan built by the destination processor.