3 ms·

> everyone’s gonna say “but hey, google docs uses operational transform not CRDTs”.. OK yes, but you are not google. Well, google docs works not because they s

> everyone’s gonna say “but hey, google docs uses operational transform not CRDTs”.. OK yes, but you are not google. Well, google docs works not because they somehow figured out how to converge OT edits with as much precision as CRDTs do, but simply because they have a central server which orders edits anyway and don't need true leader-less convergence. In fact, I agree not many things don't need a CRDT. CRDTs help with mathematical rigidity of convergence when you want true peer-2-peer collaboration which works without any central authority. However, most apps anyway work on top of a central authority (example SaaS apps) so there is no real reason to accomodate all the compexity that comes with CRDT. They might get far with a simpler OT based model + central server based ordering. For example even Figma doesn't call its model a 100% pure CRDT. It's a partial, simpler CRDT implemented with an assumption that there's going to be a server that understands ordering. It's the same with Google Docs. They don't need a CRDT because it's a cloud app after all, which means OT is more convenient with major heavylifting (ordering and conflict handlings) outsourced to the server.

josephg 3y ago
Yeah. Text based OT is pretty simple to implement, too. It’s about 200 lines of code, plus a simple network protocol. It’s fast and relatively straightforward to code up, and unlike text CRDTs it’s pretty fast by default. I use it as my standard test when trying out a new programming language. It was unexpectedly ugly in go because of go’s lack of enums & unions, and that’s one of the big reasons I never got in to programming Go.
- jay-aye-see-key 3y ago
  Operational transforms are one of those interesting technologies I’ve wanted to learn by implementing but haven’t made the time yet. I also didn’t realise it could be implemented in that little code. Can you recommend any learning resources for implementing an OT? (Ideally typescript, python, or rust)
  - jahfer 3y ago
    I haven’t explored this space in a while, but I have a couple of examples that could be helpful. A Clojure library of mine [0] has a decent README with some background reading on how to use operational transform. I also reimplemented it in a surprisingly tiny amount of OCaml [1] which was a fun way to learn that language :) [0]: https://github.com/jahfer/othello https://github.com/jahfer/othello [1]: https://github.com/jahfer/othello-ocaml https://github.com/jahfer/othello-ocaml
  - dugmartin 3y ago
    This single file shows the entire set of OT transformations (retain, insert, delete): https://github.com/Operational-Transformation/ot.js/blob/master/lib/text-operation.js https://github.com/Operational-Transformation/ot.js/blob/mas... and this is a good post outlining the basics of OT, from the creator of CodeMirror: https://marijnhaverbeke.nl/blog/collaborative-editing-cm.html https://marijnhaverbeke.nl/blog/collaborative-editing-cm.htm...
- Reinmar 3y ago
  > Yeah. Text based OT is pretty simple to implement, too. It’s about 200 lines of code, plus a simple network protocol. Just for clarification, while OT for plain-text (linear model) might be simple to implement, OT for typical rich-text editors (like Google Docs) that need to rely on a tree-structured data model is a whole different story: https://ckeditor.com/blog/lessons-learned-from-creating-a-rich-text-editor-with-real-time-collaboration/ https://ckeditor.com/blog/lessons-learned-from-creating-a-ri....
  - tkone 3y ago
    nah, that’s not true at all. have a look at ‘rich-text’[1] which allows for transforms on metadata in a separate stream from the main content. it’s the same basic algo used for OT on plain text. (i was the cto at a startup which used this to create a multi-user text editor with rich text support in 2015ish) 1: https://github.com/ottypes/rich-text https://github.com/ottypes/rich-text
    - Reinmar 3y ago
      What's not true at all? That more powerful rich text editors need to rely on a tree structure?
      - tkone 3y ago
        yes. that is not true. you can build a rich text editor with simple ot. no tree necessary.
        Reinmar 3y ago
        I agree. Yes, you can. Quill is the example here. Actually, back in 2015 when we started prototyping CKEditor 5, we started with this approach as well. Our goal from the beginning was to combine real-time editing capabilities with an engine capable of storing and rendering complex rich-text structures (nested tables, complex nested lists, other rich widgets, etc.). We quickly realized that a linear structure is going to be a huge bottleneck. In the end, if you want to represent trees, storing them as a linear structure is counterproductive. So, we went for a tree model. That got many things in the engine an order of magnitude harder (OT being one). But I choose to encapsulate this complexity in the model rather than make it leak to particular plugins. In fact, from what I remember, https://github.com/quilljs/quill/issues/117 https://github.com/quilljs/quill/issues/117 (e.g. https://github.com/quilljs/quill/issues/117#issuecomment-644724151 https://github.com/quilljs/quill/issues/117#issuecomment-644...) is a good example of issues that we avoided. I also talked to companies that built their platforms on top of Quill. One of them ended up gluing together countless Quill instances to power their editor and overcome the limitations of the linear data model but is now looking for a way to rebuild their editor from scratch due to the issues (performance, complexity, stability). So, yes. You can implement a rich-text editor based on a linear model. But it has its immediate limitations that you need to take into consideration.

