local-first-sync

How it is built

Architecture overview

Local-first software keeps the primary copy of the user's data on the user's own devices. Every edit is applied to the local copy at once, so the app is as fast and as available offline as it is online; a sync layer then exchanges changes with other devices and collaborators whenever any path to them exists. Servers still exist, but as relays and backups, not as the place where truth lives (Kleppmann et al. 2019). The system therefore has to answer a question a client-server app never meets: two replicas edited the same data while apart; what is the merged result, and how do they find out what the other one has?

The idea that makes it work is a document that is its own history. Automerge, the reference example here, stores a document as a set of immutable changes, each a group of operations by one actor, each identified by a cryptographic hash and naming the changes it depends on, like commits in git (Automerge binary format spec). Merging two replicas is the union of their change sets; a deterministic set of rules for maps, lists and text (a CRDT) turns the same set of changes into the same document on every device, in any arrival order. Syncing two peers is then a small set problem: find which changes the other side lacks and send exactly those.

This page is the whole assembled system. The merge mathematics is in CRDTs; the live-typing special case with a central session server is Real-time collaborative document editing; the file-shaped sibling is File sync across devices; a canvas of objects is Collaborative whiteboard.

Parts:

• Document model — maps, lists and text built from operations with unique ids; merge rules — CRDTs, Lamport clocks, Vector clocks, Rope for the materialised text
• Change encoding — compact binary form of changes and whole documents — run-length-encoding (no page yet), Delta encoding, Varint (LEB128), Cryptographic hashes (SHA-2, BLAKE3)
• Local storage — durable log of changes plus periodic snapshots on the device — Write-ahead log, Point-in-time recovery
• Sync protocol — a peer pair works out which changes the other lacks — Bloom filter, merkle-tree (no page yet), Incremental sync cursors
• Transport — a message channel between peers or to a relay — WebSockets, NAT traversal (STUN, ICE, TURN)
• Sync server — always-on peer that stores and relays; holds no special authority — Primary-backup replication, Graceful draining, Process supervision
• Security — authenticated, encrypted channels and, optionally, encrypted changes — AEAD (AES-GCM, ChaCha20-Poly1305), ECDH key exchange (X25519, P-256), Mutual TLS
• Operations and tests — metrics, fault injection, parsers that read bytes from strangers — hdr-histogram (no page yet), Deterministic simulation testing, Coverage-guided fuzzing

 device A                                              device B
┌──────────────────────────┐                    ┌──────────────────────────┐
│ UI ◄─ materialised doc   │                    │ UI ◄─ materialised doc   │
│        ▲ (map/list/text) │                    │        ▲                 │
│  CRDT doc = change DAG   │                    │  CRDT doc = change DAG   │
│        │ new change      │                    │        │                 │
│  local store: snapshot + │                    │  local store: snapshot + │
│  appended change chunks  │                    │  appended change chunks  │
│        │                 │                    │        │                 │
│  sync state per peer     │◄──heads + Bloom───►│  sync state per peer     │
│        │                 │  filter, changes   │        │                 │
└────────┼─────────────────┘                    └────────┼─────────────────┘
         └───── WebSocket ──►  sync server (relay + backup copy)  ◄── WebSocket ─┘
                              (or direct WebRTC after ICE/NAT traversal)

How the parts fit together

Document model

CRDTs give the guarantee that matters: replicas that have received the same set of operations hold the same state, whatever the order or number of deliveries. Automerge's model is JSON-like: a root map holding maps, lists, text and scalar values, plus counters that merge by adding (Automerge binary format spec; Kleppmann and Beresford for the JSON CRDT). Every operation has an id, a pair of actor id and a per-actor counter, and refers to the ids of what it modifies. A list insert names the element it goes after, not an index, so a concurrent edit elsewhere cannot shift its meaning. Concurrent writes to one map key are both kept and one is chosen arbitrarily but identically on every replica; concurrent inserts at the same spot are ordered deterministically; a delete concurrent with an update keeps the update (Automerge docs, merge rules). Operation counters work like Lamport clocks; what Vector clocks answer in other systems (which changes are concurrent) is carried here by each change's explicit dependency hashes.

Text is the demanding case: every character is an operation with an id, so metadata can dwarf content. The tricks are in the encoding, below, and in algorithms that keep less in memory; Eg-walker, for instance, reports an order of magnitude less steady-state memory than existing text CRDTs and much faster document loading (Gentle and Kleppmann 2024). A Rope of the materialised text gives the editor O(log n) offset-based edits, translated to and from id-based operations.

