To be honest, I'm really surprised they let PWAs have notifications. That's literally the only use case we have on that entire page and it actually works.
I wouldn't even call this a Turing test, in the traditional sense. This commenter claims to have recently read several papers on this topic, and I'm curious what papers those are.
If these papers don't exist, this commenter's opinions should be disregarded, irrespective of how their comment was generated.
Just use OT like normal people, it’s been proven to work. No tombstones, no infinite storage requirements or forced “compaction”, fairly easy to debug, algorithm is moderate to complex but there are reference open source implementations to cross check against. You need a server for OT but you’re always going to have a server anyway, one extra websocket won’t hurt you. We regularly have 30-50k websockets connected at a time. CRDTs are a meme and are not for serious applications.
Author here, I did not specifically mention OT in the article, since our main focus was to help people understand the downsides of the currently-most-popular system, which is built on CRDTs.
BUT, since you mention it, I'll say a bit here. It sounds like you have your own experience, and we'd love to hear about that. But OUR experience was: (1) we found (contrary to popular belief) that OT actually does not require a centralized server, (2) we found it to be harder to implement OT exactly right vs CRDTs, and (3) we found many (though not all) of the problems that CRDTs have, are also problems in practice for OT—although in fairness to OT, we think the problems CRDTs have in general are vastly worse to the end-user experience.
If there's interest I'm happy to write a similar article entirely dedicated to OT. But, for (3), as intuition, we found a lot of the problems that both CRDTs and OT have seem to arise from a fundamental impedance mismatch between the in-memory representation of the state of a modern editor, and the representation that is actually synchronized. That is, when you apply an op (CRDT) or a transform (OT), you have to transform the change into a (to use ProseMirror as an example) valid `Transaction` on an `EditorState`. This is not always easy in either case, and to do it right you might have to think very hard about things like "how to preserve position mappings," and other parts of editor state that are crucial to (say) plugins that manage locations of comment marks or presence cursors.
With all of that said, OT is definitely much closer to what modern editors need, in my opinion at least. The less-well-known algorithm we ended up recommending here (which I will call "Marjin Collab", after its author) is essentially a very lightweight OT, without the "transformation" step.
I feel we were quite lucky back in 2015 when we started rewriting CKEditor with RTC as a core requirement. At the time, OT seemed like the only viable option, so the choice was simple :)
What definitely helped too was having a very specific use case (rich-text editing) which guided many of our decisions. We focused heavily on getting the user experience right for common editing scenarios. And I fully agree that it's not just about conflict resolution, but also things like preserving position mappings. All these mechanisms need to work together for the experience to make sense to the end user.
One clear issue with OT that we still face today is its complexity. It's nearly 8 years since we launched it, and we still occasionally run into bugs in OT – even though it sits at the very core of our engine. I remember seeing a similar comment from the Google Docs team :D
> (1) we found (contrary to popular belief) that OT actually does not require a centralized server
In theory, yes, but in practice, any OT that operates without a central server (or master peer) essentially ends up being a CRDT. A CRDT is a subset of OT, specifically one that adds the requirement of P2P support.
> (2) we found it to be harder to implement OT exactly right vs CRDTs
I would say that each has its own complexity in different areas. CRDT's complexity lies in its data structure and algorithm, while OT's lies in its sync engine (since it must handle race conditions and guarantee deterministic ordering). In my opinion, OT is simpler overall. Hopefully DocNode and DocSync will make OT even easier.
> (3) we found many (though not all) of the problems that CRDTs have, are also problems in practice for OT
Oh, definitely not! OT has many benefits[1]. I think the misconception stems from the common belief that OT should be positional, rather than id-based. In the first case, operations are transformed on other operations. In the second case, operations can also be transformed on the current document (O(1)), eliminating the problems commonly associated with OT. This is the approach I use in DocNode.
> the problems CRDTs have in general are vastly worse to the end-user experience.
Having a central server is not necessary, but we have one anyway and we use it, especially if you have a permissions system. It lets us use the "Google wave" algorithm which vastly simplifies things.
> This is not always easy in either case, and to do it right you might have to think very hard about things like "how to preserve position mappings," and other parts of editor state that are crucial to (say) plugins that manage locations of comment marks or presence cursors.
Maintaining text editor state is normal. Yes you do need to convert the OT messages into whatever diff format your editor requires (and back), but that's the standard glue code.
The nice thing about OT is that you can just feed the positions of marks into the OT algorithm to get the new positional value. Worst case, you just have the server send the server side position when sending the OT event and the client just displays the server side position.
I always mentally slotted prosemirror-collab/your recommended solution in the OT category. What’s the difference between the “rebase” step and the “transformation” step you’re saying it doesn’t need?
Great question. Matt has a comment about this here, and he has an actual PhD on the subject! So rather than doing a worse job explaining I will leave it to him to explain: https://news.ycombinator.com/user?id=mweidner
One way to minimize impedance mismatch is to work with DOM-like or JSON-like structures mostly immune to transient bugs, which I am doing currently in the librdx project. It has full-CRDT RDX format[1] and essentially-JSON BASON[2] format. It does not solve all the problems, more like the set of problems is different. On the good side, it is really difficult to break. On the bad side, it lacks some of the rigor (esp BASON) that mature CRDT models have. But, those models are way more complex and, most likely, will have mismatching bugs in different implementations. No free lunch.
> The less-well-known algorithm we ended up recommending here (which I will call "Marjin Collab", after its author) is essentially a very lightweight OT, without the "transformation" step.
You talk about "rebasing" changes in the article. Does that not imply a "transformation" step?
The rebasing step is indeed a transformation. Some info in the "rebasing" link here [1].
Unlike traditional Operational Transformation, though, there are no "transformation properties" [2] that this rebasing needs to satisfy. (Normally a central-server OT would need to satisfy TP1, or else users may end up in inconsistent states.) Instead, the rebased operations just need to "make sense" to users, i.e., be a reasonable way to apply your original edit to a slightly-further-ahead state. ProseMirror has this sort of rebasing built in, via its step mappings, which lets the collaboration-specific parts of the algorithm look very simple - perhaps deceptively so.
Author here, just chiming in to say that Matt has an actual PhD on the subject so rather than explain it worse, I will just let him say the probably-actually-correct thing here.
> CRDTs are a meme and are not for serious applications.
You don't think Figma is a serious application?
By all means, use OT. I worked on OT software for many years - and my work on OT types, ShareJS and ShareDB is still in production all over the place. But I don't think there's anything you can do with OT that you can't do just as well with CRDTs.
The only real benefit of OT is that its simpler to reason about. Maybe that's enough.
I don't know where this popular belief came from. The Figma blog literally says "Figma isn't using true CRDTs"[1].
> The only real benefit of OT is that its simpler to reason about.
That's incorrect. When you free yourself from the P2P restriction that CRDTs are subject to, there's a huge amount of metadata you can get rid of, just to mention one benefit.
> I don't know where this popular belief came from.
It may be worth reading the whole paragraph of the blog you referenced...
> Figma isn't using true CRDTs though. CRDTs are designed for decentralized systems where there is no single central authority to decide what the final state should be. There is some unavoidable performance and memory overhead with doing this. Since Figma is centralized (our server is the central authority), we can simplify our system by removing this extra overhead and benefit from a faster and leaner implementation.
> It’s also worth noting that Figma's data structure isn't a single CRDT. Instead it's inspired by multiple separate CRDTs and uses them in combination to create the final data structure that represents a Figma document (described below).
So, it's multiple CRDTs, not just one. And they've made some optimizations on top, but that doesn't make it not a CRDT?
> When you free yourself from the P2P restriction that CRDTs are subject to...
CRDT stands for "Conflict-free replicating data type". They're just, any data type with an idempotent, commutative merge function defined on the entire range of input. Technically, CRDTs have nothing to do with networks at all.
The simplest "real" CRDT is integers and the MAX function. Eg, you think of an integer. I think of an integer. We merge by taking the max of our integers. This is a CRDT. Would it have eventual consistency? Yes! Would it work in a server-to-client setup? Of course! Does it need any metadata at all? Nope! It doesn't even need versions.
There's no such thing as a "P2P restriction". Anything that works p2p also works server-to-client. You can always treat the server and client as peers.
> there's a huge amount of metadata you can get rid of, just to mention one benefit.
Can you give some examples of this metadata? In my experience (10-15 years with this stuff now), I've found you can get the same or better performance out of CRDTs and OT based systems if you're willing to make the same set of tradeoffs.
For example, OT has a tradeoff where you can discard old operations. The cost of doing so is that you can no longer merge old changes. But, you can do exactly the same thing in CRDTs, with the same cost and same benefits. Yjs calls this "garbage collection".
In my own eg-walker algorithm, there's 3 different ways you can do this. You can throw away old operations like in OT based systems - with the same cost and benefit. You can keep old metadata but throw away old data. This lets you still merge but you can't see old versions. Or you can keep old edits on the server and only lazy-load them on the client. Clients are small and fast, and you have full change history.
CRDTs generally give you more options. But more options = more complexity.
I'm no p2p idealist. Central servers definitely make some things easier, like access control. But CRDTs still work great in a centralised context.
Ok, replace "P2P restriction" with "idempotent, commutative restriction".
> For example, OT has a tradeoff where you can discard old operations. The cost of doing so is that you can no longer merge old changes.
Why wouldn’t you be able to? My server receives operations, applies them to the document, and discards them. It can receive operations as old as it wants.
___
> Can you give some examples of this metadata?
Yes, it depends on the CRDT, but if we're talking about lists or tree structures with insert and delete operations, these can come in the form of thombstones, or operation logs, or originRight or originLeft, or DAG. Even with a garbage collector, the CRDT needs to retain some of this metadata.
Yes, you can optimize by not bringing it into memory when it’s not needed. But they’re still there, even though they could be avoided entirely if you assume a central server that guarantees a deterministic ordering of operations.
> Why wouldn’t you be able to? My server receives operations, applies them to the document, and discards them. It can receive operations as old as it wants.
OT needs to do operation transformation. If you get passed old operations, you need to transform them before they can be applied. This requires keeping extra data around. I mean, this is entirely the point of the metadata you describe in the second part of your comment:
> these can come in the form of thombstones, or operation logs, or originRight or originLeft, or DAG. Even with a garbage collector, the CRDT needs to retain some of this metadata.
> But they’re still there, even though they could be avoided entirely if you assume a central server that guarantees a deterministic ordering of operations.
A central server doesn't remove the need for this data though! Lets assume a completely deterministic ordering of operations on the server, like Jupiter. If the server is at version 1000, and I send the server an operation at version 900, the server needs to use information about operations 900-1000 to be able to apply the change. This is true in Jupiter OT - which uses the actual operations. Or in Yjs or Diamond Types or any other collaborative text editing system. We need some of that information to figure out how to transform the incoming change and order it correctly.
At least, I've never seen or heard of any scheme which doesn't need some data like this.
> A central server doesn't remove the need for this data though!
Yes, it's possible. The problem is that we're using different definitions of what OT means. This conversation has converged on the same point we started in another thread; I suggest we continue it there:
Are there any major libraries for OT? I've been looking into this recently for a project at work, and OT would be completely sufficient for our use case, and does look simpler overall, but from what I could tell, we'd need to write a lot of stuff ourselves. The only vaguely active-looking project in JS at least seems to be DocNode (https://www.docukit.dev/docnode), and that looks very cool but also very early days.
Author here. I think it depends what you're doing! OT is a true distributed systems algorithm and to my knowledge there are no projects that implement true, distributed OT with strong support for modern rich text editor SDKs like ProseMirror. ShareJS, for example, is abandoned, and predates most modern editors.
If you are using a centralized server and ProseMirror, there are several OT and pseudo-OT implementations. Most popularly, there is prosemirror-collab[4], which is basically "OT without the stuff you don't need with an authoritative source for documents." Practically speaking that means "OT without T", but because it does not transform the ops to be order-independent, it has an extra step on conflict where the user has to rebase changes and re-submit. This is can cause minor edit starvation of less-connected clients. prosemirror-collab-commit[5] fixes this by performing the rebasing on the server... so it's still "OT without the T", but also with an authoritative conflict resolution pseudo-T at the end. I personally recommend prosemirror-collab-commit, it's what we use, and it's extremely fast and predictable.
If you just want something pedogocically helpful, the blessed upstream collaborative editing solution for CodeMirror is OT. See author's blog post[1], the @codemirror/collab package[2], and the live demo[3]. In general this implementation is quite good and worth reading if you are interested in this kind of thing. ShareJS and OTTypes are both very readable and very good, although we found them very challenging to adopt in a real-world ProseMirror-based editor.
When I was starting my research into collaborative editing as a PhD student 20+ years ago, rebase-and-resubmit was well known. It was used in one Microsoft team collab product (I forgot the name). It is 100% legit algo except intermittently-connected clients may face challenges (screw them then).
Unless you have to support some complicated scenarios, it will work. I believe Google Docs initially used something of the sort (diff-match-patch based). It annoyed users with alerts "lets rebase your changes", esp on bad WiFi. So they borrowed proper OT from Google Wave and lived happily since (not really).
One way to think about it: how many users will your product have and how strange your data races / corner cases can get. At Google's scale, 0.1% users complaining is a huge shit storm. For others, that is one crazy guy in the channel, no biggie. It all depends.
First of all, thanks for chiming in! I wish someone would collect stuff like this and write it down in some sort of "oral history of collab editing."
Second of all, I actually think we're more aligned than it seems here. What we're really advocating for is being super clear about what your end-user goals are, and deriving technology decisions from them, instead of the reverse. Our goals for this technology are (1) users should be able to predict what happens to their data, (2) the editor always run at 60fps, and (3) we are reasonably tolerant of transient periods of disconnection (up to, say, 30s-1m).
Because of (1) in particular, a lot of our evaluation was focused on understanding which situations users would be unable to predict what was going to happen to their data. This is only our own experience, but what we found (and the impetus for part 1 of this series) is that almost 100% of the time, when there is a direct editing conflict, users interpret the results of the dominant CRDT and OT implementations as silently corrupting their data. So, the name of the game is to decrease the likelihood of direct editing conflicts, e.g. presence carets in the live-collab case. In particular, we did not notice a meaningful difference between how users view reconciliations of OT and CRDT implementations.
Since our users could not tell the difference, and in fact viewed all options as equally bad ("disastrous" as one user said), this freed us up to consider a much broader class of algorithms, including prosemirror-collab and prosemirror-collab-commit.
I know there is a rich history of why OT is OT, but our final determination was made pretty simple by the fact that the source of the majority of race conditions in our view come from the difficulty of integrating CRDTs and OT directly into modern editing stacks, like ProseMirror. As far as I am aware, prosemirror-collab-commit behaves as good or better on every dimension than, say, an OTTypes implementation would... and mostly that is because it is native to the expressive `Transaction` model of the modern editor. If we had to do interop I think we would have shipped something noticably worse, and much slower.
If you have a different experience I would love to hear about it, as we are perennially in the market for new ideas here.
> I wish someone would collect stuff like this and write it down in some sort of "oral history of collab editing.
I'd be very happy to contribute to this if someone wanted to do some storytelling.
I also interviewed Kevin Jahns, the author of Yjs several years ago to get his take on how Yjs works and how he thinks about it all [1]. The conversation was long but I very much enjoyed it.
> This is only our own experience, but what we found (and the impetus for part 1 of this series) is that almost 100% of the time, when there is a direct editing conflict, users interpret the results of the dominant CRDT and OT implementations as silently corrupting their data.
That's not been my experience. Have edits been visible in realtime? I think about it as if there's essentially 2 use cases where collaborative editing shows up:
1. Realtime collab editing. So long as both users' cursors are visible on screen at the same time, users are often hesitant to type at the same place & same time anyway. And if any problems happen, they will simply fix them.
2. Offline (async) collab editing. Eg, editing a project in git. In this case, I think we really want conflict markers & conflict ranges. I've been saying this for years hoping someone implements conflicts within a CRDT, but as far as I know, nobody has done it yet. CRDTs have strictly more information than git does about what has changed. It would be very doable for a CRDT to support the sort of conflict merging that git can do. But, nobody has implemented it yet.
Sorry, I see why this was confusing. What I'm saying is that because users perceive the results of OT, CRDTs, prosemirror-collab, etc. as data corruption, they require presence carets as a UI affordance, to steer them away from direct edit conflicts.
If you can't have presence carets, yes... likely best to have a diff view. And in our case, we use git/jj for this, rather than CRDTs.
For the "history of" stuff... in spite of the fact that we have our disagreements, I actually think it would be very nice to have Kevin and everyone else on the record long-form talking about this. Just because I am a non-believer doesn't mean it wasn't worth trying!
> For the "history of" stuff... in spite of the fact that we have our disagreements, I actually think it would be very nice to have Kevin and everyone else on the record long-form talking about this. Just because I am a non-believer doesn't mean it wasn't worth trying!
I'd enjoy that too. Hit me up if you wanna chat about this stuff - I'd enjoy the opportunity to convince you over video. Maybe even recorded, if people are interested in that.
> Maybe even recorded, if people are interested in that.
I would be. IIRC you interviewed the Yjs creator years ago in a YT video I watched? This post has been fun spicey discourse not withstanding. It's not often a lot of the people in the collab space are together in the same spot, and the clash of academics and product builders is valuable.
As an aside I'd put Marjin in the product builder side. A lot of people dabble in collab algorithms and have a hobby editor on the side, but he created and maintains the most popular rich text editor framework on the planet(made up statistic, but seems true!).
In our case, we're not using a text editor, but instead building a spreadsheet, so a lot of these collab-built-into-an-editor are, like you say, pedagogically useful but less helpful as direct building blocks that we can just pull in and use. But the advice is very useful, thank you!
Interesting! I am building a spreadsheet and the next few months will be building the collaborative side of it. I think many of the things that work for text don't necessarily translate for spreadsheets.
We made a spreadsheet on top of OT several years ago. Most OT related documentation doesn't talk about how to do this. But it worked pretty well for us.
Author of DocNode here. Yes, it’s still early days. But it’s a very robust library that I don’t expect will go through many breaking changes. It has been developed privately for over 2 years and has 100% test coverage. Additionally, each test uses a wrapper to validate things like operation reversibility, consistency across different replicas, etc.
DocSync, which is the sync engine mainly designed with DocNode in mind, I would say is a bit less mature.
I’d love it if you could take a look and see if there’s anything that doesn’t convince you. I’ll be happy to answer any questions.
I've looked through the site, and right now it's probably the thing I'd try out first, but my main concerns are the missing documentation, particular the more cookbook-y kinds of documentation — how you might achieve such-and-such effect, etc. For example, the sync example is very terse, although I can understand why you'd like to encourage people to use the more robust, paid-for solution! Also just general advice on how to use DocNode effectively from your experience would be useful, things like schema design or notes about how each operation works and when to prefer one kind of operation or structure over another.
All that said, I feel like the documentation has improved since the last time I looked, and I suspect a lot of the finer details come with community and experience.
Thanks! I've recently made some improvements to the documentation. I agree the synchronization section could be improved more. I'll keep your feedback in mind.
If you'd like to try the library, feel free to ask me anything on Discord and I'll help you.
Agreed. In my limited experience, conflict resolution rules are very domain specific, whereas CTDTs encourage a lazy attitude that "if it's associative and commutative it must be correct".
Why should we presume it’s an AI description? The writing seems reasonable enough. Some people are more naturally inclined towards articulate writing than others (seems like projection) and furthermore the OP claims to be a screenwriter.
AI helped me write the documentation because it does a better job than I ever could. I honestly wish I’d had AI to help me write my screenplay ten years ago.
reply