10 ms·

Yeah CRDTs are pretty annoying for collaborative text editing, even Google Docs doesn't use them. Some companies have switched from CRDTs back to traditional me

Yeah CRDTs are pretty annoying for collaborative text editing, even Google Docs doesn't use them. Some companies have switched from CRDTs back to traditional methods.

nathansobo 4y ago
We're quite happy with them. Why do you find them annoying?
- tlb 4y ago
  One common failure mode is that two people start typing at the beginning of the same line, and rather than getting two lines, it alternates characters. At least, Etherpad did this.
  - maxbond 4y ago
    This is a common artifact of operational transforms I believe. Etherpad launched in 2008; CRDTs were proposed in 2011. AFAIK Etherpad used (uses?) OT. Open to correction though, it's been a while since I dug into the differences in these approaches & my memory is imperfect.
  - muxator 4y ago
    Etherpad used Operational Transform, not CRDTs. Source: I have been etherpad's maintainer for two years.
  - josephg 4y ago
    This is called the “interleaving problem”. It shows up with simple list algorithms like fractional indexing. All the main text editing CRDT algorithms around today solve this no problem. (Yjs, automerge, diamond types, etc).
    - nathansobo 4y ago
      We honestly don’t solve it yet, but haven’t found it that big of an issue in practice. Would be curious to see the best resource on it.
      - josephg 4y ago
        I remember reading about it in one of Martin Kleppmann’s papers, though I can’t remember which one. It’s an ordering problem that comes from some of the simpler ordering algorithms. For Diamond types I’m using a variant of Yjs’s ordering. But even RGA doesn’t have this problem because each character’s insert location is specified by naming the character immediately to the left when that character was typed. This repository implements a few different list CRDTs using an insertion sort approach, where the algorithm scans for the appropriate location every time an insert happens. This is the scanning function for RGA (automerge’s algorithm): https://github.com/josephg/reference-crdts/blob/fed747255df9d457e11f36575de555b39f07e909/crdts.ts#L401-L459 https://github.com/josephg/reference-crdts/blob/fed747255df9... And this is an interactive visualisation of how diamond types works (which uses Yjs’s algorithm instead), complete with run-length encoding: https://home.seph.codes/public/diamond-vis/ https://home.seph.codes/public/diamond-vis/
      - Horusiath 4y ago
        I've described this issue in my blog post together with CRDT variants that address and solve it: https://bartoszsypytkowski.com/operation-based-crdts-arrays-1/#interleaving https://bartoszsypytkowski.com/operation-based-crdts-arrays-... In practice, many CRDT libraries nowadays (eg. Yjs and Automerge) are using structures that don't come with interleaving issues.
    - sureglymop 4y ago
      Has anyone used Yjs in practice? I've tried recently but the docs seem terribly unfinished sadly. And their lacking examples of how to use it for another purpose (other than text editing).
      - Horusiath 4y ago
        Yjs is being quite heavily used in the industry[1], and being researched by even more companies. There are also demos showing how to integrate it with an existing rich text editors[2]. If you have some ideas about the missing parts, you could also open topic on discuss.yjs.dev - the documentation page (https://docs.yjs.dev https://docs.yjs.dev) has tons of useful links thou. Re. other purpose projects - Yjs/Yrs main target are sequential data structures (text, arrays), but it also has support for maps and xml-like elements. In general you can build most data structures with it. I agree that it would be nice to have some other applications in demos though. [1] https://docs.yjs.dev/yjs-in-the-wild https://docs.yjs.dev/yjs-in-the-wild [2] https://github.com/yjs/yjs-demos https://github.com/yjs/yjs-demos
      - interactivecode 4y ago
        check out https://tiptap.dev/hocuspocus https://tiptap.dev/hocuspocus if you want to have a simple and plug and play option for text editor
- maxbond 4y ago
  I'll offer up that I've had a hard time wrapping my mind around them and that in practice it seems like you need to implement a check pointing operation on top of them which is necessarily not conflict-free, or your replication log will expand without bound & eventually overwhelm your system. (Though perhaps not, depending on your problem domain. Not CRDTs but in this interview the engineers discuss a massive, high frequency replication log that they don't checkpoint, which they've been running at scale for years. Though you could also say they implicitly checkpoint every trading day, and they're working on implementing checkpointing. https://signalsandthreads.com/state-machine-replication-and-why-you-should-care/ https://signalsandthreads.com/state-machine-replication-and-...) That being said I would use CRDTs for any greenfield collaboration project.
paulgb 4y ago
In addition to OP (nice work, Nathan!), one of the yjs authors has made a pretty in-depth argument that (modern) CRDTs are suitable for human-scale text editing. https://blog.kevinjahns.de/are-crdts-suitable-for-shared-editing/ https://blog.kevinjahns.de/are-crdts-suitable-for-shared-edi...
- nathansobo 4y ago
  Thanks very much!
maxbond 4y ago
The first version of Google Docs was written in 2006; CRDTs weren't proposed until 2011, and still seem to be maturing as a technology. So, I don't think this is a reflection on the merits of CRDTs versus operational transforms as much as it is a reflection on the ecosystem and the history of the codebase.
- josephg 4y ago
  Yep. I’ve been working in the collaborative editing space for over a decade - with both OT algorithms and CRDT algorithms. The modern CRDTs I’ve been developing are significantly faster and smaller than any OT system I made 5+ years ago. Much more complex though. (~3k loc for a good, high performance text crdt merging algorithm, vs 300 loc for a good text OT algorithm.)
  - HWR_14 4y ago
    Sorry, I'm not sure I properly understood OT as an acronym. Did you mean "operational transformation"? Because I thought that OT was method of making operational based CRDTs[0]. But I'm probably wrong in at least one way! Hoping to learn. [0] https://link.springer.com/chapter/10.1007/978-3-662-43352-2_11 https://link.springer.com/chapter/10.1007/978-3-662-43352-2_...
    - throwawaymaths 4y ago
      Quick and dirty: OTs require a centralized controller and a (potentially complicated) merge strategy to shepherd conflicting changes. CRDTs on the other hand apply commutative operations so they don't need be centralized, though nodes that communicate infrequently might get very out of sync
    - josephg 4y ago
      Yes, OT = Operational Transform[1]. Usually the difference is that operational transform algorithms create an ordered global list of all the changes (typically on a centralized server). They flatten operations using a heuristic "transform" function. CRDTs don't reorder the changes, but guarantee that when all changes are merged (in any order) the final result would be the same. For example, MAX() is a complete CRDT merging function. But the distinction gets much more blurry at the edges. You can make OT algorithms which work without a central server, and CRDTs which use operation reordering to guarantee merge consistency. [1] https://en.wikipedia.org/wiki/Operational_transformation https://en.wikipedia.org/wiki/Operational_transformation

Yeah CRDTs are pretty annoying for collaborative text editing, even Google Docs doesn't use them. Some companies have switched from CRDTs back to traditional methods.

nathansobo 4y ago

We're quite happy with them. Why do you find them annoying?

tlb 4y ago
One common failure mode is that two people start typing at the beginning of the same line, and rather than getting two lines, it alternates characters. At least, Etherpad did this.
- maxbond 4y ago
  This is a common artifact of operational transforms I believe. Etherpad launched in 2008; CRDTs were proposed in 2011. AFAIK Etherpad used (uses?) OT. Open to correction though, it's been a while since I dug into the differences in these approaches & my memory is imperfect.
- muxator 4y ago
  Etherpad used Operational Transform, not CRDTs. Source: I have been etherpad's maintainer for two years.
- josephg 4y ago
  This is called the “interleaving problem”. It shows up with simple list algorithms like fractional indexing. All the main text editing CRDT algorithms around today solve this no problem. (Yjs, automerge, diamond types, etc).
  - nathansobo 4y ago
    We honestly don’t solve it yet, but haven’t found it that big of an issue in practice. Would be curious to see the best resource on it.
    - josephg 4y ago
      I remember reading about it in one of Martin Kleppmann’s papers, though I can’t remember which one. It’s an ordering problem that comes from some of the simpler ordering algorithms. For Diamond types I’m using a variant of Yjs’s ordering. But even RGA doesn’t have this problem because each character’s insert location is specified by naming the character immediately to the left when that character was typed. This repository implements a few different list CRDTs using an insertion sort approach, where the algorithm scans for the appropriate location every time an insert happens. This is the scanning function for RGA (automerge’s algorithm): https://github.com/josephg/reference-crdts/blob/fed747255df9d457e11f36575de555b39f07e909/crdts.ts#L401-L459 https://github.com/josephg/reference-crdts/blob/fed747255df9... And this is an interactive visualisation of how diamond types works (which uses Yjs’s algorithm instead), complete with run-length encoding: https://home.seph.codes/public/diamond-vis/ https://home.seph.codes/public/diamond-vis/
    - Horusiath 4y ago
      I've described this issue in my blog post together with CRDT variants that address and solve it: https://bartoszsypytkowski.com/operation-based-crdts-arrays-1/#interleaving https://bartoszsypytkowski.com/operation-based-crdts-arrays-... In practice, many CRDT libraries nowadays (eg. Yjs and Automerge) are using structures that don't come with interleaving issues.
  - sureglymop 4y ago
    Has anyone used Yjs in practice? I've tried recently but the docs seem terribly unfinished sadly. And their lacking examples of how to use it for another purpose (other than text editing).
    - Horusiath 4y ago
      Yjs is being quite heavily used in the industry[1], and being researched by even more companies. There are also demos showing how to integrate it with an existing rich text editors[2]. If you have some ideas about the missing parts, you could also open topic on discuss.yjs.dev - the documentation page (https://docs.yjs.dev https://docs.yjs.dev) has tons of useful links thou. Re. other purpose projects - Yjs/Yrs main target are sequential data structures (text, arrays), but it also has support for maps and xml-like elements. In general you can build most data structures with it. I agree that it would be nice to have some other applications in demos though. [1] https://docs.yjs.dev/yjs-in-the-wild https://docs.yjs.dev/yjs-in-the-wild [2] https://github.com/yjs/yjs-demos https://github.com/yjs/yjs-demos
    - interactivecode 4y ago
      check out https://tiptap.dev/hocuspocus https://tiptap.dev/hocuspocus if you want to have a simple and plug and play option for text editor
maxbond 4y ago
I'll offer up that I've had a hard time wrapping my mind around them and that in practice it seems like you need to implement a check pointing operation on top of them which is necessarily not conflict-free, or your replication log will expand without bound & eventually overwhelm your system. (Though perhaps not, depending on your problem domain. Not CRDTs but in this interview the engineers discuss a massive, high frequency replication log that they don't checkpoint, which they've been running at scale for years. Though you could also say they implicitly checkpoint every trading day, and they're working on implementing checkpointing. https://signalsandthreads.com/state-machine-replication-and-why-you-should-care/ https://signalsandthreads.com/state-machine-replication-and-...) That being said I would use CRDTs for any greenfield collaboration project.

paulgb 4y ago

In addition to OP (nice work, Nathan!), one of the yjs authors has made a pretty in-depth argument that (modern) CRDTs are suitable for human-scale text editing. https://blog.kevinjahns.de/are-crdts-suitable-for-shared-editing/ https://blog.kevinjahns.de/are-crdts-suitable-for-shared-edi...

nathansobo 4y ago
Thanks very much!

maxbond 4y ago

The first version of Google Docs was written in 2006; CRDTs weren't proposed until 2011, and still seem to be maturing as a technology. So, I don't think this is a reflection on the merits of CRDTs versus operational transforms as much as it is a reflection on the ecosystem and the history of the codebase.

josephg 4y ago
Yep. I’ve been working in the collaborative editing space for over a decade - with both OT algorithms and CRDT algorithms. The modern CRDTs I’ve been developing are significantly faster and smaller than any OT system I made 5+ years ago. Much more complex though. (~3k loc for a good, high performance text crdt merging algorithm, vs 300 loc for a good text OT algorithm.)
- HWR_14 4y ago
  Sorry, I'm not sure I properly understood OT as an acronym. Did you mean "operational transformation"? Because I thought that OT was method of making operational based CRDTs[0]. But I'm probably wrong in at least one way! Hoping to learn. [0] https://link.springer.com/chapter/10.1007/978-3-662-43352-2_11 https://link.springer.com/chapter/10.1007/978-3-662-43352-2_...
  - throwawaymaths 4y ago
    Quick and dirty: OTs require a centralized controller and a (potentially complicated) merge strategy to shepherd conflicting changes. CRDTs on the other hand apply commutative operations so they don't need be centralized, though nodes that communicate infrequently might get very out of sync
  - josephg 4y ago
    Yes, OT = Operational Transform[1]. Usually the difference is that operational transform algorithms create an ordered global list of all the changes (typically on a centralized server). They flatten operations using a heuristic "transform" function. CRDTs don't reorder the changes, but guarantee that when all changes are merged (in any order) the final result would be the same. For example, MAX() is a complete CRDT merging function. But the distinction gets much more blurry at the edges. You can make OT algorithms which work without a central server, and CRDTs which use operation reordering to guarantee merge consistency. [1] https://en.wikipedia.org/wiki/Operational_transformation https://en.wikipedia.org/wiki/Operational_transformation