Contract with neighbours: the model accepts changes in any order provided their dependencies are present (a change names its predecessors by hash, so a change that arrives early is held until they do), and exposes a read view that is deterministic for a given set of changes.

Change encoding

A change carries its dependency hashes, an actor id, a sequence number, a start counter, an optional timestamp and message, and its operations; its identity is the SHA-256 hash of its binary form (Automerge binary format spec). Hash identity makes sync idempotent: a change received twice is a no-op. See Cryptographic hashes (SHA-2, BLAKE3).

The spec's design goal is compactness and parse speed for a history that is huge but repetitive. Whole documents are stored column-wise: all actor ids of all operations in one column, all counters in another, and so on, because adjacent operations are alike (the same actor typing a run of characters). Columns then use cheap codecs, and the spec names them: run-length columns, delta columns for counters that increase by one, boolean columns, and unsigned and signed LEB128 integers. These are exactly run-length-encoding (no page yet), Delta encoding and Varint (LEB128) from the graph. A single-change chunk can additionally be DEFLATE-compressed. Each chunk starts with magic bytes, a 4-byte checksum (the first four bytes of a SHA-256) and a length, and implementations must abort on a mismatch. The contract with storage and network is simply "bytes of chunks"; any transport that can carry them works.

Local storage

On the device the document is stored as a snapshot plus appended incremental chunks. The automerge-repo storage documentation shows the layout in a browser: a binary value in IndexedDB under a key made of the document id, the word "incremental" and a hash. Writes are append-only, which is the idea of a Write-ahead log: a crash loses at most the unflushed tail, never corrupts earlier chunks. A background step compacts accumulated chunks into a new snapshot. The same adapter interface is designed to be safe for several processes or browser tabs using one store, and the docs say that concurrent writers merge by the normal merge rules on reload. Any key-value store with range queries will do (automerge-repo docs). Because history is kept, old versions can be read and branched; Point-in-time recovery is the same idea at database scale. History only grows unless truncated, which breaks dependencies for peers that have not seen it.

Sync protocol

Two peers hold sets of changes that overlap. The wasteful way is to send everything; the cursor way of Incremental sync cursors needs a single total order, which a multi-writer system does not have. Automerge's sync works on heads (the changes nobody depends on yet, which summarise a replica's state because every ancestor is implied) and a Bloom filter over recent change hashes. Each peer keeps a sync state per remote peer and generates messages in turn: "my heads are H, here is a Bloom filter of the changes I have since our last shared heads, and these are the changes I think you lack". The receiver sends back what the filter says it is missing plus anything that was a false positive; the loop ends when neither side has anything new to say (Automerge sync module docs, in the Rust source). A Bloom filter is the right tool because a false positive only costs an extra round, never a wrong result, and it is far smaller than a list of hashes. The source comment of the module cites arXiv 2012.00472 (Kleppmann and Howard) for the protocol, a paper about Byzantine eventual consistency.

The alternative for deep histories is a hash tree over changes (merkle-tree, no page yet; see Anti-entropy repair): compare roots, descend where they differ. The protocol assumes a reliable in-order stream between two peers, whatever carries it.

Transport and sync server

Peers exchange sync messages over any channel that gives ordered, reliable delivery. In automerge-repo this is a NetworkAdapter, and a repository can have many (or zero) of them: WebSockets to a server, MessageChannel or BroadcastChannel between tabs on one device (automerge-repo docs). Direct peer-to-peer connections between devices need to find each other through NATs, which is the job of NAT traversal (STUN, ICE, TURN): learn the public address, swap candidates through a signalling channel (which can be the sync server), test pairs, and fall back to a relay if no direct path works.

The sync server is just another peer that happens to be always on. It holds a copy so that devices that are never online together still converge, serves a new device's first download, and relays changes to connected peers. It does not order or validate writes, so it is simple to run and to replace: if it loses its data, clients restore it by syncing, which is the local-first answer to backup. If it should not see content, the changes must be encrypted before upload; then it can store and forward but cannot index, deduplicate by content or merge on behalf of clients. Automerge lists encryption and access control tooling (Keyhive) as work in progress in its documentation, so treat per-document keys and revocation as a design obligation of the application today, not a given.

