What it is
In a store where several replicas accept writes, three questions follow from each other. How many replicas must a read and a write touch to see each other (quorums)? When two writes happen without knowing about each other, how do you notice (versioning)? And once you notice, how do you merge them (conflict resolution)? These are the mechanics behind “always writable” systems like Dynamo and Cassandra, and behind collaborative editors.
Important
Key takeaway: In a leaderless store, conflicts are not a bug; they are the purchase price of the always-writable contract. The design question is whether you detect them honestly (vector clocks, siblings) or erase them silently (last-writer-wins). Wall-clock timestamps cannot tell “later” from “concurrent”.
When you care
“What happens when two users write the same key during a partition?” is the standard follow-up to any replicated store, and a senior answer names the failure of timestamps, the mechanism that replaces them, and who owns the merge.
Note
Interview signal:
Saying “R + W > N does not make it linearizable” and “LWW silently loses writes” in the same answer marks someone who has
read past the headline. Add that the merge function is a product decision, because the store cannot know the semantics.
Quorums
With N replicas per key, a write succeeds after W acknowledgments and a read consults R replicas. If R + W > N, the read set and the write set must overlap, so at least one replica in every read has the latest acknowledged write.
| N | W | R | R + W > N? | Behavior |
|---|---|---|---|---|
| 3 | 2 | 2 | Yes | Overlap guaranteed; tolerates one slow or dead replica on either side |
| 3 | 1 | 1 | No | Fastest and always available; reads may miss recent writes |
| 3 | 3 | 1 | Yes | Fast reads; one dead replica blocks all writes |
| 3 | 1 | 3 | Yes | Fast writes; the read side pays the coordination cost |
The overlap makes stale reads the exception, not the rule. It does not make the system linearizable: concurrent writes, and
sloppy quorums, still produce anomalies. A sensible default is N=3, W=2, R=2, with per-request overrides.
Sloppy quorum and hinted handoff. If one of the N replicas for a key is down, a strict quorum fails the write or under-replicates. A sloppy quorum writes the missing copy to the next healthy node with a hint (“this belongs to node C; deliver it when it returns”). The write meets W with a stand-in, so the cluster accepts writes as long as any W nodes are up, not any W specific nodes. The price: until the hint is replayed, a read quorum may not overlap the write quorum.
Why timestamps fail
The naive merge is last-write-wins (LWW): keep the version with the later wall-clock timestamp.
Worked example. A shopping-cart key has the same version on both sides of a partition. A client on the left adds item X at
14:00:00.003; a client on the right adds item Y at 14:00:00.007. LWW keeps the right side’s version and silently discards
X. Nothing was logged and the customer sees an item missing. It fails for two reasons:
- Clock skew is real. NTP keeps clocks within roughly 1 to 100 ms, not microseconds, so “later” can mean “that node’s clock ran fast”.
- Causality is invisible. A timestamp cannot tell “this write supersedes the other” from “these writes were concurrent and both should survive”.
LWW is acceptable only for genuinely overwrite-style data (a session token, a device heartbeat), where the latest physical value is exactly what you want.
Vector clocks
A vector clock is a map from node id to a counter, stored with every value. It records causal history, not time.
- On a write at coordinator X, increment X’s entry. The new version causally supersedes any version it descends from.
- Version V1 descends from V2 if every entry in V1 is at least as large as V2’s (and one is strictly larger). Then V1 is newer, and V2 can be discarded.
- Two versions are concurrent if neither descends from the other. Neither is newer, so both must survive as siblings.
Worked example. The cart starts at [(A,3)] everywhere. During a partition, the left side writes via A and gets [(A,4)]; the
right side writes via C and gets [(A,3),(C,1)]. Compare them: A’s entry is 4 versus 3 (left is ahead on A); C’s entry is 0 versus 1
(right is ahead on C). Neither descends from the other, so they are concurrent and the coordinator returns both siblings to the
client with a merged context token.
Resolving siblings
The client (or the application) merges the siblings and writes back with the combined context:
Sibling 1: { items: [X, Y] } <- [(A,4)]
Sibling 2: { items: [Y, Z] } <- [(A,3),(C,1)]
Merged: { items: [X, Y, Z] } written with context [(A,5),(C,1)]The merged version descends from both siblings, so the conflict is closed. Who resolves is a product decision: a cart merges with set union, a counter with a sum, a document may pick one. The store cannot know, which is why Riak exposes siblings and supports pluggable resolvers, while Cassandra defaults to LWW and trades correctness for simplicity.
Vector clocks grow. One entry per coordinator that ever handled the key means a key written by 50 coordinators has a 50-entry vector. Two mitigations: truncate (Dynamo caps vectors at around 10 entries, accepting an occasional false sibling, which costs reconciliation work but never data), or use server-managed dotted version vectors (Riak) that stop client retries from inflating the clock.
Warning
Production reality: Knowing that vectors must be managed, not just used, is a staff-level detail. “What happens to the vector clock of a key written by every node?” has one correct answer: truncation with an accepted false-concurrency risk, not unbounded growth.
Merging by construction: CRDTs
Instead of detecting conflicts and merging later, a conflict-free replicated data type (CRDT) is designed so that every operation commutes: apply the operations in any order, on any replica, and the final state is the same. Examples:
| CRDT | How it merges |
|---|---|
| Grow-only counter | Each replica keeps its own count; the value is the sum, and merging takes the per-replica maximum |
| Set with add and remove | Each element carries unique tags; a removal removes only the tags it has seen, so a concurrent add survives |
| Sequence (text) | Each inserted character gets a unique id and anchors to its neighbors, so concurrent inserts land between the same stable neighbors; a delete is a tombstone on the original insert’s id |
Collaborative editors choose between operational transformation (OT), where a central server transforms each incoming operation against concurrent ones (compact, battle-tested, needs a global order), and CRDTs (decentralized, merges offline by construction, with more metadata per character). Offline editing is the deciding factor: OT needs the server to linearize a client that was gone for hours, while a CRDT merges locally and converges regardless of order.
Caution
Common mistake: Reaching for LWW because it is the default, then describing the lost writes as “eventual consistency”. Eventual consistency promises convergence, not that nobody’s write is thrown away. If a lost write matters, detect it (vector clocks) or make the data type merge by construction (a CRDT).
When to pick what
| Data | Approach | Why |
|---|---|---|
| Session tokens, heartbeats, last-known location | LWW | The latest physical value is what you want |
| Shopping cart, sets of items | Vector clocks and a union merge | Concurrent adds must both survive |
| Counters, likes | A counter CRDT, or aggregate in a stream | Increments commute |
| Collaborative text | CRDT or OT | Concurrent edits to the same document |
| Money, inventory, uniqueness | Do not use a leaderless store | Needs a single serialization point |
Related
- Walkthrough: Designing a Distributed Key-Value Store — quorums, vector clocks, and hinted handoff in one design.
- Walkthrough: Designing a Collaborative Editor — OT versus CRDT, where offline editing decides the merge strategy.
- Reference: Anti-Entropy and Failure Detection — how replicas that missed writes converge again.