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.
More recently, it's been designed so this is the case. Namespaces, enums, and the property constructor shortcut thing were all added relatively early on, before the philosophy of "just JS + types" had been fully defined.
These days, TypeScript will only add new features if they are either JavaScript features that have reached consensus (stage 3 iirc), or exist at the type system only.
There have been attempts to add type hints directly to JavaScript, so that you really could run something like TypeScript in the browser directly (with the types being automatically stripped out), but this causes a lot of additional parsing complexity and so nothing's really come of it yet. There's also the question of how useful it would even be in the end, given you can get much the same effect by using TypeScript's JSDoc-based annotations instead of `.ts` files, if you really need to be able to run your source code directly.
I've worked through the same process in SolidJS, which had the dynamic dependency tracking from the beginning.
I agree that not seeing reactivity in the type system can be irritating. In theory, you can wrap reactive elements in `Computed` objects (Angular's signals have this, I believe) so you can follow them a bit better, but the problem is that you can still accidentally end up with implicitly reactive values, so it only works as a kind of opt-in "here be reactivity" signal, and you can't guarantee that just because you can't see a `Computed`, that reactivity has been ruled out.
That said, I find I eventually built up a good intuition for where reactivity would be, usually with the logic that functions were reactive and single values weren't, kind of like thunks in other contexts. For me, at least, it feels much simpler to have this implicit tracking, because then I don't need to define dependencies explicitly, but I can generally see them in my code.
Yeah, the UX/DX of the turning these algorithms into something usable is really interesting, and something I didn't get to talk much about.
With the variations on the push algorithm, you do kind of need to know the graph topology ahead of time, at least to be able to traverse it efficiently and correctly (this is the topological sorting thing). But for pull (and therefore for push-pull), the dependencies can be completely dynamic - in a programming language, you can call `eval` or something, or in a spreadsheet you could use `indirect` to generate cell references dynamically. For push-pull specifically, when you evaluate a node you would generally delete all of its upstream connections (i.e. for each cell it depends on currently, remove that dependency) and then rebuild that node's connections to the graph while evaluating it.
Signals libraries are exactly where I found this concept, and they work basically like you describe. I think this is a big part of what makes signals work so well in comparison to, say, RxJS - they're basically the same concept (here's a new reactive primitive, let's model our data in terms of this primitive and then plug that into the UI, so we can separate business logic from rendering logic more cleanly), but the behaviour of a signal is often easier to understand because it's not built from different combinators but just described in "ordinary" code. In effect, if observables are monads that need to be wired together with the correct combinators, then signals are do-notation.
With your push-pull algorithm, were you considering that the graph had already been built up, e.g. by an earlier pull phase? And the push-pull bit is just for subsequent updates? If so, then I think I'm following :).
I've been working in the context of reactivity on the backend where you're often loading up the calculations "from scratch" in a request.
I agree with your monad analogy! We looked into using something like Rx in the name of not reinventing the wheel. If you build out your calculation graph in a DSL like that, then you can do more analysis of the graph structure. But as you said in the article, it can get complicated. And Rx and co are oriented towards "push" flows where you always need to process every input event. In our context, you don't necessarily care about every input if the user makes a bunch of changes at once; it's very acceptable to e.g. debounce the end result.
With push-pull, assuming you set up the dependency chain on pull, you need an initial pull to give you your initial values and wire up the graph, and then every time an update comes in you use the push phase to determine what should be changed, and the pull phase to update it consistently.
There's some great discussion over on lobste.rs (https://lobste.rs/s/2zk3oe/pushing_pulling_three_reactivity), but I particularly recommend this link that someone posted there to a post that covers much of the same topic but in a lot more detail with reference to various existing libraries and tools and how they do things: https://lord.io/spreadsheets/
Yours might go a little less into the details, but its really clear and I like the diagrams and explanation around glitch hazards. Please do follow up on your tangents if you have time.
I really enjoyed your post and was surprised to see it not posted here. I guess now I can leave the comment I wasn't able to leave on lobste.rs :)
The format made for good lunchtime reading -- the care you put into making it easily readable shows. Are the illustrations actually hand-drawn? Looking forward to the next part(s) that you hinted at!
The illustrations are hand-drawn on my tablet, and then converted to SVG and touched up via an incredibly laborious and probably fairly unnecessary process.
Not the author, but when I want to make diagrams like this, I usually use tldraw! It has a nice nearly-hand-drawn feel that's casual and approachable for these kinds of sketches.
> This way you never have content that is out of sync.
They can definitely go out of sync, particularly if something that isn't the editor or the AI changes the code (e.g. running shell commands or opening the file in a different editor and making changes there). I've had a whole load of issues with VSCode where there's been spurious edits all over the place that show up again even if I try and revert them, because every time the AI makes an unrelated edit, VSCode tries to reset the file to the version it thinks exists and then play the AI's edits on top.
Firstly, if you're doing those steps, you're building your own tutorial, not just following the exact steps in a manual provided with the software. The sample config won't be exact or perfect for your setup, so you'll need to say least figure out how to adjust it to your needs.
That said, I think you're still leaning things building IKEA-style software. The first time I learned how to program, I learned from a book and I tried things out by copying listings from the book by hand into files on my computer and executing them. Essentially, it was programming-by-IKEA-manual, but it was valuable because I was trying things out with my own hands, even if I didn't fully understand every time why I needed the code I'd been told to write.
From there I graduated to fiddling with those examples and making changes to make it do what I wanted, not what the book said. And over time I figured out how to write entirely new things, and so on and so forth. But the first step required following very simple instructions.
The analogy isn't perfect, because my goal with IKEA furniture is usually not to learn how to build furniture, but to get a finished product. So I learn a little bit about using tools, but not a huge amount. Whereas when typing in that code as a kid, my goal was learning, and the finished product was basically useless outside of that.
The author's example there feels like a bit of both worlds. The task requires more independent thought than an IKEA manual, so they need to learn and understand more. But the end goal is still practical.
But Anthropic can't be a winning bidder, can they? They're specifically saying they won't offer certain services that the US Gov wants. Therefore they de facto fail any bid that requires them to offer those services. (And from Anthropic's side, it sounds like they're also refusing to bid for those contracts.)
The first two things that spring to mind are pasties from the UK (which are not usually spherical but can get quite hemispherical), and the "UFO-Döner" from Germany (which are more oblate spheroids). Maybe by combining these ideas, your friend can get closer to their dream?
reply