Data flow windowing and triggering

• US 10,037,187 B2
• Filed: 11/03/2015
• Issued: 07/31/2018
• Est. Priority Date: 11/03/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Akidau, Tyler, Bradshaw, Robert, Chambers, Ben, Chambers, Craig, Lax, Reuven, Mills, Daniel, Perry, Frances
• Primary Examiner(s): Vostal, O. C.
• Application Number:
  US14/931,006
• Publication Number:
  US 20160285711A1
• Time in Patent Office: 1,001 Days
• Field of Search: 709224
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: H04L 47/00 Traffic control in data switching networks arrangements for detecting or preventing errors in the information received H04L1/00
• CPC Class Codes: H04L 47/28 in relation to timing considerations

Abstract

A method includes receiving data corresponding one of streaming data or batch data and a content of the received data for computation. The method also includes determining an event time of the data for slicing the data, determining a processing time to output results of the received data, and emitting at least a portion of the results of the received data based on the processing time and the event time.

Claims

1. A method comprising:

receiving, at data processing hardware, data corresponding to one of streaming data or batch data;

determining, using the data processing hardware, a content of the received data for computation;

determining, using the data processing hardware, an event time of the data for slicing the data;

determining a processing time to output results of the received data using the data processing hardware;

grouping, using the data processing hardware, a first subset of the received data into a first window, the first window defining a first sub-event time of the first data subset;

aggregating, using the data processing hardware, a first result of the first data subset for the first window; and

determining, by the data processing hardware, a first trigger time to;

emit the first aggregated result of the first data subset;

store a copy of the first aggregated result in a persistent state within memory hardware; and

refine a next aggregate result of a later subset with the first aggregated result,

wherein the first trigger time comprises at least one of;

when a watermark reaches an end of the first window;

every threshold number of seconds of a walltime;

after receiving a punctuation record that terminates the first window;

every threshold number of records;

after arbitrary user logic decides to trigger;

or

after an arbitrary combination of concrete triggers.

2. The method of claim 1, further comprising:

grouping, using the data processing hardware, later subsets of the received data into windows based on the event time, the windows comprising one of;

fixed windows defined by a static time period, each fixed window applied across all of the data within the associated time period;

sliding windows defined by a time period and a slide period, each sliding window applied across all of the data within the associated time period and associated with a start time separated from a start time of an immediately successive window by the slide period;

session windows defined by a timeout gap, each session window applied across a subset of the data occurring within a span of time less than the associated timeout gap;

or

user-defined windows defined by a pair of functions.

3. The method of claim 1, further comprising:

assigning, using the data processing hardware, a mergable window for each element of the received data, each element including an associated input timestamp and each session window extending a predefined range of time beyond the input timestamp for the associated window;

merging, using the data processing hardware, two or more of the mergable windows belonging to a same key that overlap into a single merged window; and

setting, using the data processing hardware, an associated output timestamp for each element to a value greater than or equal to an earliest time in the associated merged window or the associated mergeable window.

4. The method of claim 3, wherein the single merged window includes a range of time greater than the predefined range of time.

5. The method of claim 1, further comprising, when the received data corresponds to streaming data:

grouping, using the data processing hardware, the streaming data into windows;

setting, using the data processing hardware, an input timestamp on an element of the streaming data; and

when the input timestamp on the element occurs earlier than a watermark, determining, using the data processing hardware, the streaming data comprises late streaming data; and

one of;

dropping the late streaming data;

or

allowing the late streaming data by creating a duplicate window in an output for the late streaming data.

6. The method of claim 1, further comprising:

grouping, using the data processing hardware, a second subset of the received data into a second window, the second window defining a second sub-event time of the second data subset;

aggregating, using the data processing hardware, a second result of the second data subset for the second window; and

determining, using the data processing hardware, a second trigger time to emit the second aggregated result of the second data subset, the second trigger time comprising at least one of;

when a watermark reaches an end of the second window;

every threshold number of seconds of a walltime;

after receiving a punctuation record that terminates the second window;

every threshold number of records;

after arbitrary user logic decides to trigger;

or

after an arbitrary combination of concrete triggers.

7. The method of claim 1, further comprising, when determining the first trigger time to emit the first aggregated result of the first data subset, discarding, using the data processing hardware, the first aggregated result from use when aggregating results of later subsets of the received data.

8. The method of claim 1, further comprising:

when determining the first trigger time to emit the first aggregated result of the first data subset, storing the copy of the first aggregated result in the persistent state within the memory hardware; and

when the next aggregated result of the later subset associated with the same window emits;

emitting a retraction of the first aggregated result; and

emitting a combined session result for the first window.

