4 ms·

> 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

> 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?
  - archagon 9y ago
    1. Yeah, that's why I mentioned "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". It's those points c) and d) that benefit most from the CRDT model. Point a) has of course been proven to work well with a central server, but not usually together with c) and d). It's very hard to handle all four cases if you're relying on a single source of truth. 2. Sure. Actually, if your design happens to be commutative for every operation after causal delivery, then you've invented what the paper calls a "pure op-based CRDT"! That means it'll work with a server or even through P2P (again, w/causal delivery) just by sending the operations around — no extra information required. I believe your vertex/edge example qualifies as long as each new object is created with a unique ID. However, if there's even a remote chance that two objects could be created with the same ID, then things fall apart, since you could have three concurrent operations of DEL-A, INS-A (the new one), and DEL-A, assuming a starting set that includes A. Depending on the order, you could end up with the set including or excluding A. This is why there are multiple kinds of CRDT sets and why they're not "pure op-based", e.g. Add-Wins and Remove-Wins as mentioned in the paper. I think you'll find that most data structures that are remotely interesting can't really be simplified down to the "pure op-based CRDT". PS, I made a mistake in the last comment, at least in terms of intent: the server won't be able to tiebreak that concurrency case since the ops have already been applied locally to all the clients and they don't commute. Instead, the server will be forced to either transform the operations (as in Operational Transformation) and then send them off (thus making them de facto commute), or alternatively panic, rebase (replaying part of its history), and force all clients to resync. That is, assuming the clients don't keep around the operation history themselves; if they do, they could perform the rebase/replay locally and the operations would (technically) commute. And this would even work for arbitrary operation-based data structures, including sequences or anything else. But then you have to make sure that replaying history has reasonable complexity, e.g. not O(N^2), or you'll be waiting hours if a concurrent commit resolves at the beginning of your operation stack. Ugh, this stuff is confusing...

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?
- archagon 9y ago
  1. Yeah, that's why I mentioned "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". It's those points c) and d) that benefit most from the CRDT model. Point a) has of course been proven to work well with a central server, but not usually together with c) and d). It's very hard to handle all four cases if you're relying on a single source of truth. 2. Sure. Actually, if your design happens to be commutative for every operation after causal delivery, then you've invented what the paper calls a "pure op-based CRDT"! That means it'll work with a server or even through P2P (again, w/causal delivery) just by sending the operations around — no extra information required. I believe your vertex/edge example qualifies as long as each new object is created with a unique ID. However, if there's even a remote chance that two objects could be created with the same ID, then things fall apart, since you could have three concurrent operations of DEL-A, INS-A (the new one), and DEL-A, assuming a starting set that includes A. Depending on the order, you could end up with the set including or excluding A. This is why there are multiple kinds of CRDT sets and why they're not "pure op-based", e.g. Add-Wins and Remove-Wins as mentioned in the paper. I think you'll find that most data structures that are remotely interesting can't really be simplified down to the "pure op-based CRDT". PS, I made a mistake in the last comment, at least in terms of intent: the server won't be able to tiebreak that concurrency case since the ops have already been applied locally to all the clients and they don't commute. Instead, the server will be forced to either transform the operations (as in Operational Transformation) and then send them off (thus making them de facto commute), or alternatively panic, rebase (replaying part of its history), and force all clients to resync. That is, assuming the clients don't keep around the operation history themselves; if they do, they could perform the rebase/replay locally and the operations would (technically) commute. And this would even work for arbitrary operation-based data structures, including sequences or anything else. But then you have to make sure that replaying history has reasonable complexity, e.g. not O(N^2), or you'll be waiting hours if a concurrent commit resolves at the beginning of your operation stack. Ugh, this stuff is confusing...