4 ms·

Help me understand this more clearly. At what level of abstraction does the CRDT definition apply? At the data structure level, the application level, the end u

Help me understand this more clearly. At what level of abstraction does the CRDT definition apply? At the data structure level, the application level, the end user level? We can, for instance, use a simple directed acyclic graph of immutable data types as a data structure that can handle asynchronous updates and result in eventual consistency across all computers. We have a node in this DAG that says there’s a meeting at 1pm. Two people update this meeting time. One updates it to start at 2pm, and the other updates it to start at 3pm, and these changes happen simultaneously. The data structure now has a tree with the original parent node (1pm), and two new child nodes with new times (2pm and 3pm). All computers are updated cleanly and contain the same updated data structure. All conflicts handled. Zero conflicts exist at the data structure level. At the application level, the app now shows there’s a meeting “at 2pm or 3pm”. And all apps on all computers will reflect this same, consistent information. But to the people, there is a conflict in the meaning of this data. Is the meeting at 2pm or 3pm? This is somewhat analogous to a git merge conflict, where the “what to do about it” depends on the meaning to a human. Like I get the impression that a lot of people don’t consider the “meeting at 2pm or 3pm” to be a CRDT because it “doesn’t converge to a single value”. But from a physics perspective, there’s some binary data, some changes happen, and the new binary data is now replicated to all end user devices in the same state.

jakelazaroff 2y ago
The CRDT definition applies at the data structure level. Let’s model your meeting example as a set. Any local changes would atomically remove the current meeting time and add a new one. Multiple concurrent edits could result in two meeting times in the set. In terms of user experience, that’s a conflict — but from the CRDT’s perspective, it’s still a single consistent state upon which all peers eventually agree. Or, put slightly differently: the CRDT’s job is purely to make sure the peers can always agree on the same state. Any semantic conflicts within that state are an application-level concern. Slightly shameless plug, but I wrote a post showing how a CRDT fits into a toy application if you want to see how the layers fit together: https://jakelazaroff.com/words/building-a-collaborative-pixel-art-editor-with-crdts/ https://jakelazaroff.com/words/building-a-collaborative-pixe...
- yazaddaruvala 2y ago
  > In terms of user experience, that’s a conflict — but from the CRDT’s perspective, it’s still a single consistent state upon which all peers eventually agree. So then Git uses a CRDT internally? Merge conflicts are user experience "semantic conflicts" within the Git application. The internal state in the Git commit tree contain all commits consistent across the synced replicas. Without further inputs, all the repos would render the exact same user experience conflict. "The data type i.e. Git's internal state is conflict free - but there are times the user needs to correct the semantic state." "The Git application wants to guarantee semantic state, so unless the semantic conflicts are resolved, the Git internal state i.e. 'data type' will continue to be conflict-free using the 'rollback technique' to reconcile conflicts with the local copy's 'data type'." Roughly: git fetch would be the conflict-free update of the internal data type. While git merge would be the application level, semantic conflict resolution.
  - jakelazaroff 2y ago
    I don’t know enough about Git’s internals to be able to say. My gut says no; the (state-based) CRDT “rules” are that merges must be commutative, associative and idempotent, and I think if you tried to merge conflicting changes on multiple remotes in different orders, you would get different internal states. Not sure though!
  - josephg 2y ago
    Yeah I think you’re correct: Git’s internal data structure is a grow-only set CRDT (well, graph) of commit objects. Grow only sets of hashed contents are one of the simplest CRDTs out there - the network just implements set union. If git only had commit and fetch, it would be a crdt (though not a very useful one). But git also needs to merge commits / branches together. And it does that via diff-match-patch, which doesn’t pass the crdt rules. (Since it’s not idempotent, associative, automatic and in many cases deterministic).
    - yazaddaruvala 2y ago
      Thank you, I appreciate you taking the time to agree and offer additional nuance. I agree with your nuance. That is the nuance that makes Git not a CRDT. I can also appreciate academics need a time and place to be academic about their definitions (e.g. papers, and in-depth answers). > What are some real world apps using CRDTs that have really good experiences? I also feel, academics could do more to appreciate questions like this one are non-academic. The question above could just as easily be interpreted by many as "I'm building a multi-player application. I want it to be a really awesome experience but I don't know if I'll get the concurrency right. I've heard concurrency is hard. I've heard good things about CRDTs tho, should I be using them?". To which we should absolutely be mentioning truly pure CRDT based applications/frameworks, but not mentioning similar but nuancedly different applications/frameworks, hurts 1. any less educated readers' ability to instinctively understand what a CRDT is; and 2. how it might help them create the next great multi-player application. It also hurts someone that has spent the last N nights trying desperately to make their pure CRDT application/framework fun and valuable but its just not happening. Allowing them to loosen up and be a bit more creative, helping to empower their application/framework because the universe of "asymptotically approaching a CRDT; but will definitely not have concurrency bugs/issues" (which doesn't have a nice academic name + explicit ruleset yet) is so much larger "than strictly a CRDT". Meanwhile, I could if this was a paper or lecture have said "... are examples asymptotically approaching a CRDT; So don't really worry just because something is not strictly a CRDT doesn't mean you're gonna have bugs in your concurrency implementation". But "in passing" on a comment thread that should have been 30 seconds of all our time, who wants to specifically write all of that nuance every comment? In fairness I even tried to differentiate academic vs non-academic. If you're still reading this thread (especially anyone that has been downvoting me) I hope you can appreciate this context.

