4 ms·

An introduction to timely dataflow, part 2

70 points by mrry 11y ago

erickt 11y ago
I love these articles, thanks! I can't wait for rust to get more involved in this space. How do you plan on doing error handling in timely? Do you expect it to be more along the lines of MPI, where you restart from the last snapshot, or MapReduce/Spark, where lost work is transparently recomputed?
- frankmcsherry 11y ago
  It's a good question. I'm punting for the moment because it isn't clear that there is one true solution that makes everyone happy. So, let's say MPI then. :) I think the more optimistic version is probably that the signals Timely Dataflow (the model) gives should make tasteful fault-tolerance logic easier to write. Michael Isard did some work here just before leaving MSR. Realistically, errors haven't been a big problem yet (thanks Rust!) and it's a research prototype for understanding efficient data-parallel compute, so not too bothered yet. The MR/Spark approach comes with lots of hidden costs in the programming model; I'm not clear on when these costs make sense. Using lots more resources so that you survive being killed because you were using too many resources seems like a not-best solution. Some of the layers on top have better fault-tolerance properties. For example, differential dataflow operators are functional and have append-only logs as their internal state; I could see that stack ending up with more transparent fault-tolerance properties, though not yet.
amelius 11y ago
What advantage does a dataflow language have over a functional language? And how is laziness handled (i.e., does it happen that in a dataflow language, tokens are being sent unnecessarily)? Is it easy to perform memoization in a dataflow language (to avoid performing the same computation twice)?
- frankmcsherry 11y ago
  I don't want to speak for all of dataflow-dom, but the main differences that I see (and exploit) are that data-parallel dataflow languages isolate control flow into small independent regions, making the larger computation data-driven. This does mean things are eager rather than lazy, but it also makes things much easier to parallelize (because of the independence) and much easier to incrementalize.[0] [0]: https://github.com/frankmcsherry/differential-dataflow https://github.com/frankmcsherry/differential-dataflow
- chipsy 11y ago
  A dataflow language overlaps with functional programming in many respects but has one key difference - components are defined to allow some form of many-in, many-out, rather than a mathematical function's many-in, one-out. This change in syntax - which comes with design concerns around how many-out manifests(e.g. static # of outs vs. automatic copy) - has large effects on programming style. It limits how cleanly one can compose dataflow modules, and compounds the possibilities of type-mismatch, but it also affords a richer definition of module responsibilities and relationships. Memoization is one of several possible optimizations. Lazy eval may appear in a fashion by blocking a module from processing an input on one channel until its other input channels also have data, but in e.g. the J. Paul Morrison definition, there's a finite dataset and data does not get dropped on the floor, nor does it get stored in components. Eager is the default. If component implementations have broad control over when they process I/O, they can do some fairly substantial optimizations internally, though. Dataflow works best as a mid-level system, controlled by and controlling other code in other styles. It can model the computing universe ground-up as a kind of electronics hardware in abstracted form(pure logic gates, no physical constraints), but this is a misuse of it. There are languages that can express control flow and arithmetic more succinctly. Moreover, the complexity of component relationship graphs in dataflow precludes using it for boilerplate of that type. It works best, instead, when the components are large enough to perform substantial functionality, but need some form of dynamic configuration. Analogizing again to electronics, modular synthesis is the canonical example of dataflow in action. A modular synthesizer contains a set of building blocks - the modules - each of which turn some number of input voltages into output voltages, sometimes with physical knobs and switches on the panel. Patch cables are used to connect the modules together, allowing for a great deal of flexibility over the final signal path. In software, by comparison, a modular system operates on chunks of digital samples instead of voltage over time. The principles are the same for the end-user, while the implementation may be completely different underneath. One should also note that analog synthesizers started incorporating digital CPUs as soon as it was affordable, for their most state-heavy functionality: tracking keypresses over time, and store and recall of patch data. This gives some idea of where dataflow techniques trail off and an imperative style can start to shine, hence why I call it a "mid-level" technique, not something that describes the whole system.
amirouche 11y ago
It seems like timely dataflow relates to Tinkerpop Gremlin graph traversal language. You build a pipeline a "steps" and those get executed over the input data one after the other. How timely dataflow can be compared to Gremin DSL?

