3 ms·

Usually people find that there are simpler/better ways to get the job done. Here's all the ways I know for dealing with write conflicts in a distributed system

Usually people find that there are simpler/better ways to get the job done. Here's all the ways I know for dealing with write conflicts in a distributed systems: - Last write wins, AKA I'm going to pretend I've solved the problem and just randomly lose data - Record all versions of the data, pick an arbitrary winner, store a revision, and surface it to the user if there's a conflict (the CouchDB strategy, I don't know anything else using this) - Model your data so it's append only (events, maybe) then merge just becomes a set union of all the different nodes[0] So including CRDTs, that's my general taxonomy of solutions to this problem. Are there more? [0] Working on a prototype for this right now, if anyone has done similar work I'd love to pick your brain, email in profile.

maffydub 5y ago
Slightly pedantic, but I think you'll actually find that all of these are CRDTs. If you read "Conflict-free Replicated Data Types: An Overview" (https://arxiv.org/pdf/1806.10254.pdf https://arxiv.org/pdf/1806.10254.pdf), it refers to both last write wins and "record all versions of the data" as CRDTs in 2.1.1. My understanding is that "CRDT" really just means that you've defined how you're going to resolve conflicts consistently (see criteria in s2.2 of the paper above).
- LAC-Tech 5y ago
  Yeah it had occurred to me that what I'm doing was just a GSet writ large. In my mind a CRDT was always a single record, not a collection of them - still not convinced that doesn't change it. But if CRDTs really are a kind of a meta-language for resolving conflicts in a sane way - whether the CRDT is a single record or a whole data store - that's a nice thought. The CouchDB CRDT could be defined.
kd5bjo 5y ago
CRDTs don’t quite fit in this list, as these are all valid merge strategies that a CRDT can use. The fundamental idea of a CRDT is that all of these schemes have something in common: They’re based on iteratively merging a bunch of versions together with a merge operator that fulfills a few basic properties (where + means merge: - Associativity: (A + B) + C == A + (B + C) - Commutativity: A + B == B + A - Idempotency: A + A = A - Closure: Every merge result is a valid merge argument - (perhaps a few others; it’s been a while since I read the original papers) As long as your merge operator has all of these properties, you get the strong eventual consistency result that makes CRDTs a useful abstraction: Any two users that have received versions including the same updates will reconstruct the document in the same way, even if the actual set of versions seen differs.
- LAC-Tech 5y ago
  That part is clear to me. What's not immediately obvious is that the DT in a CRDT can be entire database. Certainly the focus seems to be on individual data structures within a data store. Might have to re-read the papers with this thought in mind. It did seem like there was a duality there but I kind of dismissed it.
  - josephg 5y ago
    A CRDT is still just a data structure. Most of my work lately has been on building an operation based CRDT for lists. Storage wise, you basically just store the set of all the operations you know about. (Though you can trim that set down if you want, like a shallow git clone). You can store that set of operations just as easily in a file or in a database table. (Though the table will take a bit more space on disk because you can't be quite as clever). To generate the data value itself, you can either replay all the operations from scratch (which is not as bad as it sounds), or store a cached copy of the data at some version and use that. You can think about it as, the operations give you history, tell you how to merge in remote changes and contain the data remote peers need to sync. The data itself is the value you read out & display. There's nothing special about the data itself. You can store all that data in a flat file, or a database table, or in a few arrays in memory. The fancy part is (usually) how you merge changes together.
  - zozbot234 5y ago
    The conditions referenced in GP seem to imply that the most general state-based CRDT is simply a set of all reported outcomes. Something commutative, associative and idempotent is basically describing set union. So whether it's easy to go from one to the other would seem to depend on what constraints you're enforcing on your database. Operation-based CRDT's are a bit different, these require commutativity and associativity. So you would be dealing with a multiset of reported operations.

maffydub 5y ago

Slightly pedantic, but I think you'll actually find that all of these are CRDTs. If you read "Conflict-free Replicated Data Types: An Overview" (https://arxiv.org/pdf/1806.10254.pdf https://arxiv.org/pdf/1806.10254.pdf), it refers to both last write wins and "record all versions of the data" as CRDTs in 2.1.1. My understanding is that "CRDT" really just means that you've defined how you're going to resolve conflicts consistently (see criteria in s2.2 of the paper above).

LAC-Tech 5y ago
Yeah it had occurred to me that what I'm doing was just a GSet writ large. In my mind a CRDT was always a single record, not a collection of them - still not convinced that doesn't change it. But if CRDTs really are a kind of a meta-language for resolving conflicts in a sane way - whether the CRDT is a single record or a whole data store - that's a nice thought. The CouchDB CRDT could be defined.

kd5bjo 5y ago

CRDTs don’t quite fit in this list, as these are all valid merge strategies that a CRDT can use. The fundamental idea of a CRDT is that all of these schemes have something in common: They’re based on iteratively merging a bunch of versions together with a merge operator that fulfills a few basic properties (where + means merge: - Associativity: (A + B) + C == A + (B + C) - Commutativity: A + B == B + A - Idempotency: A + A = A - Closure: Every merge result is a valid merge argument - (perhaps a few others; it’s been a while since I read the original papers) As long as your merge operator has all of these properties, you get the strong eventual consistency result that makes CRDTs a useful abstraction: Any two users that have received versions including the same updates will reconstruct the document in the same way, even if the actual set of versions seen differs.

LAC-Tech 5y ago
That part is clear to me. What's not immediately obvious is that the DT in a CRDT can be entire database. Certainly the focus seems to be on individual data structures within a data store. Might have to re-read the papers with this thought in mind. It did seem like there was a duality there but I kind of dismissed it.
- josephg 5y ago
  A CRDT is still just a data structure. Most of my work lately has been on building an operation based CRDT for lists. Storage wise, you basically just store the set of all the operations you know about. (Though you can trim that set down if you want, like a shallow git clone). You can store that set of operations just as easily in a file or in a database table. (Though the table will take a bit more space on disk because you can't be quite as clever). To generate the data value itself, you can either replay all the operations from scratch (which is not as bad as it sounds), or store a cached copy of the data at some version and use that. You can think about it as, the operations give you history, tell you how to merge in remote changes and contain the data remote peers need to sync. The data itself is the value you read out & display. There's nothing special about the data itself. You can store all that data in a flat file, or a database table, or in a few arrays in memory. The fancy part is (usually) how you merge changes together.
- zozbot234 5y ago
  The conditions referenced in GP seem to imply that the most general state-based CRDT is simply a set of all reported outcomes. Something commutative, associative and idempotent is basically describing set union. So whether it's easy to go from one to the other would seem to depend on what constraints you're enforcing on your database. Operation-based CRDT's are a bit different, these require commutativity and associativity. So you would be dealing with a multiset of reported operations.