7 ms·

This is the most underrated problem with CRDTs: > Both paths will allow us to ensure that each replica converges on the same state, but that alone does not gua

This is the most underrated problem with CRDTs: > Both paths will allow us to ensure that each replica converges on the same state, but that alone does not guarantee that this state is the “correct” state from the point of view of user intent. In context of richtext editors, it's easy to converge a rich-text JSON into a single state for all collaborators. What's difficult is to ensure that the converged state is renderable as richtext. For example, is there a table cell that was inserted where a column was deleted? I wrote a summary of this issue with CRDTs here - https://writer.zohopublic.com/writer/published/grcwy5c699d67b9c444219b60cdb90ccbabc7 https://writer.zohopublic.com/writer/published/grcwy5c699d67... for those interested. While I'm optimistic it's not impossible to solve, it's surprising why most CRDT literatures don't go into these details on correctness. Appreciate the author for putting this out. PS: We currently use OT for collaboration in Zoho Writer (https://writer.zoho.com/ https://writer.zoho.com/). I'm looking out for practical CRDT ideas that works well with richtext.

samwillis 4y ago
Exactly, the "C" in CRDT is a little misleading. They are "conflict free" in as much as they are able to merge and resolve in the basic sense. That does not mean that the resulting state is valid or meets your internal schema. A good example of this is using Yjs with ProseMirror, it's possible for two concurrent edits to resolve to a structure that doesn't meet your ProseMirror schema. An example I have used before is a <figure> element that can contain a single optional <caption> element. It's possible for two users to add that caption to the figure concurrently, Yjs will happily merge its XMLFragment structures and place two captions in the figure. However when this is loaded into ProseMirror it will see that the document does not match its schema and dump the second caption. Fortunately the captions are ordered and so the same state will re resolved by all parties. This is all ok if you are doing the merging on the front end, but if you try to merge the documents on the server, not involving ProseMirror, the structure you save, and potentially index or save as html, will be incorrect. Point is, it's still essential with CRDTs to have a schema and a validation/resolution process. That or you use completely custom CRDTs that encodes into their resolution process the validation of the schema.
- lewisjoe 4y ago
  Your example is spot on :) I believe we shouldn't lock our richtext state to Prosemirror's specs. The state should better be modelled as a CRDT and ensuring correctness should be part of CRDT operations. This way we unlock other possibilities like server-side merging and the editing library can be swapped (eg. lexical) All this sounds right but it's lot of work.
- lijogdfljk 4y ago
  Yea, this is kinda why i don't understand a lot of these off the shelf CRDT solutions. Like CRDTs for JSON. I'm still trying to learn CRDTs; but early on in my learning process i had the thought that CRDTs don't have mere data types - as you say, they have Data Type + Conflict Resolution bundled into one. It's not enough to make a String type, because different types need to be resolved differently. Plus some types of resolution have a lot more metadata, so you want to choose the best fitting one. I found that my goal to make SQL + CRDT meant i had to expose this combo of Type + Resolution to the end user. It seems essential to how the app works. But maybe i don't know anything, /shrug. I'm still learning them.
  - toomim 4y ago
    Yes! We call this the "Merge Type" of data in the braid.org group. Each datum as both a data type and a merge type. The programmer just needs to specify these two types, and then the programming runtime can choose which synchronization algorithm to use.
    - preseinger 4y ago
      Er, how can you express the merge operation as a type?
      - toomim 4y ago
        See https://raw.githubusercontent.com/braid-org/braid-spec/master/draft-toomim-httpbis-merge-types-00.txt https://raw.githubusercontent.com/braid-org/braid-spec/maste... And for a more intuitive explanation, this might help: https://braid.org/demo/interact#a-merge-type-defines-how-to-flatten-bubbles-in-space https://braid.org/demo/interact#a-merge-type-defines-how-to-...
