Distributed differential datalog (DDD) -- where to find?

[shaunc]

The main GitHub readme states that you are working on a distributed version of datalog. Can you post links to plans/discussions/projects/ongoing work?

At the moment I am particularly interested in distributed consensus. Have you chosen a solution? Are there discussions on requirements, etc? Any interface, or even working code? Are you building your own distributed consensus mechanisms or adopting a third-party solution?

Thanks!

[mihaibudiu]

You can have distributed systems that do not care about consensus. Consensus is essentially a tool for improving a system's reliability (so it can continue to operate when some parts fail), and this is currently not one of the goals we have for DDlog.

DDlog as a distributed system addresses two primary use cases:

• sharding of the data for higher throughput (we currently only shard between multiple cores, and not between multiple machines)
• distributed processing where different parts of the computation are hosted on different machines. This can be either to improve throughput or, more commonly, because the computation naturally runs in a system on multiple machines (e.g., a centralized control plane and the entities that the plane is controlling).

That being said, our current implementation of distributed processing uses zookeeper as a reliable replicated state machine that describes the shape of the distributed computation. So the consensus is hidden in there. The distributed system aspects have been neglected lately, but we hope that development will pick up some speed soon.

[shaunc]

You can have distributed systems that do not care about consensus.

While that may be true strictly speaking, if you really want to go down that path then, practically, you won't be able to scale to very many nodes as any slow communications, etc between parts must be constituted as a failure (timeout reached, and so ... we're dead? Or we just wait?). As @ryzhyk mentions, in fact you do have some notion of eventual consistency (which is a consensus mechanism -- usually relying on being able to undo local state to make operations commute).

Zookeeper ... ok. I've been working on distributed consensus, so was curious. We aren't there yet, but probably in about 6 months we'll want to adopt/adapt a query system for a very distributed use case. In other respects datalog looks excellent.

Unfortunately we are all really busy at the moment, but if you are open to additions/extensions, I'd like to encourage you to document how you do deal with this aspect (including thoughts and wishes)... :) Thank you for this excellent project!

[ryzhyk]

Existing incomplete implementation is here: https://github.com/vmware/differential-datalog/tree/master/rust/template/distributed_datalog

We don't have a great write-up, but here are two documents that talk about enforcing consistency in the simple case where there are no failures and an extension that deals with failures and reconfigurations.

Intuitively, we partition the dataflow graph into multiple components and run each component in a separate node, with their respective inputs and outputs connected with message channels. In the failure-free case eventual consistency only requires that channels are reliable. The ordering of messages across channels (and, under some additional constraints, even within a single channel) does not affect eventual consistency. Error handling relies on the fact that one can always recover the state of a DDlog program by feeding the latest snapshot of input tables to it (i.e., we don't need to replay the entire history). In the presence of a reliable failure detector, we can easily recover and reconfigure the distributed computation graph by caching input and output snapshots of each component and replaying the cached state during recovery.