Skip to content
benmckibbenPublic

About

A branchable, snapshot-based SQLite page store: a crash-consistent log, a loadable extension that gives SQLite cheap branches, and a CLI.

Topics

Resources

Contributing

Security policy

Stars

0 stars

Watchers

0 watching

Forks

Repository files navigation

forkdb

A branchable, snapshot-based SQLite page store with a library, a loadable extension, and a CLI.

Status: 0.1.0, the first release, and unstable. Nothing here is a promise about what stays the same (see STABILITY.md). What is tested, and against what, is in Durability and Platforms.

On top of an append-only log with power-loss recovery (tested against a simulated disk: see Durability), forkdb layers branching (fork, snapshot, diff, promote, undo), garbage collection, and an open-time checkpoint so frequent opens stay fast. Applications connect through a SQLite VFS that enforces one-writer-per-branch.

What you need

forkdb is a C library that requires:

  • A SQLite built with the session API (SQLITE_ENABLE_SESSION, SQLITE_ENABLE_PREUPDATE_HOOK) for diff/promote/undo. The CLI and the library are built with it. The portable loadable extension (scripts/build-ext.sh) is not: the session API is not in the table SQLite gives an extension, so its diff, promote and undo report that this host has none (forkdb_info.session_api is 0), and the VFS and branch operations work.
  • A file system that supports rename over an open file for compaction (otherwise the store works without it).
  • One writer per branch. SQLite allows one write transaction at a time on a branch. Connections on different branches can each have a write transaction open at once and commit independently (measured, see KNOWN-LIMITS.md); one connection cannot write two branches in one transaction.

Quick start

# Once per checkout, before the CLI and the test programs below: fetch the pinned SQLite (3.50.0) and compile it with the session API
# (needs gcc, curl, sha256sum and python3; about a minute). scripts/build-ext.sh does not need this step.
./vfs/build.sh sqlite

# Build the CLI (offline, for inspecting stores no app has open)
./scripts/build-step4.sh cli        # produces build/forkdb

# Build the extension for the sqlite3 shell (needs the symbols of a host that exports SQLite)
./scripts/build-step4.sh ext        # produces build/forkdb.so

# Build the portable extension: loads into SQLite 3.24 and later (tested hosts: Python's sqlite3, Node's built-in node:sqlite, better-sqlite3), no session driver
./scripts/build-ext.sh              # produces build/ext/forkdb.so (.dylib on macOS, .dll on Windows)
./scripts/test-ext.sh               # builds it and runs test/ext_py_test.py through Python's sqlite3
./scripts/test-ext-node.sh          # builds it and runs test/ext_node*_test.js through Node 24's built-in node:sqlite
./scripts/test-ext-bsq.sh           # installs better-sqlite3 13.0.3 (npm, into build/) and runs test/ext_bsq*_test.js through it
./scripts/test-oldest-sqlite.sh      # builds the SQLite 3.24.0 shell (the oldest supported) and checks the extension works in it and is refused by 3.23.1

# Build the CLI and the extension above, and smoke-test the CLI (the test suites are the scripts/test-*.sh scripts)
./scripts/build-step4.sh test

The CLI binary is self-contained: it links against its own SQLite. Use it on a store no application has open: the store file is locked while it is open, so the CLI (or a second application) is refused with an error if another process holds it.

CLI

forkdb init <path> [branch]         create a store, default branch "main"
forkdb fork <path> <name> [--from]  branch off another branch
forkdb snapshot <path> <name>       create a named snapshot
forkdb list <path>                  list branches
forkdb info <path> [branch]         show branch metadata and state
forkdb diff <path> <branch>         show changes relative to the base
forkdb promote <path> <branch>      promote a branch into its base (fast-forward or replay)
forkdb undo <path> <branch>         undo the last promote
forkdb discard <path> <branch>      remove a branch
forkdb reset <path> <branch> <to>   reset a branch's content to another
forkdb gc <path>                    garbage-collect unreachable undo points
forkdb compact <path>               compact the log to a clean snapshot
forkdb sql <path> <branch> [sql]    run SQL on a branch (--write for writes)
forkdb shell <path> <branch>        open an interactive SQLite shell

All commands accept --json for machine-readable output.

Extension

.load forkdb

-- Check if the host has the session API
SELECT * FROM forkdb_info;

-- Create a store and branch off (fork takes the store, the branch to fork from, and the new name)
SELECT forkdb_init('/tmp/mine.fk', 'main');
SELECT forkdb_fork('/tmp/mine.fk', 'main', 'feat-x');

-- Get the URI of a branch and open it with a second connection
SELECT forkdb_open_db('/tmp/mine.fk', 'feat-x');  -- file:/forkdb/b1?vfs=forkdb
-- ... sqlite3.connect(uri, uri=True) in Python, sqlite3_open_v2 in C ...
SELECT forkdb_close('/tmp/mine.fk');

