Source-linked AI summary
Spinning Fast Iterative Data Flows
Stephan Ewen, Kostas Tzoumas, Moritz Kaufmann, Volker Markl
TL;DR
Many iterative algorithms remain inefficient in dataflow systems because those systems cannot exploit their sparse computational dependencies, motivating specialized alternatives. The paper integrates bulk and workset-based incremental iterations into parallel dataflows, including mutable-state-like updates through the programming model. In experiments, incremental iterations were competitive with specialized systems, with reported algorithm-runtime speedups of up to two orders of magnitude, while retaining a unified dataflow abstraction.
Problem
Many graph and machine-learning algorithms remain inefficient in dataflow systems because existing systems cannot exploit their sparse computational dependencies.
Method
The paper integrates bulk iterations and workset-based incremental iterations into parallel dataflows, with optimizer and execution strategies that update only state affected by computation.
Results
Incremental iterations were competitive with specialized systems and outperformed batch processing and bulk iterations by up to two orders of magnitude.
Takeaways & Limitations
Incremental iterations preserve a general dataflow abstraction while reducing the number of systems required for large-scale analytics.
Takeaways & Limitations
A general formal characterization of which functions admit effective and efficient incremental fixpoint computation is not known; distributive functions are a known supported class.
Abstract
from arXiv · showhide
Parallel dataflow systems are a central part of most analytic pipelines for big data. The iterative nature of many analysis and machine learning algorithms, however, is still a challenge for current systems. While certain types of bulk iterative algorithms are supported by novel dataflow frameworks, these systems cannot exploit computational dependencies present in many algorithms, such as graph algorithms. As a result, these algorithms are inefficiently executed and have led to specialized systems based on other paradigms, such as message passing or shared memory. We propose a method to integrate incremental iterations, a form of workset iterations, with parallel dataflows. After showing how to integrate bulk iterations into a dataflow system and its optimizer, we present an extension to the programming model for incremental iterations. The extension alleviates for the lack of mutable state in dataflows and allows for exploiting the sparse computational dependencies inherent in many iterative algorithms. The evaluation of a prototypical implementation shows that those aspects lead to up to two orders of magnitude speedup in algorithm runtime, when exploited. In our experiments, the improved dataflow system is highly competitive with specialized systems while maintaining a transparent and unified dataflow abstraction.
1. INTRODUCTION
Parallel dataflow systems simplify and scale large-data analytics, but iterative and recursive algorithms challenge their acyclic execution model. This paper integrates bulk and incremental iterations into dataflows, using computational dependencies to improve efficiency while preserving a unified abstraction.
- Motivation: Parallel dataflow systems provide a simple abstraction for distributing large-data computations while hiding scheduling, data transfer, and failure-management tasks.MapReduce, Dryad, Hyracks, and Stratosphere exemplify this paradigm.
- Motivation: Iterative and recursive machine-learning and graph algorithms challenge dataflows because they repeat computation until a condition is fulfilled, making the data flow no longer acyclic.Existing systems support some iterative workloads, but many algorithms remain inefficient when their sparse computational dependencies cannot be exploited.
- Iteration Models: Incremental iterations differ from bulk iterations by changing only part of the previous result and exploiting sparse dependencies between solution elements.Connected Components illustrates the pattern: an update to one vertex directly affects only a small number of neighboring vertices.
- Motivation: Existing dataflow systems execute incremental algorithms as bulk iterations, causing severe inefficiency and motivating specialized systems or multi-system pipelines.Such pipelines may combine dataflow preprocessing, specialized training, and dataflow postprocessing.
- Contributions: The paper integrates bulk iterations with a dataflow system and introduces workset-based incremental iterations that exploit computational dependencies for graph and machine-learning algorithms.The approach also addresses optimizer and execution-engine integration while retaining the dataflow programming model.
- Evaluation: Up to two orders of magnitude speedup was observed for incremental iterations, which were competitive with specialized systems while bulk iterations outperformed the specialized system.The comparison used graph algorithms across a batch system, a dedicated graph system, and Stratosphere.
2. ITERATIVE COMPUTATIONS
The section distinguishes bulk, incremental, and microstep iterations, then explains how sparse computational dependencies make incremental execution more efficient for Connected Components. It also describes the convergence assumptions and performance implications of focusing work on changing graph regions.
- Fixpoint Iterations: Fixpoint iterations repeatedly apply a step function until the partial solution no longer changes or reaches a specified error threshold.Exact fixpoint convergence requires a suitable complete partial order and a step function that guarantees progress toward a supremum.
- Fixpoint Iterations: Connected Components assigns each vertex a component ID and repeatedly replaces it with the minimum ID among itself and its neighbors.The algorithm starts with unique IDs and iteratively improves the mapping until no vertex changes.
- Incremental Iterations & Microsteps: Sparse computational dependencies mean that changing one data point affects only a small number of others, especially neighboring vertices in graph algorithms.This structure allows algorithms to update selected data points rather than fully recomputing each partial solution.
- Incremental Iterations & Microsteps: Incremental iterations use a working set of candidate updates and combine it with persistent solution state instead of recomputing the full next solution.The update function merges relevant candidates with the state, while the delta function identifies work that can change the solution.
- Incremental Iterations & Microsteps: Microsteps interleave one working-set update with one partial-solution update, enabling fine-grained asynchronous parallelism when updates conform to the ordering.Individual element updates can take effect in parallel without synchronizing iteration supersteps.
- Performance Implications: In the Connected Components example, all but one vertex reach their final component ID in one step, so incremental execution avoids re-inspecting unchanged regions.On the FOAF subgraph, later iterations perform significantly less work, and changed vertices closely track working-set size.
3. DATAFLOW SYSTEMS
The dataflow system represents computations as directed acyclic graphs of operators over record bags and supports user-defined code. Its optimizer selects parallel execution strategies for operators using cost-based alternatives.
- Dataflow Abstraction: A dataflow is a directed acyclic graph whose operators transform bags of records from sources to sinks.Closing the loop around a dataflow construct provides a function whose fixpoint can be computed iteratively.
- Operators: Operators may contain arbitrary user-defined code and can process records individually or groups of records before producing output.The system also distinguishes unary operators from operators receiving multiple inputs.
- Operators: Stratosphere encapsulates user-defined functions in Parallelization Contracts that operate over one or more input datasets.The contracts include common data-manipulation patterns such as filtering, joining, and grouping.
- Optimization: The optimizer chooses execution strategies such as broadcasting, partitioning, or repartitioning inputs and may use hash-based or sort-merge implementations.These alternatives are explored for operators such as equi-joins using a cost model.
4. BULK ITERATIONS
Bulk iterations repeatedly recompute an entire partial solution within a dataflow, using PageRank to illustrate the model. The system embeds iteration constructs, supports alternative execution strategies, and extends optimization to account for iterative data paths.
- Bulk iterations recompute the entire partial solution in every iteration until a termination criterion is met.
- PageRank example: PageRank joins the rank vector with a sparse transition matrix, groups contributions by target page, and sums them into the next rank vector.
- The iterative dataflow separates dynamic paths carrying changing iteration results from constant paths carrying data reused across iterations.
- Execution: Iterations can execute by lazily unrolling the dataflow or by reusing it through feedback channels.
- Optimization: The optimizer chooses execution plans based on data sizes, including broadcasting smaller models or partitioning the rank vector and transition matrix.
- Optimization: Iterative optimization propagates interesting properties across the dynamic data path and creates candidates that establish useful partitioning or sorting early.
5. INCREMENTAL ITERATIONS
Incremental iterations update a persistent solution with only changed records and derive the next working set from those changes. This dataflow abstraction targets sparse dependencies while preserving side-effect-free, optimizable execution.
- Incremental iterations compute a delta set and next working set instead of rebuilding the entire partial solution.
- The delta set replaces records with matching keys in the persistent solution, allowing updates without mutable operator state.
- The combined step function ∆ computes changed records and the next working set, and iteration terminates when that working set is empty.
- Connected Components: Connected Components represents vertex-component mappings as the solution set and candidate updates as the working set.
- Generalization: The abstraction generalizes message-passing algorithms by treating states as S and messages as W, then producing changed states and new messages.
- A comparator resolves duplicate delta records by ordering competing states and retaining the larger record.
6. EVALUATION
The evaluation compares Stratosphere, Spark, and Giraph on bulk and incremental graph workloads using PageRank and Connected Components. Incremental iterations exploit sparse dependencies, producing much lower later-iteration costs and substantial end-to-end speedups on suitable graphs.
- Evaluation setup: The evaluation compares Stratosphere, Spark, and Giraph across PageRank and Connected Components on four graph datasets using a four-machine cluster.All systems ran in a JVM; the datasets include Wikipedia, Webbase, Hollywood, and Twitter graphs.
- 6.1 Full Iterations: PageRank runtimes are similar on the small Wikipedia dataset, while Spark and Giraph could not run the large datasets because their messages exceeded node heap capacity.Stratosphere’s broadcasting strategy also degraded on Webbase because hash-table construction used a single thread per machine.
- 6.2 Incremental Iterations: 5.3 times faster: Stratosphere’s incremental Connected Components execution on Twitter compared with bulk iterations.The remaining ten iterations change less than 5% of the partial solution after most vertices settle within the first four iterations.
- 6.2 Incremental Iterations: 75 times faster: incremental algorithms complete Webbase Connected Components in 37 minutes versus an extrapolated roughly 47 hours for bulk iterations.The graph requires 744 iterations to converge, and the incremental algorithms are already three times as fast within the first 20 iterations.
- 6.2 Incremental Iterations: Incremental Stratosphere and Giraph algorithms converge toward very low iteration times after four iterations by avoiding already converged solution elements.Giraph reaches the lowest iteration times after five iterations, while simulated incremental Spark remains slower because it copies unchanged records.
- 6.2 Incremental Iterations: Microstep Connected Components has a much lower runtime slope than batch incremental execution as candidate component IDs increase.Its cheaper update function permits larger working sets containing more redundant candidate IDs within equal time.
- Evaluation conclusion: Incremental iterations touch only potentially modified solution elements, while Stratosphere can also outperform specialized systems on bulk iterative algorithms.The evaluation attributes the incremental advantage to exploiting sparse computational dependencies rather than fully recomputing each iteration.
7. RELATED WORK
The paper positions incremental iterations within broader efforts to support iterative analytics in dataflow systems. It contrasts this approach with recursive query techniques and specialized systems such as Pregel and GraphLab.
- Recursive query evaluation: Recursive query research has focused on top-down versus bottom-up evaluation and optimizations such as predicate pushdown.
- Recursive query evaluation: Incremental iteration techniques resemble semi-naïve evaluation, while recursive relational queries may add tuples without a synchronization barrier.
- Parallel data analysis systems: HaLoop and Twister support iterative MapReduce queries, whereas the paper targets more general dataflows and subsumes their special-case optimizations.
- Parallel data analysis systems: Pregel exploits sparse computational dependencies through mutable vertex state and selective propagation, capabilities also supported by the proposed incremental iterations.
- Parallel data analysis systems: GraphLab models computational dependencies as a graph and uses distributed shared memory with configurable consistency levels and update schedulers.
- Parallel data analysis systems: Ciel provides fine-grained task dependencies and runtime scheduling for iterations but lacks a direct iteration abstraction and shared state across iterations.
8. CONCLUSIONS AND OUTLOOK
The paper presents incremental iterations as a general dataflow abstraction for exploiting sparse computational dependencies. Its prototype competes with specialized systems while retaining a general dataflow model, and future work targets compiler transformations and fault tolerance.
- Conclusions: Incremental iterations let dataflow systems touch only the state that must change, exploiting sparse computational dependencies for large speedups.
- Conclusions: Incremental iterations subsume specialized models such as Pregel in expressibility and efficiency, including its naturally expressible algorithms without a performance hit.
- Conclusions: Incremental iterations also permit asynchronous microstep execution under well-defined conditions.
- Evaluation: A Stratosphere prototype competed with specialized systems on algorithms suited to those systems while retaining a general dataflow abstraction.
- Outlook: Future work will investigate automatic compiler transformations to incremental algorithms and fault-tolerance techniques that learn across repeated dataflow executions.