CRDTs: Conflict-free Replicated Data Types

In this lesson, you will learn how Conflict-free Replicated Data Types (CRDTs) enable distributed nodes to achieve strong eventual consistency without the need for central coordination or consensus protocols.

When distributed databases face the constraints of the CAP theorem, we often favor availability over strong consistency. However, conflicts arise when multiple replicas accept independent writes. CRDTs solve this by designing data structures with mathematical properties—specifically commutativity, associativity, and idempotency—ensuring that replicas always arrive at the same state regardless of the order in which updates are received.

State-based vs. Operation-based CRDTs

1. State-based (CvRDTs): Replicas exchange their full state. To merge two states, we define a "join" function that computes the least upper bound. For example, a G-Counter (Grow-only Counter) is a vector of integers where each node maintains its own count. Merging simply involves taking the max() of each corresponding element in the vector.

   # Merge logic for a simple G-Counter state
   def merge(state_a, state_b):
       return [max(a, b) for a, b in zip(state_a, state_b)]
   

2. Operation-based (CmRDTs): Replicas propagate the operation performed rather than the full state. This is more bandwidth-efficient but requires the underlying communication channel to guarantee delivery (or handle causal ordering). Because operations are commutative, applying Add(5) and Add(10) in any order results in the same final sum.

Why this matters

CRDTs allow us to build systems that remain highly available even during network partitions. Because the merge logic is deterministic and commutative, we eliminate the need for complex conflict resolution mechanisms like "last-write-wins," which can silently discard data. By embedding the rules of resolution into the data structure itself, we move consistency from the application layer into the database schema, ensuring that as long as every update eventually reaches every node, the database remains in a globally consistent state.

Key Takeaway: CRDTs achieve convergence in distributed systems by ensuring that all concurrent updates are commutative, allowing independent replicas to reach the same state through deterministic merging rather than central coordination.