The URI names the branch by its store id (b<N>), which is only stable until the next fork, discard or reset on that store: open it right away.

The SQL functions are forkdb_init(path[, root[, options]]) (the one option, 'nosync', skips every fsync for a throwaway store: 6 to 900 times faster per operation depending on the operation and the disk (see What nosync saves), safe against the death of the process, not against a power cut), forkdb_fork(path, from, name), forkdb_snapshot(path, from, name), forkdb_discard(path, name), forkdb_reset(path, name[, to]), forkdb_compact(path), forkdb_vfs_name(path), forkdb_open_db(path[, ref]), forkdb_close(path), and forkdb_diff, forkdb_promote and forkdb_undo where the session API is present. The table forkdb_info reports the session API, the VFS name and the version. They are direct-only: a view or trigger cannot call them. A store that cannot be opened is an SQL error. The extension stays loaded for the life of the process (it registers a VFS).

The other fkx operations (list, info, gc) are in the CLI and the C library, not in SQL.

A worked example: a fresh database for every pytest test. examples/pytest-branch-per-test is a pytest plugin that gives each test its own branch of a seeded database, a 116-test suite and isolation canaries for it, and measurements of what it costs (cheap on tmpfs and for large seeds; for a small seed on a disk a file copy is as good).

How it works

The store is an append-only log (see DURABLE-STORE.md). Recovery truncates a torn tail, replays the committed prefix, and rebuilds an in-memory index. On open, if the log exceeds 16 MiB, the store compacts it to a clean snapshot — the next open loads instantly.

The branch layer (FKX-DESIGN.md) keeps branches in a tree of layers. A fork copies nothing — it creates an empty child layer that reads through to the parent. Discard folds the smaller layer into the survivor, keeping reads fast. Promote replays or fast-forwards a branch's changes into its base, recording an undo point. GC collects unreachable undo points.

The session driver (SESSION-DESIGN.md) uses SQLite's session extension for diff, conflict detection, replay, and undo. Schema changes and tables without a PRIMARY KEY are detected and reported; the policy controls whether they block the promote.

Durability: what is proven, and against what

A commit that returns is meant to survive a power cut, and recovery is meant to yield exactly the state after the last acknowledged operation (or that plus the one operation that was in flight). That is tested against a simulated disk, not against a real power cut. No real disk was power-cycled, for either mode.

  • The simulated disk (test/simdisk.c, driven by test/crash_test.c) is deliberately pessimistic: writes are pending until an fsync, and at a power cut the surviving image is the durable data plus any subset of the pending writes, in any order, each possibly torn. Seeded workloads (commits, forks, discards, compactions) are cut before every I/O event, including the I/O events of recovery itself and of a compaction, and after a failed fsync. Targeted mutants (for example, commits acknowledged without an fsync) are caught. DURABLE-STORE.md has the details and the mutants that were not caught.
  • What the model assumes: 512-byte sector atomicity, that fsync really makes data durable (on macOS, forkdb calls plain fsync and not F_FULLFSYNC, which does not meet that: see What nosync saves), and that data does not rot while the machine runs. A drive that lies about fsync, or a file system that loses a file's size update, is outside it. File systems that cannot lock or do not honour fsync (some network mounts) get no protection.
  • nosync stores (forkdb_init(path, root, 'nosync'), for throwaway stores) survive the death of the process, which is tested with real kills. After a power cut they either refuse to open or open to a state the workload had acknowledged, usually an older one, never one it did not have. That claim rests on the simulator, at the page-store level and under SQLite (images from a power cut before every I/O event: about 45% are refused, and of those that open about 90% are older than the last acknowledged transaction and about half of them are empty; none is a state the workload never had). forkdb_sync_count() reports the durability calls a process's stores have made, and is how the tests check that a nosync store makes none.
  • Windows: the store calls FlushFileBuffers, and compaction needs NTFS on Windows 10 1709 or later. The directory sync after a compaction is best effort. Windows runs in CI as a smoke test, with a flush counter, and nothing was tested against a power cut there.
  • Tested on: see Platforms for what runs where. Not tested on any platform: a power cut.

If you need the durable guarantee, run your own power-cut test on your hardware and file system before relying on it.

What nosync saves

Measured by CI on its runners (scripts/bench-nosync.sh: the median of 5 runs on fresh stores after a warm-up, Node 24; the job summary of What nosync saves has each table). Durability calls per operation are the same on every platform (1.03, 4.13, 5.16); the times are not, and are the time of one disk of one runner on one day, not a property of the platform.

