GermanJablo

Interesting. I'm the author of DocNode, a library that does exactly what you're describing; it might be useful. https://docukit.dev

Cheers!

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:

https://news.ycombinator.com/item?id=47436249

The root of our misunderstanding or debate is clear: although CRDT is fairly well defined, I don’t think the same is true for OT.

What I have in mind is what I mentioned earlier:

OT can be id-based, in which case operations are transformed directly on the document, not on other operations.

This is exactly what I do in my library DocNode[1], which I describe as “id-based OT”.

With this model, it’s not even necessary to satisfy TP1. In fact, the concept T(o1, o2) doesn’t exist, because operations aren’t “transformed” against other operations, but against the document. Maybe the word “transform” is a bit misleading, and “apply” would be more appropriate. The problem is that there is still a slight transformation. For example, if a client inserts a node between nodes A and B, but by the time it reaches the server B has been deleted, the effective operation might become “insert between A and C”.

The server is append-only. The client has several options to synchronize with the server: rebasing, undo-do-redo, or overwriting the document.

Maybe I’m the one who shouldn’t describe DocNode as “[id-based] OT” and should instead coin a new term. Operational Application (OA)? Operations Without Transformation (OWT)? Operations Directly Transformed (ODT)? Operational Rebasing (OR)? Not sure. What would you recommend?

[1] https://www.docukit.dev/docnode

Citation needed

It seems to me the burden of proof is on you. You were the one who claimed that “CRDTs perform better than OT-based systems.” I’m simply denying it. My reasoning is that CRDTs require idempotence and commutativity, while OTs do not. What requirement does OT have that CRDT does not? Because if there isn’t one, then by definition your claim can’t be correct. And if there is one, that would be new to me, although I suspect you might be using a very particular definition of OT.

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.

Nowhere does it say it's multiple CRDTs. It says "isn't a single CRDT" and that "it's inspired by multiple separate CRDTs." A bit confusing, I agree.

By the way, I work at Figma.

But with some optimisation work, CRDTs perform better than OT based systems.

I read your paper and I think this is a mistake. You assume that OT has quadratic complexity because you're considering classic operation-based OT. But OT can be id-based, in which case operations are transformed directly on the document, not on other operations. This is essentially CRDT without the problems of supporting P2P, and therefore the best CRDT will never perform better than the best OT.

CRDTs let you scale your backend. OT (usually) requires server affinity. CRDT based systems are way more flexible. Personally I'd rather complex code and simpler networking than the other way around.

All productivity apps that use these tools in any way shard by workspace or user, so OT can scale very well.

If you don't scale CRDT that way, by the way, you'd be relying too much on "eventual consistency" instead of "consistency as quickly as possible."

