30-Second Glance
- CRDTs let replicas accept concurrent updates with no coordination and still converge — used in Riak and Redis Enterprise sets.
- Operation-based CRDTs ship operations; they are compact but demand exactly-once, ordered delivery.
- State-based CRDTs ship whole state and merge with a commutative, associative, idempotent function — duplicates are safe, gossip suffices.
- Gossip spreads state peer-to-peer (periodic random exchange + merge) but adds traffic, slower convergence, and duplicate processing.
- Counters are easy (per-node inc/dec vectors summed); ordered sequences (Google Docs-style collaborative text) are the hard case.
Introduction
Conflict-Free Replicated Data Types (CRDTs) are designed to enable concurrent updates and ensure eventual consistency across distributed systems without requiring coordination.
Where're CRDTs used?
- Riak
- Redis (sets in Redis Enterprise)
Types of CRDTs:
1. Operational CRDTs:
Disadvantages:
Imagine we've a Set of DB-1 and DB-2:
2. State based CRDTs:
Let's send the whole CRDT, instead of the operators on it! -> Now, we can have duplicate messages.
For this to work, merge fn should be:
- Commutative: f(a,b) = f(b,a)
- Associative: f(a, f(b,c)) = f(f(a,b), c)
- Idempotent: f(a, b) = f(f(a, b), b)
Since, order doesn't matter, we can communicate via GOSSIP PROTOCOL (requires no extra messaging infrastructure)
How Gossip Protocol Works ??
The gossip protocol, inspired by the way rumors spread in social networks, works as follows:
- Periodic Communication:
- Each node periodically selects one or more random nodes to share its state.
- Information Exchange:
- Nodes exchange information about their local state, including updates they have received.
- State Merging:
- Nodes merge the received information with their local state, ensuring that all updates are eventually propagated to all nodes.
Disadvantages of GOSSIP Protocol:
- Network Overhead:
- The periodic communication can lead to increased network traffic, especially in very large systems.
- Convergence Time:
- The time it takes for all nodes to converge to the same state can vary and may be longer in systems with high latency or frequent partitions.
- Duplicate Messages:
- Nodes may receive the same update multiple times, leading to redundant processing.
Let's go through some types of CRDTs:
| Name | Operations | State |
|---|---|---|
| Counter | inc(leader) | incs: [0, 3, 2] -> sum(incs) = 5 |
| Decrease-able Counter | inc(leader), dec(leader) | incs: [0, 3, 2] & decs: [0, 1, 2] -> sum: (incs - decs) or (0, 3, 2) - (0 + 1 + 0) = 4 |
3. Sequential CRDTs:
Build an eventual consistent list. Very hard because elements are ordered! Used in Google Docs and other collaborative text editors!
Implementing sequential CRDTs is particularly challenging due to the inherent complexity of maintaining a consistent order across distributed nodes.
Why Sequential CRDTs are Tough to Implement ??
- Maintaining Order Consistency: Unlike sets or counters, where the order of elements does not matter, sequences must preserve the relative ordering of elements across all replicas.
- Handling Concurrent Inserts: When multiple nodes insert elements at the same position concurrently, the system must determine a consistent order for these elements.
- Complexity of Merge Functions: The merge functions that combine different replicas’ states must ensure that all operations are applied in a manner that maintains the sequence’s consistency and order. Designing these merge functions to handle all possible states and operations efficiently is complex and error-prone.
- Latency and Performance Trade-offs: Ensuring that all operations are correctly ordered and merged can introduce significant latency, especially in systems with high network latency or frequent partitions.
Trade-offs
| Approach | Pros | Cons | Use when |
|---|---|---|---|
| Operation-based CRDTs | Small messages (just the op) | Needs reliable exactly-once ordered messaging | Stable networks with messaging infra |
| State-based CRDTs + gossip | Tolerant of duplicates/reorder; no extra messaging infra | Ships whole state; gossip traffic and slower convergence | Partition-prone or infra-light deployments |
| G-Counter / PN-Counter | Trivial correct merge (sum per-node slots) | Only models counters, not arbitrary values | Likes, votes, inventory deltas |
| Sequential (list) CRDTs | Convergent ordered lists for collaboration | Hard: concurrent inserts at one position, complex merges, extra latency | Collaborative editors like Google Docs |
Interview One-Liners
Q: What problem do CRDTs solve? A: Concurrent updates across replicas that converge to the same state without coordination.
Q: Where are CRDTs used, per the note? A: Riak and sets in Redis Enterprise.
Q: Operation-based vs state-based CRDTs? A: Op-based sends operations (fragile to loss/duplication); state-based sends whole state and merges idempotently, so duplicates are harmless.
Q: What three properties must a state-based merge function have? A: Commutative, associative, and idempotent — order and repeats must not matter.
Q: How does gossip dissemination work and what does it cost? A: Nodes periodically swap state with random peers and merge; costs are network overhead, variable convergence time, and duplicate processing.
Q: Why are sequential CRDTs the hardest? A: They must keep a global element order despite concurrent inserts at the same position, which complicates merges and adds latency.