operation (durable ms/op, then nosync ms/op, then the ratio) Linux (ext4) macOS (virtual machine) Windows (NTFS)
commit (insert one row): 1.03 syncs durable, 0 with nosync 0.133, 0.0152, 9x 0.827, 0.0115, 72x 5.577, 0.0237, 235x
fork and discard: 4.13 syncs durable, 0 with nosync 0.448, 0.0190, 24x 0.304, 0.0124, 25x 21.834, 0.0243, 900x
fork, write, commit, close, discard (a test fixture): 5.16 syncs, 0 0.680, 0.1104, 6x 0.453, 0.0542, 8x 27.842, 0.0962, 290x
  • The saving is a property of the disk. On the Linux runner an fsync costs about 0.1 ms and the saving is 6 to 24 times; on the same operations NTFS on the Windows runner costs about 5 ms and the saving is 235 to 900 times. A local NVMe, a network disk and tmpfs each give another answer (tmpfs: no saving, an fsync costs nothing there). Run scripts/bench-nosync.sh with FK_BENCH_DIR on the disk you care about.
  • A durable fork and discard costs 4.13 syncs against 1.03 for a commit. Why has not been investigated.
  • macOS: the durable path calls fsync, and forkdb never calls F_FULLFSYNC. On macOS fsync does not ask the drive to empty its own write cache, which F_FULLFSYNC does. So a durable store on macOS is weaker against a power cut than the simulator's model (an fsync that really makes data durable) assumes, and the durable macOS figures above are probably the cheaper call for that reason. What F_FULLFSYNC would cost has not been measured, and the code has not been changed.

Platforms: what is built and tested where

Every row is something CI (ci.yml) or the Release build workflow (release.yml, which makes the wheel row) runs; a blank cell is something that is not tested, not something known to work.

Linux macOS Windows
Store and VFS tests, power-loss simulator, fuzzer, sanitizers all store tests store tests
Loadable extension builds (scripts/build-ext.sh) .so, gcc .dylib, Apple clang .dll, mingw-w64 gcc (not MSVC)
Extension from Node 24's built-in node:sqlite (23 tests, plus the nosync file) yes yes yes
Extension from better-sqlite3 13.0.3 (22 tests, plus the nosync file) yes yes yes
Extension from Python's sqlite3: the full suite (64 tests) yes
The Python wheel installed in a clean virtual environment, with test/smoke_py.py yes yes (Homebrew's Python: the one actions/setup-python installs cannot load extensions) yes
Extension in SQLite 3.24.0, the oldest supported (shell built from the amalgamation) yes

What runs only on Linux, and why: the full Python suite (it uses LD_PRELOAD and POSIX signals; only the smoke test of the installed wheel runs on macOS and Windows), and the one test per Node host that checks forkdb_sync_count() against the fsync system calls (an LD_PRELOAD interposer). The nosync behaviour tests run on all three, counting with forkdb_sync_count(). Power loss under nosync is simulated, never real, on every platform.

macOS has been tested only in CI, on GitHub's macOS runner (an arm64 virtual machine, macOS 11 as the minimum the build asserts): the store tests, the extension from Node, the wheel and the CLI. Nobody has run forkdb on a real Mac, and the macOS wheel and CLI have never been run anywhere else. Windows is tested in CI and was also checked once by hand on Windows 11 (Python 3.13, Node 24), with scripts/verify-windows.ps1: the wheel and the npm package installed and run (12 of 12 checks), on a build of the same sources made by CI. SQLite versions the extension has run in: 3.24.0 (shell), 3.45.1 (Python), 3.50.0 (C tests), 3.53.x (both Node hosts). 32-bit builds, MSVC, and any macOS or Windows version other than the CI runners' are untested.

Known limitations

See KNOWN-LIMITS.md. The short version:

  • Tables without a PRIMARY KEY are not compared (diff reports them, promote refuses them with FKX_TABLE_NO_PK)
  • DDL: new tables, indexes and triggers are replayed by promote; alterations to existing objects and dropped objects are refused with the reason named
  • Virtual tables and FTS shadow tables are not compared
  • Large changesets are held in memory (a streaming interface exists but is not exposed to callers yet)
  • One writer per branch (writers on different branches can overlap; one connection cannot write two branches in one transaction)
  • Durability is tested against a simulated disk, not a real power cut (see Durability above)
  • better-sqlite3 needs the environment variable SQLITE_USE_URI=1 before it is required; without it opening a branch fails (see KNOWN-LIMITS.md)

Documentation

License

Licensed under either of Apache License, Version 2.0 or MIT license at your option.

About

A branchable, snapshot-based SQLite page store: a crash-consistent log, a loadable extension that gives SQLite cheap branches, and a CLI.

Topics

Resources

Contributing

Security policy

Stars

0 stars

Watchers

0 watching

Forks

Releases

Used by

Contributors

Languages