4 ms·

I was also a "true believer" in CRDTs for a long time, implementing my first ones in Erlang about 9 years ago[1], but my opinion of where they fit has changed s

by thamer 5y ago

I was also a "true believer" in CRDTs for a long time, implementing my first ones in Erlang about 9 years ago[1], but my opinion of where they fit has changed significantly. The one issue with CRDT that I find is rarely mentioned and often ignored is the case where you've deployed these data structures that include merge logic to a set of participating nodes that you can't necessarily update at will. Think phones that people don't update, or IOT/sensor devices like electric meters or other devices "in the wild". When you include merge logic – really any code or rules that dictate what happens when the the data of 2 or more CRDTs are merged – and you have bugs in this code running on devices you can never update, this can be a huge mess. Sure you can implement simple counters easily (like the ones I linked to), and you can even use model checking to validate them. But what about complex tree logic like for edits made to a document? Conflict resolution logic? Distributed file system operations? These are already very complex and hard to get right without multiple versions involved and unfixable bugs causing mayhem. Having to deal with these bugs in the context of a fleet of participants on a wide range of versions of the code, the combinatorial explosion of the number of possible interactions and effects of these differing versions and bugs taken together can really become impossible to manage. I'd be interested to hear from folks who have experience with these kinds of issues and how they have dealt with them, especially if they are still convinced that CRDTs were the right choice. [1] https://github.com/nicolasff/distributed-counters https://github.com/nicolasff/distributed-counters

bmurphy1976 5y ago
How are CRDTs unique in this respect? Ossification is a challenge for all APIs, domain models, network layers, protocol specs, etc.
- lazide 5y ago
  Because those other options abstract the decision making away from the ‘can never be updated’ part usually into some part of the system where the consequences of a problem/interest in the right solution are also collocated with someone who can do something about it (a API server with ossified clients, or network switch with buggy NIC’s wired into it, etc.) If truly peer to peer, that is a lot less clear - do you end up in a collaborative p2p document model forking the documents between ‘new rev’ clients and ‘old rev’ clients? Who ‘wins’? What is the consequence of losing? At least an API server can clearly reject the client and give an error message - if it’s a CRDT, how does that work?
josephg 5y ago
> ... you can't necessarily update at will. > When you include merge logic – really any code or rules that dictate what happens when the the data of 2 or more CRDTs are merged – and you have bugs in this code running on devices you can never update, this can be a huge mess. This is a really important point, and its a problem with distributed systems in general. Moxie Marlinspike (the guy behind Signal) gave a great talk on this a few years ago thats well worth a watch. He argues that distributed systems will always be outcompeted by their centralised counterpart because they can't add features as quickly: https://www.youtube.com/watch?v=Nj3YFprqAr8 https://www.youtube.com/watch?v=Nj3YFprqAr8 We've seen this playing out in real time watching git slowly upgrade its hashing function. The migration is taking years. I don't know a general solution, but a partial solution in my mind is that we need to knuckle up and make these base layers be correct. Model testing and fuzz testing can absolutely iron out bugs in this stuff, no matter how complex it seems. Bugs in application software usually aren't a big deal, but CRDTs fall in the same category as databases and compilers - we need to prioritise correctness so you can deploy this stuff and forget about it. Its not as bad as it sounds. The models which underpin even complex list CRDTs are still are orders of magnitude simpler than what compiler authors deal with daily. Correctness in a CRDT is also very easy to test for because there just aren't that many edge cases to find. You can count on one hand the number of ways you can modify a list and the invariants are straightforward to validate. We used fuzz testing for json-ot a few years ago and never ran into a single bug in production which was in the domain of things the fuzzer tested for. (Though the fuzzer was missing some obscure tests around updating cursor positions.)
_fullpint 5y ago
I’m not particularly familiar with CRDTs but it sounds like you’d need to define a semigroup no?

by thamer 5y ago

bmurphy1976 5y ago

How are CRDTs unique in this respect? Ossification is a challenge for all APIs, domain models, network layers, protocol specs, etc.

lazide 5y ago
Because those other options abstract the decision making away from the ‘can never be updated’ part usually into some part of the system where the consequences of a problem/interest in the right solution are also collocated with someone who can do something about it (a API server with ossified clients, or network switch with buggy NIC’s wired into it, etc.) If truly peer to peer, that is a lot less clear - do you end up in a collaborative p2p document model forking the documents between ‘new rev’ clients and ‘old rev’ clients? Who ‘wins’? What is the consequence of losing? At least an API server can clearly reject the client and give an error message - if it’s a CRDT, how does that work?

josephg 5y ago

> ... you can't necessarily update at will. > When you include merge logic – really any code or rules that dictate what happens when the the data of 2 or more CRDTs are merged – and you have bugs in this code running on devices you can never update, this can be a huge mess. This is a really important point, and its a problem with distributed systems in general. Moxie Marlinspike (the guy behind Signal) gave a great talk on this a few years ago thats well worth a watch. He argues that distributed systems will always be outcompeted by their centralised counterpart because they can't add features as quickly: https://www.youtube.com/watch?v=Nj3YFprqAr8 https://www.youtube.com/watch?v=Nj3YFprqAr8 We've seen this playing out in real time watching git slowly upgrade its hashing function. The migration is taking years. I don't know a general solution, but a partial solution in my mind is that we need to knuckle up and make these base layers be correct. Model testing and fuzz testing can absolutely iron out bugs in this stuff, no matter how complex it seems. Bugs in application software usually aren't a big deal, but CRDTs fall in the same category as databases and compilers - we need to prioritise correctness so you can deploy this stuff and forget about it. Its not as bad as it sounds. The models which underpin even complex list CRDTs are still are orders of magnitude simpler than what compiler authors deal with daily. Correctness in a CRDT is also very easy to test for because there just aren't that many edge cases to find. You can count on one hand the number of ways you can modify a list and the invariants are straightforward to validate. We used fuzz testing for json-ot a few years ago and never ran into a single bug in production which was in the domain of things the fuzzer tested for. (Though the fuzzer was missing some obscure tests around updating cursor positions.)

_fullpint 5y ago

I’m not particularly familiar with CRDTs but it sounds like you’d need to define a semigroup no?