Multi-worker SharedArrayBuffer+OPFS VFS?

[samwillis]

I've been thinking of trying to build a cross tab/worker in-memory VFS with persistence to OPFS. In essence:

• Need to set:
 PRAGMA journal_mode=WAL;
PRAGMA wal_autocheckpoint=0;
• Each file is fully loaded into a SharedArrayBuffer when opening and shared between tabs/workers.
• The files SharedArrayBuffer has a header that implements locks using the sync Atomics api.
• A leader election is used to nominate one worker as leader, if it is closed a new leader election is run.
• The leader is responsible for loading files into memory, and responding to other workers when they ask for the file.
• The leader performs manual checkpoints, probably on an interval.
• The WAL if never written to disk, it's in-memory only - if the browser crashes a short period of writes will be lost.
• Only the leader is writing to disk, and only when performing a checkpoint.

If I'm not mistaken the only async call would be xOpen as it requires cross tab communication to retrieve the SharedArrayBuffer. However, that could be made sync if there was a preload function that the developer could call to preemptively load the database into memory in that worker. We then have a fully sync (when in a worker as we need Atomics.wait) VFS that could be used with the sync build of SQLite.

There are then a few extra things that could built on top of this:

• We could use WAL2 and BEGIN CONCURRENT to have better concurrency. With the periodic checkpoints WAL2 should help.
• We could experiment with using a "busy spin" lock on the main thread to enable sync SQLite on the main thread (sounds crazy but there are compelling use-cases), WAL2 and BEGIN CONCURRENT would possibly help reduce locking here.

So, my question is, how crazy is this as an idea and do you think it could work?

[rhashimoto]

I don't think wa-sqlite as-is has everything you need for SQLite WAL. First of all, right now wa-sqlite only supports sqlite3_io_methods version 1 when implementing a JavaScript VFS, which doesn't include the shared memory methods WAL needs. Enabling that support should be straightforward, but it's not in my own plans. The trickier problem is that WAL uses atomic load/store on shared memory without calling the VFS. It does this via macros that call intrinsic functions, directly on WASM memory. If you're planning on implementing the "shared memory" VFS methods by transferring data between WASM memory and a distinct SharedArrayBuffer, then you would to need to redefine these macros to operate on your SharedArrayBuffer. I think this is doable but not within the scope of wa-sqlite - you'll likely need your own custom SQLite build.

A possible alternative to using a JavaScript VFS that stores files in a dedicated SharedArrayBuffer is to instantiate your entire WASM module into a SharedArrayBuffer using WebAssembly.Memory (so all your workers use the same WASM address space). Then you could write your VFS in C, which should be good for performance as it wouldn't need to cross the language boundary nearly as often. I have not tried running multiple Workers in the same address space like this, but my reading of the doc is that can be made to work with the right build options (both Emscripten and SQLite). I think you would still need to customize the atomic macros.

If neither of those approaches is both workable and appealing, it is possible to implement something like WAL completely within a VFS. I see you tagged that post, so maybe you are considering or have already considered that. The details would be quite different with the "WAL" in a SharedArrayBuffer (instead of OPFS and IndexedDB) and using only synchronous APIs, but the basic idea would be the same. There's a good chance such a VFS could work with the stock wa-sqlite build.

I don't know anything about WAL2 so I have nothing to offer there.

[rhashimoto]

Note also that for SQLite WAL, you'll need to figure out how to implement xShmLock (as well as plain xLock) in a way that (1) is synchronous and (2) releases the lock if the tab exits uncleanly. If you build something like FLOOR instead, you won't have to support the shared memory methods but you will need to track the latest transaction each client sees, so that's a very similar problem.

It's possible to solve this by calling asynchronous APIs (like WebLocks, my hammer for every synchronization nail) in a separate Worker and using SharedArrayBuffer as a synchronous bridge; that's what absurd-sql and the official SQLite WASM do for all their VFS methods. An alternative is to use asynchronous APIs to establish the state you'll need before calling into SQLite - just like you're already suggesting for preloading your database before calling SQLite to open it. In this case, you would want to know whether incoming SQL is a read or write transaction (either by parsing it or relying on the submitter to tell you), and preconfigure the state accordingly. I think this would be simpler and faster than a SharedArrayBuffer bridge (at least if you're not parsing the SQL).

[rhashimoto]

Separate sub-thread: How are you planning to implement checkpointing to persistent storage? I can think of a few ways:

• After the SQLite checkpoint completes, write the entire file to a new temporary file in OPFS and then rename that over the original file (renaming should be atomic). Could be inefficient if only a few pages change and your database is large.

• In your VFS, when a page is written to the main database, first get the original page and write it to a journal file in OPFS (not a SQLite rollback journal, a custom journal you come up with) before writing the new page contents. Delete the journal file after checkpointing. This is probably inefficient because you have to flush the journal file after each write.

• In your VFS, before checkpointing but with the write lock, parse the WAL file and copy the corresponding pages from the main database to a journal file in OPFS (again, a custom journal). Delete the journal file after checkpointing. This is the best I can think of with OPFS.

• Persist to IndexedDB instead of OPFS. In your VFS, when a page is written to the main database, also write it to IndexedDB. If all the writes for a checkpoint are in one IndexedDB transaction, the database in persistent storage will always be consistent. This is my favorite so far. Your initial database load into memory will be slower than with OPFS, but (1) you don't have to deal with recovery at all and (2) I expect this to be the fastest way to checkpoint (a journal requires sync journal, sync database, reset journal, while IndexedDB commits can be streamed without syncing if durability isn't critical).

[samwillis]

Thanks Roy, there is much to digest there and I need to read up a little more.

Maybe the route here is to experiment first with a non-persisted shared memory VFS not using the WAL, keep it as simple as possible. That way it would be possible to learn more about locking (I hadn't considered a tab holding a lock when closing) and having a SharedArrayBuffer based VFS.

How are you planning to implement checkpointing to persistent storage?

My (possibly naive) thinking was that as the VFS would know if a file is a main DB file or a journal/wal file, when it writes to the main file it multiplexes the write to both the in-memory file and the on disk file. So, hopefully it could just use SQLites own WAL checkpointing to update the pages on disk. You may be 10 steps ahead of me win your thinking though.

[rhashimoto]

Maybe the route here is to experiment first with a non-persisted shared memory VFS not using the WAL, keep it as simple as possible.

I agree, that sounds like a good way to get started.

when [checkpointing] writes to the main file it multiplexes the write to both the in-memory file and the on disk file.

This is basically my fourth suggestion, my favorite, but note that this doesn't work with your plan to persist to OPFS (so I suggest IndexedDB instead). The problem is that checkpointing a transaction must be atomic in case of an interruption (tab closed, browser crash, power failure, etc.) during checkpointing. If you use OPFS I think you'll need some sort of checkpointing journal to implement atomic behavior. Real WAL doesn't require this because the WAL file is persistent, but yours isn't. Not checkpointing at all works. Checkpointing complete transactions works. Anything in between leaves your database corrupted.