Naiad: A Timely Dataflow System

Notes from the whitepaper Naiad: A Timely Dataflow System.

The original paper was published in 2013 via Microsoft Research. Interestingly enough, this paper was republished in 2016 as a short article, with most of the authors now working at Google.

On tracking a message's position (in the compute graph) via timestamp "modification":

Messages in a timely dataflow system flow only along edges, and their timestamps are modified by ingress, egress, and feedback vertices.

The modification is more like an augmentation:

Each event has a timestamp and a location (either a vertex or edge), and we refer to these as a pointstamp

On using this pointstamp to determine a watermark:

Since events cannot send messages backwards in time, we can use this structure to compute lower bounds on the timestamps of messages an event can cause

On using this pointstamp and watermark to determine a window:

By applying this computation to the set of unprocessed events, we can identify the vertex notifications that may be correctly delivered.

On the distinction between the logical graph and the physical one (in the case of a distributed implementation), and on the implications of using either to determine (compute) watermarks and windows:

using the logical graph ensures that the size of the data structures used to compute the relation depends only on the logical graph and not the much larger physical graph

On routing and executing messages vs coordination notifications:

When faced with multiple runnable actions (messages and notifications to deliver) workers break ties by delivering messages before notifications, in order to reduce the amount of queued data. Different policies could be used, such as prioritizing the delivery of messages and notifications with the earliest pointstamp to reduce end-to-end latency

On the performance characteristics of routing 're-entrant' messages in iterative/cyclical graphs:

Without support for re-entrancy, the implementations of many iterative patterns would overload the system queues. Re-entrancy allows the vertex implementation to coalesce incoming messages in [the 'on receive' handler], and thereby reduce overall memory consumption.

On global coordination (between partitioned workers) of watermarks/frontiers:

We adapt the approach for progress tracking based on a single global frontier to a distributed setting in which multiple workers coordinate independent sets of events using a local view of the global state.  
The worker does not immediately update its local occurrence counts as it dispatches events, but instead broadcasts (to all workers, including itself) progress updates

On stragglers:

we view the resulting micro-stragglers as the main obstacle to scalability for low-latency workloads

On related work:

MillWheel is a recent example of a streaming system with punctuations (and sophisticated fault-tolerance) that adopts a vertex API very similar to Naiad’s, but does not support loops