Local-first data

What is a merge function?

A merge function takes two versions of the same data and returns one combined version. In a state-based CRDT the merge function is commutative, associative and idempotent, so replicas can merge in any order, any number of times, and still agree. More broadly, it is whatever rule an app or database uses to reconcile copies that changed apart.

TL;DR

A usable merge function gives the same result whatever the order, grouping or repetition of incoming states, so set union and maximum work while addition does not. Hand-written merges go wrong by trusting wall clocks, breaking ties inconsistently or silently dropping writes. A correct merge only guarantees agreement, so claiming the last spare part still needs an authority.

Learning objectives

After reading this article you will be able to:

  • Explain why a CRDT merge must be commutative, associative and idempotent
  • Identify which familiar operations pass or fail the three merge properties
  • Recognise common traps in hand-written merge functions, such as trusting wall clocks

Merge function definition

A merge function takes two versions of the same data and returns one. When two copies change apart, it is what combines them.

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.

Commutative, associative and idempotent merges

Commutativity, associativity and idempotence let replicas agree whatever order states arrive in, however they are combined along the way, and however often each one arrives.

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 CRDT types

Sets merge by union, grow-only counters by the larger value per replica entry, and last-writer-wins registers by keeping the value with the higher timestamp. The comprehensive study gives a merge for each CRDT in its portfolio. A few show the range.

DataMerge functionEffect
Grow-only setUnion of both setsEvery added item is kept
Grow-only counterLarger value per replica entry; the value is the sumEvery device’s increments count once
Last-writer-wins registerKeep the value with the higher timestampOne concurrent write is dropped
Multi-value registerKeep every value not superseded by a later oneConcurrent writes are all kept for later resolution
Two-phase setUnion of the added set and union of the removed setA 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.

Hand-written merge function pitfalls

The common traps in hand-written merge functions are trusting wall clocks, breaking ties differently, losing data silently and merging coarse values. 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.

Merge function limits

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.

Frequently asked questions

Can I write my own merge function?

Yes, but it has to be commutative, associative and idempotent for every pair of states, or replicas can disagree. Composing a custom type from existing CRDTs, such as maps of registers and counters, avoids having to prove those properties from scratch.

Why is addition not a valid merge function?

Addition is commutative and associative but not idempotent, so adding the same state twice counts it twice. A grow-only counter instead keeps the larger value per replica entry, and its value is the sum.

Is last writer wins a valid merge function?

Yes, but the losing write disappears. Kleppmann and Beresford reject it for their JSON datatype because it loses user input.

Should a merge function keep the value with the newest timestamp?

Not by wall-clock time alone, because the clocks on two devices need not agree, and every replica must break ties the same way. Automerge picks the winner of concurrent writes by an operation ID made of a counter and the ID of the writing replica.

How does CouchDB merge conflicting versions?

It does not merge them itself. Kleppmann and Beresford point out that CouchDB keeps every conflicting value and leaves the merge to application code.

Sources

Build it with Offline Protocol

The shared state guide lists the merge behaviour of each collection in Offline Protocol's replicated documents, explains how to split data so fields merge independently, and notes that convergence does not enforce business invariants.

Read the shared state guide