70 points by mrry 11y ago

I love these articles, thanks! I can't wait for rust to get more involved in this space. How do you plan on doing error handling in timely? Do you expect it to be more along the lines of MPI, where you restart from the last snapshot, or MapReduce/Spark, where lost work is transparently recomputed?

frankmcsherry 11y ago
It's a good question. I'm punting for the moment because it isn't clear that there is one true solution that makes everyone happy. So, let's say MPI then. :) I think the more optimistic version is probably that the signals Timely Dataflow (the model) gives should make tasteful fault-tolerance logic easier to write. Michael Isard did some work here just before leaving MSR. Realistically, errors haven't been a big problem yet (thanks Rust!) and it's a research prototype for understanding efficient data-parallel compute, so not too bothered yet. The MR/Spark approach comes with lots of hidden costs in the programming model; I'm not clear on when these costs make sense. Using lots more resources so that you survive being killed because you were using too many resources seems like a not-best solution. Some of the layers on top have better fault-tolerance properties. For example, differential dataflow operators are functional and have append-only logs as their internal state; I could see that stack ending up with more transparent fault-tolerance properties, though not yet.

amelius 11y ago

What advantage does a dataflow language have over a functional language? And how is laziness handled (i.e., does it happen that in a dataflow language, tokens are being sent unnecessarily)? Is it easy to perform memoization in a dataflow language (to avoid performing the same computation twice)?

frankmcsherry 11y ago
I don't want to speak for all of dataflow-dom, but the main differences that I see (and exploit) are that data-parallel dataflow languages isolate control flow into small independent regions, making the larger computation data-driven. This does mean things are eager rather than lazy, but it also makes things much easier to parallelize (because of the independence) and much easier to incrementalize.[0] [0]: https://github.com/frankmcsherry/differential-dataflow https://github.com/frankmcsherry/differential-dataflow
chipsy 11y ago
A dataflow language overlaps with functional programming in many respects but has one key difference - components are defined to allow some form of many-in, many-out, rather than a mathematical function's many-in, one-out. This change in syntax - which comes with design concerns around how many-out manifests(e.g. static # of outs vs. automatic copy) - has large effects on programming style. It limits how cleanly one can compose dataflow modules, and compounds the possibilities of type-mismatch, but it also affords a richer definition of module responsibilities and relationships. Memoization is one of several possible optimizations. Lazy eval may appear in a fashion by blocking a module from processing an input on one channel until its other input channels also have data, but in e.g. the J. Paul Morrison definition, there's a finite dataset and data does not get dropped on the floor, nor does it get stored in components. Eager is the default. If component implementations have broad control over when they process I/O, they can do some fairly substantial optimizations internally, though. Dataflow works best as a mid-level system, controlled by and controlling other code in other styles. It can model the computing universe ground-up as a kind of electronics hardware in abstracted form(pure logic gates, no physical constraints), but this is a misuse of it. There are languages that can express control flow and arithmetic more succinctly. Moreover, the complexity of component relationship graphs in dataflow precludes using it for boilerplate of that type. It works best, instead, when the components are large enough to perform substantial functionality, but need some form of dynamic configuration. Analogizing again to electronics, modular synthesis is the canonical example of dataflow in action. A modular synthesizer contains a set of building blocks - the modules - each of which turn some number of input voltages into output voltages, sometimes with physical knobs and switches on the panel. Patch cables are used to connect the modules together, allowing for a great deal of flexibility over the final signal path. In software, by comparison, a modular system operates on chunks of digital samples instead of voltage over time. The principles are the same for the end-user, while the implementation may be completely different underneath. One should also note that analog synthesizers started incorporating digital CPUs as soon as it was affordable, for their most state-heavy functionality: tracking keypresses over time, and store and recall of patch data. This gives some idea of where dataflow techniques trail off and an imperative style can start to shine, hence why I call it a "mid-level" technique, not something that describes the whole system.

amirouche 11y ago

It seems like timely dataflow relates to Tinkerpop Gremlin graph traversal language. You build a pipeline a "steps" and those get executed over the input data one after the other. How timely dataflow can be compared to Gremin DSL?