DEV Community

Cover image for crdt-sync: a small local-first sync engine in Rust, with CRDTs, sqlite and websockets
Abdeldjalil Chougui
Abdeldjalil Chougui

Posted on Originally published at abdeldjalilchougui.biz

crdt-sync: a small local-first sync engine in Rust, with CRDTs, sqlite and websockets

Two people edit the same note. One is on a train with no signal, the other at a desk. Both keep typing. When the train leaves the tunnel, what should the note look like?

The classic answer is to make the server the judge: every edit goes to it, it decides the order, and a client without a connection waits. Local-first apps turn this around. Each device holds a full copy, edits apply immediately and offline, and devices exchange changes whenever they can reach each other. The hard requirement is that after exchanging everything, all copies are identical, no matter in which order the changes arrived.

Data structures with that guarantee are called CRDTs, conflict-free replicated data types. Automerge and Yjs are the well-known libraries built on them. They are mature, optimized libraries, which makes them a long read if your goal is to learn how the idea works.

crdt-sync is a small local-first sync engine in Rust. Documents are trees of CRDTs, backed by an operation log and vector clocks. Replicas edit offline, store operations in sqlite, and sync through an axum websocket server with a two-message protocol. The README names its two audiences: developers who want to understand how local-first apps work underneath, and those who need a compact, readable starting point for syncing small documents between devices and a server they control.

What it does

Four CRDT types. A document is a tree built from these:

  • LwwRegister, a last-writer-wins register: the highest (Lamport, replica) stamp wins.
  • LwwMap, a map with an LWW register per key. A delete is a write of "nothing", and a value can be a scalar or a nested object.
  • OrSet, an observed-remove set with add-wins behaviour: each add makes a unique tag, and a remove deletes only the tags it observed.
  • Rga, text. Each character is inserted after a reference character, concurrent inserts at the same spot are ordered by stamp, and deletes leave tombstones.

An operation log. Every edit is an Op with an id (replica, seq), where seq counts 1, 2, 3 and so on per replica, plus a Lamport timestamp, a target object and an action. Because sequence numbers have no gaps, a vector clock replica → highest seq says exactly which operations a replica has. "Have I seen op X" is one comparison.

Delivery in any order. Doc::apply_remote accepts operations in any order, any number of times. Known ones are dropped. The rest wait in a pending list until their dependencies are integrated: the previous op of the same replica, the object they target, the character an insert goes after, and the tags a set-remove observed.

A two-message sync protocol. StateVector(clock) is answered with Ops(missing), and Ops(ops) is integrated. Both ends send their state vector on connect, so one round trip each way brings both up to date. The server then relays newly integrated operations to every other client on the same document.

A compact encoding. LEB128 varints, a per-batch replica table so op ids take one or two bytes, delta-coded sequence numbers and Lamport times, and one-byte shortcuts for "same object as the previous op" and "insert after the previous op". The README states that typing 1000 characters encodes to under 8 KB. The decoder rejects truncated or hostile input without panicking or over-allocating.

A server and storage. The axum server exposes GET /sync/{doc} as a websocket with binary frames, plus GET /docs and GET /docs/{doc} as JSON. It keeps one in-memory Doc per open document, loaded from sqlite on first use, and appends integrated ops to sqlite before relaying them. Storage is one table, ops(doc, replica, seq, body), written with INSERT OR IGNORE so saving is idempotent.

How to use it

Install the two binaries, crdt-server and crdt-cli, from GitHub with Cargo, or add the library to a project:

cargo install --git https://github.com/AbdeldjalilChougui/crdt-sync --locked
cargo add --git https://github.com/AbdeldjalilChougui/crdt-sync
Enter fullscreen mode Exit fullscreen mode

The README's quick start runs a server and two clients, each with its own local database, from a clone of the repository:

cargo run --release --bin crdt-server -- --listen 127.0.0.1:3030 --db server.db

