16 ms·

Differential Datalog

231 points by maximilianroos 6y ago

userbinator 6y ago
I'm curious what VMware uses this for.
- dataflow 6y ago
  Maybe for hot migration?
  - rrdharan 6y ago
    Pretty sure not. Posted in reply to the sibling. This is a VMware research project but looks like the target use case is for OVN: https://blogs.vmware.com/opensource/2018/07/26/open-source-ovn-gains-momentum/ https://blogs.vmware.com/opensource/2018/07/26/open-source-o... https://blogs.vmware.com/research/2020/12/07/whats-new-differential-datalog/ https://blogs.vmware.com/research/2020/12/07/whats-new-diffe... https://twitter.com/Ben_Pfaff/status/1047905803250724865 https://twitter.com/Ben_Pfaff/status/1047905803250724865
    - dataflow 6y ago
      Oh interesting, thanks!
  - ben_pfaff 6y ago
    Speaking with my VMware hat on, I don't know of use cases there.
- rrdharan 6y ago
  https://twitter.com/Ben_Pfaff/status/1047905803250724865 https://twitter.com/Ben_Pfaff/status/1047905803250724865
  - ben_pfaff 6y ago
    Yes, and I'm really impressed with what we've been able to do with it in OVN lately. The patches aren't posted yet (probably Monday) but (with Leonid Ryzhyk's help) I managed to take one benchmark from about 110 seconds in the C version of OVN to about 35 seconds with DDlog. We have other internal-to-VMware use cases for DDlog. The OVN use case is the one that's easiest to evangelize since it's all open source.
- lstamour 6y ago
  Section 4 of [1] lists applications, including OVN, but it appears to be used primarily for experimental or research projects at the moment, but that should change given enough time… maybe? 1: https://github.com/vmware/differential-datalog/blob/master/doc/datalog2.0-workshop/paper.pdf https://github.com/vmware/differential-datalog/blob/master/d...
- namibj 6y ago
  I'm told it's primarily used for "networking stuff and big data processing", but "log processing" and "network switches" were also mentioned as (I assume active) use-cases.
- jacques_chester 6y ago
  I don't how much I can say since I work for VMware, but it's finding new uses all the time and I've personally brought it up with other teams. I'd known of it a while before seeing a presentation on how one service team used it. They had a stream processing problem where they were beginning to lag the input by up to an hour. With differential datalog the lag dropped to sub-second. It's seriously cool technology.
ampdepolymerase 6y ago
Building it from source looks tricky but the concepts are quite interesting.
- ben_pfaff 6y ago
  If you're talking about building the DDlog-to-Rust compiler, then it's not that hard. Really it's just a matter of installing Haskell then typing "stack build". But each release also comes with binaries for GNU/Linux, OS X, and Windows, e.g. for 0.38.0: https://github.com/vmware/differential-datalog/releases/tag/v0.38.0 https://github.com/vmware/differential-datalog/releases/tag/...
sriku 6y ago
It's great to see differential-dataflow and timely-dataflow (both by Frank McSherry) come to life recently with this and materialize.com
jitl 6y ago
Very interesting! I started playing with Rust, timely-dataflow and differential-dataflow last weekend, but it was a lot to learn all at once. This looks like it's solved or suggested a path to productionizing differential-dataflow without needing a separate rust service and lots of operation tooling. It would be cool to use something like this for Notion's user-defined databases and queries.
- namibj 6y ago
  You'll be happy to hear that logic/rule updates at runtime recently transitioned from the "todo... at some time" to the "todo... working on it" state. Do these databases ever grow beyond what you can afford to keep in RAM/swap? I'm working towards high-throughput out-of-core support in differential-dataflow, but can't get much actual coding done in my off time. Understanding/concepts/discussions are not affected, so feel free to contact me.
  - lukeswissman 6y ago
    > You'll be happy to hear that logic/rule updates at runtime recently transitioned from the "todo... at some time" to the "todo... working on it" state. What exactly do you mean with "logic/rule updates" ...in dd I can change/modify the actual dataflow?
  - jitl 6y ago
    I would love to have the option to suspend computation for unwanted outputs somehow (to disk) so I can scale way, way down with only partial data. My solution for “fits in RAM” is just “shard it”... but really I haven’t gotten far enough in my experiments to need to yet.
