Vibe Engines
YouTube

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

Systems · Distributed

Merge, No Conflict.

Two people edit the same offline document and later sync — normally you get a merge conflict. A Conflict-free Replicated Data Type (CRDT) is designed so that never happens: replicas can be updated independently, concurrently, without any coordination, and when they eventually exchange state they always converge to the same value — no conflicts, no consensus, no central authority. The trick is choosing a merge function that is commutative (order doesn’t matter), associative (grouping doesn’t matter), and idempotent (merging twice is harmless). The classic example, a grow-only counter, stores a per-replica count and merges by taking the element-wise max. Increment the replicas, merge them in any order you like, and watch them all land on the same number.

strong eventual consistency · commutative + associative + idempotent merge · no coordination
CRDT

A data type whose replicas can be updated independently and always merge without conflict.

G-Counter

A grow-only counter: each replica keeps its own count; the value is their sum.

merge

Combine two replica states — here, take the element-wise max of the per-replica counts.

convergence

After enough merges, every replica holds the identical state (strong eventual consistency).

crdt.js — max merge, always converges
Ready
Three replicas of a grow-only counter. Each holds a per-replica count vector; the counter’s value is the sum. Increment replicas independently, then merge (element-wise max) — in any order — and watch them converge. A++/B++/C++ then merge.
0
A value
0
B value
0
C value

How it works

A grow-only counter (G-Counter) makes the CRDT magic concrete. Instead of one shared number (which two replicas would clobber), each replica keeps a small vector: entry i is “how many increments replica i has done, as far as I know.” A replica only ever increments its own entry, so no two replicas can conflict on the same slot. The counter’s value is just the sum of the vector. Merging two replicas takes the element-wise max — and max is commutative, associative, and idempotent, which is exactly the mathematical structure (a join-semilattice) that guarantees convergence no matter what order, or how many times, replicas sync. So you can partition the network, let replicas drift apart, and reconnect them in any pattern: once every increment has propagated, all replicas compute the identical sum. This is strong eventual consistency — available and partition-tolerant, with automatic conflict-free convergence.

1

Each replica owns one slot

A G-Counter stores a per-replica count vector. A replica only ever increments its own slot, so concurrent increments on different replicas never touch the same entry — no conflict is possible.

2

Value is the sum

To read the counter, sum all the per-replica counts. Each replica may have a different view until it has merged in the others’ updates.

3

Merge by element-wise max

When two replicas sync, each entry becomes the max of the two values — adopting the higher (more up-to-date) count for every replica. Max is commutative, associative, and idempotent.

✓

Converge no matter the order

Because the merge has that algebraic structure, replicas converge to the identical state regardless of the order or number of merges — strong eventual consistency, with no coordination.

Coordination
none needed
Merge
commutative/assoc/idempotent
Guarantees
convergence
Used in
Redis, Riak, collab apps

The code

# grow-only counter (G-Counter) CRDT for replica r of n counts = [0] * n def increment(): counts[r] += 1 # only ever your own slot def value(): return sum(counts) # the counter's value def merge(other): for i in range(n): counts[i] = max(counts[i], other.counts[i]) # join by max # max is commutative + associative + idempotent => replicas # converge to the same value no matter the merge order.

The picture: two merge orders, one state

local ++ only merge = element-wise max two orders, one state replica A[2,0,0] = 2 replica B[0,1,0] = 1 replica C[0,0,3] = 3 max(A,B)[2,1,0] = 3 max(C,B)[0,1,3] = 4 converged[2,1,3] = 6 one int + max= 3, lost 3 + C + A same answer in any order, and re-merging changes nothing
Each replica only ever raises its own slot, so the three vectors never fight over an entry. Merge them in either order and the result is the same vector, [2,1,3], whose sum is 6: every increment counted exactly once. Keep one plain integer instead and merge by max, and you get 3. The other three increments are gone.

Worked example: three replicas, a duplicate message, and a late increment

Replicas A, B and C start at [0,0,0]. They increment while cut off from each other, then sync in an untidy order, including one message that arrives twice. Each row is one event. The value is the sum of the vector.

StepEventVector afterValue
1A does ++ twiceA = [2,0,0]2
2B does ++ onceB = [0,1,0]1
3C does ++ three timesC = [0,0,3]3
4A merges BA = max([2,0,0],[0,1,0]) = [2,1,0]3
5B’s state reaches A again (duplicate)A = [2,1,0], unchanged3
6B does ++ once moreB = [0,2,0]2
7C merges AC = [2,1,3]6
8C merges BC = [2,2,3]7
9A and B each merge CA = B = C = [2,2,3]7 everywhere

There were 2 + 2 + 3 = 7 increments, and all three replicas end on 7. Step 5 is where a naive design breaks. If each replica kept one number and merged by adding the other’s count, the duplicate would push A from 3 to 4. If it merged by max of single numbers, step 9 would land on 3. The vector plus max survives both: a resent state is harmless, and no increment is overwritten. Notice also what never happened: no replica waited for another, and none was in charge. After step 8, A showed 3, B showed 2 and C showed 7, and each was a correct count of the increments that replica had heard about. That temporary disagreement is the whole cost; agreement arrives as soon as the last vector has been passed around.

