CRDTs. Data structures that can be replicated across multiple nodes, edited independently, merged back together, and it all just works. But collaborative document editing and multiplayer TODO lists are just the tip of the iceberg – I believe the big application is distributed databases, and for that we need to talk about consistency.

CRDTs are a tool for Strong Eventual Consistency. Let’s start with the definition of normal Eventual Consistency¹:

Eventual Delivery

An update delivered to one node will eventually reaches all nodes

Eventual Convergence

If two nodes have seen all the same updates, they will eventually have the same state.

Strong Eventual Consistency (SEC) replaces Eventual Convergence with Strong Convergence:

Strong Convergence

If two nodes have seen all the same updates, they will have the same state.

Spot the difference! In SEC two replicas have the same state as soon as the updates are processed, not eventually. If multiple nodes are updated independently, there will be conflicts – this is inevitable. What SEC guarantees is that these conflicts are solved automatically and deterministically.

This has massive implications. SEC means low latency, because nodes don’t need to coordinate to handle reads and writes. It means incredible fault tolerance – every single node in the system bar one could simultaneously crash, and reads and writes could still happen normally. And it means nodes still function properly if they’re offline or split from the network for arbitrary time periods.

Strong Eventual Consistency is Eventual Consistency that works. If you’re doing local first, or low latency geo-replicated systems – accept no substitute. This is the context I think we should see CRDTs in – building blocks of Strongly Eventually Consistent systems. CRDTs as application state as one thing, CRDTs as entire databases are quite another.

I’m available for hire.