Data Flow Windowing and Triggering

• US 20160285711A1
• Filed: 11/03/2015
• Published: 09/29/2016
• Est. Priority Date: 11/03/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Akidau, Tyler, Bradshaw, Robert, Chambers, Ben, Chambers, Craig, Mills, Daniel, Perry, Frances, Lax, Reuven
• Granted Patent: US 10,037,187 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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; and

emitting at least a portion of the results of the received data based on the event time and the processing time.

2. The method of claim 1, further comprising:

grouping, using the data processing hardware, 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 first subset of the received data into a window, the window defining a sub-event time of the data subset;

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

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

when a watermark reaches an end of the window;

every threshold number of seconds of a walltime;

after receiving a punctuation record that terminates the 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 6, further comprising, when determining the 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 6, further comprising, when determining the trigger time to emit the first aggregated result of the first data subset:

storing a copy of the first aggregated result in a persistent state within memory hardware in communication with the data processing hardware; and

refining, by the data processing hardware, a next aggregate result of a later subset with the first aggregated result.

9. The method of claim 6, further comprising:

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

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

emitting a retraction of the first aggregated result; and

emitting a combined session result for the window.

10. The method of claim 6, further comprising:

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

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

11. The method of claim 6, further comprising:

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

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

12. The method of claim 6, further comprising:

receiving, at the data processing hardware, a late data point after grouping the first data subset into the window, the late data point related to the 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.

13. 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; and

emitting at least a portion of the results of the received data based on the processing time and the event time.

14. The system of claim 13, wherein the operations further comprise grouping 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.

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

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

17. The system of claim 13, 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.

18. The system of claim 13, wherein the operations further comprise:

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

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

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

when a watermark reaches an end of the window;

every threshold number of seconds of a walltime;

after receiving a punctuation record that terminates the window;

every threshold number of records;

after arbitrary user logic decides to trigger;

or

after an arbitrary combination of concrete triggers.

19. The system of claim 18, wherein the operations further comprise, when determining the 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.

20. The system of claim 18, wherein the operations further comprise, when determining the trigger time to emit the first aggregated result of the first data subset:

storing a copy of the first aggregated result in a persistent state within memory hardware in communication with the data processing hardware; and

refining a next aggregate result of a later subset with the first aggregated result.

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

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

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

emitting a retraction of the first aggregated result; and

emitting a combined session result for the window.

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

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

discarding the late data point.

23. The system of claim 18, wherein the operations further comprise:

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

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

24. The system of claim 18, wherein the operations further comprise:

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

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

emitting the combined result.