9. The method of claim 1, further comprising:

receiving, at the data processing hardware, a late data point after grouping the data subset into the first window, the late data point related to the first window; and

discarding, using the data processing hardware, the late data point.

10. The method of claim 1, further comprising:

receiving, at the data processing hardware, a late data point after grouping the first data subset into the first window, the late data point related to the first window; and

accumulating, using the data processing hardware, the late data point into the first window to refine the first aggregated result with the late data point.

11. The method of claim 1, further comprising:

receiving, at the data processing hardware, a late data point after grouping the first data subset into the first window, the late data point related to the first window;

aggregating, using the data processing hardware, a combined result of the first data subset and the late data point; and

emitting the combined result.

12. A system comprising:

data processing hardware; and

memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing hardware cause the data processing hardware to perform operations comprising;

receiving data corresponding to one of streaming data or batch data;

determining a content of the received data for computation;

determining an event time of the data for slicing the data;

determining a processing time to output results of the received data;

grouping a first subset of the received data into a first window, the first window defining a first sub-event time of the first data subset;

aggregating a first result of the first data subset for the first window;

determining a first trigger time to;

emit the first aggregated result of the first data subset;

store a copy of the first aggregated result in a persistent state within the memory hardware; and

refine a next aggregate result of a later subset with the first aggregated result,

wherein the first trigger time comprises at least one of;

when a watermark reaches an end of the first window;

every threshold number of seconds of a walltime;

after receiving a punctuation record that terminates the first window;

every threshold number of records;

after arbitrary user logic decides to trigger;

or

after an arbitrary combination of concrete triggers.

13. The system of claim 12, wherein the operations further comprise grouping later subsets of the received data into windows based on the event time, the windows comprising one of:

fixed windows defined by a static time period, each fixed window applied across all of the data within the associated time period;

sliding windows defined by a time period and a slide period, each sliding window applied across all of the data within the associated time period and associated with a start time separated from a start time of an immediately successive window by the slide period;

session windows defined by a timeout gap, each session window applied across a subset of the data occurring within a span of time less than the associated timeout gap;

or

user-defined windows defined by a pair of functions.

14. The system of claim 12, wherein the operations further comprise:

assigning a mergeable window for each element of the received data, each element including an associated input timestamp and each mergeable window extending a predefined range of time beyond the input timestamp for the associated window;

merging two or more of the mergeable windows belonging to a same key that overlap into a single merged window; and

setting an associated output timestamp for each element to a value greater than or equal to an earliest time in the associated merged window or the associated mergeable window.

15. The system of claim 14, wherein the single merged window includes an associated range of time greater than the predefined range of time.

16. The system of claim 12, wherein the operations further comprise, when the received data corresponds to streaming data:

grouping the streaming data into windows;

setting an input timestamp on an element of the streaming data; and

when the input timestamp on the element occurs earlier than a watermark;

determining the streaming data comprises late streaming data; and

one of;

dropping the late streaming data;

or

allowing the late streaming data by creating a duplicate window in an output for the late streaming data.

17. The system of claim 12, wherein the operations further comprise:

grouping a second subset of the received data into a second window, the second window defining a second sub-event time of the second data subset;

aggregating a second result of the second data subset for the second window; and

determining a second trigger time to emit the second aggregated result of the second data subset, the second trigger time comprising at least one of;

when a watermark reaches an end of the second window;

every threshold number of seconds of a walltime;

after receiving a punctuation record that terminates the second window;

every threshold number of records;

after arbitrary user logic decides to trigger;

or

after an arbitrary combination of concrete triggers.

18. The system of claim 12, wherein the operations further comprise, when determining the first trigger time to emit the first aggregated result of the first data subset, discarding the first aggregated result from use when aggregating results of later subsets of the received data.

19. The system of claim 12, wherein the operations further comprise:

when determining the first trigger time to emit the first aggregated result of the first data subset, storing the copy of the first aggregated result in the persistent state within the memory hardware; and

when the next aggregated result of the later subset associated with the same window emits;

emitting a retraction of the first aggregated result; and

emitting a combined session result for the first window.

20. The system of claim 12, wherein the operations further comprise:

receiving a late data point after grouping the first data subset into the first window, the late data point related to the first window; and

discarding the late data point.

21. The system of claim 17, wherein the operations further comprise:

receiving a late data point after grouping the first data subset into the first window, the late data point related to the second window; and

accumulating the late data point into the first window to refine the first aggregated result with the late data point.

22. The system of claim 17, wherein the operations further comprise:

receiving a late data point after grouping the first data subset into the first window, the late data point related to the first window;

aggregating a combined result of the first data subset and the late data point; and

emitting the combined result.