6 ms·

I’m part of the team that makes Zoho Writer (Google Docs alternative) - https://writer.zoho.com https://writer.zoho.com Back in 2009, we wrote our real time co

I’m part of the team that makes Zoho Writer (Google Docs alternative) - https://writer.zoho.com https://writer.zoho.com Back in 2009, we wrote our real time collaboration component using Operational Transformations (OT). But when CRDTs started to gain the spotlight, these are the reasons why it didn’t warrant a rewrite to our stack: #1 Memory issues with tombstones. Marking as deletion has a cost of maintaining them throughout the session. #2 CRDTs were perfect for plain strings and arbitrary key/value pairs. But when it comes to schematic JSON that has semantic value CRDT was an added overhead. For example, try making a collaborative HTML editor with support for table operations. It is very likely you will end up with a table structure that is invalid to render. In OT analysing, modifying or cancelling ops were much easier. #3 Since the software is primarily a cloud document editor, a central server is necessary even otherwise. So why not use the server for efficient version management and operation sequencing as well? Why prefer CRDTs whose bulk of complexity comes from eliminating the need of a central system? Such practical reasons have kept us from venturing into CRDTs. As of now, common editing platforms like Google Docs, Zoho Writer, CKeditor, ProseMirror, Quill, CodeMirror - all of these work with OTs instead of CRDT for collaborative editing.

cryptonector 6y ago
Also, if the monoids used in a CRDT implementation do not align with the mental model users have for what they're doing (hint: they do not), then the result will be artifacts the users don't like. Single user text editing is amenable to using ropes and monoids internally because none of that leaks into the UI/UX, but multi-user text editing is not amenable to representation as monoidal interactions because in the multi-user case the monoidal interactions will become evident and confusing. Or at least that's the lesson I took from all the xi blogs I've read.
- hinkley 6y ago
  This is a problem we need to solve with code editors and version control as well. Patches are always a little bit garbage, and can cause extra problems with 3 way merges because of it.
  - Chris2048 6y ago
    In feel this is probably a language-level problem, and solving it only at editor/VC level will be complicated. At the same time, changes to the lang level would require changes at editor/VC level too. As en example: a MIX type syntax can separate classes and class-methods into different files, and combine them back again. This way moving a class method around in a class won't be seen as removing a method and creating a new one: the file give the specific method an identity, and a method of differentiating between code movement and code alteration.
- dnautics 6y ago
  I think it's important to note that "they do not yet". CRDTs are an active area of research, relatively young, and it is not unreasonable to expect that new datastructures which DO align to users' mental models will appear in the not-too-distant future.
  - cryptonector 6y ago
    CRDT is very well understood. The basics of the theory is utterly trivial. The only question is whether we can design new monoids that line up better with human understandings of their own intent -- of this I am skeptical because our mental models of what we're doing are not at all monoidal, though because CRDTs are so elegant and so simple, I would be ecstatic if indeed we find/design such monoids.
    - dnautics 6y ago
      what do you think of Martin Klepmann's research, e.g: https://martin.kleppmann.com/2020/07/06/crdt-hard-parts-hydra.html https://martin.kleppmann.com/2020/07/06/crdt-hard-parts-hydr...
      - cryptonector 6y ago
        I'll watch it and let you know. Sounds very interesting!
        cryptonector 6y ago
        I'm part of the way through. Here are some thoughts. - Is there a way to materialize all of the past up to some point, throwing out history in the process, so as to reduce the overhead of CRDT? - Some CRDT algorithms (really, representations of operations) are better at modeling a user's intent -- rather than "insert 'H' at 101, insert 'e' at 102, ..." and so on, it's "insert 'Hello' between ...". As I'm not familiar with OT, I wonder whether this begins to approach OT... In any case, some of the better CRDT algorithms for text editing tend to require more overhead, which is why the preceding thought. - I'm much more interested in CRDTs for distributed relational databases, where it's much easier to reason about intent. "Relational" really means "has a well defined, enforced schema", while "text" means "anything goes" -- it's necessarily easier to reason about the former than the latter! Even so, a set of related updates to a relational database may be the complex result of a simpler abstraction -a simpler operation that the user intended- and eventual consistency semantics may ruin that result. One way to deal with that is to centralize certain kinds of operations, but those had better be less essential to business continuity.
fastball 6y ago
I think the main impetus for this post is to assert that #1 and #2 aren't much of a problem for Yjs, as they are for the arguably more well-known CRDT lib for JS, Automerge. With respect to #3, one reason to prefer CRDTs over OT (even if a central server is required for other stuff) is that making the collaboration infra P2P can save a lot of resources if most of your collab is happening between a few individuals at a time. Not very necessary at a small scale, but if you have 10,000 small teams collab'ing, the cost savings you get from off-loading RTC to the end users can definitely add up.
- lukevp 6y ago
  OT doesn’t require a central server, just a tie breaker. You could just do leader election over webRTC using raft and offload OT to the client side as well and have that node push updates to the server for durable saving every x seconds and shift RTC off your infra.
  - raphlinus 6y ago
    Right, the idea that OT requires a "central server" is a bit of an oversimplification. It requires an authority that can serialize concurrent revisions into a globally consistent sequence. By far the easiest way to achieve that is an actual central server, but distributed algorithms have also been published for a long time, for example SOCT2 which uses a state vector. The downside is the complexity. Now there are more things that can go wrong: the OT algorithm can fail (either due to bugs or because of corrupted data), and now also the distributed consensus algorithm can fail as well. When you have this level of complexity, going to CRDT is pretty appealing as an alternative.