CGamesPlay 4y ago
I don't think I've seen any implementations of this, but the table example you listed is solvable. The insight is to stop thinking of the table as a bundle of markup and think about it as itself a primitive CRDT type that contains text in the table cells. The columns are a CRDT set of column IDs. The rows are a CRDT map of row IDs to CRDT maps of column IDs to cell values, where the cell values are again the same type as your document text. Column headings are a specially formatted row. Rows are ordered using a sequence type. Removing a row is a normal CRDT map deletion. Removing a column is a normal CRDT map deletion from the columns map. Rendering the table will ignore map entries that don't correspond to real columns.
- inglor 4y ago
  So with your solution, the inserted table cell would "disappear" from what is rendered? That's not necessarily (depends on the product) great or even acceptable user experience. As a user I would certainly want a way to know there is an "orphaned" "edited after delete" cell to salvage the data inputted or understand the confusion between editors.
  - georgelyon 4y ago
    The best UX resolution to this kind of issue I have seen is to display “This table cell was added by Bob concurrently to Alice removing its row. How would you like to proceed: recover the row or ignore the change?”
    - drfuchs 4y ago
      Who gets the pop-up? If both Alice and Bob, and they simultaneously give conflicting replies, you're right back to where you started.
      - georgelyon 4y ago
        Yes, this is the correct behavior. If Alice and Bob disagree about whether or not that row should be in the table you aren't going to fix it with math. More often than not, the expected outcome will be obvious (i.e. spelling correction in a deleted cell can be ignored) and if it isn't obvious, there will need to be human interaction to determine the best path forward.
truculent 4y ago
To what extent is this an issue with CRDTs and to what extent is it an issue with the data structure(s) used to represent the state?
- dkjaudyeqooe 4y ago
  I think the short answer is: if you want your CRDTs to enforce application constraints you need to bake them into the data structure.
  - truculent 4y ago
    That makes sense. Thank you.
expede 4y ago
> I'm looking out for practical CRDT ideas that works well with richtext. Have you seen Peritext from Ink & Switch? https://www.inkandswitch.com/peritext/ https://www.inkandswitch.com/peritext/ It's relatively new, but is a CRDT aimed at rich text!
- jamil7 4y ago
  Their linked summary mentions Peritext and the current limitations. Agree it’s exciting though and you can implement it fairly easily yourself by following the blog post as it’s so well written and explained.
kevsim 4y ago
We also had the OT vs. CRDT discussion with regards to our editor at Kitemaker (kitemaker.co), and also ended up with OT. For us there were a number of factors, but (in addition to the case you mentioned) it came down to the fact that (at that time) most of the CRDT libs like automerge generate huge diffs that we'd need to send over the wire and also that the open source editor we use (SlateJS) had operations that just slotted very nicely into OT. Your editor feels really nice BTW. Well done!
jdvh 4y ago
For the table situation we solve this by have a generic concept of a "card" that is rendered as a table cell when it's the grandchild of a table (table > tr > td) but otherwise it's just a standalone item, much like a markdown callout.
deleted 4y ago
[deleted]
jkaptur 4y ago
The intuitively obvious approach here is to have some kind of schema-guided or constraint-guided CRDT. That is, you get the guarantee that not only do you end up with valid JSON, you get the guarantee that f(that_json) == true. I imagine this is considerably easier said than done, but I'm curious if there's research (or results!) in the area.
- quickthrower2 4y ago
  Parts of the tree with “don’t merge children” might be ok, then you show the user a conflict dialog when this happens. Or, inspired by your comment: run f for the tree, if false, search for the smallest subset where f is false and show the conflict dialog for that. The user chooses “mine” or “theirs”.
paulmd 4y ago
> What's difficult is to ensure that the converged state is renderable as richtext. For example, is there a table cell that was inserted where a column was deleted? Yes. This is one of the fundamental limitations of working at a textual level, which is sort of the local optimum that *nix ended up in. JSON in particular gets suuuuper fucked up if you don't merge/rebase carefully. There's no real syntax for it to grab onto and diff doesn't understand the concept of indentation or commas, so it just turns into an ocean of line-swapping and incorrect block-swapping. Diff also does an excruciatingly poor job in the very common case when everyone is appending to the same area (let's say, the end of the file). This is pretty much just an inherent weakness of textual matching, what you need is to work on trees of lexical token nodes, or some type of object structure stream like powershell. Not that it's perfect either, I'm sure there are combinations of options that can leave a node in an inconsistent state, but it at least gives you a chance at correctness. In some cases patience-diff can help, it tries to generate big blocks of changed ranges, hopefully some of the hunks being relatively syntactically well-formed, but there is still no guarantee. There is also JSON-diff which implements such a lexical-tree diff model for diff files, similar to the "jq" util. https://github.com/zgrossbart/jdd https://github.com/zgrossbart/jdd I think that's also viable for other lexable languages too - it would be cool to sed or find/replace on an tokenized representation of the code, have jquery or jpath style selectors etc. A lot of the time we kinda end up doing this with find/replace anyway.

samwillis 4y ago

Exactly, the "C" in CRDT is a little misleading. They are "conflict free" in as much as they are able to merge and resolve in the basic sense. That does not mean that the resulting state is valid or meets your internal schema. A good example of this is using Yjs with ProseMirror, it's possible for two concurrent edits to resolve to a structure that doesn't meet your ProseMirror schema. An example I have used before is a <figure> element that can contain a single optional <caption> element. It's possible for two users to add that caption to the figure concurrently, Yjs will happily merge its XMLFragment structures and place two captions in the figure. However when this is loaded into ProseMirror it will see that the document does not match its schema and dump the second caption. Fortunately the captions are ordered and so the same state will re resolved by all parties. This is all ok if you are doing the merging on the front end, but if you try to merge the documents on the server, not involving ProseMirror, the structure you save, and potentially index or save as html, will be incorrect. Point is, it's still essential with CRDTs to have a schema and a validation/resolution process. That or you use completely custom CRDTs that encodes into their resolution process the validation of the schema.

lewisjoe 4y ago
Your example is spot on :) I believe we shouldn't lock our richtext state to Prosemirror's specs. The state should better be modelled as a CRDT and ensuring correctness should be part of CRDT operations. This way we unlock other possibilities like server-side merging and the editing library can be swapped (eg. lexical) All this sounds right but it's lot of work.
lijogdfljk 4y ago
Yea, this is kinda why i don't understand a lot of these off the shelf CRDT solutions. Like CRDTs for JSON. I'm still trying to learn CRDTs; but early on in my learning process i had the thought that CRDTs don't have mere data types - as you say, they have Data Type + Conflict Resolution bundled into one. It's not enough to make a String type, because different types need to be resolved differently. Plus some types of resolution have a lot more metadata, so you want to choose the best fitting one. I found that my goal to make SQL + CRDT meant i had to expose this combo of Type + Resolution to the end user. It seems essential to how the app works. But maybe i don't know anything, /shrug. I'm still learning them.
- toomim 4y ago
  Yes! We call this the "Merge Type" of data in the braid.org group. Each datum as both a data type and a merge type. The programmer just needs to specify these two types, and then the programming runtime can choose which synchronization algorithm to use.
  - preseinger 4y ago
    Er, how can you express the merge operation as a type?
    - toomim 4y ago
      See https://raw.githubusercontent.com/braid-org/braid-spec/master/draft-toomim-httpbis-merge-types-00.txt https://raw.githubusercontent.com/braid-org/braid-spec/maste... And for a more intuitive explanation, this might help: https://braid.org/demo/interact#a-merge-type-defines-how-to-flatten-bubbles-in-space https://braid.org/demo/interact#a-merge-type-defines-how-to-...

CGamesPlay 4y ago

I don't think I've seen any implementations of this, but the table example you listed is solvable. The insight is to stop thinking of the table as a bundle of markup and think about it as itself a primitive CRDT type that contains text in the table cells. The columns are a CRDT set of column IDs. The rows are a CRDT map of row IDs to CRDT maps of column IDs to cell values, where the cell values are again the same type as your document text. Column headings are a specially formatted row. Rows are ordered using a sequence type. Removing a row is a normal CRDT map deletion. Removing a column is a normal CRDT map deletion from the columns map. Rendering the table will ignore map entries that don't correspond to real columns.

