Hacker News Reader

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.

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.

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.

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.

Er, how can you express the merge operation as a type?

See 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-...

> A Merge Type is a function

Er, okay, if you redefine "type" to mean "function" then sure.

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

I'm surprised that MS's concurrent revisions [1] haven't taken off because this is what they do by default: you specify a custom merge function for any versioned data type so you can resolve conflicts using any computable strategy.

[1] https://www.microsoft.com/en-us/research/project/concurrent-...

Right, but the problem is that most programmers don't want to reason about this stuff. The danger is that things will feel like they "just work" locally (when there's no concurrent edits) and then go potentially off the rails when actual users start editing together.

We can solve this by educating developers and giving them different merge strategies to use, but I worry that most devs won't bother most of the time. So long as the merge resolution is good enough, they'll just shrug and accept it.

That said, most collaborative editing happens online. People don't really go offline while editing a google doc with other people. Its fine if two people put their cursor in the same location - they won't edit at the same time, because that would be weird.

And with deep JSON structures, so long as the structure itself can stay intact and parsable, users will usually work on different things to avoid weird editing conflicts. Imagine a giant 3D world (like an MMO) full of lots of objects and scenery. And a team working on building out that world. Artists will probably work on different things, in different areas or different parts of the terrain. Or if they're working on the same thing, they'll do it live & online.

The one big area of CRDT research I'd love to see more of is offline conflict resolution - which should be different than online conflict resolution. Git has the right idea - I want merge conflicts when things are merged together. CRDTs have a superset of the information that git has. We have all the information we need in Yjs / automerge / etc to be able to notice merge conflicts and do whatever we want with them. But as far as I know, nobody has built something like Git on top of a CRDT yet which uses this information to create merge conflicts in a sensible way.

With the CRDT I'm building, for registers I've decided to use MVRegisters (so if multiple writes happen, we keep all conflicting values and can expose that conflict state through the API). But also have a "simple API" which picks an arbitrary, consistent winner so when developers don't care (or when they're making an MVP of their app) everything will still work fine. The (discarded) conflicting values will be in the history anyway if they want to recover it later.

Yes, offline edits tend to generate larger units of delta. The larger the deltas, the more difficult or even impossible it is to merge with a sensible outcome for all parties. Falling back to manual merging will be an useful feature.

But wouldn't this mean the CRDT will be an evergrowing set like git? Is this even practical like when say, working with a thousand page book? To me it looks like it breaks the possibility of garbage collecting portions of CRDT which will make it harder to adopt in real-world apps.

> Is this even practical like when say, working with a thousand page book?

Remarkably, yeah its fine in practice. I've done a lot of work on this recently, doing crazy optimized bit packing for text CRDT data. The numbers are wild - all the metadata (insert positions, versions, etc) ends up only accounting for a few % of the final file size. Almost all of the final file size is the inserted characters themselves. And this is still true for files with complex editing histories (eg reconstructed from git repositories).

Diamond types does LZ4 compression of the inserted text data. In most of my examples, I save more bytes on disk by LZ4 compressing the text than I spend storing all the CRDT metadata. So the file on disk (with full history and change tracking) often ends up smaller than the final document.

I'm confused here - please could you explain. Here's what I see would happen:

1. User 1 adds a caption

2. User 2 adds a caption.

3. Both transmit to the server.

4. Server receives the first edit, applies it to the doc, broadcasts the change.

5. Server receives the second edit, sees it is applied to the previous version of the document, rejects the edit.

6. Client that receives the rejection re-bases their edit, attempts to apply it, and it is rejected as it does not conform with the schema.

So the outcome is whichever client hits the server first wins, which is fine. Where's the problem?

The operation you are suggesting would not be based on CRDTs. One of the main points is that they are Conflict-free as the same suggest. So it's not allowed to reject a mutation. The merge operation "magically" has to ensure it will always confirm to the schema. That's precisely the hard part. Defining such a merge operation.

Ok, thanks very much.

So what if the server just rebases the edit, and that results in the caption being set a second time? ie most recent wins. Don’t see how this would break a schema?

Encoding “adding a caption” as “add an additional child called caption” would be silly, as we know there can only be one caption. So the op would be “set the caption”.

That is possible. But is probably not what users want. This can quickly give the impression of person x overwrote the caption of person y. Q

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

