System Design · Distributed Data

CRDTs: How Independent Changes Merge

Two devices edit a shared document while disconnected. Both should keep working, and synchronization should produce the same result wherever it runs. A conflict-free replicated data type, or CRDT, makes this possible by defining operations and merge rules that remain correct under specific replication assumptions.

The difficult part is deciding what “correct” means for concurrent changes. A counter should preserve independent increments. A set must decide what happens when an add races with a remove. A seat reservation must still prevent two successful bookings. This lesson separates convergence of stored state from those business promises. The Vector Clocks & Timestamps lesson explains the causality tools used here.

1. Convergence is a precise promise with explicit assumptions

Replicas may temporarily hold different states because updates travel asynchronously. The convergence promise says that replicas incorporating the same updates reach equivalent results under the data type's rules. For eventual convergence across the system, updates must eventually reach the relevant surviving replicas. A permanently disconnected device cannot learn changes it never receives.

This differs from agreeing on one global operation order before accepting every write. A CRDT often permits a local update without waiting for another replica, then merges knowledge later. That can improve offline behavior and latency, but a local read may omit remote work. It also does not replace durable storage: a device that loses its only unsynchronized copy can lose the update before replication ever happens. The CRDT overview by Preguiça, Baquero, and Shapiro defines the model and its synchronization requirements.

Start with the application question. For an offline grocery list, retaining a concurrent re-add might be sensible. For revoking access to a private document, allowing a concurrent stale grant to restore access may be unacceptable. Both merge outcomes can be deterministic; only the product contract tells you which outcome is valid.

Try it: merge a grow-only counter (G-counter)

Writer A owns component 0 and writer B owns component 1. Merge takes the maximum of each component, which commutes, associates, and ignores duplicate deliveries.

Replica A total: 0
Replica B total: 0
A components: [0, 0]
States agree: Yes

Replica A view

Component A / B

[0, 0] → total 0

Replica B view

Component A / B

[0, 0] → total 0

Increment each writer on its own replica, deliver snapshots, and merge with component-wise maximum. Replay the same snapshot to see idempotence.

Contrast with naive totals. Merging only the displayed sums would lose independent increments; merging by max on each writer component preserves both contributions under reorder and replay.

2. Merge accumulates knowledge using three algebraic properties

For the state-based designs below, replicas send their accumulated state and combine it with a merge function. The useful properties are commutativity, so the order of two inputs does not matter; associativity, so grouping several merges does not matter; and idempotence, so merging an identical state again has no additional effect. These properties address reordered, regrouped, and duplicated state exchanges.

The state must also evolve monotonically in an appropriate knowledge order, and merge must compute a join: the least state that includes the knowledge of both inputs. This structure is called a join-semilattice. “Monotonic” does not require the user-visible number or set to grow forever. A deletion can add evidence that an earlier item was removed, and a decrement can add evidence of a subtraction. Information grows even when the displayed result shrinks.

You can see the algebra without implementing a distributed system. Set union is a join on sets of facts: merging “A happened” with “B happened” retains both, and hearing “A happened” twice does not create a second A. A real CRDT chooses a compact representation of the facts and a domain-specific way to interpret them. Arbitrarily concatenating arrays or applying “latest arrival wins” does not acquire these guarantees merely because the operation is called merge.

3. A grow-only counter stores who contributed each increment

A classic state-based G-counter keeps one nondecreasing component per writer. Each writer increments only its own component. Merge takes the maximum of corresponding components, and a read sums the components. This preserves independent contributions while ignoring repeated evidence of the same contribution. The formal counter constructions appear in A Comprehensive Study of Convergent and Commutative Replicated Data Types.

Try a two-replica grow-only counter

A owns the first component and B owns the second. Each row shows what that replica currently knows. Increment A twice and B three times while disconnected, deliver a snapshot, then replay it. The displayed value is the sum across one row.

Local counter state at each replica
Replica	Known A increments	Known B increments	Visible total
A	0	0	0
B	0	0	0

Both replicas start at zero. Make local increments before exchanging their state.

The replica states agree. There is no saved snapshot yet.

Reset clears the entire teaching example. Resetting one real replica's owned component while reusing its identity would violate this counter's rules.

