A component of the vulcan project.
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.
- Syncing data between devices
- Implementing realtime collaboration
- Offline editing
- Being resilient to network conditions
- 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:
Individuals: robinvasan | iansinnott | davefowler | barbalex
Perf data: https://github.com/vlcn-io/cr-sqlite/blob/main/py/perf/perf.ipynb
- Currently inserts into CRRs are 2.5-3x slower than inserts into regular SQLite tables.
- Reads are the same speed
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 databaseSELECT "table", "pk", "cid", "val", "col_version", "db_version", COALESCE("site_id", crsql_site_id()) FROM crsql_changes WHERE db_version > x AND site_id IS NULL
-- to get local changesSELECT "table", "pk", "cid", "val", "col_version", "db_version", COALESCE("site_id", crsql_site_id()) FROM crsql_changes WHERE db_version > x AND site_id IS NOT some_site
-- to get all changes excluding those synced from some siteINSERT INTO crsql_changes VALUES ([patches receied 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 tocrr
s.- Until we move forward with extending the syntax of SQLite to be CRR aware, altering CRRs looks like:
A future version of cr-sqlite may extend the SQL syntax to make this more natural.
SELECT crsql_begin_alter('table_name'); -- 1 or more alterations to `table_name` ALTER TABLE table_name ...; SELECT crsql_commit_alter('table_name');
- Until we move forward with extending the syntax of SQLite to be CRR aware, altering CRRs looks like:
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 column
-- create tables as normal
create table foo (a primary key, b);
create table baz (a primary key, 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 * from crsql_changes;
table pk cid val col_version db_version site_id
----- --- --- ----- ----------- ---------- -------
foo 1 b 2 1 1 1(�zL
\hx
baz 'a' b 'woo' 1 2 1(�zL
\hx
baz 'a' c 'doo' 1 2 1(�zL
\hx
baz 'a' d 'daa' 1 2 1(�zL
\hx
-- merge changes from a peer
insert into crsql_changes
("table", pk, cid, val, col_version, db_version, site_id)
values
('foo', 5, 'b', '''thing''', 5, 5, X'7096E2D505314699A59C95FABA14ABB5');
insert into crsql_changes ("table", pk, cid, val, col_version, db_version, site_id)
values
('baz', '''a''', 'b', 123, 101, 233, X'7096E2D505314699A59C95FABA14ABB5');
-- check that peer's changes were applied
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();
Example apps that use cr-sqlite
:
- Basic setup & sync via an Observable Notebook
- TodoMVC - https://github.com/vlcn-io/live-examples
- Tutorials
- WIP Local-First Presentation Editor
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.
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.
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 is characterized by the following properties:
- Keeps no history / only keeps the current state
- Automatically handles merge conflicts. No options for manual merging.
- Tables are Grow Only Sets or variants of Observe-Remove Sets
- Rows are maps of CRDTs. The column names being the keys, column values being a specific CRDT type
- Columns can be counter, fractional index or last write wins CRDTs.
- 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,
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:
- Rows are identified by primary key
- 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.
- Last-write wins just picks the lastest write
- Counter CRDT sums the values
- Multi-value registers keep all conflicting values
- 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.
To be implemented in v2 of cr-sqlite
Approach 2 has the following properties:
- A history of every modification that happens to the database is kept
- This history can be garbage collected in certain network topologies
- Merge conflicts can be automatically handled (via CRDT style rules) or the developer can define their own conflict resolution plan.
- The developer can choose to fork the data on merge conflict rather than merging
- 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.
You'll need to install Rust.
- Installing Rust: https://www.rust-lang.org/tools/install
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 [email protected]: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
For a WASM build that works in the browser, see the js repository.
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
core:
cd core
make test
py integration tests:
cd core
make loadable
cd ../py/correctness
./install-and-test.sh
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:
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