ultimoo 6y ago
I wonder how long before someone makes a SaaS.
- namibj 6y ago
  That exists[0] already, but with Postgres-compatible SQL. But the idea of SaaS-ing the datalog variant is interesting. [0]: https://materialize.com/ https://materialize.com/
polskibus 6y ago
Is this sth like linq in c#? Declarative programming over arbitrary structures? From skimming the examples i don't really see the advertised incremental aspect, could someone explain it a bit more?
- namibj 6y ago
  It's partially inspired by Linq, so the similarity you see is expected. It's not really arbitrary structures so much, though you're mostly free in what record type you use in a relation (structs and tagged enums are typical, though). The incremental part is that you can feed it changes to the input (additions/retractions of facts) and get changes to the outputs back with low latency (you can alternatively just use it to keep an index up-to-date, where you can quickly look up based on a key (like a materialized view in SQL)). This [0] section in the readme of the underlying incremental dataflow framework may help get the concept across, but feel free to follow up if you're still not seeing the incrementality. [0]: https://github.com/TimelyDataflow/differential-dataflow#an-example-counting-degrees-in-a-graph https://github.com/TimelyDataflow/differential-dataflow#an-e...
pjungwir 6y ago
So could you use this to implement always-up-to-date materialized views in Postgres? It says it uses relational data for inputs and outputs. It says it operates in-memory but also that it starts up from a set of known facts (which sounds like it could just read the current matview at startup). This would be a really cool extension for someone to build!
- namibj 6y ago
  Yes. Almost exactly what you're describing exists [0] already. [0]: https://materialize.com/ https://materialize.com/
  - tda 6y ago
    What a horrible landing page. Is it a stand alone product? Does it integrate with my SQL database? Is it a server side application or a client side thing? What is the pricing model? So many questions, zero answers Am in the process of exploring kafka to do something similar, and I think it will work but requires quite a complex setup (compared to an incrementally updated materialized view)
    - namibj 6y ago
      It's typically integrated with Kafka sources (and often also Kafka sinks), but you can just use any normal PostgreSQL client driver and normal SQL. It does integrate with your postgres database, but logical replication target mode is still a TODO. Don't worry though, this only means the change data stream has to go through a Kafka broker. There should be a guide on this (if not, plop in the community Slack and ask). The license allows for free single-node deployments; the SaaS variant is currently in Beta, so you'll have to ask. On-premise clusters for production usage are "contact sales", but AFAIK due to the low sales volume (turns out, vertical scaling is easy and often enough), so don't let that scare you off.
  - aidos 6y ago
    Looks like it’s Postgres protocol compatible rather than running as a Postgres extension? I’ve been keeping an eye on work that’s been done to support this internally in Postgres. Looks like it’s still moving along. I guess it’s a pretty tricky puzzle (especially once you add aggregates). Depending on the performance implications, it would sit in a pretty sweet spot for some usecases. For example, at the moment I have a form of materialised view that’s simple too slow to build from scratch. My compromise is to run periodically, figure out which subset of the table needs refreshing and update just those rows. https://wiki.postgresql.org/wiki/Incremental_View_Maintenance https://wiki.postgresql.org/wiki/Incremental_View_Maintenanc...
fulafel 6y ago
Aside from their custom syntax in DDlog, how much semantic overlap is there with the query language of Datomic/Crux/Datalevin/Datascript flavour? Apart from the differential features. This one seems to be big on static type definitions at least. edit: I guess this explains some of the static nature: "A DDlog program is compiled into a Rust library"
- namibj 6y ago
  You don't really use dynamic datalog queries with DDlog. Instead you write rules that handle your queries in a streaming fashion ("prepare" statement at compile time, stream tuples of parameters at runtime and listen for outputs), if you can't afford to keep a materialized view up-to-date that turns your queries into simple KV-lookup operations. But, do not worry: Support for run-time rule updates is in the works and would allow for arbitrary dynamic datalog queries.
