Consistency sensitive streaming operators

• US 8,315,990 B2
• Filed: 11/08/2007
• Issued: 11/20/2012
• Est. Priority Date: 11/08/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Barga, Roger S, Ali, Mohamed, Hong, Mingsheng, Goldstein, Jonathan D
• Primary Examiner(s): Badawi, Sherief
• Application Number:
  US11/937,118
• Publication Number:
  US 20090125635A1
• Time in Patent Office: 1,839 Days
• Field of Search: 707/699, 707/690, 707/765, 707/691, 707/756, 709/232, 370/380, 712/239, 712/240
• US Class Current: 707/690
• 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, wherein the speculative execution comprises refraction of incorrect events by using a set of operators for removing speculatively produced incorrect output, the output produced by the speculative execution of a streaming operator is non-blocking;

the set of operators for providing multiple consistency levels by varying blocking time and data retention time in memory, wherein blocking time exposes a tradeoff between a degree of speculation and latency and data retention time in memory exposes a tradeoff between state size and correctness, via which consistency in the output is guaranteed, and the consistency is varied on a per query basis via the set of operators; and

a microprocessor that executes computer-executable instructions associated with at least one of the stream component or the set of operators.

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 multiple consistency levels are characterized by a maximum blocking time and a maximum data retention time using the set of operators.

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

10. 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.

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

receiving a stream of events that includes out-of-order events based on speculative execution that comprises retraction of incorrect events by using a set of operators for removing speculatively produced incorrect output, the output produced by the speculative execution of a streaming operator is non-blocking;

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 the set of operators;

varying the consistency on a per query basis using the set of operators, the consistency varied by acts that include;

selecting a level of consistency by varying a blocking time that exposes a tradeoff between a degree of speculation and latency;

selecting a level of consistency by varying a data retention time in memory that exposes a tradeoff between state size and correctness;

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

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

utilizing a microprocessor that executes instructions stored in memory to perform at least one of the acts of receiving, executing, processing, varying, selecting, correcting, or generating.

12. The method of claim 11, 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.

13. The method of claim 11, 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.

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

15. The method of claim 11, 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.

16. The method of claim 11, 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.

17. The method of claim 11, 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.

18. A computer-implemented system, comprising:

at least one computer including a microprocessor that executes computer-executable instructions, configured to;

receive a stream of events that includes out-of-order events based on speculative execution that comprises retraction of incorrect events by using a set of operators for removing speculatively produced incorrect output, the output produced by the speculative execution of a streaming operator is non-blocking;

execute a query against the stream of events;

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

vary the consistency on a per query basis using the set of operators;

select a level of consistency by varying blocking time that exposes a tradeoff between a degree of speculation and latency;

select a level of consistency by varying data retention time in memory that exposes a tradeoff between state size and correctness;

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

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