In the worked example, A's state becomes [2, 0] and B's becomes [0, 3]. Their merge is [max(2, 0), max(0, 3)] = [2, 3], so the value is 5. Replaying B's old [0, 3] state against [2, 3] leaves it unchanged. If B later contributes another increment, its owned component reaches 4, and a later merge correctly raises the total to 6.

Now compare two tempting shortcuts. Keeping only totals and taking their maximum would merge 2 and 3 into 3, losing A's independent work. Adding the received total to the local total would initially produce 5, but replaying the same message would produce 8. The per-writer components distinguish “a new increment happened” from “I heard about that increment again.”

4. Decrements need their own growing evidence

Decreasing a G-counter component breaks its merge rule: another replica with the earlier larger component would restore it. A PN-counter instead keeps two grow-only counters, P for positive contributions and N for negative contributions. Increment grows P, decrement grows N, and the displayed value is sum(P) − sum(N). Merge takes the componentwise maximum in each counter.

For an original example, suppose P is [4, 2] and N is [1, 0]; the value is 5. While disconnected, A decrements once, making its N contribution 2, and B increments twice, making its P contribution 4. After merging, P is [4, 4] and N is [2, 0], giving 6. The visible value follows all three operations even though every stored component only increased.

An ordinary field assignment such as “set count to 6” has different concurrent semantics from “add 2.” Choose the operation API that expresses the user's action. Automerge's counter documentation illustrates why updating a plain numeric field is different from using its counter type. A replicated counter value also should not be treated as a globally unique ID: disconnected writers can observe the same total.

5. Writer identity is part of the data structure

The example silently relies on A being the only writer of A's component. If two restored devices both claim identity A and independently move its value from 7 to 8, maximum merges them into 8, losing one increment. Likewise, if A forgets its counter and starts again at zero, peers holding 7 will suppress its next seven contributions. A merge proof cannot repair a violation of the writer model.

Persist writer identity and the corresponding sequence state together, and serialize updates within a writer. A fresh identity can represent a genuinely new writer, but identities then accumulate metadata. Systems with many short-lived clients often use a library or protocol that manages actor histories, compaction, and membership rather than directly allocating one permanent vector slot to every installation.

Do not confuse replica identity with a user account. One user can have two offline devices, and one server process can serve many users. The identity needed by the merge algorithm names an independent source of operations. Authentication still has to establish which sources may change which objects; accepting an arbitrary remote vector as trusted state would let a sender forge contributions.

6. An observed-remove set removes the additions it has seen

A set containing only current element names loses the history needed to distinguish an old add from a concurrent new add. In an illustrative observed-remove set, each add creates a unique tag. A remove records the tags for that element which the removing replica has observed. Merge combines the add and removal evidence; the element is present if at least one add tag remains unremoved.

Diagram text: the exact Mermaid definition below preserves the nodes, labels, and connections. Enable JavaScript to view the rendered diagram.

Read the diagram definition

sequenceDiagram
    participant A as Device A
    participant B as Device B
    A->>B: Add milk with tag a1
    Note over A,B: Both know a1, then communication stops
    Note over A: Remove milk: record removal of a1
    Note over B: Add milk again with fresh tag b1
    A->>B: Removal evidence for a1
    B->>A: Addition with tag b1
    Note over A,B: a1 is removed, b1 remains, milk is present

The removal at A cannot name b1 because it has not observed that concurrent addition. After exchange, both replicas therefore retain milk. This is an add-wins outcome for the concurrent add/remove pair. If A first receives b1 and then removes milk, its removal can cover both tags, so milk disappears. The difference is causality, not message arrival order at some central server.

A remove-wins set is a different type with a different concurrency policy. Choose the behavior the application needs and test that exact race. The example above deliberately uses explicit removal evidence to make the mechanism visible; production implementations can compress causal context rather than retain one tombstone forever. An Optimized Conflict-Free Replicated Set explains how an observed-remove design can reduce this metadata while preserving its semantics.

7. Registers and documents need a policy for concurrent assignments

A register stores one assigned value, such as a document title. A last-writer-wins register selects a winner using a deterministic ordering tag, often a timestamp plus a tie-breaker. If it uses physical time, clock skew can make an earlier real-world edit appear later. Every replica can converge on the same winner while still discarding a change the user considered important. A physical clock alone does not establish causality.

