system-design

Conflict Resolution: Vector Clocks, LWW, CRDTs

Two people edited the same thing at the same time on different machines. Both writes are valid. Now what?

Prerequisites: Time & Clocks, Quorums Time to read: ~24 minutes

The problem

You allow writes on multiple replicas — for availability, for local write latency, or for offline support. Then this happens:

Replica A (Karachi):  cart = {shoes, socks}
Replica B (Dubai):    cart = {shoes, hat}

Network partition heals. Which is correct?

Neither. Both are legitimate writes by real users. The system must produce some answer, and the choice of answer is a design decision with real consequences.

🚨 You only have this problem if you allow concurrent writes to the same data on different nodes. Single-leader replication avoids it entirely by serializing everything through one node. The moment you choose multi-leader, leaderless, or offline-capable clients, conflict resolution becomes your problem. That’s the trade you made.

Step 1: detecting a conflict

Before resolving, you must know a conflict exists. If replica B’s value is simply newer — B saw A’s write and then updated it — there’s no conflict, just a sequence. A conflict is when neither write saw the other.

Wall-clock timestamps cannot tell you this. A later timestamp might mean “happened after” or might mean “that machine’s clock is 200 ms fast.” → Time & Clocks

Version vectors can. Each replica tracks a counter per node:

Write on A:   [A:1, B:0]
Write on B:   [A:0, B:1]

Comparison: A's first element is greater, B's second is greater
         →  NEITHER dominates  →  genuinely CONCURRENT  →  real conflict

versus

Write on A:   [A:1, B:0]
Write on B after seeing A's:  [A:1, B:1]

Every element of the first ≤ the second  →  ORDERED, not a conflict

🚨 This distinction is the whole value of version vectors: they tell you whether you have a real conflict or just a sequence. Without them, you’re guessing.

⚖️ The cost: the vector grows with the number of replicas that have ever written. Systems prune old entries, which risks false conflict reports. This overhead is why many modern systems prefer CRDTs, which don’t need explicit conflict detection at all.

Step 2: resolving it

Five strategies, from worst to best.

1. Last write wins (LWW)

Keep the value with the highest timestamp. Discard the rest.

✅ Trivial. No metadata beyond a timestamp. Constant space.

❌ 🚨 It doesn’t resolve conflicts — it discards data, silently. No error, no log, no way to detect it later. A user’s write vanishes because another machine’s clock was 20 ms ahead, and neither the user nor your monitoring will ever know.

Acceptable when: the data is a regenerable cache, the value is approximate (a view counter), or there’s genuinely one legitimate writer (a user’s own setting).

Not acceptable when: losing a write is a bug. Which is most things.

📐 Cassandra uses LWW by default, which is why clock synchronization matters more there than people expect.

2. Keep both, let the application decide

Return all conflicting versions (“siblings”); the application resolves them with domain knowledge.

versions = db.get("cart:42")
if len(versions) > 1:
    merged = union_of_all(versions)     # for a cart, union is right
    db.put("cart:42", merged, context=versions)

✅ No data loss. The application has semantic knowledge the database can’t. ❌ Every read path must handle multi-version responses. Easy to forget, and forgetting means a crash or silently picking one.

🚨 This is what Dynamo does, and Amazon’s canonical example is instructive: for a shopping cart, union is the right merge, because “an item unexpectedly reappearing” is a far better customer experience than “the item you added is gone.” A deleted item might come back — annoying — but nothing a customer wanted is lost. That’s a product decision encoded in the merge function.

3. Application-specific merge

Same idea, but the merge logic is defined per data type up front:

Data	Merge rule
Shopping cart	Union of items (bias toward keeping)
A counter	Sum of per-replica increments
A set of tags	Union
A document	Operational transform, or ask the user
A user profile	Field-by-field, LWW per field

⚖️ Correct, but you must write and maintain a merge function for every conflicting type, and get the semantics right.

