3 ms·

I think there are few systems built like this because we're living in a decidedly centralized world. Also, CRDTs involve many tradeoffs (limited # of primitive

I think there are few systems built like this because we're living in a decidedly centralized world. Also, CRDTs involve many tradeoffs (limited # of primitive types, complex performance characteristics, difficult algorithms, garbage collection) which make them less a swap-in option than a complete paradigm shift. Still, there are many situations where building on CRDTs would make your software far more resilient. For instance: let's say you want to design a document-based app that a) supports real-time collaboration, b) supports sync to a central server, c) works offline for arbitrary periods of time, d) supports real-time sync between offline and/or local devices. If you're relying on a central server to give you a total order, this would be very hard to do. With a CRDT-based system, it's effectively built-in. Doesn't matter if your peers are local devices, ad-hoc peers, a central server, or even a file on a USB stick: everything will still merge in the end, as long as you can distribute your ops in causal order. (And if you're using a state-based CvRDT, even that doesn't matter. Just send your file and it will merge.) At the limit, this means not having to think about the consistency of your data in terms of the network.

burntsushi 9y ago
> a) supports real-time collaboration, b) supports sync to a central server, c) works offline for arbitrary periods of time, d) supports real-time sync between offline and/or local devices. If you're relying on a central server to give you a total order, this would be very hard to do. I guess my question is: why is this hard to do? I have another comment[1] in this thread that gives a bit more of a detailed example. Others in this thread also seem to be implying that my stated design is similar to how Google Wave worked. From Raph's article that I linked my initial comment: > Almost all practical implementations of OT forego TP2, and solve the problem by limiting concurrency in some way, generally requiring a central server to decide on a canonical ordering of the operations (but still using transformations to let clients apply operations out-of-order just a little bit). Maybe the parenthetical bit about transformations is the part I'm leaving out that I need to make more explicit? Not sure. [1] - https://news.ycombinator.com/item?id=15498216 https://news.ycombinator.com/item?id=15498216
- archagon 9y ago
  If your design is resilient enough to work between arbitrary peers, then you've essentially reinvented OT or a CRDT and your central server is vestigial, no? Basically, if peers are collaborating amongst themselves while disconnected from the central server (as in the case of offline devices working on the same file), they have to figure out how to resolve conflicts between each other anyway. CRDTs simply make this process deterministic. Also, it should be noted that Google's OT does not actually let you work offline for very long. Hence, "apply operations out-of-order just a little bit". As for your example: There are two things that algorithms for eventual consistency have to deal with. First, causality. This is your add/remove vertex example. Obviously, a vertex can't be removed before it's added. Any "remove" has to causally follow the "add". Causality, however, is usually dealt with on the transport layer via causal delivery, i.e. it's not really part of the CRDT. The "hard" CRDT/OT case is a set of concurrent operations without any causal order. In terms of your example, you picked a data structure which is essentially a pair of sets — an easy case. Consider instead an array. Array operations that are not commutative are not necessarily dependent, such as three peers simultaneously adding an item to the same index. There is no causal "order in which they were applied". CRDTs allow you to tiebreak this case, often by deterministically ordering concurrent operations via their causal timestamp and owner UUID. These bits of info are not really part of the data, but they're still necessary to derive a total order. Thus, they tend to be included as part of each CRDT op, ballooning its size. I believe what the paper proposes is separating out this metadata from the operations, then clearing it out to save space when it's no longer necessary. (That is, when all clients have merged past the spot of contention.) And yes, a central server could perform this tiebreaking step. But in the meantime, the peers talking amongst themselves could be building on their locally-resolved conflicts and find themselves rudely interrupted when the server decides that no, the "truth" they've been assuming for the past minute/hour/day/month is actually the wrong one. (Remember, our goal is arbitrarily long periods of local/P2P/offline communication.)
  - burntsushi 9y ago
    Interesting, thanks, this does help clarify things for me. I just wanted to post a few follow up clarifications: 1. In my world, the clients don't communicate with each other. Everything has to bounce off the central server first. 2. And yeah, a graph is the easy case. I definitely agree that my design doesn't address sequences. If your application doesn't require sequences, though, then perhaps it's possible to get away with this simpler solution?

burntsushi 9y ago

> a) supports real-time collaboration, b) supports sync to a central server, c) works offline for arbitrary periods of time, d) supports real-time sync between offline and/or local devices. If you're relying on a central server to give you a total order, this would be very hard to do. I guess my question is: why is this hard to do? I have another comment[1] in this thread that gives a bit more of a detailed example. Others in this thread also seem to be implying that my stated design is similar to how Google Wave worked. From Raph's article that I linked my initial comment: > Almost all practical implementations of OT forego TP2, and solve the problem by limiting concurrency in some way, generally requiring a central server to decide on a canonical ordering of the operations (but still using transformations to let clients apply operations out-of-order just a little bit). Maybe the parenthetical bit about transformations is the part I'm leaving out that I need to make more explicit? Not sure. [1] - https://news.ycombinator.com/item?id=15498216 https://news.ycombinator.com/item?id=15498216

archagon 9y ago
If your design is resilient enough to work between arbitrary peers, then you've essentially reinvented OT or a CRDT and your central server is vestigial, no? Basically, if peers are collaborating amongst themselves while disconnected from the central server (as in the case of offline devices working on the same file), they have to figure out how to resolve conflicts between each other anyway. CRDTs simply make this process deterministic. Also, it should be noted that Google's OT does not actually let you work offline for very long. Hence, "apply operations out-of-order just a little bit". As for your example: There are two things that algorithms for eventual consistency have to deal with. First, causality. This is your add/remove vertex example. Obviously, a vertex can't be removed before it's added. Any "remove" has to causally follow the "add". Causality, however, is usually dealt with on the transport layer via causal delivery, i.e. it's not really part of the CRDT. The "hard" CRDT/OT case is a set of concurrent operations without any causal order. In terms of your example, you picked a data structure which is essentially a pair of sets — an easy case. Consider instead an array. Array operations that are not commutative are not necessarily dependent, such as three peers simultaneously adding an item to the same index. There is no causal "order in which they were applied". CRDTs allow you to tiebreak this case, often by deterministically ordering concurrent operations via their causal timestamp and owner UUID. These bits of info are not really part of the data, but they're still necessary to derive a total order. Thus, they tend to be included as part of each CRDT op, ballooning its size. I believe what the paper proposes is separating out this metadata from the operations, then clearing it out to save space when it's no longer necessary. (That is, when all clients have merged past the spot of contention.) And yes, a central server could perform this tiebreaking step. But in the meantime, the peers talking amongst themselves could be building on their locally-resolved conflicts and find themselves rudely interrupted when the server decides that no, the "truth" they've been assuming for the past minute/hour/day/month is actually the wrong one. (Remember, our goal is arbitrarily long periods of local/P2P/offline communication.)
- burntsushi 9y ago
  Interesting, thanks, this does help clarify things for me. I just wanted to post a few follow up clarifications: 1. In my world, the clients don't communicate with each other. Everything has to bounce off the central server first. 2. And yeah, a graph is the easy case. I definitely agree that my design doesn't address sequences. If your application doesn't require sequences, though, then perhaps it's possible to get away with this simpler solution?