cr-sqlite - Convergent, Replicated, SQLite

A component of the vulcan project.

Examples

Example applications using cr-sqlite to sync state.

• Vite starter - Example | Repository
• TodoMVC - Example | Repository
• Svelte Store
• Tutorials
• WIP Local-First Presentation Editor
• Basic setup & sync via an Observable Notebook

"It's like Git, for your data."

CR-SQLite is a run-time loadable extension for SQLite and libSQL. It allows merging different SQLite databases together that have taken independent writes.

In other words, you can write to your SQLite database while offline. I can write to mine while offline. We can then both come online and merge our databases together, without conflict.

In technical terms: cr-sqlite adds multi-master replication and partition tolerance to SQLite via conflict free replicated data types (CRDTs) and/or causally ordered event logs.

When is this useful?

1. Syncing data between devices
2. Implementing realtime collaboration
3. Offline editing
4. Being resilient to network conditions
5. Enabling instantaneous interactions

All of the above involve a merging of independent edits problem. If your database can handle this for you, you don't need custom code in your application to handle those 5 cases.

Discussions of these problems in the application space:

• Meta Muse
• FB Messenger re-write

Sponsors

Companies:

Individuals: robinvasan | iansinnott | davefowler | barbalex | MohannadNaj

Perf

Perf data: https://github.com/vlcn-io/cr-sqlite/blob/main/py/perf/perf.ipynb

• Currently inserts into CRRs are 2.5x slower than inserts into regular SQLite tables.
• Reads are the same speed

Usage

The full documentation site is available here.

crsqlite exposes three main APIs:

• A function extension (crsql_as_crr) to upgrade existing tables to "crrs" or "conflict free replicated relations"
  • SELECT crsql_as_crr('table_name')
• A virtual table (crsql_changes) to ask the database for changesets or to apply changesets from another database
  • SELECT "table", "pk", "cid", "val", "col_version", "db_version", "site_id", cl, seq FROM crsql_changes WHERE db_version > x AND site_id = crsql_site_id() -- to get local changes
  • SELECT "table", "pk", "cid", "val", "col_version", "db_version", "site_id", cl, seq FROM crsql_changes WHERE db_version > x AND site_id != some_site_id -- to get all changes excluding those synced from some actor
  • INSERT INTO crsql_changes VALUES ([patches received from select on another peer])
• And crsql_begin_alter('table_name') & crsql_alter_commit('table_name') primitives to allow altering table definitions that have been upgraded to crrs.
  • Until we move forward with extending the syntax of SQLite to be CRR aware, altering CRRs looks like:

    SELECT crsql_begin_alter('table_name');
    -- 1 or more alterations to `table_name`
    ALTER TABLE table_name ...;
    SELECT crsql_commit_alter('table_name');

    A future version of cr-sqlite may extend the SQL syntax to make this more natural.

Application code uses the function extension to enable crr support on tables.

Networking code uses the crsql_changes virtual table to fetch and apply changes.

Usage looks like:

-- load the extension if it is not statically linked
.load crsqlite
.mode qbox
-- create tables as normal
create table foo (a primary key not null, b);
create table baz (a primary key not null, b, c, d);

-- update those tables to be crrs / crdts
select crsql_as_crr('foo');
select crsql_as_crr('baz');

-- insert some data / interact with tables as normal
insert into foo (a,b) values (1,2);
insert into baz (a,b,c,d) values ('a', 'woo', 'doo', 'daa');

-- ask for a record of what has changed
select "table", "pk", "cid", "val", "col_version", "db_version", "site_id", "cl", "seq" from crsql_changes;

┌───────┬─────────────┬─────┬───────┬─────────────┬────────────┬──────────────────────────────────────┬────┬─────┐
│ table │     pk      │ cid │  val  │ col_version │ db_version │ "site_id" │ cl │ seq │
├───────┼─────────────┼─────┼───────┼─────────────┼────────────┼──────────────────────────────────────┼────┼─────┤
│ 'foo' │ x'010901'   │ 'b' │ 2     │ 1           │ 1          │ x'049c48eadf4440d7944ed9ec88b13ea5'  │ 1  │ 0   │
│ 'baz' │ x'010b0161' │ 'b' │ 'woo' │ 1           │ 2          │ x'049c48eadf4440d7944ed9ec88b13ea5'  │ 1  │ 0   │
│ 'baz' │ x'010b0161' │ 'c' │ 'doo' │ 1           │ 2          │ x'049c48eadf4440d7944ed9ec88b13ea5'  │ 1  │ 1   │
│ 'baz' │ x'010b0161' │ 'd' │ 'daa' │ 1           │ 2          │ x'049c48eadf4440d7944ed9ec88b13ea5'  │ 1  │ 2   │
└───────┴─────────────┴─────┴───────┴─────────────┴────────────┴──────────────────────────────────────┴────┴─────┘

-- merge changes from a peer
insert into crsql_changes
  ("table", "pk", "cid", "val", "col_version", "db_version", "site_id", "cl", "seq")
  values
  ('foo', x'010905', 'b', 'thing', 5, 5, X'7096E2D505314699A59C95FABA14ABB5', 1, 0);
insert into crsql_changes ("table", "pk", "cid", "val", "col_version", "db_version", "site_id", "cl", "seq")
  values
  ('baz', x'010b0161', 'b', 123, 101, 233, X'7096E2D505314699A59C95FABA14ABB5', 1, 0);

