Write-ahead logging in a VFS

[rhashimoto]

TL;DR

OPFSWriteAheadVFS is a new synchronous VFS that uses write-ahead logging to achieve significant performance and concurrency improvements. It uses the proposed readwrite-unsafe mode that is currently implemented only on Chromium browsers.

Overview

I wrote a post some time ago on the promise of a couple new browser features that starts with this teaser:

How would you like a persistent browser database that...

• ...doesn't have the time and space penalties of Asyncify?
• ...doesn't have COOP/COEP restrictions?
• ...works from multiple contexts, e.g. from multiple tabs?
• ...supports simultaneous read transactions?
• ...supports write-ahead logging (WAL)?
• ...moves data faster than IndexedDB?
• ...might have similar write transaction overhead to IndexedDB?
• ...allows database copying in/out and renaming using the OPFS API?

A new example VFS, named OPFSWriteAheadVFS, has all these features except one — it doesn’t have similar write transaction overhead to IndexedDB…it’s much faster than that.

OPFSWriteAheadVFS implements write-ahead logging, an alternative journaling strategy with some performance and concurrency benefits. It is very similar in concept to SQLite’s own experimental WAL2 journal mode but it is a completely separate implementation within the VFS and without SQLite knowing anything about it.

SQLite’s standard WAL implementation (aka WAL1) uses a single WAL file, with which read transactions don’t block write transactions or other read transactions, and write transactions don’t block read transactions. However, full checkpoints are needed occasionally to prevent unbounded growth of the WAL file, and performing those checkpoints blocks both readers and writers. OPFSWriteAheadVFS is more like WAL2, switching between two WAL files, so full checkpoints are not required and checkpointing does not block readers or writers.

OPFSWriteAheadVFS makes use of OPFS readwrite-unsafe mode, a proposal to allow concurrent file access from multiple synchronous access handles that is currently supported only on Chromium browsers.

OPFSWriteAheadVFS is being developed in collaboration and consultation with PowerSync.

Who is this VFS for?

OPFSWriteAheadVFS should be considered by anyone wanting more performance and/or concurrency over browser compatibility.

Advantages

• All methods are synchronous, so it works with the smaller and faster default WebAssembly build.
• Can trade durability for much less write overhead, making it the fastest with write transactions.
• Easily beats every other VFS in multiple connection performance. Multiple read transactions and a single write transaction can execute concurrently without blocking (unless exclusive locking mode is configured).
• Roughly equal performance to other OPFS VFS implementations with everything else.

Disadvantages

• Requires OPFS readwrite-unsafe, a feature only in Chromium browsers.
• Uses OPFS synchronous access handles, which requires a Worker context.
• Doesn’t support attaching multiple databases.
• Code is new, lengthy (2000+ LoC), and moderately complicated, which makes it a higher bug risk.

OPFSWriteAheadVFS usage notes

If you want to try this VFS, here are some things you should know.

Compatibility

• OPFSWriteAheadVFS is a synchronous VFS so it can used with any wa-sqlite build (i.e. default, Asyncify, or JSPI).
• OPFSWriteAheadVFS requires the readwrite-unsafe OPFS locking mode, currently only supported in Chromium browsers.
• OPFSWriteAheadVFS implements a WAL2-like journaling approach. This is always on, i.e. it is not enabled or disabled with PRAGMA journal_mode and only journal mode DELETE (which is the default) or OFF should be used (using journal_mode=OFF is typically a SQLite anti-pattern, but it should be safe with this VFS).

Special restrictions

These are important workarounds for cases where ordinarily valid SQLite usage can produce an error with OPFSWriteAheadVFS.

• For any multiple-statement write transaction, BEGIN IMMEDIATE or BEGIN EXCLUSIVE must be used. Transactions that only read the database may start with BEGIN DEFERRED or BEGIN, but any statement that could modify the database will raise an error (technically if the first statement in a transaction is a write then no error will be raised, but depending on that is not recommended).

-- auto-commit write statement is okay
INSERT INTO t VALUES ('foo');

-- write within BEGIN IMMEDIATE or BEGIN EXCLUSIVE is okay
BEGIN IMMEDIATE;
INSERT INTO t VALUES ('foo');
COMMIT;

-- read within BEGIN or BEGIN DEFERRED is okay
BEGIN;
SELECT * FROM t LIMIT 1;
COMMIT;

-- write within BEGIN or BEGIN DEFERRED is an error
BEGIN;
SELECT * FROM t LIMIT 1;
INSERT INTO t VALUES ('foo');  -- error!
COMMIT;

