Part 4 · Redundancy

Local-First and Offline Sync

Lesson 09 admitted more than one writer and we paid for it: two leaders could edit the same record with no agreed order, so we learned to detect concurrency with version vectors and resolve it without losing data. There the writers were still servers — fast machines on good networks, disconnected only briefly. Now push that to the extreme. The writer is your phone, a laptop on a plane, a notes app in a tunnel. Each device holds its own full replica, reads and writes it at memory speed, and reaches the network only opportunistically — connectivity is the exception, not the rule. With dozens of writers that spend most of their lives offline, "detect the conflict and ask someone to merge it" is no longer enough: you want a merge that cannot conflict, that converges no matter what order updates arrive in. This is the home of CRDTs.

DDIA source

Arc drawn from Martin Kleppmann, Designing Data-Intensive Applications, Chapter 5 (Replication) — the multi-leader / offline-client and conflict-resolution material — extended with the CRDT literature (Shapiro et al. on Conflict-free Replicated Data Types) and the "local-first software" essay (Kleppmann, Wiggins, van Hardenberg, McGranaghan). Original synthesis; ML-infra and product framings are ours.

Linear position

Prerequisite: Lesson 09 — multi-leader replication, write conflicts, why last-write-wins drops data, and version vectors as a detector of concurrency. We build on "two concurrent values exist for one key" and do not re-derive it.
New capability: Design an offline-capable sync layer where every device is a writer, choose data types whose merge is conflict-free and order-independent so all replicas provably converge, and reason about the metadata and tombstone cost that buys this.

The plan

Five moves. (1) The offline-first problem — what changes when the writer is a mostly-disconnected device, and why this is multi-leader replication at its limit. (2) Why last-write-wins is unacceptable here, and what "conflict-free" must mean instead. (3) CRDTs from first principles: the algebraic property that makes merge converge regardless of order, and state-based vs operation-based flavors. (4) Three worked CRDTs — a G-Counter, an OR-Set, and a sequence CRDT for collaborative text — with the merge shown step by step and an ASCII of two replicas diverging then reconverging. (5) Sync engines and local-first software in the wild (Automerge, Yjs, Figma, Riak), plus the bill: metadata overhead, tombstones, and garbage collection.

1 · The offline-first problem: the writer is your phone

What this is: every device owns a full replica, works offline, and syncs when it can.

In server-side replication (lessons 08–09) the replicas are machines in datacenters: numerous, well-connected, and almost always reachable. A partition is a rare, alarming event. Local-first software inverts that picture. The primary copy of the data lives on the device — a phone, a tablet, a laptop — and the user reads and writes that local replica directly. The network is used only to sync with peers or a relay server, and it is assumed to be absent most of the time: airplane mode, a subway, a flaky café Wi-Fi, a phone in a pocket. Connectivity is the exception, not the rule.

This is exactly the multi-leader pattern of lesson 09 (every replica accepts writes) but pushed to its limit on three axes at once:

→Many writers. Not two datacenters but potentially every user's every device — tens or hundreds of independent leaders for one shared document.

→Long offline windows. A server replica might lag by milliseconds; a phone in a tunnel diverges for hours, accumulating a long batch of local edits before it ever syncs.

→Arbitrary sync order. When devices reconnect they exchange edits peer-to-peer or through a relay in no fixed order. Two phones might sync to each other directly, then later both sync to the server. Updates can arrive duplicated, out of order, and after long delays.

The promise that makes this worth it is the local-first ideal, summarized as a few properties a user actually feels: responsiveness (every interaction is local, so there is no spinner waiting on a server), offline (the app fully works with no network), collaboration (multiple users and devices can edit the same data and it merges), and ownership (your data lives on your device and survives the vendor going away). Think of a collaborative notes app, a shared shopping list across a family's phones, a figure being edited in a design tool by three people at once, or — in ML-infra terms — an annotation tool where field reviewers label data on tablets offline and the labels merge when they dock.

Why this breaks server-style reconciliation

On a server quorum (lesson 09) you can lean on read repair, anti-entropy, and "ask the application to merge two siblings on the next read." None of that fits a device that is offline for hours and then dumps a long batch of edits. There is no coordinator to call, no leader to serialize through, and the user will not tolerate "your edit conflicts, please resolve manually" forty times after a flight. The merge must be automatic, local, and order-independent. That requirement is what forces CRDTs.

2 · Why last-write-wins loses data here

What this is: the failure mode that ruled out LWW in lesson 09 becomes routine offline.

