Exporation: Cross Tab Sync

[tantaman]

Pre-read: design decision: synchronous queries

SQLite in the browser generally makes cross-tab sync simple. E.g., you can open https://vite-starter.fly.dev/ in several tabs and it seamlessly reflects writes across tabs.

Given the decision to provide synchronous queries in LiveStore, however, cross tab sync becomes rather complicated.

This is because the current design creates a separate database for each tab. Pictured below:

Each in-memory DB is written immediately. Those writes are lazily sent to the worker to write to disk. The data flow is currently in a single direction and updates to the disk DB don't make it back to the in-memory DB.

This means multiple tabs will quickly diverge and not see one another's changes until refresh. The disk DB is currently consistent and effectively last write wins -- assuming transactions from the memory dbs don't fail to apply to the disk DB.

So how do we enable cross tab sync?

Naive Approach

The naive solution is to:

1. Let the worker serialize writes
2. Broadcast updates from the worker to the in-memory DBs
3. Apply these writes

The problem, however, is:

1. Writes on the in-memory DBs will be applied in different orders from one another and from the disk DB
2. User's actively editing something could have their edits dropped by an update

Problem 1 illustrated:

We either need a way to perform rebases so everyone ends up with the same write order or change our operations to be independent of order (e.g., CRDTs)

Problem 2 would also be solved via rebasing since edits made to the in-memory DB that are not yet present in the disk DB will remain "on top" and uninterrupted.

Some exploration on enabling rebases in SQLite: rhashimoto/wa-sqlite#131

Rebasing

A workable solution is to do rebasing of changes. Each in-memory DB tracks two things:

1. A SQLite WAL that contains the changes that have been made locally since the mem DB last synced with the disk DB
2. A list of the mutations, and their arguments, that have been made locally since the mem DB last synced with the disk DB

(1) is a native SQLite WAL file since SQLite will fulfill read requests from the WAL first before going to the main DB file.

Sync works like so:

1. App starts, in-memory DB is created from a copy of the disk DB
2. Writes to the in-memory DB go to the WAL and not the main memory file
3. Each write is also recorded in a mutation log as "mutation_name, args"
4. When the disk DB syncs to the memory DB the memory DB throws out its WAL, resetting back to the base state
5. The memory DB applies the changes received from the disk DB
6. The memory DB then re-applies the mutation log from (3)

We pass version information around with the sync so we know what mutations the disk DB has received from the memory DB, allowing us to truncate our mutation log from (3).

Note that SQLite doesn't actually allow WAL mode for in-memory DBs 3 so we'd likely need to do this with a custom memory VFS 4. Is there a faster path forward?

References:

1. A Rebasing VFS? rhashimoto/wa-sqlite#131
2. https://fly.io/docs/litefs/how-it-works/#capturing-sqlite-transactions
3. https://sqlite.org/forum/info/a44bddd65750d084
4. Design Decision: Synchronous Queries #39 (comment)

Session Extension

The SQLite Session Extension is another option to enable rebasing.

The session extension allows one to:

1. Start a session
2. Make changes
3. Close the session

The output of this is a set of operations that were applied to the DB. This set of operations can be inverted to allow undoing those changes.

If all writes to the in-memory DB are captured as sessions then we can invert those sessions to re-wind, add changes from the disk db, then re-apply those changes on top.

This is what @pkulchenko has been doing in https://github.com/pkulchenko/fullmoon for the last 1-2 years and it seems to be working well for him. TODO: which braid meeting does he describe his system? https://braid.org/

This is the simplest route to get something working. The perf hit here is unknown but we could expand session duration to gain some perf back at the cost of less syncing to other tabs.

Implementing this would mean wrapping each transaction with something like:

sqlite3session_create(db, "main", &pSession);
sqlite3session_attach(pSession, NULL);
run_user_transaction();
sqlite3session_changeset(pSession, pnChangeset, ppChangeset);
// send ppChangeset off to the disk db
sqlite3session_delete(pSession);

And keeping a log of changeset objects. This log of changeset objects would be used to un-do the current stack of changes in order to pull in changes from the disk db.

When we know that the disk DB has incorporated a range of changesets, we can drop them from our log. We could tag each changeset with a auto increment id and have the disk DB send us that ID back when it sends changes. Using this ID, we know what changes to truncate out of the mem db log after applying disk DB changes.

Note that the Disk DB never rebases. Only tab DBs rebase. The disk DB applies changes as it receives them and is the source of truth on the order of changes.

Disk DB -> Mem DB Sync Via Session Extension

Mem DB -> Disk DB Sync via Session Extension

CR-SQLite

CR-SQLite would enable cross tab sync via CRDTs. This would also be rather trivial to get up an running.

Gathering all changes from the in-memory db to send to the disk db would be done like so:

SELECT * FROM crsql_changes WHERE db_version > $last_version_sent_to_disk_db

Gather all changes from the disk db to send to an in-memory db would be:

SELECT * FROM crsql_changes WHERE db_version > $last_version_sent_to_mem_db_x

Applying changes is as simple as:

INSERT INTO crsql_changes VALUE (result_of_select_above)

We could run this process after each transaction sync a tab to disk then sync disk to another tab.

CR-SQLite is currently used by fly.io to keep ~1,000 SQLite databases in sync so it is solid at this point.

The downsides:

• Requires each synced table to be converted to a CRDT table
• ?

SQLSync

https://github.com/orbitinghail/sqlsync is another SQLite sync that operates via rebasing. I haven't researched this much yet other than via informal discussions with @carlsverre

If we decide to implement rebasing ourselves, without using the session extension, we should look at this first.

[tantaman]

CR-SQLite tab based sync would be incredibly simple. Session extension sync would be the next simplest option.

The nice thing about the session extension sync:

• No extra code for us to maintain. Session extension is a stock SQLite extension
• No extra schema requirements. CR-SQLite has a few schema requirements it would impose on users.
• We could keep all sessions around for a debug mode to allow re-winding individual changes and walking back or forward in time.

[tantaman]

One other option for cross-tab sync is the route taken by PowerSync (https://www.powersync.com/) when it comes to client-server sync.

In their case:

A client does not accept any updates from the server until the server has incorporated all updates from the client.

In other words, tabs can send updates to the "disk worker" but the tabs will not take any updates from the disk worker until they have no writes ahead of what the disk worker has.

This is a pretty elegant solution in terms of how simple it is. No rebasing needed. The downside would be that a tab would be locked out of receiving updates while it is dirty but I don't think this would be a very long duration in practice.

cc @samwillis @balegas