Incremental, iterative data processing with timely dataflow
Communications of the ACMPublished 22 September 2016Open access
Derek G. Murray, Frank McSherry, Michael Isard, Rebecca Isaacs, Paul Barham, Martı́n Abadi
Citations37
SJR quartileQ1
SJR score1.15
SNIP3.34
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Two of the programming frameworks built on Naiad are described: GraphLINQ for parallel graph processing, and differential dataflow for nested iterative and incremental computations.
Abstract
We describe the timely dataflow model for distributed computation and its implementation in the Naiad system. The model supports stateful iterative and incremental computations. It enables both low-latency stream processing and high-throughput batch processing, using a new approach to coordination that combines asynchronous and fine-grained synchronous execution. We describe two of the programming frameworks built on Naiad: GraphLINQ for parallel graph processing, and differential dataflow for nested iterative and incremental computations. We show that a general-purpose system can achieve performance that matches, and sometimes exceeds, that of specialized systems.
Keywords
Computer Science
Communications of the ACMMapReduce
18,538 Citations2008Jay B. Dean, Sanjay Ghemawat
This presentation explains how the underlying runtime system automatically parallelizes the computation across large-scale clusters of machines, handles machine failures, and schedules inter-machine communication to make efficient use of the network and disks.
Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing
3,577 Citations2012Matei Zaharia, Mosharaf Chowdhury +7 more
Resilient Distributed Datasets is presented, a distributed memory abstraction that lets programmers perform in-memory computations on large clusters in a fault-tolerant manner and is implemented in a system called Spark, which is evaluated through a variety of user applications and benchmarks.
Dryad
2,460 Citations2007Michael Isard, Mihai Budiu +3 more
The Dryad execution engine handles all the difficult problems of creating a large distributed, concurrent application: scheduling the use of computers and their CPUs, recovering from communication or computer failures, and transporting data between vertices.
Bigtable: a distributed storage system for structured data
1,955 Citations2006Fay W. Chang, Jay B. Dean +7 more
Proceedings of the IEEESynchronous data flow
1,802 Citations1987Edward A. Lee, David G. Messerschmitt
A preliminary SDF software system for automatically generating assembly language code for DSP microcomputers is described, and two new efficiency techniques are introduced, static buffering and an extension to SDF to efficiently implement conditionals.
Operating Systems Design and ImplementationPowerGraph: distributed graph-parallel computation on natural graphs
1,503 Citations2012Joseph E. Gonzalez, Yucheng Low +3 more
This paper describes the challenges of computation on natural graphs in the context of existing graph-parallel abstractions and introduces the PowerGraph abstraction which exploits the internal structure of graph programs to address these challenges.
Communications of the ACMParallel database systems
1,281 Citations1992David J. DeWitt, Jim Gray
Over the last decade 'Eradata, Tandem, and a host of startup companies have successfully developed and marketed highly parallel machines that refutes a 1983 paper predicting the demise of database machines.
Operating Systems Design and ImplementationScaling distributed machine learning with the parameter server
1,090 Citations2014Mu Li, David G. Andersen +7 more
To demonstrate the scalability of the proposed parameter server framework, experimental results on petabytes of real data with billions of examples and parameters on problems ranging from Sparse Logistic Regression to Latent Dirichlet Allocation and Distributed Sketching are shown.
Proceedings of the VLDB EndowmentDremel
709 Citations2010Sergey Melnik, Andrey Gubarev +5 more
This paper describes the architecture and implementation of Dremel, and explains how it complements MapReduce-based computing, and presents a novel columnar storage representation for nested records.
Operating Systems Design and ImplementationDryadLINQ: a system for general-purpose distributed data-parallel computing using a high-level language
699 Citations2008Yuan Yu, Michael Isard +5 more
Proceedings of the VLDB EndowmentMillWheel
533 Citations2013Tyler Akidau, Alex Balikov +8 more
In practice, this paper finds that MillWheel's unique combination of scalability, fault tolerance, and a versatile programming model lends itself to a wide variety of problems at Google.
Large-scale incremental processing using distributed transactions and notifications
412 Citations2010Daniel N. Peng, Frank Dabek
Percolator is built, a system for incrementally processing updates to a large data set, and deployed it to create the Google web search index, which processes the same number of documents per day while reducing the average age of documents in Google search results by 50%.
IEEE Transactions on Knowledge and Data EngineeringExploiting punctuation semantics in continuous data streams
310 Citations2003Peter Tucker, David Maier +2 more
This work introduces three kinds of invariants to specify the proper behavior of operators in the presence of punctuation, and reports on the initial implementation and a strategy for proving implementations of these invariants are faithful to their relational counterparts.
CIEL: a universal execution engine for distributed data-flow computing
230 Citations2011Derek G. Murray, Malte Schwarzkopf +4 more
The execution engine provides transparent fault tolerance and distribution to Skywriting scripts and high-performance code written in other programming languages, and achieves scalable performance for both iterative and non-iterative algorithms.
Scalability! but at what cost?
218 Citations2015Frank McSherry, Michael Isard +1 more
This work surveys measurements of data-parallel systems recently reported in SOSP and OSDI, and finds that many systems have either a surprisingly large COST, often hundreds of cores, or simply underperform one thread for all of their reported configurations.
Distributed aggregation for data-parallel computing
170 Citations2009Yuan Yu, Pradeep Kumar Gunda +1 more
The degree of language integration between user-defined functions and the high-level query language has an impact on code legibility and simplicity; the choice of programming interface has a material effect on the performance of computations; some execution plans perform better than others on average; and in order to get good performance on a variety of workloads a system must be able to select between execution plans depending on the computation.
Proceedings of the VLDB EndowmentSpinning fast iterative data flows
119 Citations2012Stephan Ewen, Kostas Tzoumas +2 more
This work proposes a method to integrate incremental iterations, a form of workset iterations, with parallel dataflows and presents an extension to the programming model for incremental iterations that alleviates for the lack of mutable state in dataflow and allows for exploiting the sparse computational dependencies inherent in many iterative algorithms.
Differential dataflow
93 Citations2013Frank McSherry, Derek G. Murray +2 more
Broom: sweeping out garbage collection from big data systems
83 Citations2015Ionel Gog, Jana Giceva +7 more
The initial results show that region-based memory management reduces emulated Naiad vertex runtime by 34% for typical data analytics jobs, and could be memory-safe and inferred automatically.
Musketeer
82 Citations2015Ionel Gog, Malte Schwarzkopf +4 more
Musketeer is built, a workflow manager which can dynamically map front-end workflow descriptions to a broad range of back-end execution engines and speeds up realistic workflows by up to 9x by targeting different execution engines, without requiring any manual effort.
ACM Transactions on Programming Languages and SystemsThe derivation of distributed termination detection algorithms from garbage collection schemes
71 Citations1993Gérard Tel, Friedemann Mattern
It is shown that the termination detection problem for distributed computations can be modeled as an instance of the garbage collection problem and algorithms for thetermination detection problem are obtained by applying transformations to garbage collection algorithms.
Proceedings of the VLDB EndowmentOn-the-fly progress detection in iterative stream queries
27 Citations2009Badrish Chandramouli, Jonathan Goldstein +1 more
This work proposes a third option in which cyclic queries run continuously, but detect progress "on the fly" by means of a Flying Fixed-Point (FFP) operator, and shows how a hybrid approach limits predictions while coming close the progress-tracking ability of Probing.
Consolidation of queries with user-defined functions
11 Citations2014Marcelo Sousa, Işıl Dillig +3 more
This work presents a sound consolidation calculus and an effective algorithm for consolidating multiple UDFs and shows that the algorithm dramatically improves overall job completion time when executing user-defined filters that operate on the same data and perform similar computations.
Lecture notes in computer scienceTimely Dataflow: A Model
7 Citations2015Martı́n Abadi, Michael Isard
This paper defines and investigates the could-result-in relation which is central to this model, then the semantics of timely dataflow graphs.
Lecture notes in computer scienceTimely Rollback: Specification and Verification
6 Citations2015Martı́n Abadi, Michael Isard
A formal description and analysis of a technique for distributed rollback recovery that allows the selective undo of work at particular virtual times and a refinement theorem ensures the consistency of rollbacks.