Recall from lesson 09 that last-write-wins (LWW) attaches a timestamp to each write and, on conflict, keeps the larger timestamp and discards the rest. It always converges — and it silently drops the losing write, choosing the winner by clock order, which is not causal order. On a server with tight clock sync and millisecond divergence, LWW is merely risky. On offline devices it is a guarantee of data loss:

two phones edit a shared shopping list while both offline phone A (offline 3h): add "milk" add "bread" phone B (offline 1h): add "eggs" both reconnect, sync via the relay. LWW keeps whichever whole-list write has the larger timestamp: A's list = {milk, bread} ts = 14:02 B's list = {eggs} ts = 14:50 <- larger LWW result = {eggs} -> milk AND bread vanish. no error.

The user added three items across two phones and ended with one. Nothing told them anything was lost. And the device clocks were not even adversarial here — B simply made its edit later. Worse, a phone whose clock is set wrong (lesson 15 makes clock unreliability precise) can have its older edit win and clobber everyone. LWW collapses two genuinely concurrent, both-valid states into one by a coin-flip on wall-clock time.

What we actually want is for the merged list to be {milk, bread, eggs} — the union of what each device intended — and to reach that same answer no matter which phone synced first, whether B synced to A directly or both went through the relay, or whether an edit arrived twice. That is a strong, specific demand. It says: define a merge operation on the data that is commutative (order does not matter), associative (grouping does not matter), and idempotent (applying the same update twice is harmless). A merge with those three properties cannot conflict — every replica that has seen the same set of updates computes the identical value, no coordination required. Data types built around such a merge are CRDTs.

3 · CRDTs: a merge that cannot conflict

What this is: data types whose merge converges regardless of order, by construction.

A CRDT (Conflict-free Replicated Data Type) is a data structure whose values live in every replica and whose merge function is, by mathematical construction, commutative, associative, and idempotent. The payoff is a theorem, not a hope: any two replicas that have received the same set of updates are in the same state, regardless of the order, grouping, or duplication in which those updates arrived. This property is called strong eventual convergence. Because the merge can never "conflict," there is no manual resolution step and no coordinator — exactly the automatic, local, order-independent merge §1 demanded.

The reason this works algebraically: if you define replica states as a join-semilattice (a set with a "least upper bound" / merge operation that is commutative, associative, and idempotent) and require every update to only move a replica upward in that lattice, then merging two replicas just takes their least upper bound — and lattice merges always agree no matter the order. You do not need to follow the algebra to use CRDTs; you need to know that the data type's designer proved those three properties, so you inherit convergence for free.

There are two ways to ship updates between replicas:

State-based (CvRDT)

Each replica holds a full state and periodically sends its whole state to a peer; the peer merges (takes the least upper bound) it into its own. Robust to lost, duplicated, or reordered messages — merge is idempotent and commutative, so re-sending or re-merging is harmless. Cost: shipping the whole state is heavy for large objects (mitigated by delta-state CRDTs that send only the changed part).

Operation-based (CmRDT)

Each replica broadcasts the operations it applied ("add milk", "increment by 1") rather than full state; peers apply each op locally. Messages are tiny, but the channel must deliver every op exactly once in causal order (lesson 16) — duplicate or out-of-causal-order delivery breaks it unless the op is itself made idempotent and commutative. Most real sync engines are op-based with a log that enforces causal, dedup'd delivery.

How does this relate to lesson 09's version vectors? A version vector detects that two writes are concurrent — it tells you a conflict exists but not what to do. A CRDT goes one step further and defines the resolution so there is nothing left to decide. In fact CRDTs lean on the same per-replica-counter machinery: each update is tagged with which replica produced it and a counter, so replicas can recognize updates they have already seen (idempotence) and reason about causality. CRDTs are version vectors plus a merge rule that is guaranteed safe. The causal ordering they rely on is exactly the happened-before relation lesson 16 formalizes.

4 · Three worked CRDTs, with the merge shown

4.1 · G-Counter — a grow-only counter

What this is: the simplest CRDT — a counter that only goes up, used for likes, views, votes.

A naive shared integer fails: if two replicas both read 5 and both increment to 6, merging by LWW keeps 6, losing one increment. The G-Counter (grow-only counter) fixes this by giving each replica its own slot. The state is a vector — one non-negative count per replica. A replica increments only its own slot. The counter's value is the sum of all slots; the merge of two states takes the element-wise max of the slots.