jakelazaroff 2y ago

The CRDT definition applies at the data structure level. Let’s model your meeting example as a set. Any local changes would atomically remove the current meeting time and add a new one. Multiple concurrent edits could result in two meeting times in the set. In terms of user experience, that’s a conflict — but from the CRDT’s perspective, it’s still a single consistent state upon which all peers eventually agree. Or, put slightly differently: the CRDT’s job is purely to make sure the peers can always agree on the same state. Any semantic conflicts within that state are an application-level concern. Slightly shameless plug, but I wrote a post showing how a CRDT fits into a toy application if you want to see how the layers fit together: https://jakelazaroff.com/words/building-a-collaborative-pixel-art-editor-with-crdts/ https://jakelazaroff.com/words/building-a-collaborative-pixe...

yazaddaruvala 2y ago
> In terms of user experience, that’s a conflict — but from the CRDT’s perspective, it’s still a single consistent state upon which all peers eventually agree. So then Git uses a CRDT internally? Merge conflicts are user experience "semantic conflicts" within the Git application. The internal state in the Git commit tree contain all commits consistent across the synced replicas. Without further inputs, all the repos would render the exact same user experience conflict. "The data type i.e. Git's internal state is conflict free - but there are times the user needs to correct the semantic state." "The Git application wants to guarantee semantic state, so unless the semantic conflicts are resolved, the Git internal state i.e. 'data type' will continue to be conflict-free using the 'rollback technique' to reconcile conflicts with the local copy's 'data type'." Roughly: git fetch would be the conflict-free update of the internal data type. While git merge would be the application level, semantic conflict resolution.
- jakelazaroff 2y ago
  I don’t know enough about Git’s internals to be able to say. My gut says no; the (state-based) CRDT “rules” are that merges must be commutative, associative and idempotent, and I think if you tried to merge conflicting changes on multiple remotes in different orders, you would get different internal states. Not sure though!
- josephg 2y ago
  Yeah I think you’re correct: Git’s internal data structure is a grow-only set CRDT (well, graph) of commit objects. Grow only sets of hashed contents are one of the simplest CRDTs out there - the network just implements set union. If git only had commit and fetch, it would be a crdt (though not a very useful one). But git also needs to merge commits / branches together. And it does that via diff-match-patch, which doesn’t pass the crdt rules. (Since it’s not idempotent, associative, automatic and in many cases deterministic).
  - yazaddaruvala 2y ago
    Thank you, I appreciate you taking the time to agree and offer additional nuance. I agree with your nuance. That is the nuance that makes Git not a CRDT. I can also appreciate academics need a time and place to be academic about their definitions (e.g. papers, and in-depth answers). > What are some real world apps using CRDTs that have really good experiences? I also feel, academics could do more to appreciate questions like this one are non-academic. The question above could just as easily be interpreted by many as "I'm building a multi-player application. I want it to be a really awesome experience but I don't know if I'll get the concurrency right. I've heard concurrency is hard. I've heard good things about CRDTs tho, should I be using them?". To which we should absolutely be mentioning truly pure CRDT based applications/frameworks, but not mentioning similar but nuancedly different applications/frameworks, hurts 1. any less educated readers' ability to instinctively understand what a CRDT is; and 2. how it might help them create the next great multi-player application. It also hurts someone that has spent the last N nights trying desperately to make their pure CRDT application/framework fun and valuable but its just not happening. Allowing them to loosen up and be a bit more creative, helping to empower their application/framework because the universe of "asymptotically approaching a CRDT; but will definitely not have concurrency bugs/issues" (which doesn't have a nice academic name + explicit ruleset yet) is so much larger "than strictly a CRDT". Meanwhile, I could if this was a paper or lecture have said "... are examples asymptotically approaching a CRDT; So don't really worry just because something is not strictly a CRDT doesn't mean you're gonna have bugs in your concurrency implementation". But "in passing" on a comment thread that should have been 30 seconds of all our time, who wants to specifically write all of that nuance every comment? In fairness I even tried to differentiate academic vs non-academic. If you're still reading this thread (especially anyone that has been downvoting me) I hope you can appreciate this context.