[alserio]

What I have not understood yet is how do you preserve invariants over a merge of JSON crdt. What do you do when a document has a structure that can be represented as a json, but not every valid json is a valid document? How do you avoid merges producing valid jsons but invalid documents?

[fnordsensei]

General CRDTs will guarantee valid data structures, but not schema/domain model validity. Kind of like how CRDTs applied to text will guarantee a string, but not valid English.

[paulgb]

This is a great analogy for something I've struggled to put into words.

I’ll add: if you have invariants, you almost by definition have conflicts. The C in CRDT is for conflict-free, so if you can have conflicts in the data domain you probably want something that can preserve them (like state machine synchronization) rather than a CRDT.

[josephg]

A CRDT (well, an operation based crdt) has all the information it needs to tell that conflicts have occurred, and which operations caused them. Something I’ve wanted for awhile is a crdt which can use that information to place the data in a “conflict” state.

We can do this today with keys / values pretty easily with “MV (multi value) Registers”. If two writers concurrently set the value, the next read can see both values and decide what to do about that.

But nobody (as far as I know) has yet made a crdt for code editing which uses this same trick to mark & annotate editing conflicts. And that seems like a missing piece if we want to replace git with something better.

[fnordsensei]

I’m having trouble visualizing how a conflicted state might work. We still have to produce a valid state for the next edit to work on. Do you mean supplying conflict resolution handlers?

Also, do you mean a conflict from the perspective of “malformed data structures” or “domain invariant violated”?

[alserio]

But a JSON CRDT is in a sense a string with a particular grammar... However, my intuition ends here. You could probably model the operations on a particular document structure at a higher level and try to find a simpler domain where it's easier handling logical merges, but it sounds like something that quicky becomes too complex

[josephg]

A “json crdt” doesn’t edit a string containing json grammar. That’s a misleading idea. Instead, a json crdt stores a tree of values. Values can be lists / strings / numbers / maps / etc. Operations modify that tree of data - maybe by setting a key in an object (map). That set operation will be replicated to other peers. Or by inserting into a list, or editing a text document.

When conflicting writes happen to a key in a map, a good crdt will either transparently pick a “winner” (and the other write disappears) or when you read, you can read all conflicting values and your application can choose what to do.

The downside of all this is you can’t have database style transactions, so many application side data integrity constraints are hard or impossible to implement. Like, you can’t enforce a constraint that a list has < 10 values in it because the merging algorithm may merge two inserts and put the list over your limit.

[fnordsensei]

Perhaps relating to your other comment; is it theoretically possible to inject yourself into this logic? I.e., extend a general CRDT to be a domain specifc one, and do custom resolution before the "truth" is established?

[josephg]

Can you give some examples of what sort of domain specific rules you want to apply?

The trick is coming up with rules that let you merge concurrent edits in a consistent way on all peers, regardless of the order that any changes come in. Some things are easy - Max() is a valid CRDT. But lots of stuff is much harder than it sounds.

[alserio]

Thank you for your explanation

[jitl]

You need to design your document to minimize these kinds of issues. You can treat properties in the document as a last-write-wins register to minimize “strange merge” consistency within that property.

For use cases with a central server, you can use server reconciliation to handle “true conflicts”, essentially doing layer of OT-style ops at the application level around CRDT structures provided by a library. See how Replicache suggests handling text for example. They provide a server reconciliation framework, and suggest you use a CRDT for text within that semantics.

[alserio]

Why not going full OT then? Complexity?

[jitl]

Yes, complexity! What I meant by OT-style operations is a command queue with optimistic updates on the client, and authoritative updates made by the server. This is an easy way to structure your application. "Full OT" means you need to be able to transform any operation type against any other operation of any type. It's quite complicated to implement your application's semantics in terms of operations while maintaining the M*M transform conditions.

Again, Replicache/Reflect.net is a very practical server-reconciliation based system that uses user-defined commands for application semantics, and delegates tricky merge situations to CRDTs; see https://reflect.net/#benefits:~:text=First%2DClass%20Text,st....

Notion also uses a command queue, but we don't use a CRDT for text - although I've been thinking about that for a long time

[josephg]

OT systems generally require a single, centralised server to be a party in between any two changes. CRDTs make it really easy to do multi-server deployments or peer-to-peer data replication. That is (basically) not possible using OT based systems.

[Rapzid]

Most people wanting to use CRDTs though want to use them in scenarios where a central authority is desirable for all sorts of other reasons.

[josephg]

Oh, absolutely. And OT based approaches work great here. CRDTs have the advantage that multi-server deployments are also easy, and modern CRDTs are increasingly faster and better optimized than most OT systems (certainly the ones I've worked on). But OT is a great approach.