pagetree

Working name — rename freely.

A pure Common Lisp, dependency-free, embedded persistent key-value store: a copy-on-write B+tree over a paged block device, with an in-Lisp buffer cache and crash-atomic commits. No FFI, no sb-posix, no mmap — the only platform contact surface is a tiny block-device protocol you implement (file-backed on SBCL/Linux today; a disk driver on modus tomorrow).

Built for cl-consensus's UTXO store and for modus on Raspberry-Pi-class hardware (4–8 GB RAM, SSD), where the RAM-bounded buffer cache and compact ordered storage matter — and where C libraries (LevelDB/LMDB/RocksDB bindings) are simply unavailable.

Status & disclaimer

A from-scratch copy-on-write B+tree store — not audited or formally verified for durability. It is research / educational software; if you store data you care about, keep backups and test crash-recovery for your workload. No warranty (see LICENSE).

The core is implemented and exercised by a differential-oracle test suite (random op sequences vs an in-RAM reference, fuzzed crash-recovery, ordered-scan and bulk-load equivalence). See Build & test.

(asdf:load-system "pagetree")

(let ((db (pagetree:open-store "/path/chain.pt" :cache-bytes (* 512 1024 1024))))
  (pagetree:with-write-txn (txn db)
    (pagetree:tput txn key coin))        ; byte vectors
  (pagetree:with-read-txn (txn db)
    (pagetree:tget txn key))             ; → val | nil
  (pagetree:close-store db))

Why not LevelDB/LMDB/RocksDB?

They're C libraries reached through CFFI — they need a Linux ABI (dlopen/libc). modus is a Lisp OS, not a Linux ABI, so there's nothing to bind to. And the current mmap-based store is itself SBCL-on-Linux-only. So: pure CL, our own.

Design

Three layers; only the bottom is platform-specific:

• Layer 0 — block device: ~5 ops (read-page/write-page/sync/grow/ page-count) over fixed-size pages. File / in-RAM / modus backends.
• Layer 1 — pager + LRU buffer cache: RAM-bounded (the hardware knob), dirty tracking, free-page allocator.
• Layer 2 — copy-on-write B+tree + KV API: double-buffered meta pages give crash-atomic commit with no WAL — modified pages go to free space, commit is one atomic meta swap.

Correctness is proven the way secp256k1-fast is: a differential oracle — random op sequences checked against an in-RAM reference model, fault-injection crash tests, and (for cl-consensus) a byte-identical UTXO set-digest vs the existing store.

See PLAN.md for the full design.

Build & test

Pure ANSI Common Lisp with no external dependencies (:depends-on ()). Developed on SBCL; the only platform-specific code is the file block-device backend, which uses standard CL streams.

Load via ASDF — make the repo visible to ASDF, then load the system:

;; Either push this directory onto the central registry…
(push #p"/path/to/pagetree/" asdf:*central-registry*)
;; …or symlink it into your local-projects, e.g.:
;;   ln -s /path/to/pagetree ~/quicklisp/local-projects/pagetree

(asdf:load-system "pagetree")

Run the test suite. The one-command runner loads the system and runs the differential oracle, exiting non-zero on any failure:

./run-tests.sh

It uses sbcl on PATH by default; override with LISP=<impl> ./run-tests.sh.

Equivalently, from a REPL:

(asdf:load-system "pagetree/test")
(pagetree/test:run-tests)   ; => T iff every check passes

(asdf:test-system "pagetree") loads the test system via test-op; use run-tests.sh (or call run-tests directly) when you need a pass/fail exit status, since test-op does not itself fail the build on a check failure.

License

MIT — see LICENSE.