The Naiad project is an investigation of data-parallel dataflow computation, like Dryad and DryadLINQ, but with a focus on low-latency streaming and cyclic computations. Naiad introduces a new computational model, timely dataflow, which combines low-latency asynchronous message flow with lightweight coordination when required. These primitives allow the efficient implementation of many dataflow patterns, from bulk and streaming computation to iterative graph processing and machine learning.
Naiad is system for data-parallel dataflow computation which attempts to raise the levels of abstraction used by programmers from an imperative sequence of MapReduce-style statements, to involve higher level concepts of loops and streaming. While Naiad is not the first system to support loops or streaming computation, it does provide support for the combination of the two, nesting loops inside streaming contexts and indeed other loops, while maintaining a clean separation between the many reasons new records may flow through the computation.
Naiad is based on a computational model called Timely Dataflow. Informally, Timely Dataflow supports directed dataflow graphs with structured cycles, analogous to structured loops in a standard imperative programming language. This structure provides information about where records might possibly flow in the computation, allowing an implementation like Naiad to efficiently track and inform dataflow vertices about the possibility of additional records arriving at given streaming epochs or iterations.
Naiad's most notable performance property, when compared with other data-parallel dataflow systems, is its ability to quickly coordinate among the workers and establish that stages have completed, typically in less than a millisecond for our 64 machine cluster. By removing the overhead associated with moving between computational stages, Naiad supports efficient implementations of a variety of programming patterns not often found in dataflow systems, including prioritized iteration, nested iterative algorithms, and incremental updates to iterative computations. These lead to simple, performant, and composable libraries for event processing, graph computation, machine learning, and other real-time analytics.
Our initial work on Naiad was aimed at incremental re-evaluation of declarative data-parallel computations, including those with iterative fixed-point computations. Our work here gave rise to a new computational model, differential dataflow, capable of efficiently processing substantially more complex computations than current systems support, namely incremental and arbitrarily nested iterative dataflow computation. Differential dataflow is implemented as a library atop Naiad, and is available with the Naiad source.
Consider the problem of computing the connected component structure of a graph. One natural iterative data-parallel approach has each vertex assume a label (initially their own name) and repeatedly share their label with their neighbors, assuming the least label in their neighborhood. Eventually, all vertices in the same component will be labeled with the name of the least vertex in their component. Several data-processing systems make this sort of iterative computation easy to write and efficient to execute.
However, what happens if the input changes? Perhaps a single edge is removed, which can result in the separation of two previously connected components. The labels above are invalidated, and it is not easy to determine how to unwind their propagation to return the computation to a state from which new correct labels can be determined. The data-processing systems alluded to above are forced to discard the results of their previous computation and start over from scratch.
Naiad, by comparison, represents a dataset in a compact form indicating where and when records have changed. The specific representation enables efficient combination of incremental and iteration computation, and allows us to update computations like the connected components example above in a fraction of a second. Naiad is currently capable of maintaining the strongly connected component structure (a doubly-nested loop) of a graph defined by a sliding window over edge stream with rates exceeding Twitter's full tweet volume, all with sub-second latency.
- Derek G. Murray, Frank McSherry, Rebecca Isaacs, Michael Isard, Paul Barham, and Martin Abadi, Naiad: A Timely Dataflow System, in Proceedings of the 24th ACM Symposium on Operating Systems Principles (SOSP), ACM, 3 November 2013
- Martin Abadi, Frank McSherry, Derek G. Murray, and Thomas L. Rodeheffer, Formal Analysis of a Distributed Algorithm for Tracking Progress, in FMOODS-FORTE'13: 15th Formal Methods for Open Object-Based Distributed Systems and 33nd Formal Techniques for Networked and Distributed Systems, Springer, 3 June 2013
- Thomas L. Rodeheffer, The Naiad Clock Protocol: Specification, Model Checking, and Correctness Proof, no. MSR-TR-2013-20, 12 February 2013
- Frank McSherry, Derek G. Murray, Rebecca Isaacs, and Michael Isard, Differential dataflow, in Proceedings of CIDR 2013, 5 January 2013
- Frank McSherry, Rebecca Isaacs, Michael Isard, and Derek G. Murray, Composable Incremental and Iterative Data-Parallel Computation with Naiad, no. MSR-TR-2012-105, 9 October 2012