4. Surface the conflict to the user

Git’s approach. Present both versions and let a human decide.

✅ Always correct — humans have the context. ❌ Only viable for user-facing documents where a person is present and willing.

5. CRDTs — make conflicts impossible

The most elegant answer, and increasingly the modern one.

CRDTs: conflict-free replicated data types

🚨 The core idea, and it’s genuinely clever:

Design the data structure so that merging is mathematically guaranteed to converge, regardless of the order or number of times merges happen.

The merge operation must be:

Commutative — merge(a,b) = merge(b,a) (order doesn’t matter)
Associative — merge(merge(a,b),c) = merge(a,merge(b,c)) (grouping doesn’t matter)
Idempotent — merge(a,a) = a (duplicates are harmless)

Given those three properties, every replica converges to the same value no matter what order updates arrive in, how many times they’re duplicated, or how the network misbehaves. No conflict detection, no coordination, no resolution logic.

The counter that actually works

The naive approach fails:

A: counter = 5 → 6
B: counter = 5 → 6
Merge: max(6, 6) = 6.   Two increments, one counted. Wrong.

G-Counter (grow-only): each replica counts only its own increments.

A: {A: 1, B: 0}       (A incremented once)
B: {A: 0, B: 1}       (B incremented once)
Merge: element-wise max → {A: 1, B: 1}
Value: sum = 2         ✅ correct

Element-wise max is commutative, associative, and idempotent. It just works.

PN-Counter (supports decrement) keeps two G-Counters — increments and decrements — and returns the difference. You can’t decrement a G-Counter directly, because max() would discard it.

Sets, and the delete problem

G-Set: add only. Merge = union. Trivially a CRDT.

🚨 Deletion is the hard part, because “remove X” and “add X” concurrently have no obvious winner.

2P-Set: two sets, added and removed. Once removed, an element can never be re-added — a real limitation.

OR-Set (Observed-Remove Set): tag each addition with a unique ID. A removal removes only the tags it has observed.

A: add("shoes")  → {("shoes", tag1)}
B: add("shoes")  → {("shoes", tag2)}     (concurrently)
A: remove("shoes") → removes tag1 only

Merge: {("shoes", tag2)}  → "shoes" is still present ✅

This matches intuition: B’s addition wasn’t seen by A’s removal, so it survives. Add wins over a concurrent remove.

Text editing

RGA / LSEQ / Logoot and modern implementations (Yjs, Automerge) make collaborative text editing convergent — each character gets a unique, ordered identifier so concurrent insertions interleave deterministically.

🚨 This is what replaced Operational Transformation (OT) for many systems. OT (used by Google Docs) requires a central server to transform operations; CRDTs work peer-to-peer with no coordinator. Modern collaborative tools — Figma, Linear, and many local-first apps — use CRDTs for this reason. → Collaborative Editing case study

The two families

	State-based (CvRDT)	Operation-based (CmRDT)
What’s sent	The full state (or a delta)	Individual operations
Requires	Nothing — merges are idempotent	Exactly-once, causally-ordered delivery
Bandwidth	Higher (though delta-CRDTs fix this)	Lower
Robustness	Very high — duplicates and reordering are fine	Depends on the messaging layer

Delta-state CRDTs are the practical middle ground: send only the changed parts, keep the robustness.

⚖️ What CRDTs cost you

They’re not free, and a balanced answer says so:

Metadata overhead. OR-Sets store tags for every element ever added. Tombstones for removed elements often can’t be garbage-collected safely. CRDT state can grow much larger than the data it represents.
Limited expressiveness. Not every operation can be made a CRDT. “Transfer $100 if the balance is sufficient” cannot — it requires a global invariant, which is exactly what CRDTs give up.
Semantics may not match intent. Add-wins might not be what the user meant.
Harder to reason about. “Convergent” doesn’t mean “the answer a human would give.”

