A Rebasing VFS?

[tantaman]

As you know I maintain an extension that allows multi-writer SQLite. The approach I've taken is one that is pretty complicated and requires all nodes to run the same algorithm.

There are other, simpler, approaches which (in a client-server setup) allow the server to be mostly agnostic to how conflict resolution happens. In these approaches the user can use anything they'd like on the backend (postgres, sqlite, mongo, etc.).

One of those simpler models is the idea of "rebasing" changes on a client.

At a high level:

1. The client maintains a log of mutations that it has made locally
2. The client writes local database modifications to a separate file, similar to a WAL

When the server sends data to the client, the client throws away the file from (2), effectively re-setting its database state to what it was before the client made any local changes.

Then the client applies the changes sent by the server to its state, modifying the actual DB file.

Finally, the client re-plays the mutation log from (1) to get to the new server + local state. If any client-side mutations were incorporated in the update sent by server, the client starts at that position in the log rather than the start of the log.

---

I'm thinking it should be possible to write a VFS that re-directs xRead and xWrite requests. xWrite would send all local writes to a custom file rather than the main db file. xRead would be updated to read from the local write file if the requested range was updated locally, from the normal file if not.

Does hooking in at the VFS layer sound at all reasonable to you to implement this? I've never ventured into VFS territory so I don't know what gotchas may be lurking there. My assumption is that xRead and xWrite are always reading and writing full pages.

[rhashimoto]

In this approach, are both the server updates and the local mutation log just SQL (or some representation that can be reconstituted and applied as SQL)?

Basically what you want is a mechanism to snapshot the database at some point, apply some local write transactions, and later restore the snapshot, is that correct?

If yes, then I think this can be done with a VFS. As you say, this is similar to a WAL and coincidentally I just implemented WAL within a VFS so there's an existence proof for a big chunk of your idea. You do need to be careful that your database can recover from a crash while writing your WAL (and your local mutation log).

Since this VFS is more about behavior than platform, I would probably try to write it as a shim VFS in C that uses another VFS to do the actual reading and writing.

My assumption is that xRead and xWrite are always reading and writing full pages.

SQLite doesn't guarantee this, but it is currently mostly true. The exceptions are:

• When reading the file header from page 1 (SQLite page numbers start at 1) SQLite sometimes reads only part of a page and not necessarily on a page boundary.
• When changing the database page size with VACUUM, I think SQLite will read or write with a mismatched old or new page size, can't remember the details exactly.

The only tricky part I foresee is making sure that SQLite page cache isn't confused upon restoring a snapshot. SQLite uses a counter (offset 24 in the file header) to know when another connection has modified the database and invalidated its cache. It checks whether that counter is different; I'm not sure if it checks that it is larger. If it does then you would need to patch that value to be greater than in any page 1 in the WAL.

You will need some side channel to tell your VFS when to snapshot and begin diverting writes and when to restore the snapshot. You could use xFileControl() for this, either with a custom op or you could define a custom PRAGMA with SQLITE_FCNTL_PRAGMA.

[tantaman]

In this approach, are both the server updates and the local mutation log just SQL (or some representation that can be reconstituted and applied as SQL)?

Yes. The server will receive mutations from the client and do whatever it wants with them (apply them, reject them, change them) but, once it is done, it'll send back to the client:

1. A number indicating up to which client mutation was incorporated by the server
2. A list of insert, delete, and update operations for the client to apply to match the server state

Basically what you want is a mechanism to snapshot the database at some point, apply some local write transactions, and later restore the snapshot, is that correct?

Exactly.

You do need to be careful that your database can recover from a crash while writing your WAL (and your local mutation log).

Hmm. Yes, I suppose the tricky part here is that the mutation log could get out of sync with the WAL during a crash.

I would probably try to write it as a shim VFS

This is helpful, thanks.

[rhashimoto]

I suppose the tricky part here is that the mutation log could get out of sync with the WAL during a crash.

Definitely yes, but just handling the WAL properly will also take some attention. Your VFS will need to verify the WAL on xOpen(), making sure it accepts only complete transactions and discarding anything else.

