CRDTs and operational transformation
How replicas that accept writes independently still converge: merge rules that commute, counters and sets as CRDTs, and how OT and sequence CRDTs handle collaborative text.
30 min7 steps
By the end you can
- Explain strong eventual consistency and the merge properties that guarantee it
- Merge G-Counter and PN-Counter states and compute their values
- Predict the outcome of concurrent add and remove under an OR-Set versus last-writer-wins
- Transform concurrent text edits with OT and contrast OT with sequence CRDTs
Merge rules that cannot disagree
Last-writer-wins
- Silently drops data
Keep siblings
- Dynamo style
- App code must merge
CRDT
- Merge built into the type
- Commutative, associative, idempotent
- Strong eventual consistency
Counters: G-Counter and PN-Counter
Replica A
[3, 0, 0]
increments only slot A
Replica B
[1, 4, 0]
has seen A at 1
Merge (max)
[3, 4, 0]
value = sum = 7
Set Replication algorithm to CRDT counters, set and RGA and select counter messages reorder and duplicate in Script.
Loading question…
Why not just send increments?
Sets: add, remove and who wins
Last-writer-wins set
- Later timestamp wins
- Clock skew decides
- Intent vanishes
OR-Set (add wins)
- Each add gets a unique tag
- Remove deletes observed tags only
- Concurrent add survives
Select observed-remove add wins in Script.
Collaborative text: operational transformation
Set Replication algorithm to OT with transformation, select concurrent insertion, then repeat under OT without transformation.
Loading question…
Sequence CRDTs: give every character an identity
How
- Permanent ID per character
- Insert 'after char X'
- Deterministic tie-break
Cost
- IDs and tombstones bloat state
- GC needs every replica's ack
Win
- Peer to peer
- No central server
- Offline for days
Select concurrent RGA edits in Script and compare text with tombstones.
Check your mastery
Commutative
a+b = b+a
Associative
grouping free
Idempotent
a+a = a
Score 80% or more. See also gossip, which carries CRDT state between replicas.
Mastery check
4 questions on fresh variants. One attempt each, no time limit. Score 80% or more to master the lesson.
Answer this step to continue.