CRDTs explained: merge a counter across two replicas

In this illustrative example, two replicas accept updates while disconnected. A counts two events and B counts one. Sending each other a single integer would invite an error: if both say “my count is 2” or “my count is 1”, which value wins, and how do repeated messages avoid counting the same event twice? A conflict-free replicated data type, or CRDT, designs the state and merge rule together so that independently accepted updates can converge when communication resumes.

Two replicas, one counter#

A grow-only counter, or G-Counter, stores one non-negative slot per replica ID. The vector is written (A, B). Initially both replicas hold (0, 0). A may increment only its A slot; B may increment only its B slot. While disconnected, A reaches (2, 0) and B reaches (0, 1). Each can answer a local read immediately, so A reports 2 and B reports 1 until they communicate.

On reconnection, merge each slot by taking the larger value: (max(2, 0), max(0, 1)) = (2, 1). This is a componentwise merge, not a comparison of whole tuples. Both replicas eventually hold (2, 1) and report the sum, 3. This works because a replica’s own slot only increases; a larger value includes its earlier increments. If B sends (0, 1) twice, taking the maximum twice still produces (2, 1), not 4.

# State-based G-Counter with fixed replica IDs A and B.
increment(state, own_id): state[own_id] += 1
merge(left, right):       return [max(left[i], right[i]) for i in IDs]
value(state):             return sum(state[i] for i in IDs)

A = (2, 0)              # two local increments at A
B = (0, 1)              # one local increment at B
merge(A, B) = (2, 1)    # value 3 at either replica
merge((2, 1), B) = (2, 1)  # duplicate state is harmless

Try the same rule below: increment A and B independently, then merge their states. Repeating the merge leaves the total unchanged.

Why the merge converges#

Componentwise maximum has three useful properties. It is commutative: merging A then B gives the same result as B then A. It is associative: grouping three merges differently changes nothing. It is idempotent: merging a state with itself changes nothing. Those properties let state messages arrive in different orders or more than once. Provided each live replica eventually receives the relevant state, replicas that have seen the same updates converge. The CRDT glossary names this strong eventual consistency.

The replica IDs have to be stable while their slots contain history. If a new process reuses A’s ID with a zeroed counter, a later merge can hide its increments under A’s older, larger slot. Membership and state cleanup therefore need their own rules; the four lines of merge logic are not a complete production replication system.

State and operation delivery#

This example is state-based: replicas exchange states and merge them. Sending the same state twice is harmless because the merge is idempotent. Sending the entire state may be expensive as membership or object metadata grows; delta-state variants send smaller state fragments but must preserve the same merge properties. Delayed or lost messages still need anti-entropy or retry so all live replicas eventually learn the updates.

An operation-based CRDT sends operations instead. It needs a delivery contract appropriate to its operations, including handling loss and duplicates; “increment by one” applied twice is two increments, not a harmless duplicate. Some operation-based types also need causal delivery. The term CRDT does not, by itself, say that every network message can be replayed blindly. Idempotency keys and safe retries explain a separate way to prevent duplicate application requests from taking effect twice. The research overview by Preguiça, Baquero and Shapiro describes the broader CRDT family.

What convergence does not promise#

A local read during the partition is stale with respect to the other replica, even though both local writes are valid. CRDT convergence is not linearizability: it does not make every reader see a single most-recent value. Database replication explains how a different system can expose stale reads and choose stronger read or write guarantees. A CRDT also does not enforce a cross-replica invariant. If two replicas each sell the last item while disconnected, a PN-Counter can later report minus one; the invariant “never oversell” was already broken when the writes were accepted. That requirement needs coordination, bounded allocation or a redesigned operation, not merely a better merge.

The data type also chooses conflict semantics. For a set, adding and removing the same element concurrently cannot both be reflected as a simple Boolean; an add-wins or remove-wins design makes the outcome explicit. A last-write-wins register can converge by comparing timestamps, but clock skew or tie-breaking may discard a meaningful edit. “Conflict-free” means deterministic convergence under the chosen rules, not that the application has no product-level conflict to explain.

Metadata, deletes and text editing#

The G-Counter carries a slot per replica. Sets and sequence CRDTs can carry operation identifiers, causal context or tombstones to prevent a deleted item from reappearing after a delayed message. That metadata consumes memory and network traffic even when the visible object looks small. Garbage collection needs evidence that old operations cannot return from an offline replica, or it can break the semantics that made the merge safe.

Collaborative text is a separate design choice. Operational transformation (OT) transforms concurrent editing operations against one another using a shared context or ordering strategy. Sequence CRDTs attach stable identities and ordering rules to inserted elements so independently applied edits can converge. Both require careful treatment of cursor position, intention, deletion and history; neither can be selected from the acronym alone. Start with the product’s offline and collaboration requirements, then test real edit histories, document size and metadata growth.