3 ms·

Drifting off-topic but I've wondered this myself - I've been interested in CRDTs in a "read the news" way but not a "this rises to something I'm going to implem

Drifting off-topic but I've wondered this myself - I've been interested in CRDTs in a "read the news" way but not a "this rises to something I'm going to implement" way. Perhaps it's blindingly obvious to all here, so no one mentions it: Thinking about more practical and real-world problems seems like collaboration on on more complex/structured data. Today, it seems one would still have to transform that data to a large flat string underneath, and implement an editor that only performs edits that maintain the integrity of the higher-level object, while the flat string provides collaboration features. Perhaps it's possible to implement an XML schema known to the editor so all insertions/deletions keep the document syntactically correct. I wonder if there's some other way to either generalize on top of "big string" or create another base model (somehow?)

detaro 5y ago
CRDT is a general concept, editing text is just one possible application. If you have a stronger datatype, great, you can build operations on top of it to implement a CRDT system, depending on its properties.
- Jailbird 5y ago
  What I've read talks about character insertion and concepts that apply to editing text. Perhaps I just need to find bedrock to build up from about the properties of a stronger datatype that allow CRDTs to work.
  - detaro 5y ago
    https://arxiv.org/pdf/1805.06358.pdf https://arxiv.org/pdf/1805.06358.pdf looks like a decent starting point, with references to work on other types.
    - Jailbird 5y ago
      and pointers to other papers, too - thanks!
- sagichmal 5y ago
  It would be a little bit strange to build a CRDT system on top of a more traditional data system. CRDTs solve problems at the network layer at enormous cost basically everything else. If you're not using them there, I can't quite understand what they're doing for you?
josephg 5y ago
> Today, it seems one would still have to transform that data to a large flat string underneath, and implement an editor that only performs edits that maintain the integrity of the higher-level object, while the flat string provides collaboration features. Lots of people think this and have mentioned it over the years, but its a dangerous idea. The way concurrent edits are handled makes it really easy for the automatic merging algorithms to mess up the syntax of your XML / JSON content. And thats really hard for non-programmers to fix. The right answer for this stuff is to just make CRDTs which support other data types, the same way we did for OT with ot-types[1]. We need CRDT code for lists + text (working now - text is just a list of characters). And rich-text and JSON. And that'd cover 99% of the use cases. I'm tackling strings first in diamond-types because its probably the hardest case; but I want to have native support for other data structures soon too. Yjs and automerge already do this. They have support for plain text, XML and arbitrary JSON structures. The simplest implementation for JSON structures + tuples is probably shelf[2], which is so simple you can implement it in about 25 lines of javascript. Shelf doesn't support lists, but combining shelf with the list code I already have in diamond-types is probably going to be good enough for most applications. [1] https://github.com/ottypes/ https://github.com/ottypes/ [2] Shelf's description + code is here: https://braid.org/algorithms/shelf https://braid.org/algorithms/shelf . Or you can watch the video of Greg (shelf's author) discussing the algorithm here: https://braid.org/meeting-8 https://braid.org/meeting-8 . Kevin Jahns (Yjs's author) is in that recording too, and he's super jazzed about how simple and beautiful shelf is.
- lewisl9029 5y ago
  First of all, thank you for the amazing read! I thoroughly enjoyed the entire article, and it gave me a new perspective on the feasibility of CRDTs for real world applications performance-wise. Though I am curious now to hear your thoughts on the conflict resolution side of the equation for complex data structures like deeply nested JSON. The biggest takeaway I got from Martin's talk on the topic from a few years ago was that while CRDTs are theoretically guaranteed to eventually converge, the resulting converged state might not make any sense to applications that need to consume and act on that state [1]. It seemed like a pretty fundamental challenge to using CRDTs to store arbitrary application state to me at the time, but I imagine the field has progressed immensely since then, so would love to hear any insights you might have around strategies that could be used to alleviate or at least work around this challenge if I wanted to build a CRDT-based app today. [1] https://youtu.be/8_DfwEpHE88?t=2232 https://youtu.be/8_DfwEpHE88?t=2232

detaro 5y ago

CRDT is a general concept, editing text is just one possible application. If you have a stronger datatype, great, you can build operations on top of it to implement a CRDT system, depending on its properties.

Jailbird 5y ago
What I've read talks about character insertion and concepts that apply to editing text. Perhaps I just need to find bedrock to build up from about the properties of a stronger datatype that allow CRDTs to work.
- detaro 5y ago
  https://arxiv.org/pdf/1805.06358.pdf https://arxiv.org/pdf/1805.06358.pdf looks like a decent starting point, with references to work on other types.
  - Jailbird 5y ago
    and pointers to other papers, too - thanks!
sagichmal 5y ago
It would be a little bit strange to build a CRDT system on top of a more traditional data system. CRDTs solve problems at the network layer at enormous cost basically everything else. If you're not using them there, I can't quite understand what they're doing for you?

josephg 5y ago

> Today, it seems one would still have to transform that data to a large flat string underneath, and implement an editor that only performs edits that maintain the integrity of the higher-level object, while the flat string provides collaboration features. Lots of people think this and have mentioned it over the years, but its a dangerous idea. The way concurrent edits are handled makes it really easy for the automatic merging algorithms to mess up the syntax of your XML / JSON content. And thats really hard for non-programmers to fix. The right answer for this stuff is to just make CRDTs which support other data types, the same way we did for OT with ot-types[1]. We need CRDT code for lists + text (working now - text is just a list of characters). And rich-text and JSON. And that'd cover 99% of the use cases. I'm tackling strings first in diamond-types because its probably the hardest case; but I want to have native support for other data structures soon too. Yjs and automerge already do this. They have support for plain text, XML and arbitrary JSON structures. The simplest implementation for JSON structures + tuples is probably shelf[2], which is so simple you can implement it in about 25 lines of javascript. Shelf doesn't support lists, but combining shelf with the list code I already have in diamond-types is probably going to be good enough for most applications. [1] https://github.com/ottypes/ https://github.com/ottypes/ [2] Shelf's description + code is here: https://braid.org/algorithms/shelf https://braid.org/algorithms/shelf . Or you can watch the video of Greg (shelf's author) discussing the algorithm here: https://braid.org/meeting-8 https://braid.org/meeting-8 . Kevin Jahns (Yjs's author) is in that recording too, and he's super jazzed about how simple and beautiful shelf is.

lewisl9029 5y ago
First of all, thank you for the amazing read! I thoroughly enjoyed the entire article, and it gave me a new perspective on the feasibility of CRDTs for real world applications performance-wise. Though I am curious now to hear your thoughts on the conflict resolution side of the equation for complex data structures like deeply nested JSON. The biggest takeaway I got from Martin's talk on the topic from a few years ago was that while CRDTs are theoretically guaranteed to eventually converge, the resulting converged state might not make any sense to applications that need to consume and act on that state [1]. It seemed like a pretty fundamental challenge to using CRDTs to store arbitrary application state to me at the time, but I imagine the field has progressed immensely since then, so would love to hear any insights you might have around strategies that could be used to alleviate or at least work around this challenge if I wanted to build a CRDT-based app today. [1] https://youtu.be/8_DfwEpHE88?t=2232 https://youtu.be/8_DfwEpHE88?t=2232