A multi-value register retains concurrent assignments until a later action that observes them resolves the conflict. For example, a title changed independently to “Launch plan” and “Release plan” can retain both alternatives. The UI can show a preferred value while preserving a resolution path. Automerge's conflict documentation distinguishes its deterministic visible value from other concurrent values available to the application.

The unit of merging also matters. Treating an entire profile JSON object as one opaque register can make a change to its display name compete with an unrelated change to its biography. A map that merges fields separately can preserve both. But field-level convergence does not ensure a cross-field rule such as “start date must precede end date.” Decide whether fields are independent or whether an operation must update a larger meaningful unit.

8. Collaborative text needs stable positions, not array indexes

Suppose A inserts a character at index 3 while B deletes the character at index 1. After B's deletion, index 3 refers to a different position. A text or sequence CRDT therefore needs stable identities and ordering information that survive concurrent edits; an operation cannot depend only on an integer position in one local snapshot.

A conceptual design identifies inserted elements, records their relationship to existing elements, and deterministically orders concurrent insertions targeting the same place. Deleting an element can hide it while retaining enough identity information to interpret later operations. Efficient libraries use more sophisticated representations and compression. Automerge's merge rules explain how its maps, lists, text, and counters differ.

Correct ordering is only part of a good editor. Cursors need stable relative positions, rich-text marks need rules for how formatting extends across insertions, and undo should usually compensate the user's action without erasing unrelated remote work. Even perfectly converged text can be awkward prose when people edit the same sentence independently. The data type handles a specified merge contract; it cannot infer what each author meant.

9. State-based and operation-based replication have different transport needs

The counter explorer exchanges complete state. That makes duplicate and old snapshots harmless under its join rule, but full-state messages become expensive as state grows. A delta-state design sends smaller pieces of mergeable state while preserving the necessary causal and synchronization conditions. A raw arithmetic difference is not automatically such a delta: replaying “add 3” differs from replaying evidence that writer B has reached 3.

An operation-based design propagates operations or generated effects. Concurrent effects must commute under its model, and the protocol may require reliable causal delivery and duplicate suppression. Do not assume an arbitrary operation stream can be reordered and replayed just because the data type is a CRDT. “Increment by one” commutes with another increment, but executing the same increment twice still counts twice unless identity or transport semantics prevent it.

Library update formats can provide stronger handling than a naive operation stream. For example, Yjs document updates are documented as commutative, associative, and idempotent, and its state vectors support synchronization of missing updates. Those are guarantees of that format and protocol, not a reason to remove required metadata from a different CRDT implementation.

10. Converging counters do not automatically protect limited inventory

Start with ten units of stock. During a partition, A sees ten and accepts a sale of eight; B also sees ten and accepts a sale of eight. Each local check looked valid. A correctly merged decrement counter records all sixteen sales, leaving −6. Convergence faithfully preserves the operations, while the business invariant “stock never goes below zero” is broken.

One solution coordinates the reservation decision so concurrent sellers cannot both spend the same units. Another partitions escrow rights: give A the right to sell five units and B the right to sell five. Either can safely sell within its allocation while disconnected. An eight-unit sale then requires obtaining more rights or refusing the operation locally, even when another region still has unused stock. Transfers must preserve ownership of rights so the same capacity cannot be spent twice.

This is the central idea behind the bounded counter research. It changes the operation's preconditions rather than magically making stale global reads current. Similar reasoning applies to unique usernames, seat reservations, and access revocation: identify the invariant, then prove that the allowed concurrent operations preserve it or introduce the needed coordination.

11. Metadata cleanup and offline retention are part of the contract

Unique add tags, actor sequences, removed-element identities, and causal context can outlive the visible data. If a node forgets removal evidence too early, an old device can reconnect with a state that appears to reintroduce an already removed element. If it forgets an operation identity too early, a delayed replay may look new. Compact metadata only when the protocol proves the discarded information is no longer needed.

A practical product may bound offline retention and require a sufficiently old device to rejoin from a current snapshot. That choice needs a plan for unsynchronized local edits: reject them with a clear explanation, export them, or transform them through a supported recovery path. Silently merging an ancient state after changing the membership or compaction assumptions can invalidate the proof the system relied on.

