I read both parts. Well written, I agree with a lot of stuff.
I am long-time CKEditor dev, I was responsible for implementing real-time collaboration in the editor and the OT implementation.
Regarding the first part of your article. Guess what - CKEditor would output "" :). And even better, if the user who deleted all does undo, you'd get "u" where it was typed originally.
However, I fully agree, that for every algorithm, you will be able to find a scenario where it fails to resolve conflict in a way expected by the user. But we cannot ask user to resolve a conflict manually every time it happens.
Offline editing, as you correctly observed, is more difficult, because the conflicts pile up, and multiple wrong decisions can result in a horrifying final result. I fully agree, that this is not only an algorithmic problem but also a UX problem. Add to this, that in many apps, you will also have other (meta)data that has to be synced too (besides document data).
CKEditor is, in theory, ready for offline editing. From algorithm POV, offline is no different than very very very slow connection (*). In the end, you receive a set of operations to transform against other set of operations. However, currently we put the editor in read-only state when the connection breaks. We are aware, that even if all transformations resolve as expected, then the end result may still be "weird". And even if the end result is actually as expected, the amount of changes may be overwhelming to a person who just got the connection back, so it still may be good to provide some UI/UX to help them understand what happened.
(*) - that is, unless the editing session on the server ended already, and, simply saying, you don't have anything to connect to (to pull operations from).
Regarding OT. I have a feeling that one mistake most people make, is that they take OT as it is described in some papers or article, and don't want to iterate over this idea. To me, this is not just one algorithm, rather an idea of how to think about and mange changes happening to the data.
For CKEditor, from the very beginning, we were forced to innovate over typical OT implementations. First of all we focused on users intentions. Second of all, we needed to adapt it to tree data structure. These challenges shaped my way of thinking - OT is "an idea", you need to adapt it to your project. Someone here asked if there's library for OT, because they want to use it for spreadsheets. I'll say -- write it on your own and adapt it to spreadsheets. You'll discover that maybe you don't need some operations, or maybe you need new operations dedicated for spreadsheets. This is what we ended up doing. @Reinmar already posted this link here, but we describe our approach here: https://ckeditor.com/blog/lessons-learned-from-creating-a-ri....
Circling back to your example with typing and removing whole sentence. This is how you innovate over OT. To us, such deletion is not deleting N singular characters starting from position P. The intention is to remove some continuous range of text. If someone writes inside the range, it just changes the boundary of stuff to remove, but surely we don't want to show some random letters after the deletion happens. We account for that and make modifications in our OT implementation.
Similarly with positions in document. In CKEditor, you can use LivePositions and LiveRanges, which are basically paths in tree data structure. Every position is transformed by operation too. Many features we have base on that.
So, my take here is -- don't bash OT because you based your experience on some simple implementations. Possibly the same is with Yjs. Don't bash CRDTs because Yjs is doing something badly?
And some final words regarding the second part.
We also follow the same pattern as your diagram shows in "How the simple thing works" section. As I was reading through the article, and looking at provided examples, it's hard for me not to think, that what's happening is some kind of an OT-variant, maybe simplified, or maybe adapted to some specific cases. But there are strong similarities between what you described and CKEditor 5, and we use OT. Like, looking at this from top-level view, I could say, "well, we do the same". We have the same loop with conflict resolution, we just call "rebase" a "transformation", and instead "steps" we have "operations".
Also, you say it is 40LOCs, but how much magic happens in `step.apply()`? How much the architecture was made to make it possible? Even Marijn makes this comment here: https://news.ycombinator.com/item?id=47409647.
For comparison, this is CKEditor's file that includes the OT functions to transform operations: https://github.com/ckeditor/ckeditor5/blob/master/packages/c.... It's 2600LOCs (!), but at least most of it are comments :). Again, the basic idea for OT is very simple (and this implementation could be simpler, we also learned a lot in the process). It's up to you how much you want to delve into solving "user intention" issues.
I guess that you can argue for both sides :). But they are just different solutions. Basing on my experience and on what I read it is simply unfair saying that one is incorrect and other is correct (or one is better and the other is worse).
> OT is very simple to implement, but needs a server (...)
Well, OT in general does not need the server but server-less implementations are more complex (more transforming functions to write, except of "inclusion transformation" you also have to write "exclusion transformation" algorithms).
I also wouldn't say that "OT is very simple to implement" - it is in it's base form, for linear data, with the server in the network. But every enhancement brings a lot of complexity.
> (...) if two keys depend on each other, and one user sets one key, and the other user sets another key, and the document is now invalid, you'd need the engine to be able to reconcile at a higher level?
I am not sure if I understand you correctly here, but it's not really that. Could you give me a more concrete example?
The kind of problems for extra types are, for example: user A changes a paragraph to a list item and user B splits it. As a result you'd like to have two list items instead of a list item followed by a paragraph. This is impossible if you don't give more semantic meaning to the operations.
There are other problems though, as you mentioned - with invalid document. For example, you have this kind of a list:
* Foo
__* Bar
__* Baz
User A outdents "Bar" and user B indents "Baz" creating a list like this:
* Foo
* Bar
____* Baz
In CKE5 this is an incorrect list (we don't allow indent differences bigger than one). This cannot be fixed through OT so we fix it in post-fixers which are fired after all the changes are applied.
These content-preservation edge cases weren't possible to solve with what was available (at least at the time we started the project).
Even apart of that, ottypes/json0 was lacking some basic things, like moving objects. I see they came up with a new implementation recently (https://github.com/ottypes/json1) and it allows moving objects. Maybe the new implementation would solve some problems. However, it is in "preview" state, and the last update was 2 months ago, so I am not sure how well it will be maintained.
Also, there are some edge cases when transforming ranges (which CKE5 use to represent, for example, comments on text or content created in track changes mode). I don't want to bury you in difficult to understand examples but if you are interested you might want to check the examples listed in inline codes for this function: https://github.com/ckeditor/ckeditor5-engine/blob/master/src....
As far as Quill.js is concerned, it is based on the linear data model, which brings limitations when it comes to complex features. Transformation algorithms for linear data models are much simpler and there are more implementations and articles in this area. Everything depends on your needs. If Quill.js features set and functionality fit your needs then the solution you chose is correct.
With CKE5 however, we didn't want to go on any compromises. We needed complex structures for our features, and for having a powerful framework - to enable other developers to write whatever feature they want and have those features working in real-time collaboration. We wanted transformation algorithms which will handle all the edge cases. It is true, some of those cases are quite rare. And the old "10/90" mantra applies here, in this case "10% of use cases brings 90% of complexity". But those edge cases happen and we didn't want to disappoint our users.
I don't like "merge" word because it implies how the problem is solved. "Synchronise" would be better, as there is no merging, actually.
We use Operational Transformation, so all the changes are stored as operations (with their most important property being path - the position where the operation happened).
When a user comes online, they try to re-send all the operations that are buffered and not yet sent to the server. Then it is a matter of transforming these operations by the new operations that happened in the meantime (when the user was offline). Of course, the user also has to accept the new operations.
This is a bigger / more complex version of the basic problem of the real-time collaboration. During real-time collaboration with all users online you might need to transform your operation by maybe several other operations at most. When you go offline, it might be tens or hundreds of operations but the problem is basically the same, just bigger.
The quality of the transformation algorithms will make a huge role in how well the user intentions will be preserved.
"Platform is ready" means that the theory behind our solution is correct and that we checked some moderately complex scenarios.
Edit: still, the base scenario is that the users write "online" and "offline" kicks in when you lose a connection (for hours, even). If we are talking about "everyone writes offline and then they magically merge" then I think this might be a totally different feature (and maybe even outside of the editor and inside the CMS).
> One way to solve this is to fallback to differential sync when syncing huge offline edits
This is another question -- does automatic syncing make sense for huge differences in users' contents? The answer might be no.
OTOH, isn't this a rare scenario? How perfect it has to be?How much of a compromise can the users accept? These are interesting questions which shows that creating this kind of software isn't easy -- both from technical and UX point of view.
I still need to read that one, though it looks interesting (yes, I only got through the introduction and summary :)). Let's keep in mind that the authors already wrote several papers on OT (also ones that we based CKE5 on) -- so they have vast knowledge in the subject but may also favor one technology over the other. As much as I'd like to read that OT was the good choice I also want to be cautious in this regard :).
Of course, it depends on the collaborative editing solution. When it comes to OT -- if the implementation is correct, it doesn't really matter how many operations are queued for synchronising. So, it doesn't really matter how long users were de-synced when creating their content. But this is only theory and it applies more to technical side as there might be some semantical problems (intention preservation).
I believe the same is true for CRDT but I am not sure.
So, on one hand - if the editor is working fine for small batch of changes, it should also work fine for big batch of changes. The reality is often more harsh, though, and full of edge case scenarios.
Congratulations on providing a serverless solution. How do you think CRDT would fare in a tree-structured data model? We went with OT and server architecture because it seemed more reliable. You can read more about our solution here https://ckeditor.com/blog/Lessons-learned-from-creating-a-ri....
Oh, don't get me started on modifications we needed to do to make undo look reasonable ... :) At first, we thought that undo is the same thing as collaboration but... nope.
The crucial difference is that with undo you have a context (old document state). With collaboration, you don't. So if both users put a character at the same position, in collaboration the order of output doesn't matter (and can't be solved really). In undo it does, because a user remembers what was the order of the letters before they made a change.
Graveyard is just another root, like the main one. So, the same way that all elements have the same position in the main root for all clients, elements in graveyard also have the same position for all clients. Thus, their path is kind of UUID for them.
As far as I remember shareJS was available when we started to work on tree-based OT. We researched it but it turned out to be too simple for what we wanted to achieve and there was no special handling for some edge cases that happens during collaborative editing.
We achieved something similar to shareJS functionality quite early, to be honest. What proved to be extremely difficult was all the extras to smooth up the user experience. We would have to (heavily) extend shareJS anyway, so it made more sense to go out with own solution, crafted for our needs.
Certainly, there are different use cases and different expectations. What we call "offline collaboration" can be seen as a special case of the real-time collaboration. In "offline collaboration" you also need to merge changes so you also need the conflict resolution. However, the longer you postpone merging, the better the conflict resolution algorithms need to be because the more conflicts you have. That's one of the reasons why we introduced new, semantic operations.
The other option is so-called change tracking or suggestion mode. That's on our roadmap as well and thanks to the platform we created it's not a big deal now. In fact, if we started with implementing suggestion mode (or "offline collaboration"), we might have ended up with an engine which is not ready for real-time collaboration. But once we have real-time collaboration we can now be quite certain about solving other issues.
Our first idea was to have four basic operations (insert, move, attribute, remove) and then have “deltas” (wrap delta, unwrap delta, merge delta, split delta) which were built using those operations and for which we described additional transformation cases. In this approach operation transformations were set in stone, but you could add your own deltas and provide your own transformations for them.
In the end, we concluded that users will see defining deltas and transformations as too complicated and won’t use it. Later, we also decided to drop deltas idea at all and we rewrote deltas into operations.
As an alternative solution, we provide the post-fixing mechanism. Your plugin can listen to all the changes done on the model and apply fixes if something has gone wrong. We used it for the famous "insert table row / insert table column" problem, to add the missing cell. This alternative is not as clean as explicitly providing a transformation algorithm but it is much easier to implement.
The problem with defining your own operations is that you need to write transformations against all the other operations which is a huuuuge work. It took as a few years and we still see some room for improvement.
It truly is the most interesting subject I've been working on yet. The fascinating thing about it is that it isn't a "solved" issue with one, correct solution, so you can feel like a 19th-century scientist at times :).
I am long-time CKEditor dev, I was responsible for implementing real-time collaboration in the editor and the OT implementation.
Regarding the first part of your article. Guess what - CKEditor would output "" :). And even better, if the user who deleted all does undo, you'd get "u" where it was typed originally.
However, I fully agree, that for every algorithm, you will be able to find a scenario where it fails to resolve conflict in a way expected by the user. But we cannot ask user to resolve a conflict manually every time it happens.
Offline editing, as you correctly observed, is more difficult, because the conflicts pile up, and multiple wrong decisions can result in a horrifying final result. I fully agree, that this is not only an algorithmic problem but also a UX problem. Add to this, that in many apps, you will also have other (meta)data that has to be synced too (besides document data).
CKEditor is, in theory, ready for offline editing. From algorithm POV, offline is no different than very very very slow connection (*). In the end, you receive a set of operations to transform against other set of operations. However, currently we put the editor in read-only state when the connection breaks. We are aware, that even if all transformations resolve as expected, then the end result may still be "weird". And even if the end result is actually as expected, the amount of changes may be overwhelming to a person who just got the connection back, so it still may be good to provide some UI/UX to help them understand what happened.
(*) - that is, unless the editing session on the server ended already, and, simply saying, you don't have anything to connect to (to pull operations from).
Regarding OT. I have a feeling that one mistake most people make, is that they take OT as it is described in some papers or article, and don't want to iterate over this idea. To me, this is not just one algorithm, rather an idea of how to think about and mange changes happening to the data.
For CKEditor, from the very beginning, we were forced to innovate over typical OT implementations. First of all we focused on users intentions. Second of all, we needed to adapt it to tree data structure. These challenges shaped my way of thinking - OT is "an idea", you need to adapt it to your project. Someone here asked if there's library for OT, because they want to use it for spreadsheets. I'll say -- write it on your own and adapt it to spreadsheets. You'll discover that maybe you don't need some operations, or maybe you need new operations dedicated for spreadsheets. This is what we ended up doing. @Reinmar already posted this link here, but we describe our approach here: https://ckeditor.com/blog/lessons-learned-from-creating-a-ri....
Circling back to your example with typing and removing whole sentence. This is how you innovate over OT. To us, such deletion is not deleting N singular characters starting from position P. The intention is to remove some continuous range of text. If someone writes inside the range, it just changes the boundary of stuff to remove, but surely we don't want to show some random letters after the deletion happens. We account for that and make modifications in our OT implementation.
Similarly with positions in document. In CKEditor, you can use LivePositions and LiveRanges, which are basically paths in tree data structure. Every position is transformed by operation too. Many features we have base on that.
So, my take here is -- don't bash OT because you based your experience on some simple implementations. Possibly the same is with Yjs. Don't bash CRDTs because Yjs is doing something badly?
And some final words regarding the second part.
We also follow the same pattern as your diagram shows in "How the simple thing works" section. As I was reading through the article, and looking at provided examples, it's hard for me not to think, that what's happening is some kind of an OT-variant, maybe simplified, or maybe adapted to some specific cases. But there are strong similarities between what you described and CKEditor 5, and we use OT. Like, looking at this from top-level view, I could say, "well, we do the same". We have the same loop with conflict resolution, we just call "rebase" a "transformation", and instead "steps" we have "operations".
Also, you say it is 40LOCs, but how much magic happens in `step.apply()`? How much the architecture was made to make it possible? Even Marijn makes this comment here: https://news.ycombinator.com/item?id=47409647.
For comparison, this is CKEditor's file that includes the OT functions to transform operations: https://github.com/ckeditor/ckeditor5/blob/master/packages/c.... It's 2600LOCs (!), but at least most of it are comments :). Again, the basic idea for OT is very simple (and this implementation could be simpler, we also learned a lot in the process). It's up to you how much you want to delve into solving "user intention" issues.