# two clients, each with its own local database (works offline)
alias c='cargo run -q --release --bin crdt-cli -- --server ws://127.0.0.1:3030 --doc notes'
c --db alice.db insert title 0 "Meeting notes"
c --db alice.db add tags work
c --db alice.db sync
c --db bob.db sync
c --db alice.db set status draft        # concurrent edits while "offline"
c --db bob.db set status final
c --db bob.db add tags urgent
c --db alice.db sync && c --db bob.db sync && c --db alice.db sync
c --db alice.db show
c --db bob.db watch                     # stay connected, print every remote change
curl 127.0.0.1:3030/docs/notes          # the server's copy as JSON
Enter fullscreen mode Exit fullscreen mode

Alice and Bob both set status while "offline", and Bob adds a tag. After syncing, both hold the same document:

{
  "status": "final",
  "tags": ["urgent", "work"],
  "title": "Meeting notes"
}
Enter fullscreen mode Exit fullscreen mode

The register kept one of the two concurrent writes, the same one on every replica. The set kept both tags.

The CLI commands are show, info, set KEY VALUE, del KEY, insert KEY INDEX TEXT, erase KEY INDEX COUNT, add KEY VALUE, remove KEY VALUE, sync and watch.

As a library:

use crdt_sync::{Doc, ObjId, ObjKind, sync::sync_pair};

let mut a = Doc::new(1);
let (text, _) = a.map_new(ObjId::Root, "body", ObjKind::Text)?;
a.text_insert(text, 0, "hello")?;
let mut b = Doc::new(2);
sync_pair(&mut a, &mut b);            // state vectors, then missing ops
b.text_insert(text, 5, " world")?;
a.map_set(ObjId::Root, "title", "greeting")?;
sync_pair(&mut a, &mut b);
assert_eq!(a.to_json(), b.to_json()); // {"body":"hello world","title":"greeting"}
Enter fullscreen mode Exit fullscreen mode

Things to know

The README's limitations section is long and plain. Read it before you build on this:

  • No authentication or authorization on the server. Anyone who can reach it can read and write every document. Run it on localhost or behind an authenticating proxy.
  • Logs grow forever. There is no compaction, no snapshots and no tombstone garbage collection. A document is rebuilt by replaying its whole log.
  • Text is for notes, not books. RGA lookups are linear scans, and there is one op per character.
  • A small set of types. No rich text, lists of objects, counters or moves. Concurrent creation of a nested object under the same key keeps one object (LWW), and edits made to the other are hidden.
  • Limited peer validation. Ops from a buggy peer that target a missing object or the wrong kind are logged and ignored. There is no check of who may write which replica id.
  • watch only prints remote changes. Edits are made with separate CLI invocations.

What is tested. cargo test runs 17 unit tests, 6 proptest properties and 4 end-to-end tests. The main property is convergence: three replicas perform random text inserts and deletes, set adds and removes, register writes and map sets and deletes, while random subsets of each other's logs are delivered shuffled and duplicated. In the end everyone receives everything in a scrambled order, twice. All replicas must have no pending ops, equal clocks and equal JSON, over 300 cases. Other properties check protocol convergence over pairwise syncs in a ring, that single-replica text matches a Vec<char> model, and that random bytes and bit-flipped messages never panic the decoder.

The end-to-end tests cover offline edits from two clients merging, a restarted server serving the same document from sqlite, a live client receiving relayed edits, and two crdt-cli processes that edit offline and converge. As a sanity check, the README notes that breaking the LWW tie-break or the RGA sibling ordering makes the convergence properties fail within a few cases.

Why I built it

The idea behind local-first is easy to state and hard to trust until you have seen every piece: how an operation is identified, why a vector clock is enough to know what a peer is missing, what "wait for dependencies" means in code, and how text can merge when two people type at the same position. The mature libraries answer all of this, but inside a lot of optimization.

I wanted the whole path in one small codebase that can be read end to end: the CRDTs, the log, the binary encoding, the storage, the protocol and a server. And I wanted the convergence claim to be checked by property tests and not by a few hand-picked examples, because the bugs in this kind of code live in the interleavings nobody thinks of.

Get the code

The source and the tests are on GitHub: https://github.com/AbdeldjalilChougui/crdt-sync. It is MIT licensed. Treat it as a readable starting point for small documents, with the limits listed above.


Originally published at abdeldjalilchougui.biz.

Top comments (0)