Also plan storage format and schema evolution. Old clients can continue producing operations after a new server deploys. Replacing a counter with a plain integer, changing set semantics, or reusing an actor namespace changes meaning, not just serialization. A migration needs compatibility rules or a new object generation. Test long offline intervals and mixed client versions before promising indefinite offline editing.

12. Evaluate a CRDT through behavior, cost, and failure tests

Write the concurrent examples first: two increments, remove racing with re-add, two title changes, delete racing with text insertion, and an old device returning after cleanup. Specify the intended visible result and whether the operation needs coordination. Then choose a type or established library whose rules match those examples. A broad “eventually consistent” requirement is too vague to make this choice.

For a state-based implementation, test merge commutativity, associativity, and idempotence over valid generated states. Test that permitted local operations move forward in the knowledge order. In a protocol harness, delay, duplicate, and reorder delivery within the supported assumptions, then deliver all outstanding updates and compare replica results. Include restart and actor-identity tests: algebraic tests alone will not catch lost identity state.

Measure metadata per visible item, update payload size, merge time, startup replay time, and the cost of very old replicas. Finally test the business invariants separately. Two replicas displaying the same negative stock value pass a convergence test and fail an inventory test. The useful design argument explains both what the merge guarantees and how the remaining application rules are enforced.

Practice: can you merge a shared shopping-cart quantity by taking the larger number?

Only if “keep the largest proposed quantity” is the intended operation semantics. If two users independently add one unit to a quantity of two, both may locally show three; maximum returns three and loses one addition. A counter-like operation can preserve both contributions, but that alone does not determine how “remove item” should interact with a concurrent increment.

Model those actions explicitly. You might separate item membership from quantity, define whether a concurrent re-add survives removal, and coordinate the final stock reservation at checkout. A shopping cart can accept temporary merged preferences while checkout enforces inventory. Different stages can use different consistency requirements.

Practice and further reading

Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.

Focus for this lesson: Derive convergence from merge laws and delivery assumptions, then check whether the converged result also preserves the product’s business rules.

Explain the decision

Why can two state-based G-counters merge repeatedly without counting the same increment twice?

Read the reasoning

Each replica owns one monotonically increasing component. A local increment changes only that component, and a merge takes the maximum for each replica identity. Maximum is commutative, associative, and idempotent, so exchange order, grouping, and duplicate state deliveries do not change the final merged state. The displayed count is the sum of the merged components. Eventual communication must still deliver the relevant state, and replica identities must not be reused in a way that forgets earlier increments.

Apply it to a production scenario

Two devices edit a shared set offline. One removes an item while another adds it again. How does an observed-remove set decide the result?

Read one approach

An add creates a unique tag. A remove records only the tags that the removing device has observed for that item. A concurrent add with a new, unseen tag therefore survives the remove in an add-wins observed-remove set. This is a deliberate user-visible conflict rule, not a universal definition of deletion. Explain it to the product team, preserve the causal metadata needed for safe merging, and choose another design if deletion must prohibit all concurrent or future additions.

Work through the numbers

Replica A has counter components [4, 1] and replica B has [2, 5]. What should a state-based merge display?

Read the worked calculation

Take the maximum at each coordinate: max(4, 2) = 4 and max(1, 5) = 5. The merged vector is [4, 5], so the displayed value is 9. Adding the two displayed values, 5 and 7, would give 12 and double-count shared history. Merging [4, 5] again with either input keeps [4, 5], which demonstrates duplicate-delivery safety. The coordinates must refer to the same stable replica identities for this calculation to mean anything.

Reason through a failure

Can a convergent PN-counter guarantee that two disconnected regions never sell the same last ticket?

Read the recovery reasoning

A PN-counter can converge to the same total increments minus decrements at every replica, but both regions may independently observe one available ticket and sell it. Later convergence can reveal a negative inventory; it cannot retract the earlier promises automatically. Protect the no-oversell invariant with coordinated admission, a single authoritative writer, or an escrow-style allocation of rights that prevents either region spending rights it does not hold. Convergence solves agreement on merged state, while invariant preservation requires a separate argument.

Sources and further study

Continue with Unique ID Generation.