• Schema changes (CREATE, DROP, ALTER) using auto-commit, i.e. made outside of an explicit BEGIN IMMEDIATE or BEGIN EXCLUSIVE transaction, can raise an error in some circumstances (e.g. after another connection has also changed the schema). For this reason, it is recommended to put all schema changes within an explicit write transaction (or in exclusive locking mode).
• VACUUM should only be done while under PRAGMA locking_mode=EXCLUSIVE. This would typically be done like this (changing locking mode takes effect on the following transaction):

  PRAGMA locking_mode=exclusive;
  VACUUM;
  PRAGMA locking_mode=normal; -- takes effect after the next tx
  BEGIN IMMEDIATE;
  ROLLBACK; -- locking_mode returns to normal after this stmt

Configuration

The default configuration should work reasonably well for typical applications, but the behavior can be adjusted with the following PRAGMA settings:

• By default the WAL is not guaranteed durable — recent transactions could be lost to crash or power failure. To make the WAL durable, use PRAGMA synchronous with a setting of FULL or EXTRA (both do the same thing). Having a durable WAL will reduce write performance.
• By default, a connection executing a write transaction will switch to the other WAL file when its contents have been checkpointed and the current WAL file exceeds 1000 pages. This threshold can be modified with PRAGMA journal_size_limit.
• Checkpointing (moving data from the WAL to the main database file) is normally done automatically. You can disable automatic checkpointing on a connection with PRAGMA wal_autocheckpoint=0.
• PRAGMA wal_checkpoint with no argument or PASSIVE does the same thing as an automatic checkpoint (which does not guarantee any checkpointing takes place). Using an argument of FULL, RESTART, or TRUNCATE copies the entire contents of the WAL to the database file.
• Configuring PRAGMA cache_size sufficiently high is always important for best performance, and using OPFSWriteAheadVFS adds another reason for that. In the default journal mode (DELETE), SQLite will use its batch atomic write optimization (which avoids writing the journal to the file system) as long as the page cache does not overflow.
• The use of a rollback journal can be completely disabled with PRAGMA journal_mode=OFF. This is normally a SQLite anti-pattern that risks database corruption but that danger doesn't apply with WAL. Even so, typical applications should not need this. The primary drawback is that any use of ROLLBACK must be avoided while in this mode, including via statement, trigger, or conflict. The valid journal_mode settings for OPFSWriteAheadVFS are DELETE (which is the default), MEMORY, and OFF.
• Use PRAGMA lazy_lock=value, where value may be READ, WRITE, READWRITE, or NONE (case-insensitive) to enable lazy locking for the read lock, the write lock, both, or none. This optimization feature does not release the underlying platform lock unless an unlock request message is received, so reacquiring the lock is a synchronous no-op if there is no such request. For most practical situations this should be set to either READ or READWRITE (READWRITE is the default). Using lazy write locking increases performance for a single write connection, but may decrease performance under high contention with multiple write connections.

Performance

Write-ahead logging can improve performance in a couple ways:

1. Trading durability for performance. With a rollback journal, each write transaction must be flushed to the file system to guarantee atomicity, consistency, and durability (the A, C, and D in ACID). With WAL and WAL2, flushing is only needed for durability; transactions are atomic and consistent without it. If durability is not a requirement then writers can skip flushing, which is by far the most expensive file operation.

2. Increasing concurrency. Under normal conditions (i.e. without setting exclusive locking mode), readers are never blocked and writers are only blocked by other writers.

The test results below were measured with Chrome on a Mac mini M2.

Single connection

Single-connection performance is roughly equivalent to OPFSCoopSyncVFS, except that write transaction overhead is much faster (see Test 1):

Test	default OPFSWriteAheadVFS	default OPFSCoopSyncVFS
Test 1: 1000 INSERTs	0.132	0.748
Test 2: 25000 INSERTs in a transaction	0.067	0.065
Test 3: 25000 INSERTs into an indexed table	0.101	0.093
Test 4: 100 SELECTs without an index	0.102	0.105
Test 5: 100 SELECTs on a string comparison	0.404	0.401
Test 6: Creating an index	0.014	0.017
Test 7: 5000 SELECTs with an index	0.032	0.032
Test 8: 1000 UPDATEs without an index	0.032	0.032
Test 9: 25000 UPDATEs with an index	0.119	0.125
Test 10: 25000 text UPDATEs with an index	0.09	0.095
Test 11: INSERTs from a SELECT	0.071	0.06
Test 12: DELETE without an index	0.099	0.063
Test 13: DELETE with an index	0.036	0.044
Test 14: A big INSERT after a big DELETE	0.05	0.044
Test 15: A big DELETE followed by many small INSERTs	0.029	0.03
Test 16: DROP TABLE	0.004	0.009

Multiple connections

Here are results of a contention test with 3 readers and 1 writer with OPFSCoopSyncVFS:

[16:08:10.662] build: default  
[16:08:10.662] config: OPFSCoopSyncVFS  
[16:08:10.662] nWriters: 1  
[16:08:10.662] nReaders: 3  
[16:08:10.662] nSeconds: 10  
[16:08:15.766] launch workers  
[16:08:16.041] start  
[16:08:26.041] worker 1 reader 2675 iterations  
[16:08:26.044] worker 3 reader 2675 iterations  
[16:08:26.045] worker 0 writer 2677 iterations  
[16:08:26.046] worker 2 reader 2676 iterations  
[16:08:26.046] complete

With the new OPFSWriteAheadVFS:

[16:06:44.858] build: default  
[16:06:44.858] config: OPFSWriteAheadVFS  
[16:06:44.858] nWriters: 1  
[16:06:44.858] nReaders: 3  
[16:06:44.858] nSeconds: 10  
[16:07:01.824] launch workers  
[16:07:02.306] start  
[16:07:12.306] worker 2 reader 198833 iterations  
[16:07:12.306] worker 1 reader 197172 iterations  
[16:07:12.306] worker 3 reader 196112 iterations  
[16:07:12.306] worker 0 writer 29887 iterations  
[16:07:12.306] complete

Well, that’s just ridiculous. It’s highly unlikely that ~75x reads and ~10x writes is achievable on real workloads, but it does appear that the improvements on multiple connections could be quite dramatic.

Here are results with PRAGMA lazy_lock=READ (the default is READWRITE):

[16:31:43.658] build: default  
[16:31:43.658] config: OPFSWriteAheadVFS  
[16:31:43.658] nWriters: 1  
[16:31:43.658] nReaders: 3  
[16:31:43.658] nSeconds: 10  
[16:31:45.868] launch workers  
[16:31:46.270] start  
[16:31:56.270] worker 3 reader 251157 iterations  
[16:31:56.270] worker 2 reader 251250 iterations  
[16:31:56.270] worker 1 reader 249936 iterations  
[16:31:56.270] worker 0 writer 21644 iterations  
[16:31:56.270] complete

Hmm. The writer slowing down is totally expected, but I didn’t expect the readers to speed up. Maybe we’re saturating the platform capacity?

How it works

OPFSWriteAheadVFS is inspired by and conceptually similar to SQLite’s experimental WAL2 implementation (summary, source docs). It uses two WAL files, and a writer decides to switch from one to the other based on the number of pages in the WAL and whether the currently inactive one has been completely checkpointed to the actual database file. Any connection can checkpoint the inactive WAL file provided that all connections have accepted every transaction on it.

However, the mechanics of how OPFSWriteAheadVFS accomplishes those things is quite different from the SQLite implementation to adapt to the web platform. In SQLite, WAL management is done in shared memory, but in OPFSWriteAheadVFS, each connection maintains its own data structures to look up pages in the WAL, and connections broadcast transaction and checkpoint messages to inform other connections of their actions (with fallback mechanisms in case a message fails to be sent).

OPFSWriteAheadVFS reuses a lot of tricks from other VFS implementations:

• retry hack (used in OPFSCoopSyncVFS) - This allows the VFS to be synchronous despite using asynchronous APIs to open files and acquire locks.
• batch atomic write (used in IDBBatchAtomicWriteVFS) - This keeps a journal for explicit use of ROLLBACK in memory if there is space in the cache, and otherwise spills it to the file system.
• encoding connection state in a lock name (used in OPFSPermutedVFS) - This (ab)uses the Web Locks API to publish state (instead of arbitrate access), which enables checkpointing to avoid overwriting or removing data any connection is currently using.
• lazy locks (used in OPFSCoopSyncVFS) - This avoids releasing a platform lock unless another connection has requested it, which makes reacquisition of the lock (for the next transaction) a no-op.
• access handle pool (used in AccessHandlePoolVFS) - This pre-opens temporary files when the database file is opened, dynamically associating/disassociating them as temporaries are created/deleted.
• broadcasting transactions (used in OPFSPermutedVFS) - This updates other connections with page lookup data for new write transactions.

A key WAL feature is that readers don’t block writers and writers don’t block readers (writers do block each other). This means that readers and writers should use separate locks to manage access. But when the VFS receives the initial lock request from SQLite, how does it know whether a read or a write transaction is starting? SQLite doesn’t tell us…until now. As of SQLite 3.53, the library sends an experimental hint that it intends to lock the database for writing. OPFSWriteAheadVFS uses this new hint to distinguish readers and writers and identify the appropriate lock to use. This is why using BEGIN or BEGIN DEFERRED for a write transaction is an error with OPFSWriteAheadVFS, because it won’t receive the write hint.