Naiad: a timely dataflow system

By Derek Gordon Murray, Frank McSherry, Rebecca Isaacs, Michael Isard, Paul Barham, Martín Abadi. 2013

874 citations recorded by the source corpus.

Naiad is a distributed system for executing data parallel, cyclic dataflow programs. It offers the high throughput of batch processors, the low latency of stream processors, and the ability to perform iterative and incremental computations. Although existing systems offer some of these features, applications that require all three have relied on multiple platforms, at the expense of efficiency, maintainability, and simplicity. Naiad resolves the complexities of combining these features in one framework. A new computational model, timely dataflow, underlies Naiad and captures opportunities for parallelism across a wide class of algorithms. This model enriches dataflow computation with timestamps that represent logical points in the computation and provide the basis for an efficient, lightweight coordination mechanism. We show that many powerful high-level programming models can be built on Naiad's low-level primitives, enabling such diverse tasks as streaming data analysis, iterative machine learning, and interactive graph mining. Naiad outperforms specialized systems in their target application domains, and its unique features enable the development of new high-performance applications.

Subfields: Computer Networks and Communications, Hardware and Architecture, Information Systems, ML Systems & Hardware

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Hardware and Architecture

In Information Systems

In ML Systems & Hardware

Citations in the corpus

Pathways: Asynchronous Distributed Dataflow for ML (2022, background): “…runtime must also support sparse data exchanges along sharded edges, in which messages can be sent between a dynamically chosen subset of shards, using standard progress tracking mechanisms (Akidau et al., 2013; Murray et al., 2013) to detect when all messages for a shard have been received.”
TensorFlow: A system for large-scale machine learning (2016, positive): “The implementation of loops in TensorFlow is based on Switch and Merge [4], with additional structural constraints based on timely dataflow [54] to simplify the distributed execution state.”
TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems (2016, positive): “Its distributed architecture is closest to Naiad, in that the system uses a single, optimized dataﬂow graph to represent the entire computation, and caches information about that graph on each device to minimize coordination overhead.”
Ray: A Distributed Framework for Emerging AI Applications (2017, background): “This has led to the development of a plethora of frameworks for distributed data analysis, including batch [20, 64, 28], streaming [15, 39, 31], and graph [34, 35, 24] processing systems.”
Pipe-SGD: A Decentralized Pipelined SGD Framework for Distributed Deep Net Training (2018, methodology): “To take advantage of parallelization across machines, a variety of approaches have been developed starting from the popular MapReduce paradigm [9, 51, 19, 37].”
PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs (2019, background): “Naiad [51] provides timely dataflow abstraction to support low-latency streaming and cyclic computations, which allows the efficient implementation of iterative graph processing.”
Scaling Distributed Machine Learning with the Parameter Server (2014, neutral): “…Consistency Fault Tolerance Graphlab [34] graph eventual checkpoint Petuum [12] hash table delay bound none REEF [10] array BSP checkpoint Naiad [37] (key,value) multiple checkpoint Mlbase [29] table BSP RDD Parameter (sparse) various continuous Server vector/matrix Table 2: Attributes of…”
Flexible Scheduling of Distributed Analytic Applications (2016, methodology): “Our algorithm is evaluated using trace-driven simulations, with large-scale real system traces: our flexible scheduler outperforms a baseline approach across a variety of metrics, including application turnaround times, and resource allocation efficiency.”
Fast in-memory transaction processing using RDMA and HTM (2015, methodology): “To bridge HTM (which essentially uses OCC) and 2PL, DrTM implements the exclusive and shared locks using one-sided RDMA operations, which are cache-coherent with local accesses and thus provide strong consistency with HTM.”
Exploiting iterative-ness for parallel ML computations (2014, background): “Naiad generalizes iterative machine learning into a Dryad-like dataflow model for iterative and streaming computation of many forms [32].”
Dandelion: a compiler and runtime for heterogeneous systems (2013, background): “Extending dataflow systems to support iteration [21, 40, 70, 75] or incremental iterative computation [72, 41, 73, 74] is an active research area.”
Gemini: A Computation-Centric Distributed Graph Processing System (2016, neutral): “There also exist many systems that focus on query processing [40, 46, 54], temporal analytics [13, 19, 27, 31], machine learning and data mining [50, 58], or more general tasks [34, 35, 45] on large-scale graphs.”
Dynamic control flow in large-scale machine learning (2018, methodology): “ach to control flow draws on a long line of research on dynamic dataflow architectures, going back to the work of Arvind et al. [4, 5]. The timely dataflow model [28], implemented in the Naiad system [27], can be seen as a recent embodiment of those architectures. It supports distributed execution, ”
Discretized streams: fault-tolerant streaming computation at scale (2013, background): “Naiad [27, 28] automatically incrementalizes data flow computations written in LINQ and is unique in also being able to incrementalize iterative computations.”
Proposal Scaling Distributed Machine Learning with System and Algorithm Co-design (2016, neutral): “This (key,value) abstraction is widely adopted by existing approaches [40, 75, 102].”
Scalability! But at what COST? (2015, background): “Figure 5 presents published scaling information from PowerGraph [9], GraphX [10], and Naiad [16], as well as two single-threaded measurements as horizontal lines.”