kybernetikos 6y ago
I always fancied a database that worked like a dynamic version of prolog, with facts that could be added over time, queries that can use inference etc. I couldn't really find anything that worked like that though, everything seemed to either have a fixed set of facts or didn't support inference. Looking for something like that is what first got me interested in differential dataflow. The fact that this is bottom up makes me think that you probably can't go crazy with the number of rules.
- namibj 6y ago
  This gives you dynamic facts, feed-forward rule application, and soon even dynamic rules. It doesn't actually care much about the number of rules, and more about how much memory it costs to materialize them. There are delta-join techniques to do at least most of that in linear memory (w.r.t. input size) though, and DDlog has at least experimental support for them.
- aminechikhaoui 6y ago
  There is already https://developer.logicblox.com/ https://developer.logicblox.com/ but it's proprietary owned by Infor nowadays.
- flyingsilverfin 6y ago
  The company I work for, Grakn Labs (grakn.ai), builds a database that does datalog + negation type rules! You can add/remove data as you go, and also add/remove rules in the schema over time. The terminology the post here uses is different from ours, but roughly we do "Backward-chaining", which starts from the query to the set of facts that are inserted, which the article calls "top-down".
  - namibj 6y ago
    Do you handle incremental changes to the input data? Because that's the major selling point of DDlog: low-latency responses to changes in inputs.
    - 6y ago
0x70dd 6y ago
Rego, the language used in Open Policy Agent, is based on and extends Datalog. It's gaining a lot of traction in the past couple of years for evaluating authorization policies.
- ben_pfaff 6y ago
  There's an indirect relationship between Rego and DDlog, at least people-wise. OPA comes from Styra, which was founded by Tim Hinrichs and Teemu Koponen. Teemu designed nlog, which is also a Datalog variant, for use in NVP, which was the network virtualization product at Nicira and was later renamed NSX after VMware acquired Nicira. Tim also worked with Teemu (and me) on NSX at VMware. And Teemu was one of the architects of OVN (the biggest open source application for DDlog), with Tim also having some influence. And Teemu also knows Leonid and Mihai (the principal authors of DDlog). Some of the episodes of my OVS Orbit podcast may be relevant: * Episode 5: nlog, with Teemu Koponen from Styra and Yusheng Wang from VMware (https://ovsorbit.org/#e5 https://ovsorbit.org/#e5) * Episode 44: Cocoon-2, with Leonid Ryzhyk from VMware Research (https://ovsorbit.org/#e44 https://ovsorbit.org/#e44) * Episode 58: Toward Leaner, Faster ovn-northd, with Leonid Ryzhyk from VMware Research Group (https://ovsorbit.org/#e58 https://ovsorbit.org/#e58)
- simplify 6y ago
  Ozo[1] is another authorization language, but based on Prolog. It'd be interesting to compare the capabilities between the two. [1] https://www.osohq.com https://www.osohq.com
domoritz 6y ago
A related project is declarative dataflow, which is an interactive and reactive dataflow engine built on top of differential dataflow. https://github.com/comnik/declarative-dataflow https://github.com/comnik/declarative-dataflow
lykahb 6y ago
I wonder how the DDLog compares to Souffle. I think that the biggest difference is that Souffle is batch-oriented. It is less clear how different are the expressiveness, type systems or the recommended patterns. The syntax of DDLog looks seems to be closer to Souffle than to Datomic with EDN.
- ben_pfaff 6y ago
  I don't know anything about Souffle so I can't directly answer the question. But there is some related material. The DDlog repo includes a Souffle-to-DDlog converter: https://github.com/vmware/differential-datalog/blob/v0.38.0/tools/souffle_converter.py https://github.com/vmware/differential-datalog/blob/v0.38.0/... The Souffle converter is somewhat incomplete: https://github.com/vmware/differential-datalog/issues/174 https://github.com/vmware/differential-datalog/issues/174

