Naiad

Established: October 17, 2011

Download: Naiad is now available under the Apache 2.0 open-source license from Github (opens in new tab) (source) and NuGet.org (opens in new tab) (binary packages). For more details about the software release, see the online Naiad documentation (opens in new tab).

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.

 

News: The Naiad paper was awarded a best paper award at SOSP 2013.

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.

You can read more about Naiad on the MSR SVC Big Data blog (opens in new tab), watch Derek’s SOSP presentation (opens in new tab), and watch an interview about Naiad on Channel 9 (opens in new tab).

Differential Dataflow

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 (opens in new tab).

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.