Distributed systems
Conflict resolution and CRDTs
What to do when replicas accept concurrent writes. The options run from last-write-wins and siblings to CRDTs, operational transformation and the sync engines used by collaborative editors.
A single-leader database never has write conflicts. Every write goes through one node, which puts them in order. But a single leader adds delay. Users in Sydney wait for every write to reach a leader in Virginia. A phone on a plane cannot write at all. Two people editing one document need to see each other's typing in tens of milliseconds.
Once more than one replica accepts writes, two of them can change the same data without knowing about each other. Something has to decide the result when they sync. This topic covers the options, from the simplest and most lossy to the designs that keep every change.
Concepts in this section
Read the pages in this order.
| Step | Concept | What it answers |
|---|---|---|
| 1 | Concurrent writes and last-write-wins | What is a conflict, and why does the simplest rule lose data? |
| 2 | CRDT counters | How do replicas merge counts without coordinating? |
| 3 | OR-sets and add-wins | How do adds and removes merge without bringing deleted items back? |
| 4 | Text editing: OT vs sequence CRDTs | How do two people's typing merge? |
| 5 | Design a collaborative editor | How do the pieces fit together? |
Where conflicts come from
A conflict appears whenever a replica accepts a write that another replica has not seen yet.
- Multi-leader replication. Each region accepts writes and copies them to the others. Two users in different regions can edit one record within the replication lag.
- Leaderless replication. In Dynamo-style stores, any replica accepts writes, so two writes to one key can be concurrent.
- Offline clients. A phone that edits offline is a leader whose lag lasts hours or days.
- Real-time collaboration. Clients apply their own edits at once, so concurrent edits are the normal case.
Strategies
| Strategy | What it does | Cost |
|---|---|---|
| Last-write-wins | Keeps the write with the highest timestamp | Silently drops concurrent writes, trusts clocks |
| Application merge | Code merges the versions, such as a cart union | Merges can resurrect deletes |
| Siblings | Keeps all concurrent versions for the reader to merge | Every reader needs merge logic |
| CRDTs | Data types whose merges always converge | Metadata, and convergence is not always the answer users want |
| Server-ordered edits | A server orders operations, as in Google Docs and Figma | Edits flow through the server |
Siblings keep every concurrent value. In a Dynamo-style cart, the reader merges the siblings and writes back one value that covers both. A naive union can bring deleted items back, which is the problem OR-sets solve.
Local-first software
In 2019, Ink & Switch published "Local-first software". It argues that apps should keep the main copy of data on the user's device, work offline, sync in the background, and still support collaboration. CRDTs make that possible. Sync engines now give apps a local database that syncs automatically, and many of them use server-authoritative rules instead of full CRDTs.
Common mistakes
- Assuming last-write-wins is harmless. It loses data with no error.
- Expecting CRDTs to enforce rules. They converge, but they cannot keep "never oversell" true. That still needs one owner or consensus.
- Going multi-region without a policy. Name the rule for each entity, such as last-write-wins per field, a CRDT counter, or one home region.
Key takeaways
- Conflicts happen whenever more than one replica accepts writes.
- Last-write-wins always converges, but it drops concurrent writes.
- Siblings and merges keep every change, at the cost of reader complexity.
- CRDTs guarantee convergence without coordination, but not a particular answer.
- Google Docs uses a server, Figma uses per-property rules, and Yjs and Automerge use CRDTs without a server.
Further learning
Kleppmann's "CRDTs: The Hard Parts" covers interleaving anomalies and moving items, which is where real collaborative software gets difficult.
CRDT resources and papers (crdt.tech)Resources and community around CRDT technology — papers, blog posts, code and more.Conflict-free Replicated Data Types
Related
Replication
Keeping copies of the same data on several machines, the three topologies that databases use, and the anomalies that replication lag causes. Start here for the replication map.
Time, clocks and ordering
Why wall clocks lie across machines, how skew silently loses writes, and how Lamport clocks, vector clocks, hybrid logical clocks and TrueTime order events you can't time directly.
Case study: chat system
Design a WhatsApp or Slack style messaging system. Connection gateways, per-conversation ordering, wide-column storage and large-channel fan-out are the parts that matter.