Sliding windows

A sliding window is specified by providing both an eviction policy and a trigger policy.

The eviction policy defines the contents of the window by defining when tuples are evicted. Unlike a tumbling window, a subset of the tuples are evicted according to the policy, thus the window can be seen to slide, typically representing a collection of most recently arrived tuples.

Operators that support sliding windows do not normally submit output tuples upon eviction, instead they submit output tuples according to its trigger policy. When the window is triggered, the operator performs its function against the current set of tuples in the window. For example, sliding, time(10), count(5) means that the eviction policy keeps the window size to 10 seconds, and the trigger policy executes the operator behavior after every five tuples. A sliding window expels the oldest tuples to maintain the window size when new tuples are coming in, and it executes the operator logic each time it reaches a trigger.

The eviction and trigger policies for sliding windows are independent from each other. As a result, unlike for tumbling windows, an old tuple can still be in the window if the logic of the operator gets triggered again before the tuple is evicted. The available policies for eviction and trigger are count-based, time-based, and attribute-delta-based, but not punctuation-based. In other words, the window can use one of three eviction policies and one of three trigger policies, yielding a total of nine combinations. If the trigger policy is omitted, it defaults to count(1). For example, sliding, count(3) is equivalent to sliding, count(3), count(1).

Eviction policies

Although the same syntax is used as for tumbling windows, the meaning of each eviction policy is different for sliding windows:

Count eviction policy count(n): An eviction policy count(n) states that the sliding window is full when it contains n tuples. When the window is full, that is when it contains the last n tuples to arrive at the input port, any tuple to arrive at the input port evicts one tuple, the oldest tuple.
For example, with count(4), when four tuples have arrived, the window becomes full and continues to contain four tuples. As each new tuple arrives, the oldest tuple in the window is evicted and the new tuple inserted, leaving four tuples in the window.
Time eviction policy time(t): An eviction policy time(t) states that any tuple that has been in the sliding window for more than t seconds must be evicted. So, with a eviction policy of time(5.0), at all times the sliding window contains all tuples that arrived in the last five seconds, which includes the possibility that the window is empty. Eviction of the tuples takes place independently of any tuple insertion.
Here’s an example of a sliding window with eviction policy time(5.0) at a point in time t+4. Tuple A was inserted at time t (four seconds earlier), tuple B one second after A (t+1), and tuple C two and a half seconds after B (t+3.5). The number for each tuple in the window represents the number of seconds it remains in the window. Tuple C has been in the window for 0.5 seconds, thus it remains in the window for a further 4.5 (5 – 0.5) seconds.
Three seconds later (t+7), tuples A and B have been evicted, because A has been in the window seven seconds and B six seconds, both of which are greater than the policy value of five seconds. Tuple C now has 1.5 (4.5 – 3) seconds left in the window, and tuple D, which arrived one second ago (t+6), has four seconds left in the window.
Delta eviction policy delta(attribute, delta): The eviction policy delta(attribute, delta) defines the condition for the eviction of a tuple in a sliding window in terms of the value of attribute in an input tuple, and the value of delta. With the eviction policy delta(temperature, 1.5), when a new tuple T arrives at the input port, the value of its temperature attribute is compared with the value of the temperature attribute of all tuples in the window. For any tuple, if the difference in the values is greater than 1.5 (the delta), that tuple is evicted. More formally, a tuple in the window, Twindow, is evicted if this condition is true:
```
T_temperature - Twindow_temperature > delta
```
With this example, if the window contained tuples with the temperature values [17.1, 16.4, 16.0], the arrival of a tuple with the temperature value 17.6 would evict the tuple with the value 16.0 because (17.6 – 16.0) is greater than 1.5, leaving the window’s contents to be [17.6, 17.1, 16.4] after the insertion.
If the tuples arrive at the window in such order that the value of attribute never decreases, the window naturally slides, which means it’s always the oldest tuples that are evicted. This behavior can be typical of SPL timestamp attributes (for example, a time sensor was read or a trade was executed), and the delta policy supports timestamp attributes where the delta value represents the time difference in seconds between two values (ignoring the machine identifier). Thus, when input tuples are ordered, all tuples in the window have an attribute value that is within delta of the most recent tuple.
However, if the input tuples are not ordered with respect to attribute, the window does not act as a true “slide.” Tuples are evicted based solely on the delta value, and thus tuples might be evicted earlier than tuples that arrived before them. In addition, because only the most recently arrived tuple is used to determine what is evicted, out of order data can result in the window containing tuples that differ in the attribute value by more than the delta. Here, with the policy delta(temperature, 1.5), tuple D evicts tuple B (because 17.6 – 16.0 > 1.5) which is not the oldest tuple.Tuple E does not evict any tuples because (14.0-attribute) is not greater than 1.5 for any tuple in the window. Thus the window didn’t truly “slide” as A was left in the window, and there are pairs of tuples in the window for which the delta is exceeded.

If required, any ordering of tuples needs to be enforced by upstream operators.

Trigger policies

The trigger policy for a sliding window defines when the operator needs to perform its processing against the contents of the window. Definition of the trigger policy is independent of the eviction policy, thus a sliding window CAN have a time-based eviction policy, but a count-based trigger. While the trigger is being processed by the operator; tuples are not evicted or inserted in the window. The policy types for triggering match the syntax of the eviction policies but their definition applies to when the trigger occurs.

In SPL, the trigger policy is specified after the eviction policy. For example, sliding, count(20), time(1) has a count eviction policy of size 10 and a time trigger policy of one second.

Sliding windows support these trigger policies:

Count trigger policy count(n): A trigger policy count(n) states that the sliding window is triggered for every n tuples that arrive at the input port. A typical use is count(1), which means the window is triggered for every input tuple. For example, with the Aggregate operator this means every input tuple results in the submission of one or more tuples reflecting the most up to date aggregation of the window (which can contain any number of tuples, defined by its eviction policy). If a trigger policy is not specified then it defaults to count(1).
Time trigger policy time(t): A trigger policy time(t) states that the sliding window is triggered every t seconds, regardless of tuple arrival.
Delta trigger policy delta(attribute, delta): A trigger policy delta(attribute, delta) defines the condition for triggering of a sliding window in terms of the value of attribute in its input tuples. When a tuple T arrives at the window, the difference for attribute is calculated between T and the last tuple that triggered the window. If the difference is larger than delta, the window is triggered. For example, with delta(ts, 1), where ts is an SPL timestamp attribute, the window is triggered every second according to timestamps of the data, not wall-clock time.

You can also find examples of sliding windows configurations in these SPL samples on GitHub: