CONSISTENCY SENSITIVE STREAMING OPERATORS

• US 20090125635A1
• Filed: 11/08/2007
• Published: 05/14/2009
• Est. Priority Date: 11/08/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ali, Mohamed, Barga, Roger S., Goldstein, Jonathan D., Hong, Mingsheng
• Granted Patent: US 8,315,990 B2
• Time in Patent Office: Days
• US Class Current: 709/231
• CPC Class Codes: G06F 11/0721 within a central processing unit [CPU]
• CPC Class Codes: G06F 11/0793 Remedial or corrective actions recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40

Abstract

A new approach for handling stream imperfections based on speculative execution involves the retraction of incorrect events facilitated using operators to remove speculatively produced incorrect output. Additionally, parameters are disclosed that define a spectrum of consistency levels. A first parameter, maximum blocking time, exposes a tradeoff between a degree of speculation and latency. A second parameter, the maximum time data is remembered before being purged from the system, exposes a tradeoff between state size and correctness. Varying these two parameters produces a spectrum of consistency levels (e.g., strong, middle, weak) which address the specific tradeoffs built into other systems. Retraction is accomplished using operators that include Select, AlterLifetime, Join, Sum, Align, and Finalize.

Claims

1. A computer-implemented system for stream processing, comprising:

a stream component for receiving an input stream that includes event imperfections based on speculative execution and for providing consistency in an output; and

a set of operators for providing multiple consistency levels via which consistency in the output is guaranteed.

2. The system of claim 1, wherein the set of operators includes an operator that passes inserts and retractions unchanged according to a Boolean function.

3. The system of claim 1, wherein the set of operators includes an operator that maps incoming events from one valid time domain to another valid time domain.

4. The system of claim 1, wherein the set of operators includes an operator that tests equality of table columns of multiple input streams.

5. The system of claim 1, wherein the set of operators includes an operator that checks for join candidates which have lifetimes that overlap a lifetime of an incoming event.

6. The system of claim 1, wherein the set of operators includes an operator that checks if an applied retraction causes a previously output lifetime to shorten.

7. The system of claim 1, wherein the set of operators includes an operator that ensures a full retraction in the input stream leads to a full retraction in the output.

8. The system of claim 1, wherein the output produced by the speculative execution of a streaming operator is non-blocking.

9. The system of claim 1, wherein the multiple consistency levels are characterized by a maximum blocking time and a data retention time using the set of operators.

10. The system of claim 1, wherein the consistency is varied on a per query basis via the operators.

11. The system of claim 1, wherein one or more of the set of operators are view update compliant.

12. The system of claim 1, wherein the set of operators includes an operator that receives an insert event, a retraction event, and a current time increment event.

13. A computer-implemented method of processing a stream of events, comprising:

receiving a stream of events that includes out-of-order events based on speculative execution;

executing a query against the stream of events;

processing the stream of events associated with the query based on multiple levels of consistency defined by a set of operators;

correcting the out-of-order events based on the set of operators; and

generating an output in which consistency is guaranteed based on the corrected out-of-order events.

14. The method of claim 13, further comprising correcting the out-of-order events based on an operator that passes an insert event and a retraction event unchanged subject to a function that considers event payload.

15. The method of claim 13, further comprising correcting the out-of-order events based on an operator the output of which describes changing state of a view which joins two input relations.

16. The method of claim 13, further comprising correcting the out-of-order events based on an operator that aggregates values of an attribute for all table rows for a snapshot of the stream of events.

17. The method of claim 13, further comprising correcting the out-of-order events based on an operator that reduces a query which crosses snapshot boundaries to a query that is view update compliant.

18. The method of claim 13, further comprising correcting the out-of-order events based on an operator that blocks the events of the stream of events and combines insets and retractions with other retractions.

19. The method of claim 13, further comprising correcting the out-of-order events based on an operator that ensures that output current time increment events are no earlier than an earliest correct time and that retractions in a retraction chain are issued in correct relative order.

20. A computer-implemented system, comprising:

computer-implemented means for receiving a stream of events that includes out-of-order events based on speculative execution;

computer-implemented means for executing a query against the stream of events;

computer-implemented means for processing the stream of events associated with the query based on multiple levels of consistency defined by a set of operators;

computer-implemented means for correcting the out-of-order events based on the set of operators; and

computer-implemented means for generating an output in which consistency is guaranteed based on the corrected out-of-order events.