zzz61831 6y ago
> Memory issues with tombstones. Marking as deletion has a cost of maintaining them throughout the session. That's not true, you don't need to keep them throughout the session. You can drop them as soon as you either synchronize with other clients or with the server, which can then synchronize with the clients, that's what conflict-free nature of CRDTs allows you to do. The only fundamental requirement is to keep track of changes when you are offline or out of sync until they are sent to others and even then you are supposed to merge those changes into fewer changes keeping disk and memory use down to a minimum. > CRDTs were perfect for plain strings and arbitrary key/value pairs. But when it comes to schematic JSON that has semantic value CRDT was an added overhead. Also not true. They were never perfect for plain strings, even incompatible semantically, but perfect for sets, counters, numbers, where basic commutative math is enough, a few other things and anything that combines those primitives into more complex ones, especially true for schematic structures, tables. You should really try implementing CRDTs, especially OP-based, they change the way you think about keeping shared state in distributed systems. > Since the software is primarily a cloud document editor, a central server is necessary even otherwise. So why not use the server for efficient version management and operation sequencing as well? Why chose CRDTs whose bulk of complexity comes from eliminating the need of a central system? There is zero complexity in CRDTs that comes from eliminating the need of a central system, it's a completely different problem orthogonal to CRDTs. Central systems is where CRDTs are used the most actually.
- lewisjoe 6y ago
  > You can drop them as soon as you either synchronize with other clients or with the server Say 100 nodes edit a doc. To drop a tombstone, without a central server we need 99 acks. Even with a server, the server keeps an ever-growing list of ops unless it uses some garbage collection techniques. And as stated by OP those techniques have their own problems. Remember, OP relies on V8's hidden classes for deriving an optimal representation without eliminating tombstones. Servers though need not necessarily hold CRDTs in JS. It might be a different VM altogether. > anything that combines those primitives into more complex ones, especially true for schematic structures, tables. I'm not implying CRDTs are only for simple structures. Automerge has support for tables too. I'm talking about structures with semantic meaning. In database tables the ops are always inserting/delete columns/rows and updating cells. In HTML tables, it extends into cell-merging, cell-splitting, inner tables and all sorts of valid operations. Merging these operations without inspecting the op and writing a custom modifier - will certainly end up in an invalid table structure. > Central systems is where CRDTs are used the most actually. I'm assuming the central system referred here is the database resilience systems using CRDTs to merge. Database syncing without master/slave is exactly the kind of problem best solved with CRDTs. The very point is to eliminate the need for a central point of failure.
ianopolous 6y ago
What do you think of Chronofold [1]? [1] https://arxiv.org/abs/2002.09511 https://arxiv.org/abs/2002.09511

cryptonector 6y ago

Also, if the monoids used in a CRDT implementation do not align with the mental model users have for what they're doing (hint: they do not), then the result will be artifacts the users don't like. Single user text editing is amenable to using ropes and monoids internally because none of that leaks into the UI/UX, but multi-user text editing is not amenable to representation as monoidal interactions because in the multi-user case the monoidal interactions will become evident and confusing. Or at least that's the lesson I took from all the xi blogs I've read.

hinkley 6y ago
This is a problem we need to solve with code editors and version control as well. Patches are always a little bit garbage, and can cause extra problems with 3 way merges because of it.
- Chris2048 6y ago
  In feel this is probably a language-level problem, and solving it only at editor/VC level will be complicated. At the same time, changes to the lang level would require changes at editor/VC level too. As en example: a MIX type syntax can separate classes and class-methods into different files, and combine them back again. This way moving a class method around in a class won't be seen as removing a method and creating a new one: the file give the specific method an identity, and a method of differentiating between code movement and code alteration.
