5 ms·

Have you used CRDTs to solve any practical problems? If so, how does the CRDT solution compare to a non-CRDT solution? If a non-CRDT solution is feasible at al

Have you used CRDTs to solve any practical problems? If so, how does the CRDT solution compare to a non-CRDT solution? If a non-CRDT solution is feasible at all?

mirekrusin 5y ago
Article mentions at the beginning that the author used CRDT in Google Wave/ShareJS.
- paulgb 5y ago
  Wave used OT rather than CRDTs, as the author discusses in another post: https://josephg.com/blog/crdts-are-the-future/ https://josephg.com/blog/crdts-are-the-future/
- saurik 5y ago
  AFAIK Wave and ShareJS both used OT (which the paper that this article referred to was also attempting to benchmark). FWIW, I am myself also curious about this (the question of comparing CRDT to non-CRDT solutions): I found OT beautiful, but never really felt CRDT had the same feeling of elegance; and so I am downright fascinated to see the person I have always seen as a "god of OT" deciding to forsake it and move to CRDTs going forward. Are they really that great? Is there something simple I am missing for the explanation for why they are so much better? (Is it maybe that they can support arbitrary merging without a sequencer to linearize the edits? Honestly, my question probably sucks a bit as I haven't spent any time thinking about OT or CRDT in at least three years--and even then only once since a few years before that, as I have had other things to spend most of my mental energy on recently--and so I am failing to remember the details of my use cases or the tradeoffs I saw or the implementation issues I felt were easy/hard.)
  - the-smug-one 5y ago
    Do you want a centralized server to control the data? Then just use OT. Do you want users to control the data, and have your server essentially just be a forever-present user? Then use CRDT. CRDTs certainly do have a mathematical elegance to them.
    - josephg 5y ago
      Yep, this is the best practical advice at the moment. Well, for list CRDTs. State CRDTs (like a counter) are small and fast, and kinda better than OT in every way. List ("operation based") CRDTs and OT systems are "equivalent" in a very academic sense that nobody really talks about or understands. Its really not obvious unless you've been staring at this stuff for years but the equivalence is there: You can make a CRDT out of any OT system by just shipping the entire history of operations to each peer. List CRDTs essentially do that, with a whole lot of tricks to compress that data set and use it without needing to linearly scan. And you can convert the other way too. You can add a "rename" operation into a list CRDT which assigns a new name to each element currently in the document. Before the rename operation document "hello" might have IDs [a4, b2, b3, b1, a5]. The rename operation changes the IDs to [c1, c2, c3, c4, c5]. When an operation happens you specify the version and the ID at that version of the predecessor (eg c2). The insert happens there. Then you need a method to take the ID at one version and "transform" it to the ID of the same item at a different version. Do the rename operation implicitly after every change, and viola! You now have OT semantics. "Insert after c1" means "Insert after position 1". OT systems have one big advantage which is that you don't have to ship the CRDT state to every peer. With a rename operation, we can add back the operational simplicity of OT systems into a CRDT. But the code is (and always will be) much more complicated. So I think OT makes sense for strictly server-client systems. You can also have a hybrid server, which talks CRDT to full peers on the network but just does OT when talking to browser clients and things like that. We talked about this at our public braid meeting at the start of the week. The discussion about this stuff starts about 30 minutes in: https://braid.org/meeting-15 https://braid.org/meeting-15
      - zozbot234 5y ago
        > And you can convert the other way too. You can add a "rename" operation into a list CRDT which assigns a new name to each element currently in the document. Operations in a CRDT must be commutative for merge/update to be well-defined, so it's not immediately clear how a "rename" operation can be expected to work properly.
      - archagon 5y ago
- mirekrusin 5y ago
  My mistake, it says OT was used, thank you for correcting me.
Jailbird 5y ago
Drifting off-topic but I've wondered this myself - I've been interested in CRDTs in a "read the news" way but not a "this rises to something I'm going to implement" way. Perhaps it's blindingly obvious to all here, so no one mentions it: Thinking about more practical and real-world problems seems like collaboration on on more complex/structured data. Today, it seems one would still have to transform that data to a large flat string underneath, and implement an editor that only performs edits that maintain the integrity of the higher-level object, while the flat string provides collaboration features. Perhaps it's possible to implement an XML schema known to the editor so all insertions/deletions keep the document syntactically correct. I wonder if there's some other way to either generalize on top of "big string" or create another base model (somehow?)
- detaro 5y ago
  CRDT is a general concept, editing text is just one possible application. If you have a stronger datatype, great, you can build operations on top of it to implement a CRDT system, depending on its properties.
  - Jailbird 5y ago
    What I've read talks about character insertion and concepts that apply to editing text. Perhaps I just need to find bedrock to build up from about the properties of a stronger datatype that allow CRDTs to work.
    - detaro 5y ago
      https://arxiv.org/pdf/1805.06358.pdf https://arxiv.org/pdf/1805.06358.pdf looks like a decent starting point, with references to work on other types.
      - Jailbird 5y ago
        and pointers to other papers, too - thanks!
  - 5y ago

Have you used CRDTs to solve any practical problems? If so, how does the CRDT solution compare to a non-CRDT solution? If a non-CRDT solution is feasible at all?

mirekrusin 5y ago

Article mentions at the beginning that the author used CRDT in Google Wave/ShareJS.

paulgb 5y ago
Wave used OT rather than CRDTs, as the author discusses in another post: https://josephg.com/blog/crdts-are-the-future/ https://josephg.com/blog/crdts-are-the-future/
saurik 5y ago
AFAIK Wave and ShareJS both used OT (which the paper that this article referred to was also attempting to benchmark). FWIW, I am myself also curious about this (the question of comparing CRDT to non-CRDT solutions): I found OT beautiful, but never really felt CRDT had the same feeling of elegance; and so I am downright fascinated to see the person I have always seen as a "god of OT" deciding to forsake it and move to CRDTs going forward. Are they really that great? Is there something simple I am missing for the explanation for why they are so much better? (Is it maybe that they can support arbitrary merging without a sequencer to linearize the edits? Honestly, my question probably sucks a bit as I haven't spent any time thinking about OT or CRDT in at least three years--and even then only once since a few years before that, as I have had other things to spend most of my mental energy on recently--and so I am failing to remember the details of my use cases or the tradeoffs I saw or the implementation issues I felt were easy/hard.)
- the-smug-one 5y ago
  Do you want a centralized server to control the data? Then just use OT. Do you want users to control the data, and have your server essentially just be a forever-present user? Then use CRDT. CRDTs certainly do have a mathematical elegance to them.
  - josephg 5y ago
    Yep, this is the best practical advice at the moment. Well, for list CRDTs. State CRDTs (like a counter) are small and fast, and kinda better than OT in every way. List ("operation based") CRDTs and OT systems are "equivalent" in a very academic sense that nobody really talks about or understands. Its really not obvious unless you've been staring at this stuff for years but the equivalence is there: You can make a CRDT out of any OT system by just shipping the entire history of operations to each peer. List CRDTs essentially do that, with a whole lot of tricks to compress that data set and use it without needing to linearly scan. And you can convert the other way too. You can add a "rename" operation into a list CRDT which assigns a new name to each element currently in the document. Before the rename operation document "hello" might have IDs [a4, b2, b3, b1, a5]. The rename operation changes the IDs to [c1, c2, c3, c4, c5]. When an operation happens you specify the version and the ID at that version of the predecessor (eg c2). The insert happens there. Then you need a method to take the ID at one version and "transform" it to the ID of the same item at a different version. Do the rename operation implicitly after every change, and viola! You now have OT semantics. "Insert after c1" means "Insert after position 1". OT systems have one big advantage which is that you don't have to ship the CRDT state to every peer. With a rename operation, we can add back the operational simplicity of OT systems into a CRDT. But the code is (and always will be) much more complicated. So I think OT makes sense for strictly server-client systems. You can also have a hybrid server, which talks CRDT to full peers on the network but just does OT when talking to browser clients and things like that. We talked about this at our public braid meeting at the start of the week. The discussion about this stuff starts about 30 minutes in: https://braid.org/meeting-15 https://braid.org/meeting-15
    - zozbot234 5y ago
      > And you can convert the other way too. You can add a "rename" operation into a list CRDT which assigns a new name to each element currently in the document. Operations in a CRDT must be commutative for merge/update to be well-defined, so it's not immediately clear how a "rename" operation can be expected to work properly.
    - archagon 5y ago
mirekrusin 5y ago
My mistake, it says OT was used, thank you for correcting me.

Jailbird 5y ago

Drifting off-topic but I've wondered this myself - I've been interested in CRDTs in a "read the news" way but not a "this rises to something I'm going to implement" way. Perhaps it's blindingly obvious to all here, so no one mentions it: Thinking about more practical and real-world problems seems like collaboration on on more complex/structured data. Today, it seems one would still have to transform that data to a large flat string underneath, and implement an editor that only performs edits that maintain the integrity of the higher-level object, while the flat string provides collaboration features. Perhaps it's possible to implement an XML schema known to the editor so all insertions/deletions keep the document syntactically correct. I wonder if there's some other way to either generalize on top of "big string" or create another base model (somehow?)

detaro 5y ago
CRDT is a general concept, editing text is just one possible application. If you have a stronger datatype, great, you can build operations on top of it to implement a CRDT system, depending on its properties.
- Jailbird 5y ago
  What I've read talks about character insertion and concepts that apply to editing text. Perhaps I just need to find bedrock to build up from about the properties of a stronger datatype that allow CRDTs to work.
  - detaro 5y ago
    https://arxiv.org/pdf/1805.06358.pdf https://arxiv.org/pdf/1805.06358.pdf looks like a decent starting point, with references to work on other types.
    - Jailbird 5y ago
      and pointers to other papers, too - thanks!
- 5y ago