userbinator 6y ago

I'm curious what VMware uses this for.

dataflow 6y ago
Maybe for hot migration?
- rrdharan 6y ago
  Pretty sure not. Posted in reply to the sibling. This is a VMware research project but looks like the target use case is for OVN: https://blogs.vmware.com/opensource/2018/07/26/open-source-ovn-gains-momentum/ https://blogs.vmware.com/opensource/2018/07/26/open-source-o... https://blogs.vmware.com/research/2020/12/07/whats-new-differential-datalog/ https://blogs.vmware.com/research/2020/12/07/whats-new-diffe... https://twitter.com/Ben_Pfaff/status/1047905803250724865 https://twitter.com/Ben_Pfaff/status/1047905803250724865
  - dataflow 6y ago
    Oh interesting, thanks!
- ben_pfaff 6y ago
  Speaking with my VMware hat on, I don't know of use cases there.
rrdharan 6y ago
https://twitter.com/Ben_Pfaff/status/1047905803250724865 https://twitter.com/Ben_Pfaff/status/1047905803250724865
- ben_pfaff 6y ago
  Yes, and I'm really impressed with what we've been able to do with it in OVN lately. The patches aren't posted yet (probably Monday) but (with Leonid Ryzhyk's help) I managed to take one benchmark from about 110 seconds in the C version of OVN to about 35 seconds with DDlog. We have other internal-to-VMware use cases for DDlog. The OVN use case is the one that's easiest to evangelize since it's all open source.
lstamour 6y ago
Section 4 of [1] lists applications, including OVN, but it appears to be used primarily for experimental or research projects at the moment, but that should change given enough time… maybe? 1: https://github.com/vmware/differential-datalog/blob/master/doc/datalog2.0-workshop/paper.pdf https://github.com/vmware/differential-datalog/blob/master/d...
namibj 6y ago
I'm told it's primarily used for "networking stuff and big data processing", but "log processing" and "network switches" were also mentioned as (I assume active) use-cases.
jacques_chester 6y ago
I don't how much I can say since I work for VMware, but it's finding new uses all the time and I've personally brought it up with other teams. I'd known of it a while before seeing a presentation on how one service team used it. They had a stream processing problem where they were beginning to lag the input by up to an hour. With differential datalog the lag dropped to sub-second. It's seriously cool technology.

ampdepolymerase 6y ago

Building it from source looks tricky but the concepts are quite interesting.

ben_pfaff 6y ago
If you're talking about building the DDlog-to-Rust compiler, then it's not that hard. Really it's just a matter of installing Haskell then typing "stack build". But each release also comes with binaries for GNU/Linux, OS X, and Windows, e.g. for 0.38.0: https://github.com/vmware/differential-datalog/releases/tag/v0.38.0 https://github.com/vmware/differential-datalog/releases/tag/...

sriku 6y ago

It's great to see differential-dataflow and timely-dataflow (both by Frank McSherry) come to life recently with this and materialize.com

jitl 6y ago

Very interesting! I started playing with Rust, timely-dataflow and differential-dataflow last weekend, but it was a lot to learn all at once. This looks like it's solved or suggested a path to productionizing differential-dataflow without needing a separate rust service and lots of operation tooling. It would be cool to use something like this for Notion's user-defined databases and queries.

namibj 6y ago
You'll be happy to hear that logic/rule updates at runtime recently transitioned from the "todo... at some time" to the "todo... working on it" state. Do these databases ever grow beyond what you can afford to keep in RAM/swap? I'm working towards high-throughput out-of-core support in differential-dataflow, but can't get much actual coding done in my off time. Understanding/concepts/discussions are not affected, so feel free to contact me.
- lukeswissman 6y ago
  > You'll be happy to hear that logic/rule updates at runtime recently transitioned from the "todo... at some time" to the "todo... working on it" state. What exactly do you mean with "logic/rule updates" ...in dd I can change/modify the actual dataflow?
