You Might Not Need a CRDT: Document Sync in the Wild [video]

https://www.youtube.com/watch?v=0d73MdQkJOk

by eatonphil • 2 years ago

55 22 2 years ago

eatonphil• 2 years ago

This talk is from a new independent talk series, NYC Systems [0].

If you're in the area for one of these, I hope you join us! We've got an interesting planned lineup (not all public) among startups, large tech, and academia in the broad systems space.

The same night, Stefan Karpinski of Julia gave a talk on Floating Point Ranges in Julia [1].

[0] https://eatonphil.com/nyc-systems.html

[1] https://www.youtube.com/watch?v=F6tAksgboA8

pvg• 2 years ago

130 comment discussion about a year ago:

https://news.ycombinator.com/item?id=33865672

kevsim• 2 years ago

When we built Kitemaker [0] we elected to not use CRDTs. We built our sync engine after reading the blog article Figma wrote about they didn't need CRDTs because they have the server arbitrating any conflicts. We ended up taking the same approach. It's worked out very well for us though in a tool like our "last one in wins" generally works fine and doesn't lead to a lot of surprises.

For documents, we had to do something more sophisticated. At the time we built our collaborative text editing, the prevailing opinions were that CRDTs were inferior for text editing so we ended up going with Operational Transforms. That took a LOT of work to get right and is still problematic from time to time. If we had it to do all over again now, we'd definitely challenge that decision (and may do so in the future anyway even though we have a system that works).

0: https://kitemaker.co

jitl3• 2 years ago

Maybe you don’t need it for shapes and what not, but for collaborative text documents it’s really hard to have a good experience without convergent intention preserving async merges on text - you’re gonna want OT or CRDT for collaborative text editing eventually.

I work on Notion, a collaborate editor that (famously?) doesn’t merge text updates. Our editor predates the popular CRDT libraries. We’ve taken the last write wins optimistic model about as far as it will go, and now we’re building CRDT text as the basis for a bunch of new features. It’s challenging to integrate with our existing model but I think the end result will be well worth it.

If you’re interested in this sort of thing and want to work in SF or NY, shoot me an email jake@makenotion.com or dm me on Twitter @jitl

acacac• 2 years ago

is that why you guys acquired skiff?

jitl3• 2 years ago

nope

spankalee3• 2 years ago

You can merge text, preserving intention, without CRDTs. In fact, you can do a better job of preserving a history log without CRDTs.

For an app like Notion you don't have direct peer-to-peer syncing: you have a star topology with a central service able to create a canonical total ordering of events, so you really don't need CRDTs at all.

shaunxcode• 2 years ago

I am assuming they want to add an offline mode?

antirez3• 2 years ago

I'll try to expose again my idea that somebody should try to use fast (and cheap) local LLMs to resolve conflicts. So you have a stateless CRDT, and when conflict updates reach the server, you ask the LLM how to merge them. You mark the merge with some attribute so that users will see it with a different background or alike to review to check if it's sane.

yowlingcat2• 2 years ago

Couldn't this make merge behavior of the same conflict non-deterministic? If there was an LLM equivalent of a seed for an RNG, I think that would avoid this issue but I'm not sure if there is.

antirez3• 2 years ago

Sure, you can do it in a deterministic way just setting the temperature to zero and writing the prompt always in the same way. If T=0 (you always select top scoring token) and prompt is identical, the result is always the same.

jsunderland323• 2 years ago

There is a way you could make it deterministic. You could basically let the LLM select the resolution edits and preserve that. Just as you could write a bash script to let an LLM handle your git merges. But then we go back to why? This seems like a really high risk thing to do, since at the point of conflict you really do want to know intent. While copilot is great on the code editing level I’m not sure I’d want 20% of my conflict resolutions to be the opposite of what I intended.

immibis2• 2 years ago

There is one. LLMs are only non-random because they use an RNG. If you use a seeded PRNG then you get deterministic behaviour.

jitl3• 2 years ago

I want to try it out, but I imagine I’d only go through the LLM flow using a heuristic or explicit user action around branch/merge workflow from a long offline editor. I’m not sure I see a reason for more “online” realtime collaboration to prefer LLM intervention. For realtime it’s much more important things converge so we can just send little updates, and if you need things to converge deterministically I don’t think you can use an LLM.

I wonder when VS Code Copilot will start suggesting git rebase solutions.

chaostheory• 2 years ago

Didn’t realize that apps with reliable network connections would get much use, but I’m wrong when I think about it collaborative document editors.

immibis2• 2 years ago

It's a given that a "realtime collaborative" app should be used with a reliable network connection. Otherwise you're not really doing realtime collaboration. The presentation has a point that everyone talks about CRDTs all the time but you only need one if your collaboration has a particular structure that requires one, which most collaborations don't. Google Docs, for example, is not peer-to-peer nor does it have long intervals where clients are desynchronized.

spankalee3• 2 years ago

This talk makes a really important point for multiplayer app implementations!

But I don't love how he separates the global order approach from operational transform. Those two approaches go very well together in my experience: - Global ordering eliminates much of the complexity of OT - OT enables optimistic, offline edits and fine-grained merging on top of global ordering

Most SaaS editors are not truly peer-to-peer: edits are sent to a central server before being broadcast back to clients. The service can define the global ordering then - the point of this talk.

But you need the server to be able to reconcile and merge concurrent edits from clients that haven't fully sync'ed yet, and you want clients to be able to locally apply edits before receiving the latest state from the server, so you need some way to undo and replay edits on top of newly discovered edits that happened before (like a Git rebase). This is the basic operational transform function.

The knock on OT has been complexity - the claim that you need n^2 merge functions for n operations. But... most operations in a real app don't collide in ways that require merges so in reality you need far fewer than than n^2. You generally need text and collection merges.

Marijn Haverbeke, the author of ProseMirror and CodeMirror, has a great blog post on a lot of this here: https://marijnhaverbeke.nl/blog/collaborative-editing-cm.htm...

gzapp• 2 years ago

We stuck with ProseMirror steps for these reasons(and more) on my project.

I did, however, create a new collab plugin based on commits from this Google Wave white paper: https://svn.apache.org/repos/asf/incubator/wave/whitepapers/... , and wrote about it here https://stepwisehq.com/blog/2023-07-25-prosemirror-collab-pe... . Anyone needing more performance out of ProseMirror collab while sticking with traditional steps/transactions may find that information useful.

You Might Not Need a CRDT: Document Sync in the Wild [video]

Related Stories