What a merge function does
When two copies of the same data change apart, something has to combine them. A merge function is that something: it takes two versions and returns one.
The term has a precise meaning in CRDTs. The CRDT glossary describes a state-based CRDT as one where replicas send each other their entire state, and a replica that receives a state “uses a merge function to combine the two states”. Outside CRDTs the term is looser. Kleppmann and Beresford point out that a database such as CouchDB keeps every conflicting value and leaves the merge to application code, while other systems apply a fixed rule such as keeping the newest value.
A merge function is only useful if every replica that runs it ends up in the same place, whatever order the states arrived in and however often each one arrived. Three properties guarantee that.
The three properties
The CRDT glossary defines a state-based merge as:
- Commutative: merge(a, b) = merge(b, a). It does not matter which device’s state arrives first.
- Associative: merge(a, merge(b, c)) = merge(merge(a, b), c). A device can merge states it collected from several others and pass on the result, and nothing changes.
- Idempotent: merge(a, a) = a. Receiving the same state twice does no harm, which matters when the same update arrives through two routes, as it can in a mesh. The idempotency article covers the same idea for message delivery.
Shapiro, Preguiça, Baquero and Zawirski show where these come from. If the possible states can be ordered so that any two have a least upper bound, the smallest state that includes both, then a merge that computes that bound has all three properties. If every local update also moves the state upward, all replicas that receive the same updates converge.
Familiar operations pass or fail these tests:
- Set union passes all three. It is the merge for a grow-only set.
- Maximum passes all three. It is the merge for a value that only increases.
- Addition is commutative and associative but not idempotent: adding the same state twice counts it twice.
- “Keep my version” is not commutative: each device would keep its own and they would never agree.
Merge functions for common types
The comprehensive study gives a merge for each CRDT in its portfolio. A few show the range.
| Data | Merge function | Effect |
|---|---|---|
| Grow-only set | Union of both sets | Every added item is kept |
| Grow-only counter | Larger value per replica entry; the value is the sum | Every device’s increments count once |
| Last-writer-wins register | Keep the value with the higher timestamp | One concurrent write is dropped |
| Multi-value register | Keep every value not superseded by a later one | Concurrent writes are all kept for later resolution |
| Two-phase set | Union of the added set and union of the removed set | A removed item stays removed |
Larger structures compose these. A map merges key by key using each value’s own merge, and a whole document merges by merging its parts.
Where hand-written merges go wrong
Writing a merge function by hand is easy to get subtly wrong. The same paper warns that “naively chosen merge functions often exhibit anomalies such as deleted items reappearing”, and argues that conflict resolution cannot reasonably be left to application programmers.
Common traps:
- Trusting wall clocks. “Keep the newest” depends on timestamps, and the wall clocks on two devices need not agree. Automerge, for example, picks the winner of concurrent writes by an operation ID made of a counter and the ID of the writing replica, not by wall-clock time.
- Breaking ties differently. If two values have the same timestamp, every replica must break the tie the same way, for instance by replica identifier. Otherwise replicas diverge.
- Losing data silently. Last writer wins is a valid merge, but the losing write disappears. Kleppmann and Beresford reject it for their JSON datatype because it loses user input.
- Merging coarse values. If a whole record is one value, two edits to different fields collide and one is lost. Splitting the record into separate keys lets each field merge on its own.
What no merge function can do
A merge function guarantees agreement, not correctness. Shapiro and colleagues define a conflict as concurrent updates that are each valid alone but together violate an invariant. Two technicians claiming the last spare part will merge into a state where both have it. That rule needs an authority, such as a backend, to check it and reject one claim. For deciding when to merge, when to keep both versions and when to defer to an authority, see how sync conflicts are resolved. For how the two CRDT families use merging, see how CRDTs merge changes.