- jitl 6y ago
  I would love to have the option to suspend computation for unwanted outputs somehow (to disk) so I can scale way, way down with only partial data. My solution for “fits in RAM” is just “shard it”... but really I haven’t gotten far enough in my experiments to need to yet.

ultimoo 6y ago

I wonder how long before someone makes a SaaS.

namibj 6y ago
That exists[0] already, but with Postgres-compatible SQL. But the idea of SaaS-ing the datalog variant is interesting. [0]: https://materialize.com/ https://materialize.com/

polskibus 6y ago

Is this sth like linq in c#? Declarative programming over arbitrary structures? From skimming the examples i don't really see the advertised incremental aspect, could someone explain it a bit more?

namibj 6y ago
It's partially inspired by Linq, so the similarity you see is expected. It's not really arbitrary structures so much, though you're mostly free in what record type you use in a relation (structs and tagged enums are typical, though). The incremental part is that you can feed it changes to the input (additions/retractions of facts) and get changes to the outputs back with low latency (you can alternatively just use it to keep an index up-to-date, where you can quickly look up based on a key (like a materialized view in SQL)). This [0] section in the readme of the underlying incremental dataflow framework may help get the concept across, but feel free to follow up if you're still not seeing the incrementality. [0]: https://github.com/TimelyDataflow/differential-dataflow#an-example-counting-degrees-in-a-graph https://github.com/TimelyDataflow/differential-dataflow#an-e...

pjungwir 6y ago

So could you use this to implement always-up-to-date materialized views in Postgres? It says it uses relational data for inputs and outputs. It says it operates in-memory but also that it starts up from a set of known facts (which sounds like it could just read the current matview at startup). This would be a really cool extension for someone to build!

namibj 6y ago
Yes. Almost exactly what you're describing exists [0] already. [0]: https://materialize.com/ https://materialize.com/
- tda 6y ago
  What a horrible landing page. Is it a stand alone product? Does it integrate with my SQL database? Is it a server side application or a client side thing? What is the pricing model? So many questions, zero answers Am in the process of exploring kafka to do something similar, and I think it will work but requires quite a complex setup (compared to an incrementally updated materialized view)
  - namibj 6y ago
    It's typically integrated with Kafka sources (and often also Kafka sinks), but you can just use any normal PostgreSQL client driver and normal SQL. It does integrate with your postgres database, but logical replication target mode is still a TODO. Don't worry though, this only means the change data stream has to go through a Kafka broker. There should be a guide on this (if not, plop in the community Slack and ask). The license allows for free single-node deployments; the SaaS variant is currently in Beta, so you'll have to ask. On-premise clusters for production usage are "contact sales", but AFAIK due to the low sales volume (turns out, vertical scaling is easy and often enough), so don't let that scare you off.
- aidos 6y ago
  Looks like it’s Postgres protocol compatible rather than running as a Postgres extension? I’ve been keeping an eye on work that’s been done to support this internally in Postgres. Looks like it’s still moving along. I guess it’s a pretty tricky puzzle (especially once you add aggregates). Depending on the performance implications, it would sit in a pretty sweet spot for some usecases. For example, at the moment I have a form of materialised view that’s simple too slow to build from scratch. My compromise is to run periodically, figure out which subset of the table needs refreshing and update just those rows. https://wiki.postgresql.org/wiki/Incremental_View_Maintenance https://wiki.postgresql.org/wiki/Incremental_View_Maintenanc...

fulafel 6y ago

Aside from their custom syntax in DDlog, how much semantic overlap is there with the query language of Datomic/Crux/Datalevin/Datascript flavour? Apart from the differential features. This one seems to be big on static type definitions at least. edit: I guess this explains some of the static nature: "A DDlog program is compiled into a Rust library"

namibj 6y ago
You don't really use dynamic datalog queries with DDlog. Instead you write rules that handle your queries in a streaming fashion ("prepare" statement at compile time, stream tuples of parameters at runtime and listen for outputs), if you can't afford to keep a materialized view up-to-date that turns your queries into simple KV-lookup operations. But, do not worry: Support for run-time rule updates is in the works and would allow for arbitrary dynamic datalog queries.