G-Counter over replicas A, B, C. value = sum of slots. start: A=[0,0,0] B=[0,0,0] C=[0,0,0] A increments twice -> A=[2,0,0] B increments once -> B=[0,1,0] (both offline, concurrent) A and B sync. merge = element-wise MAX: max([2,0,0],[0,1,0]) = [2,1,0] value = 2+1 = 3 correct! now C syncs with the OLD A=[2,0,0] too, then with merged [2,1,0]: max([0,0,0],[2,0,0]) = [2,0,0] max([2,0,0],[2,1,0]) = [2,1,0] value = 3 same answer.

Element-wise max is commutative, associative, and idempotent — so the order C synced in, and the fact it merged A's state twice, changed nothing. No increment is ever lost because each replica owns its slot and only ever raises it; max never lowers a slot. (To also decrement, use a PN-Counter: two G-Counters, one for increments and one for decrements, value = sum of P minus sum of N.)

4.2 · OR-Set — a set you can add to and remove from

What this is: a set with conflict-free add and remove — the shopping list, a tag set, group members.

A grow-only set (G-Set) is trivial: merge is union, and you can never remove. The hard part is supporting remove while staying conflict-free, because "add X here" and "remove X there" are concurrent and you must not let a stale remove erase a fresh add. The OR-Set (Observed-Remove Set) solves it with unique tags: every add of an element attaches a fresh unique tag; a remove deletes only the tags it has actually observed. An element is "in the set" if it has at least one tag that has not been removed.

OR-Set on the shared shopping list. element "milk". phone A (offline): add milk -> tag a1 set = { milk:{a1} } phone B (offline): add milk -> tag b1 set = { milk:{b1} } phone B: remove milk -> removes observed {b1} set = { milk:{} } (gone on B) A and B sync. merge each element's live-tag set: A's milk tags = {a1} B's milk tags = {} (b1 removed) union of adds = {a1,b1}; removed = {b1} live tags = {a1,b1} - {b1} = {a1} -> milk IS still present! B's remove only erased the add IT saw (b1). A's concurrent add (a1) survives. "add wins" against a concurrent remove, by construction.

This is the principled version of lesson 09's "keep siblings and union the cart," but the union is automatic and the remove is honest: it deletes exactly what it observed and nothing it didn't. The cost — visible above — is the per-add tag metadata, and the fact that removes leave behind tombstones (records that a tag was removed) so a late-arriving duplicate of an old add cannot resurrect a deleted element. Tombstones are the recurring tax of conflict-free deletion; §5 addresses paying it down.

4.3 · Sequence CRDTs — collaborative text

What this is: ordered text or lists where many people insert and delete concurrently.

Text is the hardest case because position is relative: if you address characters by index, a concurrent insert upstream shifts everyone else's indices and two edits collide. Sequence CRDTs (RGA, Logoot/LSEQ, Yjs's YATA, Automerge's approach) give every inserted character a stable, globally unique identifier that encodes its position between its neighbors rather than at an absolute index. An insert says "this character goes between identifier P and identifier Q"; a delete tombstones a character's identifier rather than shifting anything. Because identifiers are unique and ordered, two concurrent inserts at the "same" spot get a deterministic, total order (ties broken by replica id), so every replica lays the characters out identically.

two editors, both starting from "HI", both offline. identifiers shown as ; tombstones marked [x]. A inserts "!" after I: H I -> "HI!" B inserts "?" after I: H I -> "HI?" merge: both inserts are positioned "after I"; order the two new ids deterministically (say a < b): H I -> "HI!?" on BOTH replicas. A then deletes I: tombstone it, don't reindex: H [x:I] -> "H!?" still converges.

The user-visible text might surprise (!? vs ?!), but it is identical on every replica and no character is lost — which is the contract. This is distinct from Operational Transformation (OT), the older approach (used by Google Docs) that transforms each operation against concurrent ones to fix up indices; OT needs a central server to order operations, whereas sequence CRDTs converge peer-to-peer with no server, at the cost of carrying an identifier and a tombstone per character.

5 · Sync engines, local-first software, and the bill

What this is: the libraries and systems that ship CRDTs, and what they cost in practice.

CRDTs are the convergence math; a sync engine is the surrounding machinery that stores the local replica, journals updates, and moves them between peers or through a relay. Real systems:

System	What it is	Notes
Automerge	JSON-document CRDT library	State/op-based; full history; rich nested maps, lists, text. Heavier metadata, strong offline story.
Yjs	High-performance CRDT framework	Op-based, YATA sequence; powers many production collaborative editors; tuned to keep metadata small.
Figma multiplayer	Design-tool collaboration	Not pure CRDT — uses a central server with LWW per-property plus CRDT-like structures; pragmatic blend, server is the relay.
Riak	Distributed KV store	Server-side CRDTs ("Riak data types": counters, sets, maps) for conflict-free leaderless writes — the lesson 09 store, with CRDTs as the merge.

Note the spectrum: Riak applies CRDTs server-side to dodge lesson 09's sibling-merge problem, while Automerge/Yjs apply them client-side for genuine offline-first apps. Figma shows the pragmatic middle — a central relay with CRDT-ish per-property merge, because their data has a natural authority and full peer-to-peer CRDTs were not worth the metadata.

Which brings us to the bill. Conflict-free convergence is not free:

Metadata overhead. Every element carries identity (the OR-Set's tags, the sequence CRDT's per-character ids, per-replica counters). For a long document this metadata can dwarf the actual content; minimizing it is the entire game in engines like Yjs.
Tombstones. Conflict-free deletion requires remembering what was deleted (so a late duplicate cannot resurrect it). Tombstones accumulate forever unless reclaimed, so a heavily-edited document's storage grows with its history, not its current size.
Garbage collection. You can reclaim a tombstone only once you are sure every replica has seen the deletion — otherwise a still-offline phone could resurrect it. Determining that "everyone has seen it" requires knowing the causal frontier of all replicas (a version-vector watermark), which is hard when replicas may be offline indefinitely. Many systems GC conservatively, or only when a coordinator/relay can vouch for all peers.

Worked numbers — the tombstone tax

A collaborative doc reaches a steady visible size of 10,000 characters. Suppose each character carries an identifier of about 16 bytes of CRDT metadata. Live content metadata: 10,000 × 16 = 160 KB on top of the 10 KB of text — a 16× overhead already. Now suppose users have, over the document's life, inserted and deleted 200,000 characters total (lots of editing). Until GC runs, the deleted 190,000 also keep tombstones: 190,000 × 16 ≈ 3.0 MB of dead metadata for a 10 KB document. The fix is GC once all replicas confirm the deletes — but if one phone has been offline for a month, you cannot reclaim until it returns. The trade is stark: convergence with no coordinator is paid for in storage that grows with edit history, not current state.

Failure modes

LWW on offline data. Whole-object last-write-wins silently discards a device's entire batch of offline edits. Symptom: edits "disappear" after a long offline stint, no error.
Index-based positions. Editing ordered data by absolute index instead of stable ids — concurrent inserts collide and text scrambles. Symptom: characters interleave wrongly after merge.
Op-based CRDT on a lossy channel. CmRDT ops delivered duplicated or out of causal order without dedup break convergence. Symptom: counters drift, removed items reappear.
Tombstone / metadata blowup. No GC, or GC blocked by a perpetually-offline replica; storage grows without bound. Symptom: a tiny document is megabytes on disk and slow to sync.
CRDT on data that needs a real invariant. A unique-username or non-negative-balance constraint cannot be a CRDT — automatic merge has no notion of "reject." Those need consensus (lesson 17), not convergence.

Decision checklist

Is the writer genuinely mostly-offline, or a well-connected server? If servers, a quorum (lesson 09) may be simpler than client CRDTs.
Does the data have a conflict-free merge — counter (G/PN-Counter), set (OR-Set), ordered text (sequence CRDT), or nested map? If not, it is not a CRDT problem.
State-based or op-based? Op-based needs causal, exactly-once delivery; state/delta-based tolerates a lossy channel.
How is deletion handled, and how do tombstones get garbage-collected — and what happens if a replica is offline indefinitely?
What is the metadata budget per element, and does it dominate the payload for your sizes?
Does any field carry a hard invariant (uniqueness, balance ≥ 0)? Route that to a single authority / consensus, not a CRDT.

Where is truth?

For local-first sync there is no single system of record — and that is the defining feature, not a bug. System of record: ambiguous on purpose; authority is distributed across all device replicas, none privileged (a relay server, if present, is just a convenient meeting point, not the truth). Copies / derived views: every device holds a full, equal replica. Freshness budget: unbounded — a replica may be hours or weeks stale while offline, by design. Owner: the user / each device owns its copy. Deletion path: tombstones — you record that something was removed (you cannot just drop it, or a late duplicate would resurrect it), and reclaim the tombstone only after every replica has observed it. Reconciliation / repair path: CRDT merge — commutative, associative, idempotent, so replicas converge automatically with no coordinator. Evidence it is correct: the convergence proof itself — replicas that have seen the same update set are provably in the same state (strong eventual convergence), checkable by comparing version vectors / state hashes.

