CRDTs

What are CRDTs?

Imagine you and your partner share a digital grocery list app. You are at the store, but you lose cell service. Offline, you check off "Milk" and add "Eggs." At the exact same time, your partner at home deletes "Bread" and adds "Apples." When your phone gets cell service back, what happens to the list?

Does your version overwrite theirs? Does the app throw a merge conflict error?

A CRDT (Conflict-free Replicated Data Type) is a brilliant mathematical solution to this problem. It is a specific type of data structure that guarantees that even if users make concurrent changes offline or on different servers, the data can always be merged back together flawlessly, without conflicts.

The Core Concept

In most databases, if two people update the same record at the same time, the last writer wins (meaning the first person's data is lost), or the database throws an error.

CRDTs are designed so that the operations are commutative. In math, addition is commutative (5 + 3 is the same as 3 + 5). CRDTs apply this logic to data structures. If you have two operations, it doesn't matter what order they are applied in. The final result will be identical.

Types of CRDTs

There are two main families of CRDTs:

1. State-based (CvRDT): Nodes send their entire state to each other. When a node receives a state, it runs a "merge" function that combines it with its own state. The merge function must be idempotent and commutative.
2. Operation-based (CmRDT): Nodes only send the specific operations (e.g., "Add 'Eggs'"). As long as the messaging system guarantees every message is delivered eventually (even if out of order), all nodes will arrive at the same state.

An Example: The G-Counter (Grow-only Counter)

Imagine a "Like" button on a viral video. You have 3 servers handling clicks.

• Server A gets 5 likes.
• Server B gets 3 likes.
• Server C gets 2 likes.

Instead of all servers trying to update a single central number (which creates a huge bottleneck), they use a G-Counter CRDT.

• The structure looks like this: { A: 5, B: 3, C: 2 }.
• When Server A gossips its state to Server B, they merge by taking the maximum value for each server.
• The total likes is just the sum of the array: 5 + 3 + 2 = 10. No matter how these servers exchange data, they will never conflict, and they will all eventually agree on the total.

More Complex CRDTs

• Sets: You can have an OR-Set (Observed-Remove Set) that tracks items added and removed, using unique tags to ensure if I add "Milk" and you delete "Milk," the system knows exactly which action happened first based on the tags.
• Text: The most complex CRDTs (like Yjs or Automerge) manage text editing, allowing multiple people to type in the same paragraph simultaneously.

Real-World Examples

• Figma: The multiplayer design tool uses CRDT concepts so multiple designers can edit a canvas simultaneously without stepping on each other's toes.
• Apple Notes: Shared notes sync via CRDTs, allowing you and a friend to edit a checklist offline, and it seamlessly merges when you reconnect.
• Redis Enterprise: Supports CRDT-based data types for active-active geo-replication, so users in the US and Europe can write to their local databases simultaneously without conflicts.
• Riak & Cassandra: Distributed databases that offer CRDT implementations for specific data types like counters and sets.

Summary

• CRDTs (Conflict-free Replicated Data Types) are data structures designed to perfectly merge concurrent updates without manual conflict resolution.
• They rely on mathematical properties (like commutativity) ensuring that no matter the order of updates, the final state is identical across all nodes.
• They are heavily used in collaborative software (Google Docs alternatives, Figma, local-first apps) and geo-distributed databases where high availability and offline work are required.