Hacker News Reader

Comment by endisneigh | Hacker News Reader

CRDTs seem like one of these things that are mentioned on here frequently, but I haven't seen that many popular apps that use them. Any examples?

View on HN

Once you start adding enough complexity, there will arise cases that the primitives are an awkward place for the merging to happen. There will arise cases where that user expectations and the merge function behavior don't agree. There will arise cases where the server can do a better job than the client at applying the change. There will arise cases where you need to undo but the undo function violates the merge function. And as the author freely states, there will arise cases where sending the whole state is prohibitively slow.

Those are really only issues with state-based CRDTs. The fundamental concepts behind operation-based CRDTs vs operational transforms vs bespoke hybrid approaches aren't really different. It's all about determining an unambiguous order, then getting everyone to update their state as if it had been applied in that order. Much less democratic but much more practical.

Is Figma popular enough?

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

Figma's interesting because it's not strictly speaking a CRDT. It borrows heavily from some of the CRDT ideas, but it's really an editable tree where most changes are atomic and thus use a last-writer-wins approach. That, and re-ordering tree nodes uses fractional indexing.

https://web.archive.org/web/20230223081016/https://www.figma...

It’s a client-server architecture with a bit of CRDT inspired algorithm sprinkle on for offline mode. The name of the game remains consensus and CRDTs convoluted approach is there to server a niche in the spectrum of distributed consensus. It is slower, more complex, and less transparent. I wouldn’t really use it outside of long lived and erratic P2P nodes — CRDTs solve that problem and that is what they are really designed for: partition prone, long lived, distributed, peer to peer, collaborative global state changes.

Yes, I think most practical solutions are not strictly CRDTs, not even Automerge, I think.

Right, there are quite some collaborative applications for which a hybrid approach is useful. We're building a collaborative editor (https://thymer.com) for example, where the underlying data structure is also a tree (as the text documents also support outliner-like features, so a flat list of characters/lines isn't enough). To avoid tree conflicts, insert and move operations look more like OT than CRDT however, where other updates can use a simple CRDT mutation.

Automerge is interesting as it's an op-based CRDT system vs state-based.. This should make use cases involving a central authority easier to work with but.. Their docs lack any detail useful to taking advantage of this haha.

The academic version of them is not used that widely AFAIK outside of newer companies using Yjs.

I believe Figma, Notion, Google Docs, etc all use some form of OTs which aren't necessarily a perfect CRDT

Notion doesn't use OT. Most things are last-write-wins, but we have operations that merge like list re-ordering or permission changes. Today our text is last-write-wins, but we're developing a CRDT solution – if that sounds like something you'd like to work on, shoot me an email jake@makenotion.com or apply https://boards.greenhouse.io/notion/jobs/5602426003

I believe Actual Budget, a local-first personal finance app uses them.

https://github.com/actualbudget/actual

The original author has both written about and given presentations about CRDTs.

I've seen it come up often in collaborative text editors.

Also see: https://github.com/yjs/yjs

A lot of the popular document/notes/whiteboard apps would use Yjs or Automerge or even a ready solution like Liveblocks.

Modyfi.com built a raster image editor on Yjs[1]

[1] https://digest.browsertech.com/archive/browsertech-digest-ho...

Redis uses them in their enterprise products for active-active distribution.

https://redis.com/blog/diving-into-crdts/

Well, isn't it the sense of CRDTs that you don't see them? I mean, traditionally users are asked what the system should once it finds a lock, but with CRDTs they should never find a lock and therefore the user isn't bothered.

Ditto (https://portal.ditto.live and https://docs.ditto.live) uses them.

They've only recently become practical.

pijul version control is not yet popular but might become so.

https://pijul.org/manual/theory.html?highlight=CRDT#conflict...

> In Pijul, there are two kinds of conflicts inside a file:

> When two different authors add lines at the same position in a file, and it is impossible to tell which comes first in the file.

> When one author adds a line in a block of text or code, while another author deletes that block.

I don't think this is true. Two different authors can modify the same line in different ways, which is a conflict that's different than either of these categories.

> It is important to note that conflicts in Pijul always happen between changes, for example we might say that “change A conflicts with change B”.

I also don't think this is true. Conflicts can occur in a history (lineage, sequence, etc.) of concurrent changes, which are different than the delta between any two independent changes.

Apple Notes.

ah, very cool. TIL.

I believe Notion uses them.

Notion doesn't use OT or CRDT in production. Most things are last-write-wins, but we have operations that merge like list re-ordering or permission changes. Today our text is last-write-wins, but we're developing a CRDT solution – if that sounds like something you'd like to work on, shoot me an email jake@makenotion.com or apply https://boards.greenhouse.io/notion/jobs/5602426003

Isn't last-write-wins technically a CRDT? It's just not a very good one. For many use-cases though a per-column last-writer-wins CRDT is perfectly adequate.

- Edits can be made on any node at any time independently and without coordinating with other nodes.

- All nodes eventually converge to the same state.

A CRDT can have last-write-wins semantics (as in the article above), but LWW doesn’t fully describe a CRDT because it doesn’t specify a way to determine which write is actually “last”. CRDTs don’t assume that there is a fully-ordered stream of updates, so there is no “last update” per se.

Yeah so something like a last write wins + hybrid logical clocks for ordering is a crdt then.

really? you have a link to a blog post or something? last I heard they explicitly did not use them.

In production, they don’t. This is evident when two users try to edit the same block at the same time — its last writer wins right now, not merging. They have hired some engineers to work on a CRDT text editor implementation though.

No idea whether Notion uses CRDTs, but last writer wins is a (naive) strategy for editing text. You can see this in the article — if you edit the LWW Map, for example, even though the keys are merged, each value will be taken from one peer or the other. Once you get to that last “primitive” CRDT — the register holding each map value — updates are atomic. So Notion may be using CRDTs for e.g. the order of blocks in a page, but not (yet?) using them to merge text.

No, Notion uses OT (operational transform).

Google docs, really any online collaborative editor uses them. If you have a distributed system with multiple asynchronous data feeds into the same sink, this is one way of automatically resolving conflicts. A complicated way that most applications probably don’t really need, and that does not guarantee consistency. But they are neat.

I'm pretty sure Google Docs use Operational transformation (OT). Google Docs pre-dates the paper that defined CRDTs. It's certainly possible they've updated their algorithms since then though.

Source? Heard Google Docs stopped using CRDT.

Reply on news.ycombinator.com