IMPLEMENTATION OF STREAM ALGEBRA OVER CLASS INSTANCES

• US 20100131543A1
• Filed: 01/26/2010
• Published: 05/27/2010
• Est. Priority Date: 07/18/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Goldstein, Jonathan, Barga, Roger Shane, Tarnavski, Tihomir T., Shen, Andy, Chkodrov, Gueorgui B., Ringseth, Paul F.
• Granted Patent: US 8,296,331 B2
• Time in Patent Office: Days
• US Class Current: 707/765
• 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 method for configuring an operator graph to process a high-volume continuous stream of events, said method comprising:

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

generating, by the subscriber machine, an abstract syntax tree corresponding to the object;

serializing, by the subscriber machine, the generated abstract syntax tree into a message; and

sending, by the subscriber machine, the message including a query representing the object to a destination machine, said destination machine being one of a plurality of destination machines, wherein the expression is configured to be compiled by the destination machine from the abstract syntax tree into executable code to be executed by the designation machine on events received from the event stream.

2. The method of claim 1, wherein the executable code is represented as an operator in an operator graph.

3. The method of claim 2 further comprising:

receiving, by the destination machine, the message including the query comprising query data and operator semantics, said query representing a request for data;

translating, by the destination machine, the received query into a plurality of stream algebra operators;

defining, by the destination machine, an execution plan representing a data flow implemented by the stream algebra operators;

receiving, by the destination machine, a first event from a high volume continuous data stream while maintaining minimal state information associated with the data;

assigning, by the destination machine, an expiration time to the received first event as a function of the query data;

receiving, by the destination machine, a plurality of second events from the data stream;

executing, by the destination machine, one or more of the stream algebra operators according to the defined execution plan and as a function of the operator semantics from the received query to find a match between the received first event and at least one of the received plurality of second events prior to expiration of the first event based on the assigned expiration time associated with the first event wherein second events matching unexpired first events are combined; and

executing, by the destination machine, combined events according to the execution plan.

4. The method of claim 3, further comprising assigning an expiration time to each of the received plurality of second events, wherein the assigned expiration time comprises infinity or zero.

5. The method of claim 3, wherein translating the query comprises compiling by the destination machine a description of the stream algebra operators into assembly code for efficient execution.

6. The method of claim 3, further comprising distributing by the subscriber machine one of the stream algebra operators to the destination machine by:

pausing execution of the stream algebra operator;

storing state information maintained by the stream algebra operator; and

sending the stream algebra operator and the stored state information to the destination machine.

7. The method of claim 6, wherein distributing one of the stream algebra operators to the destination machine comprises identifying the destination machine and the one of the stream algebra operators based on the execution plan;

pausing execution of the stream algebra operator;

storing state information maintained by the stream algebra operator; and

sending the stream algebra operator and the stored state information to the destination machine.

8. The method of claim 6, further comprising adjusting the expiration time assigned to the first event to minimize the quantity of state information maintained by the stream algebra operator.

9. The method of claim 8, further comprising assigning an expiration time to each of the received plurality of second events, wherein the assigned expiration time comprises infinity or zero.

10. The method of claim 3, further comprising maintaining a state of the first event only until the first event has expired based on the associated expiration time.

11. The method of claim 3, further comprising discarding the first event as a function of the assigned expiration time.

12. The method of claim 3, wherein receiving the first event comprises receiving a request for data, and wherein receiving the plurality of second events comprises receiving a plurality of responses.

13. A method of processing high-volume continuous streams of data comprising:

receiving, by a destination machine, a query from a subscriber machine, said query comprising query data and operator semantics, said query representing a request for data and further representing a function to be performed on events from an event stream;

translating, by the destination machine, the received query into a plurality of stream algebra operators;

defining, by the destination machine, an execution plan representing a data flow implemented by the stream algebra operators;

receiving, by the destination machine, a first event from a high volume continuous data stream while maintaining minimal state information associated with the data;

assigning, by the destination machine, an expiration time to the received first event as a function of the query data;

receiving, by the destination machine, a plurality of second events from the data stream;

executing, by the destination machine, one or more of the stream algebra operators according to the defined execution plan and as a function of the operator semantics from the received query to find a match between the received first event and at least one of the received plurality of second events prior to expiration of the first event based on the assigned expiration time associated with the first event wherein second events matching unexpired first events are combined; and

executing, by the destination machine, combined events according to the execution plan.

14. A system for processing high-volume continuous streams of data while maintaining minimal state information associated with the data, said system comprising:

a plurality of destination machines;

a subscriber machine having a subscriber processor 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 destination machines which compiles the expression from the abstract syntax tree into executable code, and wherein the executable code is executed by the one destination machine on events received from the event stream.

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

16. The system of claim 15, wherein the subscriber machine identifies the one of the plurality of destination machines to host said one of the plurality of stream algebra operators.

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

18. The system of claim 15, 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.

19. The system of claim 15, 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.

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