(For anyone who's read the papers, I'm conflating OT == the old Jupiter-based OT algorithm that's popular in Google Docs and others.)

Similar to what I said before. I think limiting OT to an implementation that’s over three decades old doesn’t do OT justice.

The biggest evidence for collaborative editing is the immense popularity of Google Docs, Notion and Figma.

Just because programming code isn't a good use case for automated conflict resolution doesn't mean everything else isn't.

Just imagine non-technical people using git to collaborate on a report, essay, or blog post. It's never going to happen.

(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.

This is 100% correct.

____

https://www.docukit.dev/docnode#how-does-it-compare-to-yjs

You don't think Figma is a serious application?

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.

[1] https://www.figma.com/blog/how-figmas-multiplayer-technology...

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.

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.

Yes, the undo issue is a known bug in the website demo because it's messing with Lexical's undo functionality. It's not actually a DocNode bug. I'll fix it soon.

The feedback about the delay/pause button is also good, thanks!

I remember reading Part 1 back in the day, and this is also an excellent article.

I’ve spent 3+ years fighting the same problems while building DocNode and DocSync, two libraries that do exactly what you describe.

DocSync is a client-server library that synchronizes documents of any type (Yjs, Loro, Automerge, DocNode) while guaranteeing that all clients apply operations in the same order. It’s a lot more than 40 lines because it handles many things beyond what’s described here. For example:

It’s local-first, which means you have to handle race conditions.

Multi-tab synchronization works via BroadcastChannel even offline, which is another source of race conditions that needs to be controlled.

DocNode is an alternative to Yjs, but with all the simplicity that comes from assuming a central server. No tombstones, no metadata, no vector clock diffing, supports move operations, etc.

I think you might find them interesting. Take a look at https://docukit.dev and let me know what you think.

The tombstone problem is exactly why I built DocNode. You're right that you can't compact them without consensus, so DocNode just doesn't create them. It assumes a server decides the order, which is already the case in 99% of collaborative apps. The result: a doc stays the same size whether it was edited once or a thousand times. Yjs for the same doc grows every time someone types, pastes, or undoes. Check it out: https://docukit.dev

Interesting! I'm the author of https://docnode.dev and I see some similar concepts

Thank you so much for your help! I followed your advice:

https://news.ycombinator.com/item?id=46211551

I think it's debatable what constitutes an "operation". In a CvRDT, a delta or diff can be considered an operation. In an ID-based OT, it can be considered that there is a transformation of operations, only instead of transforming with respect to other operations, they are transformed with respect to the current document (if there were conflicts, they cannot always be applied in their original form).

Thanks for the advice. I'll try it when the post is a week old. I hope it doesn't get rejected.

I think there's a misunderstanding here.

People often associate CRDTs with IDs and tombstones, while associating OTs with positions.

This is incorrect. What makes them different is that CRDTs must work in P2P environments *by definition*. That's all.

Other true statements:

- All CRDTs are OTs, but not all OTs are CRDTs.

- If an OT supports P2P, then it's also a CRDT.

- If it doesn't support P2P, it's not a CRDT.

- A CRDT can have no IDs and be operation-based.

- An OT can have no positions and be ID-based.

In fact, I just released an ID-based OT framework yesterday: https://docnode.dev.

I hope that clarifies things a bit more!

That's an interesting idea.

A "bring your own cloud" provider could be used for DocNode Sync. For example, Dropbox. Dropbox doesn't have the ability to resolve conflicts, but it can be used to deterministically store the order of operations. Then, clients would reconcile and combine the operations into a single state file. Authentication might be a bit tricky, since permissions would have to reside elsewhere. But I think it's doable.

I'll consider it!

Thanks! The answer depends on what you want:

1. Do you care about resolving concurrent conflicts? That is, if two users modify the same document simultaneously (or while one is offline), is it acceptable if one of their changes is lost? If that’s not a problem, then using Dropbox or something similar is totally fine, and you don't need a CRDT or OT like DocNode at all. Technologies like Dropbox aren't designed for conflict resolution and can't be integrated with CRDT or OT protocols.

2. If you do want to resolve conflicts, you have two options. (a) Use a CRDT, which doesn’t require a server. One downside is that clients must be connected simultaneously to synchronize changes. Personally, I don’t think most people want software that behaves like that, and that’s one of the reasons I didn’t focus on building a CRDT. If you’re going to end up needing a server anyway, what’s the point? (b) Use a server, either hosted by you or by your users. The good news is that it’s extremely simple. With DocNode Sync, you can literally set it up with one line of code on the server.

That doesn't apply if you're using a CRDT with "a server as an always-present client". But in that scenario, DocNode will be more efficient.

Hi everyone! After two years of development, I’m excited to announce DocNode: a type-safe, fast, ID-based Operational Transformation (OT) framework for conflict-free collaborative editing. CRDT mode is in progress.

Along the way, I learned a ton. I rewrote the library several times. Sometimes because I was obsessed with the API, other times for technical reasons. I moved from CvRDT to CmRDT, and finally to ID-based OT.

Happy to answer questions!

When an OT ends up working in a P2P environment, you basically end up with a CRDT. I would say that all CRDTs are OTs (which can be ID-based or positional-based), while not all OTs are CRDTs.

It's funny you mention that, because 4 days ago I wrote a blog post about exactly that: https://docnode.dev/blog/text-conflicts

You need OT or CRDT because otherwise you'd have LWW over the entire document. However, I agree that resolving conflicts at the character/letter level isn't the best idea. Doing it at the node level is a more reasonable balance.

Hi Seph, great to hear from you! I emailed you about a week ago with a private beta to thank you for your contributions (you’re in the acknowledgements section [1]) and to ask for your feedback. I’m not sure if I got your email right.

The tradeoffs I mention mostly concern metadata: insert (OriginLeft, OriginRight), delete (tombstones), and moving (a full topic, you know what I mean).

I know that with eg-walker you managed to reduce those costs by loading metadata into memory only when required. Still, I believe that for me, and for many others, a central server makes more sense, since P2P is a requirement for very few.

DocNode isn’t traditional OT. It’s ID based instead of positional. I essentially started from a CRDT and stripped out the compromises that come with supporting P2P.

That said, CRDT trade-offs weren’t my only motivation for building DocNode. Even if I had gone with a “classic” CRDT, I wanted a different API and a new approach to type safety.

On top of that, I also have a non-mainstream stance regarding text CRDTs. I wrote a blog post explaining it, and I mention you there as well [2].

I'd love to hear your feedback!

[1] https://docnode.dev/docs#credits--acknowledgements [2] https://docnode.dev/blog/text-conflicts

Triplit is my favorite local-first database. However, it doesn't compete in the same space as Automerge, which is doc-based. If you want a user-friendly alternative, I'm launching my proposal this week: https://docnode.dev

Interesting read. I’ve spent the past two years developing my own CRDT, but along the way, I realized a CRDT involves too many trade-offs, so I ended up implementing an ID-based OT framework. Coincidentally, I’m planning to launch it this Tuesday, so here’s an exclusive for you: https://docnode.dev. I'd like to hear your thoughts!

In the future, I plan to add a CRDT mode for scenarios where P2P is required.

Now you're storing all the rows as units, right? When users create tables in Triplit, do they end up with really different tables or are they more more like a single table of content in json + table_meta_ref? I would love to know more about architecture and the changes that you have made

I don't know where you got that idea. People are leaving because they don't like Elon.