kybernetikos 6y ago

I always fancied a database that worked like a dynamic version of prolog, with facts that could be added over time, queries that can use inference etc. I couldn't really find anything that worked like that though, everything seemed to either have a fixed set of facts or didn't support inference. Looking for something like that is what first got me interested in differential dataflow. The fact that this is bottom up makes me think that you probably can't go crazy with the number of rules.

namibj 6y ago
This gives you dynamic facts, feed-forward rule application, and soon even dynamic rules. It doesn't actually care much about the number of rules, and more about how much memory it costs to materialize them. There are delta-join techniques to do at least most of that in linear memory (w.r.t. input size) though, and DDlog has at least experimental support for them.
aminechikhaoui 6y ago
There is already https://developer.logicblox.com/ https://developer.logicblox.com/ but it's proprietary owned by Infor nowadays.
flyingsilverfin 6y ago
The company I work for, Grakn Labs (grakn.ai), builds a database that does datalog + negation type rules! You can add/remove data as you go, and also add/remove rules in the schema over time. The terminology the post here uses is different from ours, but roughly we do "Backward-chaining", which starts from the query to the set of facts that are inserted, which the article calls "top-down".
- namibj 6y ago
  Do you handle incremental changes to the input data? Because that's the major selling point of DDlog: low-latency responses to changes in inputs.
  - 6y ago

0x70dd 6y ago

Rego, the language used in Open Policy Agent, is based on and extends Datalog. It's gaining a lot of traction in the past couple of years for evaluating authorization policies.

ben_pfaff 6y ago
There's an indirect relationship between Rego and DDlog, at least people-wise. OPA comes from Styra, which was founded by Tim Hinrichs and Teemu Koponen. Teemu designed nlog, which is also a Datalog variant, for use in NVP, which was the network virtualization product at Nicira and was later renamed NSX after VMware acquired Nicira. Tim also worked with Teemu (and me) on NSX at VMware. And Teemu was one of the architects of OVN (the biggest open source application for DDlog), with Tim also having some influence. And Teemu also knows Leonid and Mihai (the principal authors of DDlog). Some of the episodes of my OVS Orbit podcast may be relevant: * Episode 5: nlog, with Teemu Koponen from Styra and Yusheng Wang from VMware (https://ovsorbit.org/#e5 https://ovsorbit.org/#e5) * Episode 44: Cocoon-2, with Leonid Ryzhyk from VMware Research (https://ovsorbit.org/#e44 https://ovsorbit.org/#e44) * Episode 58: Toward Leaner, Faster ovn-northd, with Leonid Ryzhyk from VMware Research Group (https://ovsorbit.org/#e58 https://ovsorbit.org/#e58)
simplify 6y ago
Ozo[1] is another authorization language, but based on Prolog. It'd be interesting to compare the capabilities between the two. [1] https://www.osohq.com https://www.osohq.com

domoritz 6y ago

A related project is declarative dataflow, which is an interactive and reactive dataflow engine built on top of differential dataflow. https://github.com/comnik/declarative-dataflow https://github.com/comnik/declarative-dataflow

lykahb 6y ago

I wonder how the DDLog compares to Souffle. I think that the biggest difference is that Souffle is batch-oriented. It is less clear how different are the expressiveness, type systems or the recommended patterns. The syntax of DDLog looks seems to be closer to Souffle than to Datomic with EDN.

ben_pfaff 6y ago
I don't know anything about Souffle so I can't directly answer the question. But there is some related material. The DDlog repo includes a Souffle-to-DDlog converter: https://github.com/vmware/differential-datalog/blob/v0.38.0/tools/souffle_converter.py https://github.com/vmware/differential-datalog/blob/v0.38.0/... The Souffle converter is somewhat incomplete: https://github.com/vmware/differential-datalog/issues/174 https://github.com/vmware/differential-datalog/issues/174