inglor 4y ago
So with your solution, the inserted table cell would "disappear" from what is rendered? That's not necessarily (depends on the product) great or even acceptable user experience. As a user I would certainly want a way to know there is an "orphaned" "edited after delete" cell to salvage the data inputted or understand the confusion between editors.
- georgelyon 4y ago
  The best UX resolution to this kind of issue I have seen is to display “This table cell was added by Bob concurrently to Alice removing its row. How would you like to proceed: recover the row or ignore the change?”
  - drfuchs 4y ago
    Who gets the pop-up? If both Alice and Bob, and they simultaneously give conflicting replies, you're right back to where you started.
    - georgelyon 4y ago
      Yes, this is the correct behavior. If Alice and Bob disagree about whether or not that row should be in the table you aren't going to fix it with math. More often than not, the expected outcome will be obvious (i.e. spelling correction in a deleted cell can be ignored) and if it isn't obvious, there will need to be human interaction to determine the best path forward.

truculent 4y ago

To what extent is this an issue with CRDTs and to what extent is it an issue with the data structure(s) used to represent the state?

dkjaudyeqooe 4y ago
I think the short answer is: if you want your CRDTs to enforce application constraints you need to bake them into the data structure.
- truculent 4y ago
  That makes sense. Thank you.

expede 4y ago

> I'm looking out for practical CRDT ideas that works well with richtext. Have you seen Peritext from Ink & Switch? https://www.inkandswitch.com/peritext/ https://www.inkandswitch.com/peritext/ It's relatively new, but is a CRDT aimed at rich text!

jamil7 4y ago
Their linked summary mentions Peritext and the current limitations. Agree it’s exciting though and you can implement it fairly easily yourself by following the blog post as it’s so well written and explained.

kevsim 4y ago

We also had the OT vs. CRDT discussion with regards to our editor at Kitemaker (kitemaker.co), and also ended up with OT. For us there were a number of factors, but (in addition to the case you mentioned) it came down to the fact that (at that time) most of the CRDT libs like automerge generate huge diffs that we'd need to send over the wire and also that the open source editor we use (SlateJS) had operations that just slotted very nicely into OT. Your editor feels really nice BTW. Well done!

jdvh 4y ago

For the table situation we solve this by have a generic concept of a "card" that is rendered as a table cell when it's the grandchild of a table (table > tr > td) but otherwise it's just a standalone item, much like a markdown callout.

deleted 4y ago

[deleted]

jkaptur 4y ago

The intuitively obvious approach here is to have some kind of schema-guided or constraint-guided CRDT. That is, you get the guarantee that not only do you end up with valid JSON, you get the guarantee that f(that_json) == true. I imagine this is considerably easier said than done, but I'm curious if there's research (or results!) in the area.

quickthrower2 4y ago
Parts of the tree with “don’t merge children” might be ok, then you show the user a conflict dialog when this happens. Or, inspired by your comment: run f for the tree, if false, search for the smallest subset where f is false and show the conflict dialog for that. The user chooses “mine” or “theirs”.

paulmd 4y ago

> What's difficult is to ensure that the converged state is renderable as richtext. For example, is there a table cell that was inserted where a column was deleted? Yes. This is one of the fundamental limitations of working at a textual level, which is sort of the local optimum that *nix ended up in. JSON in particular gets suuuuper fucked up if you don't merge/rebase carefully. There's no real syntax for it to grab onto and diff doesn't understand the concept of indentation or commas, so it just turns into an ocean of line-swapping and incorrect block-swapping. Diff also does an excruciatingly poor job in the very common case when everyone is appending to the same area (let's say, the end of the file). This is pretty much just an inherent weakness of textual matching, what you need is to work on trees of lexical token nodes, or some type of object structure stream like powershell. Not that it's perfect either, I'm sure there are combinations of options that can leave a node in an inconsistent state, but it at least gives you a chance at correctness. In some cases patience-diff can help, it tries to generate big blocks of changed ranges, hopefully some of the hunks being relatively syntactically well-formed, but there is still no guarantee. There is also JSON-diff which implements such a lexical-tree diff model for diff files, similar to the "jq" util. https://github.com/zgrossbart/jdd https://github.com/zgrossbart/jdd I think that's also viable for other lexable languages too - it would be cool to sed or find/replace on an tokenized representation of the code, have jquery or jpath style selectors etc. A lot of the time we kinda end up doing this with find/replace anyway.