“Finding a space between.”
In a normal list, if you move item #3 to position #1, you have to re-number everything. In a distributed system, if two people re-number at the same time, it’s a disaster.
Here is how CRDTs solve this simply:
1. The “Betweenness” Logic (Fractional Indexing)
Imagine you have two bullets, A and B. Instead of saying “A is at position 1” and “B is at position 2,” we give them fractional coordinates.
-
Bullet A: Position 0.5
-
Bullet B: Position 0.6
If you want to insert a bullet between them, the app simply assigns it 0.55. You can do this forever. You can go to 0.551, 0.5512, etc. Since there is always a number between any two numbers, you never have to “re-index” the rest of the list.
2. Handling the “Same Spot” Conflict
What happens if two users, working offline, both try to insert a bullet between A and B at the exact same time?
-
User 1 inserts Bullet C at 0.55.
-
User 2 inserts Bullet D at 0.55.
To prevent a collision, CRDTs add a Unique User ID to the position.
-
Bullet C becomes
0.55 (User_789) -
Bullet D becomes
0.55 (User_456)
The algorithm has a simple tie-breaker rule: “If the positions are identical, the one with the higher User ID comes first.” Every device follows this same rule, so they all eventually land on the same order without ever talking to a central server.
concurrent and independent updates on different replicas without complex co-ordination, guaranteeing eventual convergence to consistent state through mathematical properties.
Key Concepts
- Independent Updates: Nodes can update their local data without waiting for consensus from others.
- Eventual Consistency: All replicas are guaranteed to reach the same state eventually, even with network delays.
- Automatic Conflict Resolution: The data type itself handles merging divergent updates deterministically.
Types of CRDTs
- State-based (CvRDTs):
Replicas exchange their entire state, which is merged using a commutative, associative, and idempotent function (like
unionfor sets). - Operation-based (CmRDTs): Replicas propagate operations (like “increment by 1”), which are designed to be commutative, ensuring order doesn’t matter.
Common Examples & Uses
- Counters: Grow-only counters (G-Counters) or up/down counters (PN-Counters).
- Sets: Grow-only sets (G-Sets) or two-set registers (add/remove sets).
- Collaborative Editing: Google Docs, VS Code Live Share.
- Databases: Redis, Riak, Couchbase, Azure Cosmos DB.