Checkpoint exercise

Try it

You are building a collaborative to-do app: tasks can be added, removed, and reordered; each task has a "done" boolean; and devices are offline for long stretches. (a) Pick a CRDT for the set of tasks and a CRDT for the ordered list, and say what metadata each carries. (b) Two users concurrently — both offline — toggle the same task's "done" flag in opposite directions; propose a conflict-free rule and state what it does on merge. (c) A user deletes a task on phone A while phone B (offline two weeks) still has a pending "rename" op for it; trace the merge and say why a tombstone is required and when you could safely garbage-collect it. (d) The product wants "task IDs must be globally unique across the team" enforced — explain why that requirement does not belong in the CRDT layer and where it should live.

Where this points next

Replication — single-leader (08), multi-leader and leaderless (09), and now local-first to the limit (this lesson) — answered "how do we keep many copies of the same data agreeing?" But copying does nothing for a dataset too big for one machine or a write rate that swamps one node. The next move is orthogonal: partitioning (lesson 11) splits the data itself across machines so each node owns a slice. We will see the shard key as a performance contract, skew producing hot partitions, and rebalancing without downtime — and that real systems combine partitioning and replication, each partition being a small replica set running the very protocols of this part. And the causal ordering CRDTs quietly relied on gets made precise later in lesson 16.

Takeaway

Local-first software is multi-leader replication at its extreme: every device is a writer that spends most of its time offline, reads and writes a full local replica at memory speed, and syncs opportunistically in arbitrary order. Last-write-wins is unacceptable here — it silently discards whole batches of offline edits by a clock comparison that is not causal order. The fix is a merge that cannot conflict: a CRDT, whose merge is commutative, associative, and idempotent, so any two replicas that have seen the same updates are provably in the same state regardless of order, grouping, or duplication. Build them from per-replica state — element-wise max for a G-Counter, unique add-tags with observed-removes for an OR-Set, stable between-neighbor identifiers for sequence/text — and ship them state-based (robust to lossy channels) or op-based (tiny messages, needs causal exactly-once delivery). CRDTs are version vectors plus a guaranteed-safe merge rule, so reconciliation needs no coordinator. The bill is metadata per element, tombstones for conflict-free deletion, and garbage collection that stalls until every replica has seen a delete — and any data with a hard invariant (uniqueness, non-negative balance) does not belong in a CRDT at all, because convergence has no way to say "no."

Interview prompts

What makes local-first different from server-side multi-leader replication? (§1 — the writer is a mostly-offline device holding a full local replica; many writers, long offline windows, arbitrary peer-to-peer sync order, and no coordinator to call for merges, which forces automatic local merge.)
Why is last-write-wins worse offline than on a server? (§2 — offline devices diverge for hours and accumulate batches of edits; LWW keeps one timestamped write and silently discards the rest, by clock order which isn't causal, so a whole device's edits can vanish with no error.)
State the property that makes a CRDT converge, and why it removes the need for a coordinator. (§3 — its merge is commutative, associative, and idempotent (a semilattice join), so replicas that received the same updates reach the same state regardless of order/grouping/duplication — strong eventual convergence, no coordination needed.)
State-based vs operation-based CRDTs — when does each fail? (§3 — state-based ships whole state and tolerates lossy/duplicated/reordered delivery (heavy); op-based ships tiny ops but needs causal, exactly-once delivery or it drifts.)
How does an OR-Set support remove without losing concurrent adds? (§4.2 — each add gets a unique tag; a remove deletes only the tags it observed, so a concurrent add's tag survives and the element stays present — "add wins," at the cost of tags and tombstones.)
Why can't collaborative text address characters by index, and what replaces it? (§4.3 — concurrent inserts shift indices and collide; sequence CRDTs give each character a stable unique between-neighbor identifier and tombstone on delete, so all replicas order characters identically.)
What is the cost of CRDTs, and when should you NOT use one? (§5 — per-element metadata, tombstones, and GC that stalls until every replica sees a delete; don't use a CRDT for data with a hard invariant like uniqueness or non-negative balance — that needs consensus, lesson 17, since merge has no "reject.")
How do CRDTs relate to version vectors? (§3 — version vectors only detect that writes are concurrent; a CRDT adds a guaranteed-safe merge rule that defines the resolution, using the same per-replica counters to recognize already-seen updates and respect causality.)