josephg 3y ago

Yeah. Text based OT is pretty simple to implement, too. It’s about 200 lines of code, plus a simple network protocol. It’s fast and relatively straightforward to code up, and unlike text CRDTs it’s pretty fast by default. I use it as my standard test when trying out a new programming language. It was unexpectedly ugly in go because of go’s lack of enums & unions, and that’s one of the big reasons I never got in to programming Go.

jay-aye-see-key 3y ago
Operational transforms are one of those interesting technologies I’ve wanted to learn by implementing but haven’t made the time yet. I also didn’t realise it could be implemented in that little code. Can you recommend any learning resources for implementing an OT? (Ideally typescript, python, or rust)
- jahfer 3y ago
  I haven’t explored this space in a while, but I have a couple of examples that could be helpful. A Clojure library of mine [0] has a decent README with some background reading on how to use operational transform. I also reimplemented it in a surprisingly tiny amount of OCaml [1] which was a fun way to learn that language :) [0]: https://github.com/jahfer/othello https://github.com/jahfer/othello [1]: https://github.com/jahfer/othello-ocaml https://github.com/jahfer/othello-ocaml
- dugmartin 3y ago
  This single file shows the entire set of OT transformations (retain, insert, delete): https://github.com/Operational-Transformation/ot.js/blob/master/lib/text-operation.js https://github.com/Operational-Transformation/ot.js/blob/mas... and this is a good post outlining the basics of OT, from the creator of CodeMirror: https://marijnhaverbeke.nl/blog/collaborative-editing-cm.html https://marijnhaverbeke.nl/blog/collaborative-editing-cm.htm...
Reinmar 3y ago
> Yeah. Text based OT is pretty simple to implement, too. It’s about 200 lines of code, plus a simple network protocol. Just for clarification, while OT for plain-text (linear model) might be simple to implement, OT for typical rich-text editors (like Google Docs) that need to rely on a tree-structured data model is a whole different story: https://ckeditor.com/blog/lessons-learned-from-creating-a-rich-text-editor-with-real-time-collaboration/ https://ckeditor.com/blog/lessons-learned-from-creating-a-ri....
- tkone 3y ago
  nah, that’s not true at all. have a look at ‘rich-text’[1] which allows for transforms on metadata in a separate stream from the main content. it’s the same basic algo used for OT on plain text. (i was the cto at a startup which used this to create a multi-user text editor with rich text support in 2015ish) 1: https://github.com/ottypes/rich-text https://github.com/ottypes/rich-text
  - Reinmar 3y ago
    What's not true at all? That more powerful rich text editors need to rely on a tree structure?
    - tkone 3y ago
      yes. that is not true. you can build a rich text editor with simple ot. no tree necessary.
      - Reinmar 3y ago
        I agree. Yes, you can. Quill is the example here. Actually, back in 2015 when we started prototyping CKEditor 5, we started with this approach as well. Our goal from the beginning was to combine real-time editing capabilities with an engine capable of storing and rendering complex rich-text structures (nested tables, complex nested lists, other rich widgets, etc.). We quickly realized that a linear structure is going to be a huge bottleneck. In the end, if you want to represent trees, storing them as a linear structure is counterproductive. So, we went for a tree model. That got many things in the engine an order of magnitude harder (OT being one). But I choose to encapsulate this complexity in the model rather than make it leak to particular plugins. In fact, from what I remember, https://github.com/quilljs/quill/issues/117 https://github.com/quilljs/quill/issues/117 (e.g. https://github.com/quilljs/quill/issues/117#issuecomment-644724151 https://github.com/quilljs/quill/issues/117#issuecomment-644...) is a good example of issues that we avoided. I also talked to companies that built their platforms on top of Quill. One of them ended up gluing together countless Quill instances to power their editor and overcome the limitations of the linear data model but is now looking for a way to rebuild their editor from scratch due to the issues (performance, complexity, stability). So, yes. You can implement a rich-text editor based on a linear model. But it has its immediate limitations that you need to take into consideration.