I disagree, the "conflict" in "conflict-free" is not misleading at all. As I see it, your issue with the "conflict" lies in a misunderstanding of what a conflict actually is in the context of CRDTs and what eliminating them entails. Concurrent updates can be free from conflicts but still end up with a semantically inconsistent document, and that is perfectly fine.

The whole point of CRDTs is to allow collaborative editing without resorting to mutex locks or forcing users to retry cancelled updates. That's why Yjs merges two captions added to a figure, and also why other CRDTs don't stop concurrent updates that make no sense semantically, such as having users concurrently writing incoherent sentences. Document-wise, there is no conflict or inconsistence.

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.

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.

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

Who gets the pop-up? If both Alice and Bob, and they simultaneously give conflicting replies, you're right back to where you started.

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.

This isn’t really a problem. If Alice and Bob keep disagreeing, then it is appropriate that a conflict remains unresolved.

You're not back to where you started. You've gone from a technical conflict to a direct disagreement about what is supposed to happen. There's no technical solution to an edit war. So maybe ask anew about the conflicting answers, or pick one arbitrarily at that point. Or make them play rock paper scissors. But it still helps to ask before it becomes a direct disagreement.

Stupid question - are there any good resources on User Experience patterns/recipes for implementing OT/CRDTs?

Context - a lot of the literature is about the backend algorithm. But that still leaves individual teams tripping over the frontend interaction design and usability.

Example of what I'm looking for - hex.tech has a video tutorial of their "Cell locking" feature, where the cell gets disabled and a "Mac Lockard has taken control of a cell you were editing" toast notification appears. [1]. This is fully baked and a recipe which if I put in a jira ticket could actually get implemented. :)

I would love to read a book which is a "Don't make me think" and has an example with "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?". All the UI's in my head would look like "Clippy" from MS Word - or "Pipey" from Silicon Valley [2], haha.

1: https://hex.tech/blog/a-pragmatic-approach-to-live-collabora...

2: https://www.youtube.com/watch?v=E2YcOV5C2x4

This is close: https://decentpatterns.com/library/

...but my general belief is that UI patterns need to evolve as (1) specific UIs before they become (2) general patterns, and we simply don't have enough good solutions yet to make a pattern library out of them.

Very cool - thanks!

Usually that doesn't happen because their replies don't conflict within the time interval of a round trip between the two of them, so one can see the other's action first, and decide to agree.

But if it does happen, either they get a new popup, eventually, saying that their conflict-resolution decisions also conflicted and what would they like to do, or the system decays to a CRDT-style pre-determined resolution rule for the second-order conflict -- with similar problems to the original CRDT resolution rule we tried to avoid. Things like "give priority to the person who chose to keep information instead of deleting", "give priority to the person with the biggest random number", "merge them by keeping information along with a note in the document about the attempt to delete the column", or "delete the column and put the edited cell in a note". But this time, only when the users conflict after the first popup, so it doesn't occur as often.

I think you're describing a metastability effect which occurs in all distributed systems that don't use pre-determined resolution rules like pure CRDTs. It happens in network protocols, distributed transactions, and consensus protocols in general. If the process you use to resolve depends on input from multiple parties who don't have a way to communicate and could choose conflicting values, there's a non-zero probability of needing another round or to escalate upwards to a higher-level system to resolve.

In many technical systems, provided there's a way to communicate it's not difficult to make the probability of repeated rounds or escalations tend arbitrarily close to zero (but not actually zero). If there's a possibility of network partition, though, the conflict can come back later when communication returns; there's no way to completely make it go away.

Yep. And, to point it out, good CRDTs have all the information they need to implement all of this.

Git marks conflicts when merging. CRDTs could do the same, but I don't know any which have implemented this stuff yet.

What you would ‘certainly want’ depends very much on the application this is implemented in. The data isn’t gone from the CRDT table unless the program decides it is, so many ui choices are possible.

This comment really needs a “yo dawg” meme.

I mean, JSON is objects all the way down, CRDTs are conflict-free maps all the way down.

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!

> 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

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.

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.

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”.

> 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/ It's relatively new, but is a CRDT aimed at rich text!

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.

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?

I think the short answer is: if you want your CRDTs to enforce application constraints you need to bake them into the data structure.

That makes sense. Thank you.

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.