3 ms·

Remember, "conflict free" is the opposite of "transactional" (ACID). When you choose conflict-free, you're choosing to give up the ability to reject a change du

Remember, "conflict free" is the opposite of "transactional" (ACID). When you choose conflict-free, you're choosing to give up the ability to reject a change due to conflict and send it back to the user for resolution. This is the crux of the issue in my opinion.

JayStavis 4y ago
Agreed - conflict resolution and authority handling are key to advanced game networking techniques and underpin the architecture of many big multiplayer games.
aboodman 4y ago
I don't think this is true on both accounts: * There is no such thing as "conflict free". When users edit data disconnected from each other, they can conflict, because the user intent of the edits can be different and not possible to reconcile. Nothing can fix that, not even crdts (As a thought experiment - two users are working on a report about ferrets. While offline, one decides the report should be about lemurs, while the other decides it should be about otters. The resulting set of changes will not be mergable without conflicts in any reasonable sense.) * What CRDTs give you is actually convergence which is very important. But there are other ways to get convergence, and it can be done transactionallym as long as your are willing to weaken the D (durability). Replicache (my thing - replicache.dev) is one way, the way described here is another. In general game networking is also transactional in this same sense. Operations are transactions, that can affect multiple data items and enforce arbitrary invariants. But the order they apply in drifts, and so durability is sacrificed. Stepping back even further, CRDTs are also often transactional in the same way. Each operation in an op-based crdt can be thought of a transaction that applies completely or not at all. It's just that the set of available operations in a CRDT is typically fixed.
- dustingetz 4y ago
  Replicache is cool 1. So by "weaken durability" you mean basically allow committed changes to be "lost" in the case of a common conflict, aka give it up entirely? 2. CRDTs are meant to converge even in the presence of network partitions (offline first), so you're saying your committed transactions can be uncommitted? Or you're saying writers have no idea if their transaction is committed because it might converge the other way after arbitrary delay? "Durability" means "transactions that have committed will survive permanently" – wikipedia
  - aboodman 4y ago
    Thanks :) > So by "weaken durability" you mean basically allow committed changes to be "lost" in the case of a common conflict, aka give it up entirely? I should have said "weaken ordering". I mean that the transaction will run, but its order with respect to other concurrently running transactions may be different in the end than the submitting client initially thought. As an extreme case, you submitted the transaction and your local client thought you got the concert tickets, but by the time it hits the server, the last ticket was already sold. Transaction still runs: it just runs first optimistically on the client, and then later authoritatively on the server with a potentially different result. Clients converge to serve view of the world and application invariants are maintained regardless (number of sold tickets doesn't go negative). Or just read Jepsen's take: https://doc.replicache.dev/concepts/consistency https://doc.replicache.dev/concepts/consistency In the case of concert tickets, this design doesn't make a lot of sense, but in lots of other cases -- in particular document editing applications -- it makes tons of sense. The chance of concurrent edits is low, but it is critical to maintain application-defined invariants when conflicts do occur. > CRDTs are meant to converge even in the presence of network partitions (offline first) Sure. Replicache converges in the presence of network partitions, as does OP's design, as do most games, distributed databases, etc. What CRDTs uniquely provide is the ability to converge *without a leader* -- in a p2p environment. As OP observes, this is not a property that most applications today need. Because they have an obvious leader: the server. > so you're saying your committed transactions can be uncommitted? Or you're saying writers have no idea if their transaction is committed because it might converge the other way after arbitrary delay? They run optimistically (speculatively) on the client, and then later authoritatively on the server. Application can render the optimistic result, and then later the authoritative result when it is known. This is exactly what CRDTs do. The only difference is that CRDTs can do it without a leader, but the Replicache (and OP's) design offers additional flexibility -- ability to define your own operation/transactions. === We need new terminology for distributed systems. Terms invented in the 70s aren't going to make sense. I believe that "transactions" in the common parlance mean "a set of code that runs together or not at all, isolated from other concurrently running transactions". This is entirely possible to provide with convergence if we are willing to weaken ordering.
    - 4y ago

JayStavis 4y ago

Agreed - conflict resolution and authority handling are key to advanced game networking techniques and underpin the architecture of many big multiplayer games.

aboodman 4y ago

I don't think this is true on both accounts: * There is no such thing as "conflict free". When users edit data disconnected from each other, they can conflict, because the user intent of the edits can be different and not possible to reconcile. Nothing can fix that, not even crdts (As a thought experiment - two users are working on a report about ferrets. While offline, one decides the report should be about lemurs, while the other decides it should be about otters. The resulting set of changes will not be mergable without conflicts in any reasonable sense.) * What CRDTs give you is actually convergence which is very important. But there are other ways to get convergence, and it can be done transactionallym as long as your are willing to weaken the D (durability). Replicache (my thing - replicache.dev) is one way, the way described here is another. In general game networking is also transactional in this same sense. Operations are transactions, that can affect multiple data items and enforce arbitrary invariants. But the order they apply in drifts, and so durability is sacrificed. Stepping back even further, CRDTs are also often transactional in the same way. Each operation in an op-based crdt can be thought of a transaction that applies completely or not at all. It's just that the set of available operations in a CRDT is typically fixed.

dustingetz 4y ago
Replicache is cool 1. So by "weaken durability" you mean basically allow committed changes to be "lost" in the case of a common conflict, aka give it up entirely? 2. CRDTs are meant to converge even in the presence of network partitions (offline first), so you're saying your committed transactions can be uncommitted? Or you're saying writers have no idea if their transaction is committed because it might converge the other way after arbitrary delay? "Durability" means "transactions that have committed will survive permanently" – wikipedia
- aboodman 4y ago
  Thanks :) > So by "weaken durability" you mean basically allow committed changes to be "lost" in the case of a common conflict, aka give it up entirely? I should have said "weaken ordering". I mean that the transaction will run, but its order with respect to other concurrently running transactions may be different in the end than the submitting client initially thought. As an extreme case, you submitted the transaction and your local client thought you got the concert tickets, but by the time it hits the server, the last ticket was already sold. Transaction still runs: it just runs first optimistically on the client, and then later authoritatively on the server with a potentially different result. Clients converge to serve view of the world and application invariants are maintained regardless (number of sold tickets doesn't go negative). Or just read Jepsen's take: https://doc.replicache.dev/concepts/consistency https://doc.replicache.dev/concepts/consistency In the case of concert tickets, this design doesn't make a lot of sense, but in lots of other cases -- in particular document editing applications -- it makes tons of sense. The chance of concurrent edits is low, but it is critical to maintain application-defined invariants when conflicts do occur. > CRDTs are meant to converge even in the presence of network partitions (offline first) Sure. Replicache converges in the presence of network partitions, as does OP's design, as do most games, distributed databases, etc. What CRDTs uniquely provide is the ability to converge *without a leader* -- in a p2p environment. As OP observes, this is not a property that most applications today need. Because they have an obvious leader: the server. > so you're saying your committed transactions can be uncommitted? Or you're saying writers have no idea if their transaction is committed because it might converge the other way after arbitrary delay? They run optimistically (speculatively) on the client, and then later authoritatively on the server. Application can render the optimistic result, and then later the authoritative result when it is known. This is exactly what CRDTs do. The only difference is that CRDTs can do it without a leader, but the Replicache (and OP's) design offers additional flexibility -- ability to define your own operation/transactions. === We need new terminology for distributed systems. Terms invented in the 70s aren't going to make sense. I believe that "transactions" in the common parlance mean "a set of code that runs together or not at all, isolated from other concurrently running transactions". This is entirely possible to provide with convergence if we are willing to weaken ordering.
  - 4y ago