4 ms·

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 communic

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...
- burntsushi 9y ago
  > I believe your vertex/edge example qualifies as long as each new object is created with a unique ID. Aye, that is indeed the case. (Technically, clients could misbehave/be buggy and insert whatever ID they like, but I think I can live with that. Otherwise, ID generation is handled in a way that guarantees uniqueness.) > 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. I came to this same conclusion as well, and this is exactly what the system does. (Notice that I've slyly gone from "here's this hypothetical design" to "I've actually built something similar to this design." :P) Persistent data structures help a lot here. I do expect to run into scaling problems with this design, but I think there are many buttons to push (of different kinds) to help with that. In particular, while it is not a document sharing service like Google Docs, it does have the same benefit where each operation belongs to one journal, and one journal makes up one graph, but there are many graphs in the system editable by users. Regardless, I'm really happy I provoked this discussion because I learned a lot!

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...

burntsushi 9y ago
> I believe your vertex/edge example qualifies as long as each new object is created with a unique ID. Aye, that is indeed the case. (Technically, clients could misbehave/be buggy and insert whatever ID they like, but I think I can live with that. Otherwise, ID generation is handled in a way that guarantees uniqueness.) > 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. I came to this same conclusion as well, and this is exactly what the system does. (Notice that I've slyly gone from "here's this hypothetical design" to "I've actually built something similar to this design." :P) Persistent data structures help a lot here. I do expect to run into scaling problems with this design, but I think there are many buttons to push (of different kinds) to help with that. In particular, while it is not a document sharing service like Google Docs, it does have the same benefit where each operation belongs to one journal, and one journal makes up one graph, but there are many graphs in the system editable by users. Regardless, I'm really happy I provoked this discussion because I learned a lot!