Cost and trade-offs: the G-Counter and its cousins

For n replicas. A state-based CRDT pays in metadata and in the size of what it ships; consensus pays in round trips.

CaseTimeSpaceWhy
G-Counter: incrementO(1)O(n) vector per replicaTouch your own slot only.
G-Counter: read valueO(n)nothing extraSum the vector.
G-Counter: mergeO(n)O(n) sent per syncElement-wise max. The whole vector travels, even if one slot changed.
Delta-state G-CounterO(changed slots)only the slots that changed since the last syncThe same max merge on a smaller message. Because max is idempotent, a delta that arrives twice, or after a full sync, does no harm.
PN-Counter (adds decrement)O(n) merge2nTwo G-Counters, P and N. Value = sum(P) − sum(N).
OR-Set (add and remove)merge grows with tagsa unique tag per add, plus removed tags until collectedRemove deletes only the adds it has seen, so a concurrent add survives.
Op-based counterO(1) per opone small message per opCheaper on the wire, but each op must be delivered exactly once. A resent “+1” counts twice.
Counter replicated by Rafta majority round trip per writeone integerOne agreed order, but the minority side of a partition cannot write.

The vector is the price of not coordinating. It is tiny for three servers and a problem for a design that gives every browser tab its own replica id, because slots are never reclaimed by the merge itself.

Common mistakes

  • Decrementing a G-Counter slot

    Say A’s slot goes from 5 to 4. The next merge with any replica that saw 5 takes max(4, 5) = 5, and the decrement silently disappears. A counter that goes down needs a PN-Counter: count the decrements in a second grow-only vector.

  • Two writers sharing one replica id

    Two devices both believe they are replica 0. Each raises slot 0 from 3 to 4. The merge takes max(4, 4) = 4, so one increment is lost. Replica ids must be unique per writer, for example a random id generated on first run.

  • Taking “converged” to mean “correct”

    Convergence only promises that every replica agrees. A last-writer-wins register converges by throwing one concurrent write away, and with skewed clocks the older write can win. Check that the merge rule matches what users actually meant.

  • Letting metadata grow forever

    Every replica id ever seen keeps a slot. Every OR-Set add leaves a tag, and removes leave tombstones. Without stable ids and some form of garbage collection, the state you ship on each sync keeps growing.

  • Using a CRDT to enforce a global rule

    Stock cannot drop below zero; a username must be unique. Two disconnected replicas can each sell the last item, and both merges are “correct”. A rule over all replicas needs coordination: consensus, or splitting the stock between replicas ahead of time so each can only spend its own share.

Where this shows up in production and interviews

  • Databases with built-in data types

    Riak exposes counters, sets and maps that merge themselves after a partition. Redis Enterprise’s Active-Active databases let each region accept writes and resolve them with CRDTs. Both trade a single agreed order for writes that keep working while regions are cut off.

  • Collaborative and local-first apps

    Libraries such as Automerge and Yjs implement sequence CRDTs for shared documents. Each device edits its own copy offline, and the copies merge when they reconnect, with no server deciding who wins.

  • Counters at the edge

    Likes, views and rate counters spread across regions fit the G-Counter shape exactly: each region raises its own slot locally, regions gossip vectors in the background, and a read sums what it has. A read may be slightly behind, but it never double-counts.

  • The interview version

    For “count likes across regions” or “design a shared editor”, say why you are not using consensus, which merge you chose, and why it is commutative, associative and idempotent. Then name the case it cannot handle, such as an inventory floor, and what you would coordinate there.

Quick check

1. What property must a CRDT’s merge function have?

2. In a G-Counter, why can concurrent increments never conflict?

3. What does "strong eventual consistency" mean for CRDTs?

FAQ

What is a CRDT?

A Conflict-free Replicated Data Type: a structure replicated across nodes, updated independently and concurrently without coordination, and merged so all replicas converge with no conflicts. Two flavors — state-based (merge whole state via a commutative/associative/idempotent merge) and operation-based (broadcast commutative ops) — giving strong eventual consistency.

What are common CRDT types?

Grow-only and PN counters; grow-only, two-phase, and observed-remove sets (OR-Set) supporting add/remove; last-writer-wins and multi-value registers; and sequence CRDTs (RGA, LSEQ) for collaborative text. Each defines updates plus a merge satisfying the convergence properties.

Where are CRDTs used?

Collaborative editors and note apps (real-time, offline-friendly collaboration; Figma describes its multiplayer as CRDT-inspired, with a central server having the final say), distributed databases (Redis Active-Active, Riak, Azure Cosmos DB), carts and counters in eventually-consistent stores, and local-first software where devices edit offline and sync later — anywhere you need automatic, multi-writer, offline-capable merges.

How do CRDTs compare to consensus like Raft?

Consensus (Raft, Paxos) forces agreement on one total order — strong consistency, but needs coordination and a majority, sacrificing availability under partitions. CRDTs never coordinate, stay available under partitions, accept temporary divergence, and rely on their merge to converge. Consensus for "one answer now"; CRDTs for "everyone edits, reconcile automatically."

Keep going

Finished this one? 0 / 61 Labs done
NextThe Rumor Mill: Gossip Next on the “Agreement between machines” ladder · rung 5 of 5

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Labs