6 ms·

Mergeable replicated data types – Part I

104 points by telotortium 7y ago

fyp 7y ago
The "characteristic relations" of a datatype looks really interesting. It's similar to abstract data type (ADT) except you only care about modeling the state but not the operations. And if you ignore operations, many datatypes reduce down to very simple mathematical objects. For example even though set and priority queues are very different in code, they both only need membership (R_mem) to fully specify because you can rebuild a priority queue knowing just the members. To specify a list/queue/stack, you only need to additionally know ordering (they denote this relationship as R_ob for "occurs before"). The advantage of converting a datatype (bijectively) to this relational domain is that you can essentially do "state-based" merging. You only need to define: how to convert to the relational domain, how to merge within that domain (which is still rich enough for you to specify relational invariants you need preserved), and how to convert back to the concrete datatype. Contrast this with operation-based syncing, where you would need a quadratic explosion of definitions for how any two operations should merge together. Here you don't even need to handle any particular operation individually (e.g., if it works for push_front, you will likely get push_back for free). Essentially it is saying the semantics of an operation is captured by the delta caused to the characteristic relations of the datatype.
cousin_it 7y ago
The paper is based on 3-way merge of relations (sets) but I'm not sure it's uniquely defined. Imagine we have a data structure consisting of two sets A and B, with the invariant that B is a subset of A. Initially A = {1}, B = {}. Imagine this data structure is replicated across two computers. On the first computer, we add 1 to B; on the second computer, we remove 1 from A. Then we try to merge these changes. It seems that the merge result could be either A = {1}, B = {1} or A = {}, B = {} and I don't see how to choose between them.
dunkelheit 7y ago
CRDTs (and I guess MRDTs are no different in this respect) are often touted as an enabling technology for collaborative local-first applications (see e.g. recent discussion: https://news.ycombinator.com/item?id=21581444 https://news.ycombinator.com/item?id=21581444) but I fail to see how they are useful beyond the simplest of cases: the emphasis is on automatic convergence, but it seems almost impossible to preserve non-trivial application-specific invariants without manual merging (I am thinking of such applications as collaborative source code editing or vector graphics editing). Am I missing something?
- mathetic 7y ago
  The point is often you don't need to. If you use Google docs, the chances are you will be editing it disjointly most of the time and occasionally you'll edit the same bit of the document. Then you don't really care if what comes out is a meaningful sentence, but that all parties involved (regardless in which order they see the operations) see the same version of the document so that they can fix it. That's what CRDTs buy you. Without them, you have to use either explicit synchronisation which is a bad idea if you want local-first software (doesn't work offline, needs to be done even when editing disjoint bits of the file, etc.) or something like CRDTs. Now there is a great paper by Victor Gomes, Martin Kleppmann, and Dominic Mulligan that proves (in a proof assistant!) that pretty much all other alternatives that do not use strong consistency is flawed in edge cases. As for triviality of the operations, I know for a fact that Martin Kleppmann has a paper in the works that show (and prove) how to do tree move efficiently as a CRDT. That means you can basically do arbitrary edits on JSON. Hopefully, that should clear up any confusion about for which applications it might be useful.
  - dunkelheit 7y ago
    Thanks for your comment! > The point is often you don't need to. If you use Google docs, the chances are you will be editing it disjointly most of the time and occasionally you'll edit the same bit of the document. Then you don't really care if what comes out is a meaningful sentence, but that all parties involved (regardless in which order they see the operations) see the same version of the document so that they can fix it. That's what CRDTs buy you. Ok, so the hope is that semantic conflicts are rare and if they do happen, users can easily see them and promptly correct them. I guess this works well if the invariants are local and synchronization is fairly frequent (i.e. on the scale of seconds, not weeks). > That means you can basically do arbitrary edits on JSON. Hopefully, that should clear up any confusion about for which applications it might be useful. Not quite. Of course you can model everything in JSON, but the question remains as to how much additional implicit structure is needed atop the explicit tree-like structure that JSON provides and how easily this implicit structure is disturbed by merges.
    - 7y ago
Jyaif 7y ago
I believe their counter only works when they have 2 replicas: 0 / \ +1 / \ +2 / \ 1 2 \ / \ / \ / 3 <= correct result With 3 replicas it breaks apart: 0 /|\ / | \ / | \ / | \ / | \ +1 / |+100 \ +2 / | \ 1 100 2 \ / \ / \ / \ / \ / \ / 101 102 \ / \ / \ / 203 <= incorrect result, 100 is accounted for twice. It is accounted for twice because the lowest common ancestor is '0'. My team solved that problem by creating virtual common ancestors. This is similar to what git does in some cases.
- cousin_it 7y ago
  Wait, that doesn't look right. Why does 100 have two children? It seems to me that 1 should get merged with 100 to end up with 101, then that should be merged with 2 to end up with 103.
  - Jyaif 7y ago
    This is a distributed system. You can have some replica that has 100, merge with an other replica and get 101. Then an other replica that also had the same 100 merge with an other replica and get 102. Then when 101 and 102 merge, the lowest common ancestor is still 0, so you get 203.
    - cousin_it 7y ago
      Ah I see, sorry, that makes sense.
- deleted 7y ago
  [deleted]
- contravariant 7y ago
  In this case 100 is the LCA isn't it? Then you'd end up with 100 + (101 - 100) + (102 - 100) = 103, which is correct.
marknadal 7y ago
I like the phrasing "Mergeable Data" over CRDTs (I've been on the CRDT bandwagon for years now, with https://github.com/amark/gun https://github.com/amark/gun ). Probably worth it as an industry of we shift language to "Mergeable".
- gavinray 7y ago
  Holy shit, the creator of GUN lurks HN? Huge fan. Super cool, I first used the library back in 2015-ish and I remember being blown away by how innovative and unique it was. I'm working on a serverless, distributed P2P compute network that's basically a PubSub event queue/job system using some hacks on top of Dat protocol right now for a side project. Do you think I might be able to use or leverage GUN instead?
  - marknadal 7y ago
    :D glad to know some HNers are fan! Yeah, absolutely. Tho DAT is one of the better ones. Do you need mutability? That is probably the biggest differentiator. Either way, you should come chat about it on http://chat.gun.eco/ http://chat.gun.eco/ super friendly active community discussing stuff like this all the time. :)

104 points by telotortium 7y ago

fyp 7y ago

The "characteristic relations" of a datatype looks really interesting. It's similar to abstract data type (ADT) except you only care about modeling the state but not the operations. And if you ignore operations, many datatypes reduce down to very simple mathematical objects. For example even though set and priority queues are very different in code, they both only need membership (R_mem) to fully specify because you can rebuild a priority queue knowing just the members. To specify a list/queue/stack, you only need to additionally know ordering (they denote this relationship as R_ob for "occurs before"). The advantage of converting a datatype (bijectively) to this relational domain is that you can essentially do "state-based" merging. You only need to define: how to convert to the relational domain, how to merge within that domain (which is still rich enough for you to specify relational invariants you need preserved), and how to convert back to the concrete datatype. Contrast this with operation-based syncing, where you would need a quadratic explosion of definitions for how any two operations should merge together. Here you don't even need to handle any particular operation individually (e.g., if it works for push_front, you will likely get push_back for free). Essentially it is saying the semantics of an operation is captured by the delta caused to the characteristic relations of the datatype.

cousin_it 7y ago

The paper is based on 3-way merge of relations (sets) but I'm not sure it's uniquely defined. Imagine we have a data structure consisting of two sets A and B, with the invariant that B is a subset of A. Initially A = {1}, B = {}. Imagine this data structure is replicated across two computers. On the first computer, we add 1 to B; on the second computer, we remove 1 from A. Then we try to merge these changes. It seems that the merge result could be either A = {1}, B = {1} or A = {}, B = {} and I don't see how to choose between them.

dunkelheit 7y ago

CRDTs (and I guess MRDTs are no different in this respect) are often touted as an enabling technology for collaborative local-first applications (see e.g. recent discussion: https://news.ycombinator.com/item?id=21581444 https://news.ycombinator.com/item?id=21581444) but I fail to see how they are useful beyond the simplest of cases: the emphasis is on automatic convergence, but it seems almost impossible to preserve non-trivial application-specific invariants without manual merging (I am thinking of such applications as collaborative source code editing or vector graphics editing). Am I missing something?

mathetic 7y ago
The point is often you don't need to. If you use Google docs, the chances are you will be editing it disjointly most of the time and occasionally you'll edit the same bit of the document. Then you don't really care if what comes out is a meaningful sentence, but that all parties involved (regardless in which order they see the operations) see the same version of the document so that they can fix it. That's what CRDTs buy you. Without them, you have to use either explicit synchronisation which is a bad idea if you want local-first software (doesn't work offline, needs to be done even when editing disjoint bits of the file, etc.) or something like CRDTs. Now there is a great paper by Victor Gomes, Martin Kleppmann, and Dominic Mulligan that proves (in a proof assistant!) that pretty much all other alternatives that do not use strong consistency is flawed in edge cases. As for triviality of the operations, I know for a fact that Martin Kleppmann has a paper in the works that show (and prove) how to do tree move efficiently as a CRDT. That means you can basically do arbitrary edits on JSON. Hopefully, that should clear up any confusion about for which applications it might be useful.
- dunkelheit 7y ago
  Thanks for your comment! > The point is often you don't need to. If you use Google docs, the chances are you will be editing it disjointly most of the time and occasionally you'll edit the same bit of the document. Then you don't really care if what comes out is a meaningful sentence, but that all parties involved (regardless in which order they see the operations) see the same version of the document so that they can fix it. That's what CRDTs buy you. Ok, so the hope is that semantic conflicts are rare and if they do happen, users can easily see them and promptly correct them. I guess this works well if the invariants are local and synchronization is fairly frequent (i.e. on the scale of seconds, not weeks). > That means you can basically do arbitrary edits on JSON. Hopefully, that should clear up any confusion about for which applications it might be useful. Not quite. Of course you can model everything in JSON, but the question remains as to how much additional implicit structure is needed atop the explicit tree-like structure that JSON provides and how easily this implicit structure is disturbed by merges.
  - 7y ago

Jyaif 7y ago

I believe their counter only works when they have 2 replicas: 0 / \ +1 / \ +2 / \ 1 2 \ / \ / \ / 3 <= correct result With 3 replicas it breaks apart: 0 /|\ / | \ / | \ / | \ / | \ +1 / |+100 \ +2 / | \ 1 100 2 \ / \ / \ / \ / \ / \ / 101 102 \ / \ / \ / 203 <= incorrect result, 100 is accounted for twice. It is accounted for twice because the lowest common ancestor is '0'. My team solved that problem by creating virtual common ancestors. This is similar to what git does in some cases.

cousin_it 7y ago
Wait, that doesn't look right. Why does 100 have two children? It seems to me that 1 should get merged with 100 to end up with 101, then that should be merged with 2 to end up with 103.
- Jyaif 7y ago
  This is a distributed system. You can have some replica that has 100, merge with an other replica and get 101. Then an other replica that also had the same 100 merge with an other replica and get 102. Then when 101 and 102 merge, the lowest common ancestor is still 0, so you get 203.
  - cousin_it 7y ago
    Ah I see, sorry, that makes sense.
deleted 7y ago
[deleted]
contravariant 7y ago
In this case 100 is the LCA isn't it? Then you'd end up with 100 + (101 - 100) + (102 - 100) = 103, which is correct.

marknadal 7y ago

I like the phrasing "Mergeable Data" over CRDTs (I've been on the CRDT bandwagon for years now, with https://github.com/amark/gun https://github.com/amark/gun ). Probably worth it as an industry of we shift language to "Mergeable".

gavinray 7y ago
Holy shit, the creator of GUN lurks HN? Huge fan. Super cool, I first used the library back in 2015-ish and I remember being blown away by how innovative and unique it was. I'm working on a serverless, distributed P2P compute network that's basically a PubSub event queue/job system using some hacks on top of Dat protocol right now for a side project. Do you think I might be able to use or leverage GUN instead?
- marknadal 7y ago
  :D glad to know some HNers are fan! Yeah, absolutely. Tho DAT is one of the better ones. Do you need mutability? That is probably the biggest differentiator. Either way, you should come chat about it on http://chat.gun.eco/ http://chat.gun.eco/ super friendly active community discussing stuff like this all the time. :)