3 ms·

> Or any video game Agreed, BFT is clearly needed for multiplayer CRDT backed video games. > I assume you’re talking about weird merges from users putting mar

> Or any video game Agreed, BFT is clearly needed for multiplayer CRDT backed video games. > I assume you’re talking about weird merges from users putting markdown in a text crdt? Nope, although that is an issue. In that case the document shouldn't be markdown, it should be a rich text CRDT that's converted to markdown as output. On the conflicts I mentioned, an example, say you are building a to do list app. First let's do it with Prosemirror and Yjs, but for some reason we have decided to limit the length of a to do list to 10 items. Prosemirror will let you do that when defining a schema, have a maximum number of child nodes of the parent node type. With the current Yjs/Prosemirror system, if you have 9 items in the list and two people concurrently add a 10th, one of them will be dropped by prosemirror (deterministically). The document schema enforced that rule outside of the CRDT implementation. Yjs xmlFragments do not have the concept of these sort of rules. Now say you want to do this with the json like Map and Array types. Again the array type does not have the concept of a length limit, it will merge the two concurrent edits and create a document with 11 entries. In this case your application needs to manage the no longer complying document to correct it. The issue comes if you are naively merging the documents on the server, and dumping the json, it will not take into account your applications own conflict resolution. My suggestion is that a CRDT schema could do this, it would be a bit like a JSON Schema, but with rules about how to correct misshapen structures. So yes, I agree these generic rich text plus JSON types cover what 99% of applications need, but they also need to enforce a shape to the data structure that isn't built into the generic types. Having a way to do that as part of the merging layer, rather than application layer, would help to ensure correctness.

josephg 3y ago
Yeah I hear you. I've still never found a good way to implement schema validation rules like "this list cannot have more than 10 items" on top of a CRDT. Eventually consistent collaborative editing systems (like CRDTs and OT based systems) are optimistic. They allow any edits, and then later merge things if necessary. But if you only find out the list has 11 elements at the merging step, what do you do? Its too late to reject either of the inserts which put you in that state. My best answer at the moment is to tell people to rethink validation rules like that. I can't think of a lot of good use cases for collaborative editing where a "length <= 10" rule is something you want. Unfortunately, validation rules are really important for referential integrity. If you add a reference to some item in a data set and I concurrently delete that item, what should happen? Does the delete get undone? Does the reference get removed? Is the reference just invalid now? Should references only be to an item at some point in time? (Eg like a git SHA rather than a path)? Maybe optimistic systems just can't have referential integrity? Its an uncomfortable problem.

josephg 3y ago

Yeah I hear you. I've still never found a good way to implement schema validation rules like "this list cannot have more than 10 items" on top of a CRDT. Eventually consistent collaborative editing systems (like CRDTs and OT based systems) are optimistic. They allow any edits, and then later merge things if necessary. But if you only find out the list has 11 elements at the merging step, what do you do? Its too late to reject either of the inserts which put you in that state. My best answer at the moment is to tell people to rethink validation rules like that. I can't think of a lot of good use cases for collaborative editing where a "length <= 10" rule is something you want. Unfortunately, validation rules are really important for referential integrity. If you add a reference to some item in a data set and I concurrently delete that item, what should happen? Does the delete get undone? Does the reference get removed? Is the reference just invalid now? Should references only be to an item at some point in time? (Eg like a git SHA rather than a path)? Maybe optimistic systems just can't have referential integrity? Its an uncomfortable problem.