Lies I was Told About Collaborative Editing, Part 2: Why we don't use Yjs

4 points by typesanitizer

miloignis

I really disagree with this article - despite protestation, I feel like their issue is with Yjs, not CRDTs in general.

Namely, their proposed solution:

  1. For each document, there is a single authority that holds the source of truth: the document, applied steps, and the current version.
  2. A client submits some transactional steps and the lastSeenVersion.
  3. If the lastSeenVersion does not match the server’s version, the client must fetch recent changes(lastSeenVersion), rebase its own changes on top, and re-submit.
  4. (3a) If the extra round-trip for rebasing changes is not good enough for you, prosemirror-collab-commit does pretty much the same thing, but it rebases the changes on the authority itself.

This is 80% to a CRDT all by itself! Step 3 there, "rebase its own changes on top" is doing a lot of work and is essentially the core merge function of a CRDT. Also, the steps needed to get the rest of the way to a full CRDT is the solution to their logging woes: tracking every change and its causal history, which is exactly what is needed to exactly re-run any failing trace and debug it.

Here's a modified version of the steps of their proposed solution:

  1. For each document, every participating member holds the document, applied steps, and the current version.
  2. A client submits (to the "server" or p2p) some transactional steps and the lastSeenVersion.
  3. If the lastSeenVersion does not match the "server"/peer’s version, the client must fetch recent changes(lastSeenVersion). The server still accepts the changes. Both the client and the "server" rebase the changes of one on top of the other. Which one gets rebased on top of the other can be determined by change depth, author id, real-world timestamp, "server" timestamp, whatever. If it's by server timestamp, you get the exact behavior from the article's solution.

If you store the casual history of each change, you can also replay the history of the document and how every client sees the document change, exactly as it happened. This is the perfect debugging tool!

CRDTs can store this casual history very efficiently using run-length encoding: diamond-types has done really good work here, with an explanation of their internals here: https://github.com/josephg/diamond-types/blob/master/INTERNALS.md

In conclusion, the article seems to be really down on CRDTs in general, whereas I would argue that they're really down on Yjs and have written 80+% of a CRDT without meaning to, and would be happier if they finished to 100%. You can still have the exact behavior they have now by using server timestamps when available and falling back to local timestamps that always sort after server timestamps when offline. A 100% casual-history CRDT would also give them much better debugging, since they could replay whatever view of history they want over and over. The only downside is extra storage, which I think diamond-types has shown can be very reasonable.