Consistency sensitive streaming operators
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
18 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15, 16, 17)
-
-
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.
-
Specification