-- check that peer's changes were applied
sqlite> select * from foo;
┌───┬─────────┐
│ a │    b    │
├───┼─────────┤
│ 1 │ 2       │
│ 5 │ 'thing' │
└───┴─────────┘

select * from baz;
┌─────┬─────┬───────┬───────┐
│  a  │  b  │   c   │   d   │
├─────┼─────┼───────┼───────┤
│ 'a' │ 123 │ 'doo' │ 'daa' │
└─────┴─────┴───────┴───────┘

-- tear down the extension before closing the connection
-- https://sqlite.org/forum/forumpost/c94f943821
select crsql_finalize();

Packages

Pre-built binaries of the extension are available in the releases section.

These can be loaded into sqlite via the load_extension command from any language (Python, NodeJS, C++, Rust, etc.) that has SQLite bindings.

The entrypoint to the loadable extension is sqlite3_crsqlite_init so you'll either need to provide that to load_extension or rename your binary to crsqlite.[dylib/dll/so]. See the linked sqlite load_extension docs.

load_extension(extension_path, 'sqlite3_crsqlite_init')

Note: if you're using cr-sqlite as a run time loadable extension, loading the extension should be the first operation you do after opening a connection to the database. The extension needs to be loaded on every connection you create.

For a WASM build that works in the browser, see the js directory.

For UI integrations (e.g., React) see the js directory.

How does it work?

There are two approaches with very different tradeoffs. Both will eventually be supported by cr-sqlite. v1 (and current releases) support the first approach. v2 will support both approaches.

Approach 1: History-free CRDTs

Approach 1 is characterized by the following properties:

1. Keeps no history / only keeps the current state
2. Automatically handles merge conflicts. No options for manual merging.
3. Tables are Grow Only Sets or variants of Observe-Remove Sets
4. Rows are maps of CRDTs. The column names being the keys, column values being a specific CRDT type
5. Columns can be counter, fractional index or last write wins CRDTs.
   1. multi-value registers, RGA and others to come in future iterations

Tables which should be synced are defined as a composition of other types of CRDTs.

Example table definition:

CREATE CLSet post (
 id INTEGER PRIMARY KEY NOT NULL,
 views COUNTER,
 content PERITEXT,
 owner_id LWW INTEGER
);

note: given that extensions can't extend the SQLite syntax this is notional. We are, however, extending the libSQL syntax so this will be available in that fork. In base SQLite you'd run the select crsql_as_crr function as seen earlier.

• CLSet - causal length set
• COUNTER - distributed counter
• PERITEXT - collaborative text

Under approach 1, merging two tables works roughly like so:

1. Rows are identified by primary key
2. Tables are unioned (and a delete log is consulted) such that both tables will have the same rows.

If a row was modified in multiple places, then we merge the row. Merging a row involves merging each column of that row according to the semantics of the CRDT for the column.

1. Last-write wins just picks the lastest write
2. Counter CRDT sums the values
3. Multi-value registers keep all conflicting values
4. Fractional indices are taken as last write

For more background see this post.

Notes:

• LWW, Fractional Index, Observe-Remove sets are available now.
• Counter and rich-text CRDTs are still being implemented.
• Custom SQL syntax will be available in our libSQL integration. The SQLite extension requires a slightly different syntax than what is depicted above.

Approach 2: Causal Event Log

To be implemented in v2 of cr-sqlite

Approach 2 has the following properties:

1. A history of every modification that happens to the database is kept
   1. This history can be garbage collected in certain network topologies
2. Merge conflicts can be automatically handled (via CRDT style rules) or the developer can define their own conflict resolution plan.
3. The developer can choose to fork the data on merge conflict rather than merging
4. Forks can live indefinitely or a specific fork can be chosen and other forks dropped

This is much more akin to git and event sourcing but with the drawback being that it is much more write heavy and much more space intensive.

Building

For a stable version, build against a release tag as main may not be 100% stable.

You'll need to install Rust.

• Installing Rust: https://www.rust-lang.org/tools/install

Run Time Loadable Extension

Instructions on building a native library that can be loaded into SQLite in non-wasm environments.

rustup toolchain install nightly # make sure you have the rust nightly toolchain
git clone --recurse-submodules git@github.com:vlcn-io/cr-sqlite.git
cd cr-sqlite/core
make loadable

This will create a shared library at dist/crsqlite.[lib extension]

[lib extension]:

• Linux: .so
• Darwin / OS X: .dylib
• Windows: .dll

WASM

For a WASM build that works in the browser, see the js repository.

CLI

Instructions on building a sqlite3 CLI that has cr-sqlite statically linked and pre-loaded.

In the core directory of the project, run:

make sqlite3

This will create a sqlite3 binary at dist/sqlite3

Tests

core:

cd core
make test

py integration tests:

cd core
make loadable
cd ../py/correctness
./install-and-test.sh

JS APIs

JS APIs for using cr-sqlite in the browser are not yet documented but exist in the js repo. You can also see examples of them in use here:

• Observable Notebook
• https://github.com/vlcn-io/live-examples

Research & Prior Art

cr-sqlite was inspired by and built on ideas from these papers:

• Towards a General Database Management System of Conflict-Free Replicated Relations
• Conflict-Free Replicated Relations for Multi-Synchronous Database Management at Edge
• Merkle-CRDTs
• Time, Clocks, and the Ordering of Events in a Distributed System
• Replicated abstract data types: Building blocks for collaborative applications
• CRDTs for Brrr