Hacker News Reader

Comment by Jailbird | Hacker News Reader

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?)

View on HN

> 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/

[2] Shelf's description + code is here: 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 . Kevin Jahns (Yjs's author) is in that recording too, and he's super jazzed about how simple and beautiful shelf is.

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

I’m not sure how much the field has improved - good chance there’s some new papers I haven’t read. But I think it’s pretty doable. For all the talk of concurrent editing, the reality is that having multiple users edit the same value at the same time in most applications is incredibly rare. It’s rare enough that concurrent editing is just basically broken in most web apps and nobody seems to mind or talk about it. For structured / database data, the best effort merges of current systems (or doing simple last writer wins stuff) is a fine solution in 95% of applications.

But ideally we want something like the semantics of ot-json-1 [1] which supports arbitrary move operations. This is necessary if you wanted to implement a program like workflowy on top of a crdt. Martin thinks this is possible in a crdt by sort of embedding part of an OT system and doing transform, but I don’t feel very satisfied with that answer either.

The other thing I would love to see solved is how you would add git style conflicts into a crdt. The best effort merging strategy of most OT & CRDT systems is fine for real-time editing but it isn’t what you want when merging distant branches.

Automerge today supports arbitrary json data, inserts, deletes and local moves. I think that’s plenty for the data model in 99% of software. I think most software that fits well into a classical database model should be reasonably straightforward to adapt.

I’m not sure if that answers your question but yeah, I’m thinking about this stuff too.

[1] https://github.com/ottypes/json1

Thanks for the great post. Indeed, as a former scientist myself, I can say you have to take everything you read with a grain of salt. I've seen inside the sausage factory, and concluded that YMMV.

> The other thing I would love to see solved is how you would add git style conflicts into a crdt. The best effort merging strategy of most OT & CRDT systems is fine for real-time editing but it isn’t what you want when merging distant branches.

I found this comment very interesting. I have been playing with the idea of 3-way merging CRDTs, similar to the git approach. Have even used this type of branching in commercial software I work on for handling concurrent changes to files.

Be very interested to know if any efforts are being made on this in the CRDT community. (I'm more of an interested onlooker. I use a lot of the same concepts in my software, but not rigorously.)

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.

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.

https://arxiv.org/pdf/1805.06358.pdf looks like a decent starting point, with references to work on other types.

and pointers to other papers, too - thanks!

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?

Reply on news.ycombinator.com