Implementation of stream algebra over class instances

• US 7,676,461 B2
• Filed: 07/18/2007
• Issued: 03/09/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, Chkodrov, Gueorgui B., Ringseth, Paul F., Barga, Roger Shane, Tarnavski, Tihomir T., Shen, Andy
• Primary Examiner(s): Le; Debbie M
• Application Number:
  US11/779,574
• Publication Number:
  US 20090024622A1
• Time in Patent Office: 965 Days
• Field of Search: 707 2- 6
• US Class Current: 1/1
• 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 of processing high-volume continuous streams of data, said method comprising:

receiving a query comprising query data and operator semantics, said query representing a request for data;

translating the received query into a plurality of stream algebra operators;

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

receiving a first event from a high-volume continuous data stream while maintaining minimal state information associated with the data;

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

receiving a plurality of second events from the data stream;

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

if one of the second events does not match the first event, then continuing to wait until another second event is received; and

if one of the second events matches the first event, then combining the first and second events to produce a third event; and

executing the third event according to the execution plan.

2. The method of claim 1, wherein translating the query comprises compiling a description of the stream algebra operators into assembly code for efficient execution.

3. The method of claim 1, further comprising distributing one of the stream algebra operators to a destination computing device 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 computing device.

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

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

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

9. The method of claim 1, 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.

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

receiving a query comprising query data and operator semantics, said query representing a request for data;

translating the received query into a plurality of stream algebra operators;

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

receiving a first event from a data stream;

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

receiving a plurality of second events from the data stream;

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

producing, as a function of said executing, a third event to be executed according to the execution plan;

identifying the destination computing device 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 computing device.

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

receiving a query comprising query data and operator semantics, said query representing a request for data;

translating the received query into a plurality of stream algebra operators;

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

receiving a first event from a data stream;

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

receiving a plurality of second events from the data stream;

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

producing, as a function of said executing, a third event to be executed according to the execution plan; and

adjusting the expiration time assigned to the first event to minimize the quantity of state information maintained by the stream algebra operator.

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

a processor configured to execute computer-executable instructions for;

receiving a query comprising query data and operator semantics, said query representing a request for data; and

translating the received query into a plurality of stream algebra operators;

a memory area for storing the plurality of stream algebra operators for building a distributed stream processing operator graph, each of said stream algebra operators being adapted to perform one or more functions on data events from an event stream; and

said processor configured to execute computer-executable instructions for building a distributed operator graph using the stream algebra operators stored in the memory area by;

defining an object to include an expression, said expression representing the one or more functions to be performed on the data events from the event stream;

serializing the defined object including the expression into a message corresponding to one of the plurality of stream algebra operators stored in the memory area;

identifying one of a plurality of destination computing devices to host said one of the plurality of stream algebra operators;

transmitting the message to the identified destination computing device to build the distributed operator graph, wherein the destination computing device compiles the expression from the message into executable code representing said one of the plurality of stream algebra operators implementing a portion of the operator graph, wherein the executable code operates on the data events received from the event stream to produce aggregated events;

receiving the aggregated events from the destination computing device; and

processing the aggregated events in accordance with another portion of the operator graph implemented by the processor.

11. The system of claim 10, wherein the data events comprise one or more of the following:

a class instance, a C# event, and a message.

12. The system of claim 10, wherein the memory area further stores an alterlifetime operator for adjusting a timestamp associated with a data event received from the event stream.

13. The system of claim 10, further comprising one or more of the following:

means for building the distributed operator graph, means for generating the expression, and means for identifying the one of the plurality of destination computing devices to host said one of the plurality of stream algebra operators.

14. The system of claim 10, wherein the processor is configured to execute computer-executable instructions for identifying the one of the plurality of destination computing devices as a function of a placement algorithm.

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

16. The system of claim 10, wherein receiving the aggregated events from the destination computing device comprises receiving locally aggregated events from each of a plurality of destination computing devices, and wherein the processor is further configured to execute computer-executable instructions for globally aggregating the received locally aggregated event in accordance with the operator graph implemented by the processor.