3 ms·

Interesting. What about the seqeunce "Alice deletes f, Bob replaces f with b, Alice inserts m"? I guess it doesn't matter, as long as all implementations do the

by flir 6y ago

Interesting. What about the seqeunce "Alice deletes f, Bob replaces f with b, Alice inserts m"? I guess it doesn't matter, as long as all implementations do the same thing. git could easily take an approach like this too, but there are obvious reasons why it doesn't. It feels like the people designing this algorithm believe the text being worked on is less important than source code. I don't see how it's possible. I get Alice's changes, I spend 3 hours working on them, I get Bob's changes. The algorithm might be able to resolve these three sets of changes consistently according to its rules, but I've got no faith that the meaning of the text would survive the process.

atombender 6y ago
CRDTs work best for high-contention situations such as online text editing (think Google Docs) where the conflict resolution can be seen right away and addressed by the user. For offline sync, where someone edits a text document for an hour and then syncs, you're right: You can end up with something unintended, since each participant is editing based on ("branching off") a snapshot. For example, if I deleted a whole paragraph, and you edited it, what should the end result be? But at least the end result will be consistent in the sense that all participants end up seeing the same thing, though semantically it may be wrong. Note that CRDTs go beyond just text. CRDTs can be used to represent arbitrary data structures and operations on them: Array s (insert, delete, append, etc.), numbers(increment, decrement, etc.), dictionaries (insert, delete), etc. A great implementation of this is Automerge [1]. [1] https://github.com/automerge/automerge https://github.com/automerge/automerge
- flir 6y ago
  Further thought: A list of deltas in a database is reversable - you can wind back to see what the database state was 3 weeks ago. Can you reverse a CRDT? I'm not sure why I keep coming back to this. Maybe because it's a new structure I've never thought about before. Maybe I'll have to implement one, just to get a feel for them.
- flir 6y ago
  That makes sense, and is reasonable. Thank you for taking the time to explain. I am now wondering about the space where CRDTs and databases overlap. (Very unformed thoughts follow) We're used to databases storing the system's current state. If we're lucky, we're writing changes to the database, rather than just the current state, so we can reconstruct the system's state at any point in the past. What would a database that not only stores changes but also resolves conflicts look like, I wonder. A database where CRDT was a column type, I guess.

by flir 6y ago

atombender 6y ago

CRDTs work best for high-contention situations such as online text editing (think Google Docs) where the conflict resolution can be seen right away and addressed by the user. For offline sync, where someone edits a text document for an hour and then syncs, you're right: You can end up with something unintended, since each participant is editing based on ("branching off") a snapshot. For example, if I deleted a whole paragraph, and you edited it, what should the end result be? But at least the end result will be consistent in the sense that all participants end up seeing the same thing, though semantically it may be wrong. Note that CRDTs go beyond just text. CRDTs can be used to represent arbitrary data structures and operations on them: Array s (insert, delete, append, etc.), numbers(increment, decrement, etc.), dictionaries (insert, delete), etc. A great implementation of this is Automerge [1]. [1] https://github.com/automerge/automerge https://github.com/automerge/automerge

flir 6y ago
Further thought: A list of deltas in a database is reversable - you can wind back to see what the database state was 3 weeks ago. Can you reverse a CRDT? I'm not sure why I keep coming back to this. Maybe because it's a new structure I've never thought about before. Maybe I'll have to implement one, just to get a feel for them.
flir 6y ago
That makes sense, and is reasonable. Thank you for taking the time to explain. I am now wondering about the space where CRDTs and databases overlap. (Very unformed thoughts follow) We're used to databases storing the system's current state. If we're lucky, we're writing changes to the database, rather than just the current state, so we can reconstruct the system's state at any point in the past. What would a database that not only stores changes but also resolves conflicts look like, I wonder. A database where CRDT was a column type, I guess.