3 ms·

Incremental computation is a fascinating area of research, I've followed Matthew Hammer's work on Adapton[1] for a while, as well as Daco Harkes work on IceDust

by thom 8y ago

Incremental computation is a fascinating area of research, I've followed Matthew Hammer's work on Adapton[1] for a while, as well as Daco Harkes work on IceDust[2]. The issues are obviously quite deep (i.e. how do can you change a single value and recalculate quicksort without the effects of the change fanning out massively?) whether you're targeting existing languages and runtimes or building from scratch. I would very much like to see this as an area of active development both in programming languages and distributed computing platforms. Current streaming platforms are great and it's getting easier and easier to create declarative data flow pipelines, doing real-time processing, splitting things into windows etc. But on top of that I imagine incorporating incremental computation, allowing you to keep a durable history of the event stream (or at least manageable parts of it) in a way that automagically allows incremental recalculation of upstream data when an underlying fact is retracted or updated. [1] http://adapton.org/ http://adapton.org/ [2] https://dcharkes.github.io/ https://dcharkes.github.io/

thom 8y ago
Of course if that already exists then I'd love to hear about it! There seem to be all sorts of hybrid stream/batch systems but none with quite this focus. Effectively I want stuff that streams into a time series database in realtime, with the opportunity to edit or delete events later. On top of that there would be a processing pipeline with familiar streaming paradigms (transforming data, windowing data arbitrarily, aggregating on top of that) with the additional magic that the necessary events/windows/calculations re-fire if some underlying data changes. All in a magically efficient and transparent way.
- frankmcsherry 8y ago
  Shameless plug for something that does all of these things (perhaps not exactly as you want, but ..) https://github.com/frankmcsherry/differential-dataflow https://github.com/frankmcsherry/differential-dataflow
  - thom 8y ago
    Wonderful! I feel bad that I didn't follow the work after hearing about Naiad originally. Where might I go to read more about the fault tolerance story - I note that's an ongoing area of research in the README. Also the link to the Kafka adapter is dead, is that work ongoing or does the story end at the capture/replay API? (Happy to bombard you with email if that's any more manageable for you!) Reading the 'when not to use Timely Dataflow' section on sorting, are there any ideas from Nominal Adapton that are relevant in this distributed setting, when we're talking about small updates or inserts?
    - frankmcsherry 8y ago
      Durability is a student's research project at the moment. It's up and running for "Spark" style computations but the work has broader ambitions. In essence, all of the internal state in DD are easily (automatically) serialized LSM slabs, and it is cake to write them out and read them back (and almost cake to make sense of them). https://eurosys2017.github.io/assets/data/posters/poster21-Lattuada.pdf Which Kafka link is dead? The work has quiesced because any next step seems to be involve assuming something about timestamps in the input. At the same time, it seems to take about 10 lines of code to write a Kafka source or sink, minus any careful worrying about acks for durability. The DD and Adapton approaches may be a bit tricky to hybridize. Much incremental compute works by moving through a sequence of valid configurations, and DD's main departure is generalizing this to partial orders. So, maybe you could borrow ideas, but it would probably be original research to do so. Email is great, as it is def no longer about skiplang.

by thom 8y ago

thom 8y ago

Of course if that already exists then I'd love to hear about it! There seem to be all sorts of hybrid stream/batch systems but none with quite this focus. Effectively I want stuff that streams into a time series database in realtime, with the opportunity to edit or delete events later. On top of that there would be a processing pipeline with familiar streaming paradigms (transforming data, windowing data arbitrarily, aggregating on top of that) with the additional magic that the necessary events/windows/calculations re-fire if some underlying data changes. All in a magically efficient and transparent way.

frankmcsherry 8y ago
Shameless plug for something that does all of these things (perhaps not exactly as you want, but ..) https://github.com/frankmcsherry/differential-dataflow https://github.com/frankmcsherry/differential-dataflow
- thom 8y ago
  Wonderful! I feel bad that I didn't follow the work after hearing about Naiad originally. Where might I go to read more about the fault tolerance story - I note that's an ongoing area of research in the README. Also the link to the Kafka adapter is dead, is that work ongoing or does the story end at the capture/replay API? (Happy to bombard you with email if that's any more manageable for you!) Reading the 'when not to use Timely Dataflow' section on sorting, are there any ideas from Nominal Adapton that are relevant in this distributed setting, when we're talking about small updates or inserts?
  - frankmcsherry 8y ago
    Durability is a student's research project at the moment. It's up and running for "Spark" style computations but the work has broader ambitions. In essence, all of the internal state in DD are easily (automatically) serialized LSM slabs, and it is cake to write them out and read them back (and almost cake to make sense of them). https://eurosys2017.github.io/assets/data/posters/poster21-Lattuada.pdf Which Kafka link is dead? The work has quiesced because any next step seems to be involve assuming something about timestamps in the input. At the same time, it seems to take about 10 lines of code to write a Kafka source or sink, minus any careful worrying about acks for durability. The DD and Adapton approaches may be a bit tricky to hybridize. Much incremental compute works by moving through a sequence of valid configurations, and DD's main departure is generalizing this to partial orders. So, maybe you could borrow ideas, but it would probably be original research to do so. Email is great, as it is def no longer about skiplang.