You might want to define your own WAL format for this instead of reusing SQLite's. The reason is that the SQLite WAL format marks the end of a transaction in the frame header (WAL records are called frames) for the last page. That makes sense if you know which page is the last one in the transaction when you write it, which SQLite does but you won't. So if you want to keep SQLite's format then you'll either need to rewrite the last frame or defer writing each frame until you know whether it is the last one or not.

I defined my own WAL format for FLOOR, but my format likely won't be of any use to you because I store most of the frame metadata in IndexedDB. Using IndexedDB provides me with atomicity and consistency in case of a crash, but you'll have to build those guarantees on your own. Not hard, just takes a lot of attention and a healthy amount of paranoia. You could use a SQLite database for your WAL and mutation log as an easy way to get there, but that might be overkill and a performance drag.

[rhashimoto]

I had some other bits of advice:

Your proposed VFS will need to infer write transaction boundaries from the stream of VFS method calls. The obvious way is to watch calls to xLock/xUnlock for acquiring and releasing an exclusive lock, but while that can work with a highly controlled application, I don't think it's a good choice for a library. For example, using xLock/Unlock for transaction boundaries will break with PRAGMA locking_mode=exclusive. The way I've settled on is that when you're not already in a transaction then the first xWrite call on the database file marks the start of a transaction, and a transaction ends with SQLITE_FCNTL_SYNC (which could be either a commit or rollback).

SQLite's WAL support doesn't need a journal at all. When you're writing to your WAL you won't need a journal either, unless you want to support client-initiated ROLLBACK - i.e. you won't need a journal to prevent database corruption. If you do want to allow ROLLBACK when you're using a WAL, you can use PRAGMA journal_mode=memory provided you expect the journal to fit in memory.

I thought about using actual WAL mode for this, instead of writing a VFS. If you can disable all automatic checkpointing then restoring the database could be done by closing the database, deleting the WAL file, and reopening the database. But I'm not sure how to prevent the automatic checkpointing on database close, and this approach would require a platform that supports WAL mode, which currently doesn't include browsers.

[tantaman]

We're getting pretty far beyond my expertise at this point. I have a few ignorant questions to be followed up by more intelligent ones once I start working on this in earnest.

Not supporting client-initiated rollback would literally mean people couldn't bail from a transaction if they detect an exception in their application layer? That sounds rather limiting.

you can use PRAGMA journal_mode=memory provided you expect the journal to fit in memory.

Is the behavior on how large a journal grows well defined? E.g., is it only as large as the sum of un-committed transactions?

You might want to define your own WAL format for this instead of reusing SQLite's

I believe LiteFS and Litestream work by watching SQLite WAL and Journal files to detect transactions. My next step of research was to understand more about how those systems work (https://fly.io/docs/litefs/how-it-works/#capturing-sqlite-transactions).

Maybe it's possible to do a similar sort of watching then prevent SQLite's checkpointing of the WAL and throw away the WAL when receiving updates from the server.

[rhashimoto]

Not supporting client-initiated rollback would literally mean people couldn't bail from a transaction if they detect an exception in their application layer? That sounds rather limiting.

You couldn't use a ROLLBACK statement. I think you could still effectively abandon a transaction by closing and reopening the database, basically a self-initiated crash.

Is the behavior on how large a journal grows well defined? E.g., is it only as large as the sum of un-committed transactions?

The rollback journal contains database pages replaced by the current transaction, so equal to or less than the number of pages a transaction ends up writing to the database - less than because the transaction may be appending new pages or writing some pages more than once as it progresses. In the worst case the journal could hold the entire database, e.g. if someone replaces the entire schema.

Maybe it's possible to do a similar sort of watching then prevent SQLite's checkpointing of the WAL and throw away the WAL when receiving updates from the server.

Yes, maybe. I was thinking about using WAL mode and suppressing checkpointing at the application level (if that is possible on database close) to skip writing a VFS. Preventing WAL checkpointing in a VFS means you still have to write a VFS, but perhaps that would still be simpler. It might be as easy as ignoring writes to the database when in snapshot mode.