OT and CRDT trade-offs for Real-Time collaboration
tiny.cloud
tiny.cloud
I'm so glad to see that the HN community cares about this problem space. Maybe I should finally write that blog post on CRDTs and how to implement them yourself following the OpSets spec.
If you're on a Node.js/React stack, we highly recommend using the combination of OT-JSON0 [1] and ShareDB [2], two excellent libraries. OT-JSON0 lets you perform operational transforms on any JSON-serializable structure pretty intuitively, and ShareDB handles synchronizing it between multiple clients and resolving conflicts. Building your own is going to be a pain, so unless your core business is a text editor like TinyMCE, it's probably best to stand on the shoulders of giants.
Another approach that we didn't end up using is Figma's: especially if you're working on anything other than text editing, ask if you actually want to use operational transform. Something simpler might be good enough -- in Figma's case, they use "last write wins" because they were able to break the document into small enough, atomic elements. [3]
[1] https://www.npmjs.com/package/ot-json0
[2] https://www.npmjs.com/package/sharedb
[3] https://www.figma.com/blog/how-figmas-multiplayer-technology...
We also have a custom back-end that's MySQL that may have changed how it work a bit
To do something like that in arbitrary HTML you wind up locking at the top-level-block boundaries. Locking sounds great as an engineer but it leads to a garbage user experience.
It’s working great for us in beta, we’ve recently shipped multiplayer to our users and overall it’s very stable. With a lot more in store soon, please check it out!
"This is the exact "split node" scenario I described earlier; applying bold near the start of a text node necessarily has to split the text node into three parts (before, bold, and after)."
Not sure why you split it up into sections. In my CRDT implementation, I would add meta-data to each character, with the boolean property which is either bold or not. It's certainly cumbersome to keep the cursor at the right place when inserts are being made, but it's doable. https://pierrehedkvist.com/posts/1-creating-a-collaborative-...
I personally never understood how OT actually works, clearly, Google Docs and others find it useful. But to me, CRDT has more solid proof and reasoning behind it, and it is easier to comprehend. https://medium.com/@pierrehedkvist/creating-a-collaborative-...
The best CRDTs do treat each character separately (as I think I mentioned at one point?). But not all of them - the video and my example is an example of one that doesn't.
It's also very difficult to support arbitrary nested trees with a per-character data type, which leads to the compromises I talked about.
At the very least, I would expect different JSON data types to use different CRDTs. For a collaborative model, I would expect the semantics of the data model to be reflected in the choice of CRDTs for different substructures in the JSON.
Our use-case is offline-editing of documents with an eventual sync-with-yourself-online. It's mostly there as a sync tool, not as a p2p colalb editing. Unless you count yourself as a peer, I guess!
We store a document in local storage which is the result of `Automerge.save(automergedoc) => serializable string`. That can be loaded with `Automerge.load(s) => doc`.
"Changes" are a first-class concept in automerge (makes sense, I guess) so you can do
before = Automerge.from({..some doc..})
after = Automerge.change(before, "optional commit msg", (doc) => doc.hello = "world);
Those `[changes]` are what we try and send to a server and keep them in a `Set()` for each document (background sync, service worker, etc make a nice experience.
This is all wrapped up in Redux, and a middleware that captures the changes, and a reduxStore subscriber that puts the document back into local storage after any changes.
It is for the application programmer virtually transparent, and so far we've yet to find a fault with it.
I'm sure I'll come to regret making "changes" my principle data type, as the server implementation just sees serialized blobs of data, and has no concept of the structure of the document. That's solveable if I need it ever, because there's a protcol compatible implementation in Rust, and I could always use the JavaScript one on the server too, just haven't needed yet.
The serialization is also quite large, in the order of kilobytes for what are actually quite small docs, but they do contain the original commit messages too, and the Automerge team is planning to release an optimized serialization format early this year, which they say will be especially useful for fields with lots of changes, such as text fields, which currently pay a heavy toll in terms of tracking `[changes]`. Fortunately that also doesn't affect me.
I can also +1 some of the advice to keep your whole document in a CRDT. We use React+Redux, but since React Hooks made stateless functional components a reality, we felt it was appropriate to use React exclusively for the UI state, and track only document states in Redux reducers. It feels light-weight and sustainable, although we're only about a month and 5k LOC into the project. Time will tell I guess.
At some point your set of changes grows too large or you want to trim it to, say, a few weeks or months. Afaik that isn't possible yet without losing the ability to merging later on.
> In OT, every user action is broken down into one or more operations. These operations are transmitted between clients along with their baseline reference; if two users perform actions at the same time, incoming operations must be transformed to include the local operations that have happened since that baseline. They are then applied locally and form the new baseline.
> This constant transformation of operations turned out to have too many edge cases where clients were found to not produce the same baseline (the "wrong" papers above). When that happens, the clients will never converge on the same result and break the fundamental assumption of collaboration.
And that’s exactly right. It’s fairly easy to have an OT system that is very vulnerable, because clients can cheaply generate change sets that are extremely computationally expensive on the server side. I’ve seen a system where a single mobile phone could, in a few seconds, lock up the synchronisation server for days.
As for the last question, I think the later posts will get to that.
In complex models it is symptomatic of a larger issue with complexity in CRDTs; the post was already quite long and I didn't want to repeat any more of the research I'd linked to.
The post is a good introduction to OT and CRDT, but is very light on actual trade-offs and seems to end with a gut-feeling conclusion, when the title promised “trade-offs between”.
I was driving at CRDT not being capable enough for arbitrary HTML structures, and giving a quick summary of what was an extended multi-week research process.
Have you heard of CryptPad ? Not exactly peer-to-peer but has encryption so that the server sees nothing.
https://tweetnacl.js.org/ https://github.com/dchest/tweetnacl-js/wiki/Examples
I'm researching the same thing.
Any tutorial on OT implementation? Especially, I need to handle structured data, like json.
http://archagon.net/blog/2018/03/24/data-laced-with-history/
I wonder if it's better understood now and can cost less R&D time.
After 8 years of working on this, I have changed my thoughts:
- The correct algorithm is not always the correct user experience.
- End-to-end encryption is too important to not have.
- Offline support is great, but it behaving consistently is more important than it behaving "intently".
- Biggest pain points can most easily be solved at the editing layer, not data layer.
As a result, OT gets thrown out the door immediately.
I built the most popular CRDT powered database on the market (https://github.com/amark/gun, 11K+ stars, 11M+ monthly installs), but have some harsh words for CRDT obsessed people:
CRDTs are great, but if you create an infinitely complex one to handle "every word editing operation" it'll actually result in an inferior user experience.
As such, for example, GUN supports lock-free concurrent operations on any depth of data in a graph, but keeping text/strings behavior atomic is way more important than having built-in automatic string merges.
Why? It is much simpler to build a correct text/string CRDT on top of a predictable, stable, graph CRDT that is understandable.
Another example is, in our blog editing tools, despite having spent years researching & implementing (+ others in our community) precise character-by-character CRDT resolution schemes, I found I personally had a much better offline & local first user experience with a predictable per-paragraph sync scheme.
This is a stupid simple approach, but what it means is that I as a user, can easily predict whats going to happen, so if I'm offline I know I should just copy a new paragraph and fiddle with things there, cause it isn't gonna get "auto delete regrammar merged".
Generally speaking, me and colleagues don't "fight" over the same paragraph, we're usually concurrently writing different "sections" at the same time, it is pretty rare to grammar fix their edit same paragraph as they're typing it - that is also just kinda, rude looking.
Anyways, finally, is that the majority of text styling and DOM edge cases can be handled by having a deterministic canonical DOM hierarchy that always gets applied at the editing layer, BEFORE any CRDT operations even occur.
So for instance, re-arrange the DOM tree such that <i> is always inside <u> inside <b>, or something like that.
We built this into a library called normalize, and it instantly eliminated so much complexity, especially at the CRDT level. Ping me if you want a demo of this library.
Finally, for everyone else, we also built an INTERACTIVE CARTOON EXPLAINER of an extremely basic text CRDT to help others understand the more detailed concepts:
The model we've chosen is fairly agnostic to whether OT or CRDT is used to collaborate, as I'll expand on in the second post, so if we see an opportunity to switch to a CRDT-based solution we'll certainly jump on it!
You only need to normalise things like bold/italic/underline when using a browser DOM, every collaborative rich text model I've seen represents formatting as unordered attributes which is much easier to collaborate on.
It is difficult to get brief clear details about how gun.js works. There are distracting or simple documents, discussions about high level ideas and tangentially-related topics. In some cases 'worse is better' yes but it sets a tone that the project is hiding internal problems of implementation or can not easy explain its own design.
The transparency of gun.js enterprise organizations also raises questions. Are people on your team related to you? Do you pay yourself and team and open source contributors?
They also like the math & science behind it, some investors do DD, some don't.
You're tone is pretty assuming, smug, and insulting.
It is running in production with millions of people, yes there are some hiccups, but surviving & we're improving it to scale even more.
I rebuild GUN from scratch in 30min on stage, that is how little/simple GUN is:
https://gun.eco/docs/Porting-GUN
Do I pay myself? Lol. Yes. No, I do not pay OSS, but yes people contribute regardless, strangers help me, my kids help me, investors help me, family & friends help me.
BTW, the name makes it almost impossible to search for info about GUN.
"Servers" act as WebRTC bootstrapping signals, storage backups, relay/routing, etc., and you can have as many of them as you want (no need to be centralized).
True. `gunDB` tag should help a little.
For example, one peer change a property value and the other peer deletes it.
This cartoon explains it:
https://gun.eco/distributed/matters.html
It is a vector + timestamp + lexical sort.
A delete is changing a value to `null`, it would lose (I assume you are asking if/when these 2 changes happen at the exact same microsecond time, conflicting?) as is it has a lower lexical rank.
The cartoon explanation do not tackle those terms.
Let's say our state have an array like ['a','b'].
What about if Peer-A splice the first element (0) which results in ['b'] and Peer-B wants to mutate 'a' to 'A' which results in ['A','b'] and they both make the mutation at the same millisecond?
1. An atomic Array
2. Fixed index Array
3. Linked list
Now rather than not knowing what magic is going to happen, app developers know what to expect in advance.
So atomic would choose one or the other, not a combined result.
Fixed array 2nd item to 1st which nulls 2nd and makes 1st b, simultaneously also makes 1st A. Cause lower case b is lexically larger than A, you'd get [b, null].
Linked list theoretically could handle it as you suggest.
If not, any paper or doc that explain how to implement it with gun?
@nmaro has some pretty good stuff.
The cartoon explainers gives an overview.
But you'd probably want to do RGA algorithm or one of the newer ones.
Martin Kleppmann has a pretty good talk with bunch of paper references: