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, watch Derek’s SOSP presentation, and watch an interview about Naiad on Channel 9.
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.