worm-blossom

What follows are lightly edited/expanded notes, taken during a workshop session entitled “Collecting Limitations of CRDTs”. Initially intended as an outlet for some frustrations, the session ended up surprisingly productive, surfacing not only grievances but also some not-entirely-obvious facets to appreciate.

We took turns talking, bringing up new ideas with each contribution, and the notes roughly reflect that structure. The notes are chronological, except that the appreciative contributions are confined to their own section, to not taint the carthatic purity of our venting.

I feel like you can cluster the complaints into three rough categories: problems intrinsic to CRDTs, problems arising from overreliance on CRDTs, and problems of communication and understanding. Since this is only my personal take on the session, I nevertheless present the notes in their original chronological order, and leave further sensemaking to the reader. ~Aljoscha

Problems with CRDTs

• CRDTs can only express conflict-free settings, but many settings aren't conflict-free. You can argue that only boring settings are conflict-free. We must not equate p2p or local-first with a CRDT-only mentality, as that would drastically limit which domains p2p/local-first can tackle at all.
• CRDTs can result in exposing intermediate, not-yet-fully-converged, inconsistent states to users.
• CRDTs remove agency in how to handle conflicts, they deterministically and arbitrarily make those decisions for you.
• Conflicts do happen, and CRDTs hide them. You should annotate them with metadata and expose them for appropriate handling instead.
• CRDTs are about eventual consistency, without any time bounds. In the real world, you cannot wait an arbitrarily long time, instead you end up implementing time-to-live and timeout mechanisms on top of CRDTs anyway, despite them supposedly shielding you from that work. Or if you don't implement such mechanisms, you end up with a system that behaves rather badly.
• CRDTs are limited in what they can express, but people try to express more interesting (i.e., conflicting) things as CRDTs anyway. This contortion results in bad CRDT designs, being brittle, requiring reliable ordered transport, etc. (The whole starting point for CRDTs is that of commutative operations; getting from that to requiring ordered transport is a grotesque absurdity.)
• Many CRDTs grow and grow and grow, accumulating information you can never get rid of.
• CRDTs foster the misunderstanding that they inherently have to accumulate ever more information, but that is not true: moving upwards in the semilattice does not inherently imply that no information is lost. The information content corresponds to the size of the largest antichain in the underlying order that contains the current state, and antichain sizes can definitely shrink again. More concretely: in Willow, writing an entry with a high timestamp can delete many entries with lesser timestamps, thus erasing information while still monotonically progressing in the lattice.
• CRDTs do not compose well, which is less than ideal for a fundamental building block.
• Definitions around CRDTs are slowly becoming blurred: designs that perform local deletion after timeouts often market themselves as being CRDTs, despite not satisfying the formal definition anymore.
• Conversely, strict adherence to the formal definition rules out sensible optimisations. We need more nuance.
• CRDTs shield developers from the problems arising from concurrency, but these problems don't actually disappear.

Blessings of CRDTs

• CRDTs are better than everything else we have; much more structured and helpful than a datagram-based view of networking. CRDTs enable an alternate take on networking, where they act as a substitute for the concept of transport mechanisms. For example, append-only logs take on a role comparable to that of TCP (in-order, reliable delivery).
• Many of the more problematic aspects of CRDTs can be sidestepped by keeping the scope of CRTs limited to transport-layer-like application.
• CRDTs are the best approach we have in some domains, for example in group management: instead of getting inconcsistent states in case of, for example, mutual concurrent group removal, the result is guaranteed to be well-defined, allowing the system to keep functioning.
• There is an elegance to systems not only using CRDTs, but being CRDTs themselves. The Pijul-approach of surfacing conflicts by tracking them inside a CRDT instead of hiding them is a powerful way of turning high-level facets of a system into a CRDT without losing flexibility.
• Perhaps there is a general pattern, where you use information-destroying CRDTs at the bottom, information-preserving CRDTs at the top, and gradually fade from one to the other across architectural layers.
• CRDTs have a precise definition.
• CRDT thinking can lead to better data structure designs (for example, the shift from expensive singular blockchains to lightweight distributed ledgers). CRDTs provide a powerful mental model for tackling new challenges.