🚨 The key limitation to state: CRDTs guarantee convergence, not correctness. All replicas agree — on a value that might violate your business rules. You cannot enforce “balance must not go negative” with a CRDT.

Choosing

flowchart TB
    A{Can you avoid<br/>concurrent writes?} -->|yes| B[Single leader per key<br/>✅ simplest, no conflicts]
    A -->|no| C{Does the data fit<br/>a CRDT?}
    C -->|yes| D[Use a CRDT<br/>counters, sets, text]
    C -->|no| E{Is losing a write<br/>acceptable?}
    E -->|yes| F[LWW<br/>simple, lossy]
    E -->|no| G{Can a human decide?}
    G -->|yes| H[Surface both versions]
    G -->|no| I[Application merge<br/>+ version vectors to detect]

🚨 Start at the top. The best conflict resolution is not having conflicts. If you can route all writes for a given key to one node — partition by user, by document, by account — you eliminate the entire problem class.

🎙️ “I’d first ask whether we can avoid concurrent writes entirely by making each record have a home region. That removes the problem rather than solving it. If we genuinely need multi-master — for offline support — then I’d use CRDTs for the data that fits, and version vectors plus an application merge for the rest.”

⚖️ Trade-offs

Approach	Gain	Cost
Avoid conflicts (single writer per key)	No conflict logic at all	Loses local write latency and offline support
LWW	Trivial, constant space	Silently loses writes; clock-dependent
Version vectors + app merge	Detects real conflicts; no data loss	Metadata growth; merge logic per type
Siblings to the application	No loss; domain-aware resolution	Every read path must handle multiple versions
CRDTs	Automatic convergence, no coordination	Metadata overhead; limited operations; no invariants
Ask the user	Always semantically correct	Only for interactive, user-facing data

In the real world

Amazon’s Dynamo shopping cart used vector clocks with sibling resolution and a union merge. The business reasoning is the memorable part: an item reappearing is a minor annoyance; “add to cart” failing costs a sale. The technical choice followed from the product decision.
Redis Enterprise’s active-active deployment (CRDBs) uses CRDTs so multiple geographic replicas accept writes and converge. Counters, sets, and hashes are all CRDT-backed.
Figma, Linear, and Automerge/Yjs-based tools use CRDTs for real-time collaboration and local-first operation. Figma’s engineering posts on their multiplayer implementation are a good practical read — notably, they use a hybrid approach rather than pure CRDTs, because pure CRDTs were more expensive than they needed for their access patterns.
Riak exposed CRDTs as first-class data types (counters, sets, maps), which was ahead of its time and is a good reference for what the API looks like.

🚨 Interview traps

Proposing LWW without saying it loses data. Say it explicitly.
Using timestamps to detect conflicts. Clocks disagree; you need version vectors.
Claiming CRDTs solve everything. They guarantee convergence, not correctness, and can’t enforce invariants like “balance ≥ 0.”
Not considering whether conflicts can be avoided by partitioning writes.
Ignoring CRDT metadata growth. Tombstones and tags accumulate.
Forgetting that siblings must be handled on every read path.

🎙️ Soundbites

“First I’d ask whether we can give each record a home region so writes never conflict. Avoiding the problem beats solving it.”
“Last-write-wins doesn’t resolve a conflict, it discards data — silently, based on clocks that disagree. If losing a write is a bug here, we need version vectors to detect concurrency and an application merge.”
“For the cart I’d merge by union, like Dynamo. An item reappearing is far better than an item the customer added disappearing — that’s a product decision, not a technical one.”
“CRDTs guarantee all replicas converge, but not that they converge on something valid. You can’t enforce ‘balance must not go negative’ with a CRDT, because that’s exactly the global invariant they give up.”
“OR-Set semantics are add-wins: a concurrent add and remove keeps the element, because the remove only removes tags it observed. That usually matches what users expect.”

🛠️ Try it

