This blog post started with me trying to write a transcript of the talk I gave at ICDE’19 this week on Efficient Synchronization of State-based CRDTs. Soon after, it derailed in this.
UPDATE: The full transcript of the talk can now be found here.
The figure above was my first slide, where I attempted to explain the CRDT acronym. From right to left:
Data Types
In CRDTs, the abstraction is richer than simply reading and writing registers: we can increment/decrement counters, add/remove elements to/from sets, and so on…
Replicated
This is not specific to CRDTs. We replicate for quality of service. For example, with users across the globe, if we deploy replicas also across the globe, we can have low latency when accessing data. Also, if some replica is unavailable, users can fail-over to another close-by replica.
Conflict-free
Recall the PACELC theorem: if we have a network Partition, we must pick between Availability and Consistency; Else, even when everything is fine network-wise, we still must decide between low Latency and Consistency.
CRDTs are PA/EL. To achieve this, all updates are local to a replica. Then, in the background, replicas communicate in order to propagate new updates between them.
This approach can lead to conflicts when replicas concurrently write to the same object. And if that happens, which write should win? Which write is the one we want?
Why having a richer abstraction helps?
If we just have a register abstraction, any two concurrent writes to the same object conflict. But if these writes are increments to counters, there’s no conflict. Similarly, when elements are added to a set, no conflict is produced.
The general rule is that if two operations commute sequentially, then they are genuinely-conflict-free. When that doesn’t happen, CRDTs can pick one of the operations, becoming artificially-conflict-free.
Examples of pairs of operations that are genuinely-CF:
- increment / increment
- increment / decrement
- add A / add A
- add A / add B
- add A / remove B
Examples of pairs of operations that can be artificially-CF:
- write / write
- add A / remove A
Notice the “can be”: once we have identified pairs of conflicting operations, we can pick one of these operations or not. For example, a last-writer-wins register will pick one of the writes (based on a wall-clock timestamp), but a multi-value register will keep both (well, in fact, this is the only example I can think of in which both conflicting operations are kept).
Being artificial leads to concurrency semantics
Let’s focus on the last pair add A / remove A. Here we have three options:
- pick the add, and have a add-wins set
- pick the remove, and have a remove-wins set
- pick whichever has the highest timestamp, and have a last-writer-wins set
For applications, now this means that they need to figure in which artificial way should potential conflicts be resolved. For some, a removal can be discarded in the presence of an addition, while for others, the removal should always prevail. (I was trying to come up with application examples for both, but all ideas felt too farfetched. Any suggestions?)
Before we go
If you’re curious on concurrency semantics for other data types, check Section 2.1 of this great CRDT overview by Nuno Preguiça: Conflict-free Replicated Data Types: An Overview.
And as a good-bye note, we can say that “only by being artificial, one can be completely conflict-free”.
