5 ms·

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?

cdmckay 3y ago
I believe Notion uses them.
- endisneigh 3y ago
  really? you have a link to a blog post or something? last I heard they explicitly did not use them.
  - ko_pivot 3y ago
    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.
    - jakelazaroff 3y ago
      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.
- auggierose 3y ago
  No, Notion uses OT (operational transform).
- jitl 3y ago
  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 https://boards.greenhouse.io/notion/jobs/5602426003
  - tcoff91 3y ago
    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.
    - paulgb 3y ago
      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.
      - tcoff91 3y ago
        Yeah so something like a last write wins + hybrid logical clocks for ordering is a crdt then.
c_s_guy 3y ago
I've seen it come up often in collaborative text editors. Also see: https://github.com/yjs/yjs https://github.com/yjs/yjs
papercrane 3y ago
Redis uses them in their enterprise products for active-active distribution. https://redis.com/blog/diving-into-crdts/ https://redis.com/blog/diving-into-crdts/
brigadier132 3y ago
They've only recently become practical.
jamil7 3y ago
Apple Notes.
- endisneigh 3y ago
  ah, very cool. TIL.
auggierose 3y ago
Is Figma popular enough? https://www.figma.com/blog/how-figmas-multiplayer-technology-works/ https://www.figma.com/blog/how-figmas-multiplayer-technology...
- danielvaughn 3y ago
  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.
  - auggierose 3y ago
    Yes, I think most practical solutions are not strictly CRDTs, not even Automerge, I think.
    - wim 3y ago
      Right, there are quite some collaborative applications for which a hybrid approach is useful. We're building a collaborative editor (https://thymer.com 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.
    - Rapzid 3y ago
      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.
  - continuitylimit 3y ago
    https://web.archive.org/web/20230223081016/https://www.figma.com/blog/how-figmas-multiplayer-technology-works/ 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.
flatline 3y ago
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.
- rubatuga 3y ago
  Source? Heard Google Docs stopped using CRDT.
- papercrane 3y ago
  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.
tin7in 3y ago
A lot of the popular document/notes/whiteboard apps would use Yjs or Automerge or even a ready solution like Liveblocks.
paulgb 3y ago
Modyfi.com built a raster image editor on Yjs[1] [1] https://digest.browsertech.com/archive/browsertech-digest-how-modyfi-is-building-with/ https://digest.browsertech.com/archive/browsertech-digest-ho...
kitplummer 3y ago
Ditto (https://portal.ditto.live https://portal.ditto.live and https://docs.ditto.live https://docs.ditto.live) uses them.
antidnan 3y ago
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
- jitl 3y ago
  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 https://boards.greenhouse.io/notion/jobs/5602426003
unholiness 3y ago
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.
bunnybender 3y ago
I believe Actual Budget, a local-first personal finance app uses them. https://github.com/actualbudget/actual https://github.com/actualbudget/actual The original author has both written about and given presentations about CRDTs.
euroderf 3y ago
pijul version control is not yet popular but might become so. https://pijul.org/manual/theory.html?highlight=CRDT#conflicts-and-crdts https://pijul.org/manual/theory.html?highlight=CRDT#conflict...
- kiitos 3y ago
  > 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.
arendtio 3y ago
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.

cdmckay 3y ago

I believe Notion uses them.

endisneigh 3y ago
really? you have a link to a blog post or something? last I heard they explicitly did not use them.
- ko_pivot 3y ago
  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.
  - jakelazaroff 3y ago
    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.
auggierose 3y ago
No, Notion uses OT (operational transform).
jitl 3y ago
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 https://boards.greenhouse.io/notion/jobs/5602426003
- tcoff91 3y ago
  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.
  - paulgb 3y ago
    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.
    - tcoff91 3y ago
      Yeah so something like a last write wins + hybrid logical clocks for ordering is a crdt then.

c_s_guy 3y ago

I've seen it come up often in collaborative text editors. Also see: https://github.com/yjs/yjs https://github.com/yjs/yjs

papercrane 3y ago

Redis uses them in their enterprise products for active-active distribution. https://redis.com/blog/diving-into-crdts/ https://redis.com/blog/diving-into-crdts/

brigadier132 3y ago

They've only recently become practical.

jamil7 3y ago

Apple Notes.

endisneigh 3y ago
ah, very cool. TIL.

auggierose 3y ago

Is Figma popular enough? https://www.figma.com/blog/how-figmas-multiplayer-technology-works/ https://www.figma.com/blog/how-figmas-multiplayer-technology...

danielvaughn 3y ago
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.
- auggierose 3y ago
  Yes, I think most practical solutions are not strictly CRDTs, not even Automerge, I think.
  - wim 3y ago
    Right, there are quite some collaborative applications for which a hybrid approach is useful. We're building a collaborative editor (https://thymer.com 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.
  - Rapzid 3y ago
    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.
- continuitylimit 3y ago
  https://web.archive.org/web/20230223081016/https://www.figma.com/blog/how-figmas-multiplayer-technology-works/ 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.

flatline 3y ago

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.

rubatuga 3y ago
Source? Heard Google Docs stopped using CRDT.
papercrane 3y ago
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.

tin7in 3y ago

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

paulgb 3y ago

Modyfi.com built a raster image editor on Yjs[1] [1] https://digest.browsertech.com/archive/browsertech-digest-how-modyfi-is-building-with/ https://digest.browsertech.com/archive/browsertech-digest-ho...

kitplummer 3y ago

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

antidnan 3y ago

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

jitl 3y ago
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 https://boards.greenhouse.io/notion/jobs/5602426003

unholiness 3y ago

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.

bunnybender 3y ago

I believe Actual Budget, a local-first personal finance app uses them. https://github.com/actualbudget/actual https://github.com/actualbudget/actual The original author has both written about and given presentations about CRDTs.

euroderf 3y ago

pijul version control is not yet popular but might become so. https://pijul.org/manual/theory.html?highlight=CRDT#conflicts-and-crdts https://pijul.org/manual/theory.html?highlight=CRDT#conflict...

kiitos 3y ago
> 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.

arendtio 3y ago

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.