1. Build a G-Counter. Three replicas, each incrementing independently, merging in random orders. Verify the total is always correct regardless of merge order or duplicated merges.

class GCounter:
    def __init__(self, node_id):
        self.node = node_id
        self.counts = {}
    def increment(self, n=1):
        self.counts[self.node] = self.counts.get(self.node, 0) + n
    def merge(self, other):
        for k, v in other.counts.items():
            self.counts[k] = max(self.counts.get(k, 0), v)
    def value(self):
        return sum(self.counts.values())

Then merge in every possible order and confirm you always get the same answer. That’s convergence, demonstrated.

2. Show why the naive counter fails. Replace the per-node dict with a single integer and merge = max. Watch increments get lost. The contrast makes the design obvious.

3. Implement an OR-Set with add/remove and unique tags. Create a concurrent add and remove and verify the element survives. Then try a 2P-Set and observe that a removed element can never return.

4. Try Yjs or Automerge. Two clients editing the same document offline, then syncing. Watch the text merge without a server. Genuinely impressive to see, and it makes the collaborative-editing case study concrete.

Check yourself

1. Why can't you use timestamps to detect whether two writes conflict?

Because a timestamp tells you what a machine's clock said, not what happened first. Clocks on different machines disagree by milliseconds to tens of milliseconds under healthy NTP, and by unbounded amounts when NTP fails silently — and concurrent writes are typically separated by *less* time than the skew. So a later timestamp might mean "happened after" or might mean "that clock runs fast." Worse, timestamps can't distinguish "B saw A's write and updated it" (a sequence, no conflict) from "A and B wrote independently" (a genuine conflict). Version vectors capture causality directly and can report "concurrent."

2. What are the three properties a CRDT merge must satisfy, and why do they matter?

**Commutative** (`merge(a,b) = merge(b,a)`), **associative** (`merge(merge(a,b),c) = merge(a,merge(b,c))`), and **idempotent** (`merge(a,a) = a`). Together they mean the final state depends only on the *set* of updates applied, not on the order they arrived, how they were grouped, or how many times each was delivered. That's exactly what an unreliable network gives you — arbitrary reordering, batching, and duplication — so a structure with these properties converges automatically with no coordination, no conflict detection, and no resolution logic.

3. Why does a G-Counter track a value per replica instead of a single number?

Because merging single numbers loses information. If both replicas start at 5 and each increments to 6, any merge of two 6s — max, or picking one — yields 6, so one increment vanishes. Tracking a separate count per replica means each replica's contribution is preserved independently: A's count and B's count merge by element-wise max (which is safe, because each replica only ever increases its own entry), and the value is the sum. The per-replica decomposition is what makes the merge lossless. Decrement needs a second counter (PN-Counter) because max() would discard decrements.

4. What can't CRDTs do?

They cannot enforce global invariants. "The account balance must never go below zero" requires knowing the total across all replicas at the moment of the operation — which is precisely the coordination CRDTs eliminate. Two replicas can each independently approve a withdrawal that's valid locally and jointly overdraws the account; the merge converges to a negative balance, and all replicas agree on that invalid state. CRDTs guarantee **convergence**, not **correctness**. They also have practical limits: metadata (tags, tombstones) can grow much larger than the data, and not every operation has a sensible conflict-free formulation. Invariant-critical operations need consensus.

5. Amazon's cart merges by union, so deleted items can reappear. Why is that the right choice?

Because it's a product decision, not a technical one. The two possible errors are asymmetric: an item reappearing that a customer removed is a minor annoyance they can fix in one click, while an item the customer *added* silently disappearing means a lost sale and a customer who thinks the site is broken. Union biases toward the error that costs less. This is worth generalizing: the right merge strategy depends on which direction of error your business can better absorb, and that's a question for product, not engineering. Encoding it deliberately in the merge function — rather than accepting whatever LWW happens to do — is the actual engineering work.