CRDTs: The Hard Parts

The author is a researcher on distributed systems. I found this video from him to be an excellent first education on CRDTs, how they work, what they're good for and what they aren't (yet) good for: [VIDEO]

Ah, I'll put it in as a note in the beginning. You can see a more basic introduction in a previous post I wrote: [LINK] [LINK] Here's some introductory material I found helpful: - [An interactive intro to CRDTs]( [LINK] ) - [An introduction to state-based CRDTs]( [LINK] ) - [CRDTs for non-academics]( [LINK] ) - [CRDT: The Hard Parts]( [VIDEO] ) - [Readings in CRDTs]( [LINK] ) - [crdt.tech]( [LINK] )

What they claim is that if all editing stops, then after a period of time everybody will be looking at the SAME document. This is what is meant by "eventual consistency". Achieving this in general is indeed a difficult problem, but (some of) these algorithms do solve it, though it can be tricky to correctly prove that they do. I agree that it is not possible to ensure that the document everybody is looking at is what they actually wanted it to be. However, there are some options for what happens, where some results may be technically correct -- we are all looking at the same thing -- but obviously really bad. This beautiful talk has some examples: [VIDEO]

CRDTs seem very promising, but we still have a long way to go. The most exciting work in this area is being done by Ink&Switch [0]. They have a number of interesting real-world app prototypes based on CRDTs. - An interesting case where CRDTs failed is Xi-editor, where they tried to use CRDTs as the basis for a plugin system [1,2]. - One of the biggest problems with CRDTs is the overhead needed to keep track of the full document history. The automerge [3] project has been working on efficient compression of CRDTs for JSON datatypes. - The idea of monotonic updates is really appealing at first, but I was disappointed when I realized there's no good solution to handle deletions. Tombstones, to me, seem like kind of a hack, albeit a necessary one. Practically, CRDTs aren't the silver bullet they might seem like at first. - Another lesson learned is that when ten people are editing the same paragraph, there's not really a right answer. I think the key to implementing CRDTs is doing it at the correct level of granularity. - ProseMirror intentionally chose NOT to use CRDTs [4]. - Some more good references are [5,6,7] [0] [LINK] [1] [LINK] [2] [LINK] [3] [LINK] and [LINK] [4] [LINK] [5] Kleppmann 2020, "CRDTs: The Hard Parts" [VIDEO] with HN Discussion: [LINK] [6] Kleppmann 2019, "Interleaving Anomalies in Text Editors" [LINK] [7] [LINK]

Disclosure: I work on a related project (Fluid Framework) that makes application agnostic CRDTs easily available. The CKEditor folks did a great job building an OSS text editor and they did an especially strong work building a text editor that works well with collaboration. I've made a few OSS rich text editors work (mostly) with Fluid [0, 1] and the design of the text editor really changes how easily collaboration can be added. Luckily the text editor accepts remote changes, integrating an OT or CRDT solution is approximately the same. They also did a great job explaining the problem. My experience has been that people don't intuitively understand why real time collaboration is a tricky problem. I didn't. First of all, for a bunch of use cases websockets + redis + a last write wins conflict resolution (or some similar solution) is totally enough. Second, it's not immediately obvious why rich text editing requires more complex conflict resolution. Third, it's not obvious why solving the RTE problem doesn't immediately lend itself to other problems [2]. Because we started building in mid-late 2017, right as CRDTs really started to get competitive with OT, we chose a CRDT approach, but the collab problem space in general is much deeper I realized before getting into it. Anyway, I always appreciate seeing people explain their journey. Especially when it has to do with collaboration. [0] [LINK] [1] [LINK] [2] [VIDEO]

We are almost there, for lists and structs there are CDRT's but a move operation across the data structure is missing. Martin Kleppman (from automerge) talks about this in his talk "CRDTs: the hard parts"[0]. I also think a range move or range delete is missing from many of these algorithms. A submission here on HN did implement a range delete on rich text (but I forgot what the name was). [0]: [VIDEO] EDIT: Ah actually Peritext (which you linked to) was the article I was thinking of. I think the range delete would be useful for regular lists as well.