You Might Not Need a CRDT: Document Sync in the Wild [video](youtube.com)
youtube.com
You Might Not Need a CRDT: Document Sync in the Wild [video]
https://www.youtube.com/watch?v=0d73MdQkJOk
22 comments
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.
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.
I am assuming they want to add an offline mode?
For most SaaS apps even offline is going to sync with the central service and not with other peers.
Direct peer-to-peer without a intermediating server is so rare for SaaS that I don't even know of an example.
Direct peer-to-peer without a intermediating server is so rare for SaaS that I don't even know of an example.
Even with a star topology, how do you go about preserving user intent for text insertions without CRDTs and without rewriting (transforming) mutations so that client and server result in same state (basically OT)?
When inserting text, you can either use mutations that insert the text relative to some reference character(s) or at some index. The former is basically the approach of most text CRDTs. I'm having a hard time imagining the latter without modifying the insertion index relative to concurrent insertions or deletions. I believe that Jupiter based OT imposes a global order, but uses it to determine how concurrent mutations are transformed against one another.
When inserting text, you can either use mutations that insert the text relative to some reference character(s) or at some index. The former is basically the approach of most text CRDTs. I'm having a hard time imagining the latter without modifying the insertion index relative to concurrent insertions or deletions. I believe that Jupiter based OT imposes a global order, but uses it to determine how concurrent mutations are transformed against one another.
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...
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...
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.
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.
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
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
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
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
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.
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.
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.
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.
Ahh, that's a fantastic callout. I've experimented with low temperature so far but never zero temperature. Makes sense, and I think this is definitely a technique I'll use in the future.
Thank you for the legendary work on Redis by the way! It's been an invaluable part of multiple large production systems I've built and is such a well-built tool. I'm hoping from your interest in this topic (and some of the blog posts you've written about it) that some part of the roadmap for Redis might help power LLM workloads in the future.
Thank you for the legendary work on Redis by the way! It's been an invaluable part of multiple large production systems I've built and is such a well-built tool. I'm hoping from your interest in this topic (and some of the blog posts you've written about it) that some part of the roadmap for Redis might help power LLM workloads in the future.
Thanks for the nice words! Appreciated, and good hacking!
There is one. LLMs are only non-random because they use an RNG. If you use a seeded PRNG then you get deterministic behaviour.
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.
I wonder when VS Code Copilot will start suggesting git rebase solutions.
130 comment discussion about a year ago:
https://news.ycombinator.com/item?id=33865672
https://news.ycombinator.com/item?id=33865672
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.
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.
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 [email protected] or dm me on Twitter @jitl