dnautics 6y ago
I think it's important to note that "they do not yet". CRDTs are an active area of research, relatively young, and it is not unreasonable to expect that new datastructures which DO align to users' mental models will appear in the not-too-distant future.
- cryptonector 6y ago
  CRDT is very well understood. The basics of the theory is utterly trivial. The only question is whether we can design new monoids that line up better with human understandings of their own intent -- of this I am skeptical because our mental models of what we're doing are not at all monoidal, though because CRDTs are so elegant and so simple, I would be ecstatic if indeed we find/design such monoids.
  - dnautics 6y ago
    what do you think of Martin Klepmann's research, e.g: https://martin.kleppmann.com/2020/07/06/crdt-hard-parts-hydra.html https://martin.kleppmann.com/2020/07/06/crdt-hard-parts-hydr...
    - cryptonector 6y ago
      I'll watch it and let you know. Sounds very interesting!
      - cryptonector 6y ago
        I'm part of the way through. Here are some thoughts. - Is there a way to materialize all of the past up to some point, throwing out history in the process, so as to reduce the overhead of CRDT? - Some CRDT algorithms (really, representations of operations) are better at modeling a user's intent -- rather than "insert 'H' at 101, insert 'e' at 102, ..." and so on, it's "insert 'Hello' between ...". As I'm not familiar with OT, I wonder whether this begins to approach OT... In any case, some of the better CRDT algorithms for text editing tend to require more overhead, which is why the preceding thought. - I'm much more interested in CRDTs for distributed relational databases, where it's much easier to reason about intent. "Relational" really means "has a well defined, enforced schema", while "text" means "anything goes" -- it's necessarily easier to reason about the former than the latter! Even so, a set of related updates to a relational database may be the complex result of a simpler abstraction -a simpler operation that the user intended- and eventual consistency semantics may ruin that result. One way to deal with that is to centralize certain kinds of operations, but those had better be less essential to business continuity.

fastball 6y ago

I think the main impetus for this post is to assert that #1 and #2 aren't much of a problem for Yjs, as they are for the arguably more well-known CRDT lib for JS, Automerge. With respect to #3, one reason to prefer CRDTs over OT (even if a central server is required for other stuff) is that making the collaboration infra P2P can save a lot of resources if most of your collab is happening between a few individuals at a time. Not very necessary at a small scale, but if you have 10,000 small teams collab'ing, the cost savings you get from off-loading RTC to the end users can definitely add up.

lukevp 6y ago
OT doesn’t require a central server, just a tie breaker. You could just do leader election over webRTC using raft and offload OT to the client side as well and have that node push updates to the server for durable saving every x seconds and shift RTC off your infra.
- raphlinus 6y ago
  Right, the idea that OT requires a "central server" is a bit of an oversimplification. It requires an authority that can serialize concurrent revisions into a globally consistent sequence. By far the easiest way to achieve that is an actual central server, but distributed algorithms have also been published for a long time, for example SOCT2 which uses a state vector. The downside is the complexity. Now there are more things that can go wrong: the OT algorithm can fail (either due to bugs or because of corrupted data), and now also the distributed consensus algorithm can fail as well. When you have this level of complexity, going to CRDT is pretty appealing as an alternative.

zzz61831 6y ago

> Memory issues with tombstones. Marking as deletion has a cost of maintaining them throughout the session. That's not true, you don't need to keep them throughout the session. You can drop them as soon as you either synchronize with other clients or with the server, which can then synchronize with the clients, that's what conflict-free nature of CRDTs allows you to do. The only fundamental requirement is to keep track of changes when you are offline or out of sync until they are sent to others and even then you are supposed to merge those changes into fewer changes keeping disk and memory use down to a minimum. > CRDTs were perfect for plain strings and arbitrary key/value pairs. But when it comes to schematic JSON that has semantic value CRDT was an added overhead. Also not true. They were never perfect for plain strings, even incompatible semantically, but perfect for sets, counters, numbers, where basic commutative math is enough, a few other things and anything that combines those primitives into more complex ones, especially true for schematic structures, tables. You should really try implementing CRDTs, especially OP-based, they change the way you think about keeping shared state in distributed systems. > Since the software is primarily a cloud document editor, a central server is necessary even otherwise. So why not use the server for efficient version management and operation sequencing as well? Why chose CRDTs whose bulk of complexity comes from eliminating the need of a central system? There is zero complexity in CRDTs that comes from eliminating the need of a central system, it's a completely different problem orthogonal to CRDTs. Central systems is where CRDTs are used the most actually.

lewisjoe 6y ago
> You can drop them as soon as you either synchronize with other clients or with the server Say 100 nodes edit a doc. To drop a tombstone, without a central server we need 99 acks. Even with a server, the server keeps an ever-growing list of ops unless it uses some garbage collection techniques. And as stated by OP those techniques have their own problems. Remember, OP relies on V8's hidden classes for deriving an optimal representation without eliminating tombstones. Servers though need not necessarily hold CRDTs in JS. It might be a different VM altogether. > anything that combines those primitives into more complex ones, especially true for schematic structures, tables. I'm not implying CRDTs are only for simple structures. Automerge has support for tables too. I'm talking about structures with semantic meaning. In database tables the ops are always inserting/delete columns/rows and updating cells. In HTML tables, it extends into cell-merging, cell-splitting, inner tables and all sorts of valid operations. Merging these operations without inspecting the op and writing a custom modifier - will certainly end up in an invalid table structure. > Central systems is where CRDTs are used the most actually. I'm assuming the central system referred here is the database resilience systems using CRDTs to merge. Database syncing without master/slave is exactly the kind of problem best solved with CRDTs. The very point is to eliminate the need for a central point of failure.

ianopolous 6y ago

What do you think of Chronofold [1]? [1] https://arxiv.org/abs/2002.09511 https://arxiv.org/abs/2002.09511