The server needs the usual operations: Process supervision, Graceful draining before a deploy, and Primary-backup replication of its store.

Security

Transport is protected by TLS or, for peer links, an authenticated key exchange: ECDH key exchange (X25519, P-256) gives a shared secret from public keys; AEAD (AES-GCM, ChaCha20-Poly1305) encrypts and authenticates every message; Mutual TLS lets servers identify each other. Authorisation is separate and harder: a CRDT will merge any valid change from any replica, so who may write a document must be enforced by whoever admits changes (the server, or signatures checked by every peer). Byzantine eventual consistency (cited below) addresses replicas that lie. Synced history cannot be taken back from a revoked collaborator.

Operations and tests

The failures are interleavings: a device going offline mid-sync, a restart between receiving a change and writing it. Deterministic simulation testing replays any failure from a seed, and convergence is a natural property to check (same changes in random order, identical replicas). Decoders read bytes from outside, so Coverage-guided fuzzing belongs on them. Sync latency percentiles use hdr-histogram (no page yet).

Data and control flow

Offline edit, later sync:

1. The user types. The editor calls the document in a transaction; the CRDT records operations with fresh ids and a change is closed, hashed and appended to local storage. The UI reads the new materialised state; no network was involved.
2. The device reconnects. The repository opens a WebSocket to the sync server and creates a sync state for it.
3. First message: heads plus Bloom filter of the changes since the last shared heads. The server answers with its own heads and the changes the filter shows are missing on the device; the device sends the changes the server lacks.
4. The device applies received changes whose dependencies are present; others wait. Each applied change is appended to local storage, and the materialised view is updated incrementally (a patch stream to the UI).
5. Both sides send an empty or final message when they have nothing new; the exchange stops. Cost is proportional to the differences.

A second device joins: it opens the document by id with empty heads; the server sends the full history, which can be one compact columnar document chunk, much smaller than the sum of change chunks. The device stores it as a snapshot and syncs incrementally from there.

Concurrent edit of the same list: A and B both insert after element X while apart, each naming X by id. On merge both inserts exist, ordered identically on both devices. If A had deleted X and B edited it, the update survives (Automerge docs, merge rules).

Scaling

In the order you hit them:

1. History size. Metadata of every operation is kept. Levers: columnar encoding with RLE and delta codecs, DEFLATE, snapshots that replace many chunks, splitting data into many smaller documents (one per task list or note rather than one per workspace), and truncating history only when all peers can be told.
2. Load time and memory. Opening a long document means replaying or parsing its operations. Levers: load the compact document chunk instead of replaying changes, lazy loading by document id, more compact text algorithms such as Eg-walker.
3. Sync round trips on reconnect. A peer with a large divergence needs several message rounds. Levers: send heads and filter in the first message, keep per-peer sync state so reconnects resume, tree-shaped set reconciliation for very deep histories.
4. Server fan-out. Each change is relayed to all peers of a document. Levers: batch changes, send presence separately, shard documents across servers by id (Consistent hashing).
5. Documents per device. Many open documents multiply sync states. Levers: one connection for all documents, sync only those in use.

Failure modes

Real implementations

The alternative: a central server that orders all writes (the model of most web apps, and of OT-based editors) is simpler to reason about and to authorise, and gives a single history; it loses offline editing, and every write pays a round trip. Pick local-first when offline use, instant response or user-owned data are requirements, or when the data is per-user or per-small-group; pick a central log when strict invariants (balances, inventory) must hold across all writers.

Sources

• M. Kleppmann, A. Wiggins, P. van Hardenberg, M. McGranaghan, Local-first software: You own your data, in spite of the cloud, Onward! 2019. essay
• Automerge: documentation, binary document format spec, merge rules, repositories: storage and networking; sync protocol in rust/automerge/src/sync.rs.
• M. Kleppmann, A. R. Beresford, A Conflict-Free Replicated JSON Datatype, 2016 preprint. paper
• J. Gentle, M. Kleppmann, Collaborative Text Editing with Eg-walker: Better, Faster, Smaller, 2024. paper
• M. Kleppmann, H. Howard, Byzantine Eventual Consistency and the Fundamental Limits of Peer-to-Peer Databases, 2020. paper
• M. Shapiro et al., A comprehensive study of Convergent and Commutative Replicated Data Types, INRIA, 2011. report